摘要
在组合优化过程中,往往需要获得从起点到终点之间的最短路,而其所考虑的目标可能是一个与时间相关的变量.同时,对于网络中的节点往往有宵禁的限制(curfews).给出时变条件下有软、硬宵禁限制的最短路模型,设计了求解时变条件下有宵禁限制最短路的算法,并对算法的复杂性进行了分析.最后给出了一个应用算例.
Shortest path problem is a basic problem in the combinatorial optimization. The objective in the network is time-varying. Moreover, there will be curfews in some nodes in the network. The paper develops the models for time-varying shortest path problem with soft and hard curfews and gives the algorithm for them. Then, the complexity of the algorithm is discussed. At last, a case is studied.
出处
《系统工程学报》
CSCD
北大核心
2007年第4期359-366,共8页
Journal of Systems Engineering
基金
国家自然科学基金资助项目(70471039)
教育部新世纪优秀人才支持计划项目(NCET-04-0886)
关键词
最短路
时变
宵禁
标号法
shortest path
time-varying
curfews
labeling approach
