原文传递
基于随机场景数据的运输网络流问题模型与算法
| 论文题名： | 基于随机场景数据的运输网络流问题模型与算法 |
| 关键词： | 运输网络流;拉格朗日松弛算法;遗传算法;随机场景数据 |
| 摘要： | 本文以运输网络为研究背景，在战略层面上综合考虑运输网络流问题。具体的，考虑到运输网络中的不确定性因素对路段通行能力和站点中转能力的影响，运用基于场景数据的离散随机表示方法及不同场景下的唯一解约束，建立基于随机场景数据的整数规划模型。同时利用不确定规划方法，探讨基于随机场景数据的随机机会约束模型及模糊机会约束模型。为了得到原问题的近似最优解，设计拉格朗日松弛算法和遗传算法进行求解，最后通过数值算例验证所提算法的有效性和计算效率。主要内容包括： (1)不确定环境下基于随机场景数据的运输网络流问题模型 本文提出基于场景数据表示能力参数的随机性及用多等式表示不同场景下唯一解约束的方法，系统分析并建立了原问题的整数规划模型。然后根据不确定规划，考虑能力参数的随机机会函数和模糊机会函数，分别建立了随机机会约束模型和模糊机会约束模型。最后讨论了特殊情形下，能力参数的随机机会约束和模糊机会约束的确定等价类。 (2)拉格朗日松弛算法 鉴于原模型中涉及复杂的能力约束和多等式唯一解约束，本文设计了拉格朗日松弛算法求解原问题的下界。首先通过引入拉格朗日乘子将复杂约束松弛到目标函数中，然后将其依据场景数据d和商品k分解为K×D个子问题，得到的每个子问题等价于单个OD对的最短路问题，用标号修正或标号设定算法即可求解。为了得到该松弛对偶问题的最优解，同时设计了次梯度算法，在迭代过程中更新拉格朗日乘子，逐步提高解的质量。最终得到的松弛对偶问题最优解即为原问题的一个紧下界LB*。 (3)遗传算法 为了求解原问题的近似最优解，本文进一步设计遗传算法，该算法首先利用分枝定界搜索策略，寻找运输网络中每个OD对满足一定条件的潜在路径，然后在此基础上，设计了包括选择、交叉、变异等操作的遗传算法求解原问题的近似最优解，该近似最优解与拉格朗日松弛所求下界相结合，考察原问题最优解的质量。 (4)算例研究 为了验证拉格朗日松弛算法与遗传算法相结合求解原问题最优解的有效性和计算效率，本文设计了运输网络流问题算例，并进行了算例结果分析。 |
| 作者： | 文娟 |
| 专业： | 交通运输工程 |
| 导师： | 杨立兴 |
| 授予学位： | 硕士 |
| 授予学位单位： | 北京交通大学 |
| 学位年度： | 2012 |
| 正文语种： | 中文 |
检索历史
应用推荐
