区间阻抗下的鲁棒最短路算法  

Robust Shortest Path Algorithm under Interval Impedence

作　　者：周和平[1] 冯轩 彭巍[1] ZHOU He-ping,FENG Xuan,PENG Wei(School of Traffic and Transportation Engineering, Changsha University of Science and Technology,Changsha 410004, Chin)

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

出　　处：《系统工程》2017年第12期121-125,共5页Systems Engineering

基　　金：国家自然科学基金资助项目(51178061);交通运输部应用基础研究项目(2014319825190)

摘　　要：交通需求一旦发生变化,交通路网中的路段阻抗也会呈现显著的不确定性,而现行的最短路求解方法缺乏鲁棒性。为了增强最短路方法的鲁棒性,引入区间型数据的路网阻抗,同时结合鲁棒离散优化与情景分析法,给出鲁棒成本的定义。建立了区间阻抗下的鲁棒最短路模型,接下来基于模型设计了分支定界算法,并就算法的判定条件给出3个定理,最后对一个大型路网进行了仿真测试。结果表明:相对于现行的最短路方法,该方法求解得到的最短路径具有更强的鲁棒性,且求解结果准确高效。Once the traffic demand changed,the impedance of the road section in the traffic network shows significant uncertainty,but the current shortest path method is lack of robustness.In order to enhance the robustness of the shortest path method,the network impedance with interval data is introduced,and the definition of robust cost is given by combining the robust discrete optimization and the scenario analysis method.The robust shortest path model under interval impedence is established,then a branch-and-bound algorithm is designed based on the model,and three theorems are given on the deternination conditions of the algorithm.Finally,a large-scale road network is simulated and tested.The results show that compared with the current shortest path method,the shortest path obtained by this method is more robust,and the result is accurate and efficient.

关 键 词：鲁棒离散优化 分支定界算法 区间数据 最短路问题 

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