基于Benders分解的鲁棒最短路算法 |
| |
引用本文: | 冯轩,周和平,彭巍.基于Benders分解的鲁棒最短路算法[J].长沙理工大学学报(自然科学版),2018(2). |
| |
作者姓名: | 冯轩 周和平 彭巍 |
| |
作者单位: | 长沙理工大学交通运输工程学院 |
| |
摘 要: | 为了研究路段行程时间不确定条件下的最短路问题,采用区间数据表示路段行程时间,介绍了鲁棒偏差和鲁棒成本的概念,并据此给出鲁棒最短路的定义,运用鲁棒优化中的min-max准则构建了鲁棒最短路问题的混合整数规划模型。通过固定路径决策变量将鲁棒最短路问题分解为子问题和主问题,同时结合对偶理论给出子问题的对偶模型。在此基础上设计出鲁棒最短路问题的Benders分解算法,采用AMPL编程实现算法并调用CPLEX进行求解。并在一个仿真网络中对本研究方法进行了验证分析。研究结果表明,相较于传统最短路Dijkstra算法,本研究方法求得的鲁棒最短路在不确定网络中具有更强的可靠性,设计的算法迭代效率较高,能迅速缩小迭代范围并找到最优解。
|
本文献已被 CNKI 等数据库收录! |
|