摘要
在组合优化过程中,往往需要获得从起点到终点之间的最短路.由于道路、天气、交通条件等因素的影响,使得网络具有很强的时变特性.同时,对于网络中的节点往往有宵禁的限制.对时变条件下有宵禁限制并有到达时间限制的最短路进行了研究,建立了软、硬宵禁限制下的数学模型,给出并证明了时变条件下获得有宵禁限制最短路的最优条件,并设计了求解的多项式算法,通过此算法可以获得时变条件下有宵禁限制的最短路.同时,算法和模型还考虑了不同的起点出发时间,使路径决策者可以根据自身的情况,选择合适的出发时间和路径.最后给出了一个应用算例,分析了宵禁对于获得的最短路的影响.
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.
出处
《管理科学学报》
CSSCI
北大核心
2009年第1期9-17,共9页
Journal of Management Sciences in China
基金
国家自然科学基金资助项目(70471039)
教育部新世纪优秀人才支持计划资助项目(NCET-04-0886)
国家教育部"十一五"211工程资助项目
关键词
最短路
时变
宵禁
算法
shortest path
time-varying
curfews
algorithm
