含结点等待费用的离散时变最短路径.pdf

　2007 年 1 月 系统工程理论与实践 第 1 期 　 ( ) 文章编号 2007 含结点等待费用的离散时变最短路径 杨　会 ,刘震宇 (厦门大学 管理学院 ,厦门 361005) 摘要 : 　研究了结点等待费用 、弧费用和弧通过时间均为离散时变函数的最短路径问题. 基于动态规划 原理 ,给出了一种标号更新算法 ,可在 O ( n3 M3 ) 时间复杂度内求出所有结点到指定终点的最小费用路 径 ,其中 n 为网络结点数 、M 为时间间隔数. 关键词 : 　离散时变最短路径 ;最小费用路径 ;标号更新算法 中图分类号 : 　O157. 5 　　　　　　　　文献标志码 : 　A 　　　 Discrete Time Dependent Shortest Paths Considering Nodewaiting Cost YANG Xuanhui , LIU Zhenyu ( ) School of Management , Xiamen University , Xiamen 361005 , China Abstract : 　A special version of the Time Dependent Shortest Paths ( TDSP) problem is studied in this paper. The objective is to find the minimum cost path considering nodewaiting cost in a network , in which , waiting is allowed at every node and the arctraversing cost , nodewaiting cost and arctraversing time are all discrete functions of time. An label correcting algorithm is introduced to find all the minimum cost paths from every node to the destination node simultaneously with time complexity of O ( n3 M3 ) , where n is the number of the nodes in the network and M is the time interval count. Key words : 　discrete time dependent shortest paths ;minimum cost path ;label correcting algorithm 1 　引言 ( ) 最短路径问题的一种形式 ———时变最短路径问题 Time Dependent Shortest Paths , TDSP 求费用随时间