基于Benders分解的鲁棒最短路算法  

Robust shortest path algorithm based on Benders decomposition

作　　者：冯轩 周和平[1] 彭巍[1] FENG Xuan;PENG Wei(School o f Traffic and Transportation Engineering,Changsha University of Science and Technology,Changsha 410114,China)

机构地区：[1]长沙理工大学交通运输工程学院,湖南长沙410114

出　　处：《长沙理工大学学报（自然科学版）》2018年第2期16-20,42,共6页Journal of Changsha University of Science and Technology:Natural Science

基　　金：国家自然科学基金资助项目(51178061)

摘　　要：为了研究路段行程时间不确定条件下的最短路问题,采用区间数据表示路段行程时间,介绍了鲁棒偏差和鲁棒成本的概念,并据此给出鲁棒最短路的定义,运用鲁棒优化中的min-max准则构建了鲁棒最短路问题的混合整数规划模型。通过固定路径决策变量将鲁棒最短路问题分解为子问题和主问题,同时结合对偶理论给出子问题的对偶模型。在此基础上设计出鲁棒最短路问题的Benders分解算法,采用AMPL编程实现算法并调用CPLEX进行求解。并在一个仿真网络中对本研究方法进行了验证分析。研究结果表明,相较于传统最短路Dijkstra算法,本研究方法求得的鲁棒最短路在不确定网络中具有更强的可靠性,设计的算法迭代效率较高,能迅速缩小迭代范围并找到最优解。In order to study the shortest path problem under the condition of uncertain travel time,this paper uses the interval data to represent the travel time of the road,introduces the concept of robust deviation and robust cost,and gives the definition of robust shortest path,using robust min-max criterion in optimization constructs a mixed integer programming model of robust shortest path problem.The robust shortest-path problem is decomposed into sub-problems and main problems by fixing complex variables,and the duality model of sub-problems is given by combining duality theory.Based on this,we design a Benders decomposition algorithm for the robust shortest-path problem,implement the algorithm using AMPL programming and call CPLEX to solve it.The verification and analysis of this method in a simulation network show that the robust shortest path obtained by our method is more reliable than the traditional Dijkstra shortest path method and the proposed algorithm has higher iterative efficiency,quickly narrows the scope of iteration and finds the optimal solution.

关 键 词：路径选择 区间数据 鲁棒优化 最短路径 鲁棒成本 Benders分解算法 

分 类 号：U491.1[交通运输工程—交通运输规划与管理]