一种求解时变网络下多式联运最短路的算法

中国管理科学 ›› 2006, Vol. ›› Issue (4): 56-63.

一种求解时变网络下多式联运最短路的算法

魏航¹, 李军², 刘凝子²

1. 上海财经大学国际工商管理学院, 上海, 200433;
2. 西南交通大学经济管理学院, 成都, 610031

收稿日期:2005-08-22 修回日期:2006-07-05 出版日期:2006-08-28 发布日期:2012-03-07
基金资助:
国家自然科学基金资助项目(70471039);教育部新世纪优秀人才支持计划项目(NCET-04-0886)

An Algorithm for Shortest Path with Multi-Modal in Time-Varying Network

WEI Hang¹, LI Jun², LIU Ning-zi²

1. School of International Business Administration, Shanghai University of Finance and Economics, Shanghai 200433, China;
2. School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China

Received:2005-08-22 Revised:2006-07-05 Online:2006-08-28 Published:2012-03-07

摘要/Abstract

摘要： 在运输过程中,往往不止有一种运输方式,可能同时有多种运输方式交叉,即可能多式联运的方式存在,不同的运输方式之间需要通过转运才可实现.同时,在运输过程中,成本、运输时间、风险等因素会随着时间的不同而变化.首先,将运输网络进行变形,然后给出了在时变网络条件下多式联运的最短路模型,设计了求解时变条件下多式联运的最短路的算法,利用此算法可以获得从起点到终点之间的最短路,并对算法的计算复杂性进行了分析.最后给出一个应用算例.

关键词: 最短路, 时变网络, 多式联运, 转运, 成本

Abstract: In the transportation,there are many modes,such as truck,train,waterway,airplane and so on.The different mode has the different cost,but the different modes want to transship.Thus,there exists the transshipment in transportation.The paper wants to find the shortest path with multiple modes in the time-varying network.The problem also has constraints to the time and to the destination.In order to solving the problem,we transformed the transportation network and analyzed the transportation cost and transshipment cost.Then,we developed the label algorithm to the problem and gave the computational complexity of the algorithm.At last,a case was studied.

Key words: shortest path, time-varying network, multiple modes, transshipment, cost

中图分类号:

U116.2
O224

魏航, 李军, 刘凝子. 一种求解时变网络下多式联运最短路的算法[J]. 中国管理科学, 2006, (4): 56-63.

WEI Hang, LI Jun, LIU Ning-zi. An Algorithm for Shortest Path with Multi-Modal in Time-Varying Network[J]. Chinese Journal of Management Science, 2006, (4): 56-63.

参考文献

[1] E.W.Dijkstra.A note on two problems inconnection with graphs[J].Numer.Math.,1959,1:269-271.
[2] 李引珍,郭耀煌.交通运输网络最短路径关键边问题研究[J].中国管理科学,2004,12(4):69-73.
[3] 李帮义,盛昭翰.目标函数为∑和max的双目标最短路问题:算法和复杂性[J].中国管理科学,2003,11(5):37-41.
[4] National Commission on IntermodalTransportation,Toward a National IntermodalTransportation System[R].Final Report to Congress,US DOT,Washington,DC,1994.
[5] Rawlings,One System,Many Partners:Reflections of the Chicago Area TransportationStudy's Intermodal Advisory Task Force[R].1997,97-17.
[6] 张得志,凌春雨.多种运输方式的组合优化模型及求解算法[J].长沙铁道学院学报,2002,20(4):71-75.
[7] Angelica Lozano,Giovanni Storchi.Shortestviable path algorithm in multimodal networks[J].Transportation Research,Part A,2001,35:225-241.
[8] Modesti,Sciomachen.A utility measure forfinding multiobjective shortest paths in urban multimodal transportation networks[J].European Journal of Operational Research,1998,111:495-508.
[9] Angelica Lozano,Giovanni Storchi,Shortestviable hyperpath in multimodal networks[J].Transportation Research,Part B,2002,36:853-874.
[10] Elise D.M.,Hani S.M..Least possible timepaths in stochastic,time-varying networks[J].Computers and Operations Research,1998,25(12):1107-1125.
[11] Elise D.M.,Hani S.M..Path comparisons for apriori and time-adaptive decisions in stochastic,time-varying networks[J].European Journal of Operational Research,2003,146:67-82.
[12] Athanasiso Z.,Dimitrios K.,Hani S.M..Designand implementation of parallel time-dependentleast time path algorithm for intelligent transportation systems applications[J].Transportation Research,Part C,1997,5(2):95-107.
[13] Daniele P..A directed hypergraph model forrandom time dependent shortest path[J].European Journal of Operational Research,2000,123:315-342.
[14] Elise D.M.Adaptive Least Expected TimePaths in Stochastic,Time-Varying Transportation and Data Networks[J].Networks,2001,37(1):35-52.
[15] Sathaporn Opasanon,Elise D.M.Multicriteriaadaptive paths in stochastic,time-varyingnetworks[J].European Journal of Operational Research,2006,173:72 -91.