一种求解时变条件下有宵禁限制最短路的算法  

An approach for time-varying shortest path problem with curfews

作　　者：魏航[1,2] 

机构地区：[1]上海财经大学国际工商管理学院,上海200433 [2]上海财经大学500强企业研究中心,上海200433

出　　处：《管理科学学报》2009年第1期9-17,共9页Journal of Management Sciences in China

基　　金：国家自然科学基金资助项目(70471039);教育部新世纪优秀人才支持计划资助项目(NCET-04-0886);国家教育部"十一五"211工程资助项目

摘　　要：在组合优化过程中,往往需要获得从起点到终点之间的最短路.由于道路、天气、交通条件等因素的影响,使得网络具有很强的时变特性.同时,对于网络中的节点往往有宵禁的限制.对时变条件下有宵禁限制并有到达时间限制的最短路进行了研究,建立了软、硬宵禁限制下的数学模型,给出并证明了时变条件下获得有宵禁限制最短路的最优条件,并设计了求解的多项式算法,通过此算法可以获得时变条件下有宵禁限制的最短路.同时,算法和模型还考虑了不同的起点出发时间,使路径决策者可以根据自身的情况,选择合适的出发时间和路径.最后给出了一个应用算例,分析了宵禁对于获得的最短路的影响.Shortest path problem is a basic problem in the combinatorial optimization. In dynamic transportation networks, the arc travel times and costs are time-varying depending on road condition, weather and traffic condition. Moreover, there will be curfews in some nodes in the network because of resting, congestion and so on. The paper developed models for time-varying shortest path problems with both soft and hard curfews. Then, the optimal condition for getting the shortest path with curfews was proved. Based on this condition, the algorithm was proposed. In order to decrease the objective value, the algorithm also considered the multi-departure-time and compared with the value in different departure times. The paper also discussed the complexity of the algorithm. At the end, a case was studied.

关 键 词：最短路 时变 宵禁 算法 

分 类 号：U116.2[交通运输工程]