时变网络中零等待时间最短路问题的一个对偶算法(英文)  

A dual algorithm for the time-varying shortest path problem with no waiting time constraints

作　　者：朱建明[1] 沙丹[2] 

机构地区：[1]上海师范大学数理信息学院,上海200234 [2]上海对外贸易学院国际经贸学院,上海201620

出　　处：《上海师范大学学报（自然科学版）》2008年第1期14-21,共8页Journal of Shanghai Normal University(Natural Sciences)

基　　金：Partially supported by Shanghai Municipal Education Commission with project number 5Z1206.

摘　　要：时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点s,图G中的每条弧(i,j)∈A都附有两个参数:弧的传送时间b(i,j,u)和弧的传送费用c(i,j,u),它们都是在弧的顶点i上的出发时间u的函数.找出从源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.假设除源点外,在其它任何顶点都不能等待,b(i,j,u)是满足u+b(i,j,u)≥0((i,j)∈A,u=0,1,...,T)的任意整数,c(i,j,u)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.The time - varying shortest path problem is an extension of the shortest path problem. Let G = （V,A） be a directed graph with a unique source node s ∈ V. Each arc （i,j）∈ A has two numbers attached to it ： A transit time b（i,j,t） and a transit cost c（i,j,t） which are the functions of the departure time t at the beginning node of the arc. The problem is to find the shortest path, i. e. , the path with the least possible cost, from s to all other nodes, subject to the constraint that the total traverse time is no more than a given number T. We assume that waiting at nodes are strictly prohibited except the source node, all transit costs c（ i,j, u） are nonnegative integers and all the transit times b（i,j,u） are the integers which satisfy0 ≤ t = u＋b（i,j,u）（（i,j）∈A,u=0,1,...,T）. First,we formulate the problem in a dual linear programming form. Next, we propose an optimality condition and develop a dual algorithm to solve the problem. Finally, a numerical example is given to illustrate the algorithm.

关 键 词：最短路 对偶算法 时变网络 最优化 

分 类 号：O221.7[理学—运筹学与控制论]