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

时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点t,图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)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.

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

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 nodes ∈ V. Each arc (i,j) ∈ A has two numbers attached to it: A transit time b (i,j,t) and a transit cost e (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, froms 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,2,…,T ). First,we formulate the problem in a dual linear programming form. Next, we propose an optimality condition and develop a dual algo-rithm to solve the problem. Finally, a numerical example is given to illustrate the algorithm.