时变网络中任意等待时间最短路问题的一个对偶算法
给定一个时变网络G(V,A,b,c),V表示网络的顶点集,A表示网络的弧集.b(i,j,t)和c(i,j,t)表示弧的传送时间和传送费用,并且它们都是弧的顶点i的出发时间t的函数.时变最短路问题是找出从唯一源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.由于弧的传送时间b(i,j,t)和传送费用c(i,j,t)是弧的顶点i的出发时间￡的函数,所以在顶点i上的等待时间也足时变最短路问题的决策变量.本文假设:流在任何顶点上都能任意地等待b(i,j,u)是满足u+b(i,j,u)≥0((A)(i,j)∈A,u=0,1,...,T)的任意整数;c(i,j,u)是任意非负整数.首先,我们给出了该问题的对偶规划.然后,提出了一个最优性条件和一个对偶算法.最后,用一个数值例子来阐述算法.
时变网络 等待时间 最短路径 对偶算法
朱建明 沙丹
上海对外贸易学院,商务信息学院,上海,201620
国内会议
芜湖
中文
284-292
2010-05-21（万方平台首次上网日期，不代表论文的发表时间）