下载文档原格式
最短路问题的求解方法最短路问题是图论中的一个经典问题，它在很多实际应用中都有着重要的作用。
在现实生活中，我们经常需要求解最短路径，比如在地图导航、网络通信、交通运输等领域。
因此，研究最短路问题的求解方法具有重要的理论意义和实际应用价值。
在图论中，最短路问题的求解方法有很多种，其中比较经典的有Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等。
这些算法各有特点，适用于不同的场景和要求。
下面我们就逐一介绍这些算法的原理和求解方法。
Dijkstra算法是一种用于求解单源最短路径的算法，它采用贪心策略，每次找到当前距离最短的节点进行松弛操作，直到所有节点都被遍历。
Dijkstra算法的时间复杂度为O(V^2)，其中V为节点的个数。
这种算法适用于边权值为正的图，可以求解从单个源点到其他所有点的最短路径。
Bellman-Ford算法是一种用于求解单源最短路径的算法，它可以处理边权值为负的图，并且可以检测负权回路。
Bellman-Ford算法的时间复杂度为O(VE)，其中V为节点的个数，E为边的个数。
这种算法适用于一般情况下的最短路径求解，但是由于其时间复杂度较高，不适用于大规模图的求解。
Floyd-Warshall算法是一种用于求解所有点对最短路径的算法，它可以处理边权值为正或负的图，但是不能检测负权回路。
Floyd-Warshall算法的时间复杂度为O(V^3)，其中V为节点的个数。
这种算法适用于求解图中所有点对之间的最短路径，可以同时求解多个源点到多个目标点的最短路径。
除了上述几种经典的最短路求解算法外，还有一些其他的方法，比如A算法、SPFA算法等。
这些算法在不同的场景和要求下有着各自的优势和局限性，需要根据具体情况进行选择和应用。
在实际应用中，最短路问题的求解方法需要根据具体的场景和要求进行选择，需要综合考虑图的规模、边权值的情况、时间效率等因素。
同时，对于大规模图的求解，还需要考虑算法的优化和并行化问题，以提高求解效率。
第16卷第3期 湖南工程学院学报 V o1.16.N o.3 2006年9月 Journa l of Hunan Institute of Eng i n ee ring Sep.t2006有宵禁限制的成本最短路问题何彩香1,胡竞湘2,李汝烯3*(1、云南大理学院数学系,云南大理671000;2、湖南工程学院机械工程系,湖南湘潭411101;3、云南大理学院物理系,云南大理671000) 摘 要:在组合优化过程中,往往需要获得从起点到终点之间的最短路,而其所考虑的目标可能是一个与时间相关的变量,同时,对于网络中的节点往往有宵禁的限制(c u rfe w s).给出了时变条件下有软、硬宵禁限制的成本最短路模型,设计了求解时变条件下有宵禁限制的成本最短路的算法,并给出了一个应用实例.关键词:成本最短路;时变;宵禁;标号算法中图分类号:O157.2 文献标识码:A 文章编号:1671-119X(2006)03-0073-040 引 言最短路问题(SP)是网络优化中的一个经典问题,该问题已经很好的解决,如五十年代的D ij k stra 算法,六十年代的F l o yd算法,这些方法均是在静态条件下的研究.由于在实际的一些最短路问题中,如在拥挤的运输网络中,车辆运行时间是时变量,即:其运行所需的时间可能与运输所处的时段有关.所以,在求解最短路的过程中,还需要考虑时间因素对于目标值的影响.对于时变条件下的最短路问题,目前的研究还不多,主要集中在最短时间路问题的研究上,E lise D.M.,H ani S.M.研究了随机时变网络中的最短时间路,提出了两种不同的算法,并对它们进行了比较.R.W.H all给出了随机动态网络中最小期望时间路的一个解法.Daniele P.研究了离散随机动态超图网络下的最短时间路问题,给出了求解的方法.G.G allo,G.longo,S.N guyen和S.Pa llo ttion.对超图中最短路的问题进行了研究,并分析了它在运输系统上的应用.在现实情况中,还可能出现的是带有“宵禁”(cu rfe w s)限制的车辆运输问题,比如说车辆到达(或通过)某些节点是要受时间限制的,在某些时间段里车辆不能到达或是要受到“惩罚”.对于这种有宵禁限制的最短路问题,Cox和Tur qu ist在静态网络条件下进行了研究.本文给出了时变网络条件下有宵禁限制的成本最短路的数学模型,设计了成本最短路的算法,并给出了一个应用实例.1 问题描述最短路问题考虑的是有向网络G=(N,E,W),其中N为节点集,E为节点间的有向边的集合,|N| =n,|E|=m,W为权的集合.在此,设T为车辆从起点O允许出发的离散时间的集合,T={t1,t2,Λ, t k},|T|=k,这里t1<t2<Λ<t k为非负整数,记T0 =tk;令Zi表示在节点处i∈N的宵禁时间区域的并集,Z i={[αi1,βi2),Λ[αipi,βipi)},且t1≤αi1<αi2<βi2<Λ<αipi<βipi≤t k],其中[αiq,βiq)为节点i的某个宵禁时间区域,它所含T中的元素依次为αiq=t r, t r+1,Λ,t r+b;这里t r+b+1=βiq,q=1,2,Λ,p.我们的问题是:求在时间T0之前到达终点D的,满足有宵禁限制的从起点O到终点D之间的成本最短路.2 数学模型对于时变条件下有宵禁限制的最短路,车辆到达某个节点可能会超过此节点某个宵禁时间区域的起始时间,此时就给以一定的迟到惩罚及等待惩罚,且此时其出发时间为此宵禁时间区域的终止时间.而对于有硬宵禁限制的最短路问题,如果车辆到达*收稿日期:2006-04-15作者简介:何彩香(1965-),女,副教授,研究方向:组合优化研究. DOI牶牨牥牣牨牭牴牳牱牤j牣cn ki牣hgbjbz牣牪牥牥牰牣牥牫牣牥牪牥某个节点的时间在此节点某个宵禁时间区域内即为不可行解.2.1 构建一个时间扩张网络G T,将动态问题转化为静态问题来讨论在有向网络G =(N ,E ,W )中,设t ′(i ,j ,t h )为车辆在时刻t h 出发从节点i 到节点j 运行所需的时间;又设c ′(i ,j ,t h )为车辆在节点i 到节点j 之间,在时刻t h 出发时的运行成本,c ′(i ,j ,t h )为一个正实数,(i ,j )∈E.我们构建时间扩张网络G T=(V ,A )如下:V ={i h :i ∈N ,1≤h ≤k },这里i h 对应时间t h ;A ={(i h ,j t ):(i ,j )∈E ,t h +t ′(i ,j ,t h )=t l ;t h ,t l ∈T ;1≤h <l ≤k ,且t h Z i }∪{(i h ,i h +1):t h ∈Z i ,i ∈N }在网络G T=(V ,A )中,设车辆从节点i h 出发的时刻为t h ,在弧(i h ,j t )上的运行时间为t (i ,j ,t h )=t l -t h ),到达节点j t 的时刻为t l ;t h <t l ,t l ∈T ;又设c (i ,j ,t h )为弧(i h ,j t )上的运行成本.设x i h ,j l 表示弧(i h ,j l )是否位于从起点O 到终点D 的路上:当x i h ,j l =1时,表示弧(i h ,j l )位于从起点O 到终点D 的路上,x i h ,j l =0时表示弧(i h ,j l )不在从起点O 到终点D 的路上.2.2 有软宵禁限制的成本最短路的数学模型设属于节点j 的宵禁时间区域的并集为Z j ={[αj 1,βj 1),[αj 2,βj 2),Λ,[αjr ,βjr )}且t 1≤αj 1<βj 1<αj 2<βj 2<Λ<αjr <βjr ≤t k 令c (i ,j ,t h )=c ′(i ,j ,t h )当i ≠j ,t h Z i 且t l Z jc ′(i ,j ,t h )+α(t l -αj q ),当i ≠j ,t h Z i 但t l ∈[αj q ,βjq )β(t h +1-t h ),当t h ∈Z i 且t h =t r ,t r +1,Λ,t r +b时其中α为超过某个宵禁时间区域的起点时间到达节点j 所给以的单位时间的惩罚值,β为车辆因为超过某个宵禁时间区域的起点时间到达,而需要在节点进行等待到此宵禁时间区域结束的单位时间的等待成本.于是构建在G T=(V ,A )基础上的有软宵禁限制的成本最短路模型可以描述为m in ∑(i h,j t)∈Ac (i ,j ,t h )x i h j t(1)s .t .∑j l:(i h,j l)∈Ax i h ,j l -∑j l :(j l ,i h)∈A x j l ,j h=1,i =0-1,i =D 0,i ≠0,D(2)x i h ,j l ∈{0,1}, (i h ,j l )∈A (3)t h +∑(i h,j l)∈At (i ,j ,t h )x i h ,j l ≤T 0(4)有硬宵禁限制的成本最短路模型可以描述为(1)且满足(2)、(3)、(4);但是其中的c (i ,j ,t h )=c ′(i ,j ,t h ),当i ≠j ,t h Z i ,且t l Z j 时M ,当i ≠j ,t h Z i ,但t l ∈Z j 时M ,当t h ∈Z i 时这里M 为很大的整数(M →∞)3 标号算法00令h =1,h =1,T ={t 1,t 2,Λ,t k },10选取T 中最小值t h ,令S ={O h }则令u O h =020令R 0=FS (O h ) V ,这里,FS (O h )为O h 的所有前向节点的集合, i l ∈R 0,(O h ,i l )∈A ;30搜索所有的i l ∈R 0,令u i l =u O h +c (0,i ,t h ),且S =SY {i l };40若所有i =D ,则转80;50若某个i ≠D ,则令R i =FS (i l ) V ,这里FS (i l )为i l 的所有前向节点的集合, j q ∈R i ,(i l ,j q )∈A ;60搜索所有的j q ∈R i ,令u j q =u j l +c (i ,j ,t l ),且S =SY {j q };70若所有j =D ,则转80;若某个j ≠D ,令t l =t q ,i =j 返回50;80计算t h 时刻从起点O 出发到达终点D 的成本最短路长u k =m in j q∈S{u j q :j =D ,j q ∈S }90若h <k ,则令T =T \{t 1,t 2,Λ,t h }置h =h +1,返回10;100h =k 若,则令u =m i n 1≤h ≤k{u k }.4 实 例下面给出一个实例,运输网络如图1所示.表1图1 运输网络给出了在运输过程中,各个节点之间在不同时间条件下,运输过程中的运输成本.各个节点的宵禁时间区域分别如表2所示,其中Y 表示在此时间区域有宵禁限制,而N 表示无宵禁限制.假设车辆可以在74 湖南工程学院学报 2006年时刻0从起点O 出发,每隔1小时整点出发一次.现希望获得在时间0与24时之间,满足宵禁限制的从起点O 到终点D 的成本最短路.表1 各条有向边在不同时间条件下的运输成本有向边时段[0/4)[4,8)[8,12)[12,16)[16,20)[20,24)(O ,1)[20/4)20/415/325/330/210/1(O ,2)50/840/835/620/835/830/9(1,2)10/45/45/510/55/55/6(1,3)10/310/315/310/410/415/3(2,3)10/610/610/65/55/55/4(2,D )25/325/320/230/230/230/3(3,D )20/520/520/535/635/530/6表2 各节点的宵禁时间区域节点宵禁时间区域[6/8)[12/14)[17/19)[22/24)O Y N Y N 1N Y Y Y 2N Y N Y 3Y N Y N DNY NN构建时间扩张网络(部分)如图2所示:分别选取不同的出发时间,并应用给出的算法,可以获得在不同的出发时间条件下,在时间0与24时之间,有软、硬宵禁限制的从起点O 到终点D 的成本最短路如表3所示.图2 时间扩张网络75第3期 何彩香等:有宵禁限制的成本最短路总是表3 不同的出发时间条件下的成本最短路出发时间软宵禁成本最短路所需成本硬宵禁成本最短路所需成本0O-1-2-D45O-1-2-D45 1O-1-2-D45O-1-2-D45 2O-1-2-D45O-1-3-D50 3O-2-D40O-1-3-D50 4O-1-3-D55O-1-3-D55 5O-1-2-D55O-1-2-D55 6O-1-2-D54…………7O-1-2-D57…………8O-1-2-D50O-1-2-D50 9O-1-2-D59O-2-D65 10O-1-2-D62O-2-D65 11O-1-2-D55O-1-2-D55 12O-2-D50O-2-D50 13O-2-D50O-2-D505 结束语从表3可以看出,不同的出发时间条件下,不管在有软宵禁还是硬宵禁,最短路有所不同,且目标值也会有所不同.这使得决策者可以根据自身的情况,选择合适的出发时间和路径.有宵禁限制的成本最短路问题的讨论,为有害物品运输、通信网络优化等领域提供了一定的借鉴依据.参 考 文 献[1] E W D ij kstra.A note on t wo prob l em s i n connecti on w ithg raphs[J].N u m er.M a t h,1959,1:269-271.[2] E lise D.M.,H ani S.M.L east possi b le ti m e pa t h in st o-chastic,ti me-va ry i ng ne t w orks[J].Co m pu t e rs and Op-e ra tions R esearch,1998,25(12):1107-1125.[3] R.W.H a l.l T he fastest pa t h through a net wo rk w it h ran-do m ti m e-dependent trave l ti m es[J].T ranspo rt a tionScience,1986,20(3):128-188.[4] Danie l e P.A directed hype rgraph m ode l f o r random ti medependen t sho rtest pa t h[J].European Journa l o f O pe ra-ti onal R esea rch,2000,123:315-342.[5] G.G all o,G.l ongo,S.N guyen,S.P all o tti on.D irected hy-pe rgraphs and applica tions[J].D isc re t e A pp lied M athe-m a tics,1993,42:177-201.[6] C ox,Turqu is.t Scheduling truck s h i p m ent o f H azardousM a t e rials in t he present o f curfew s[J].T ranspo rt a tionResea rch Reco rd,1063,1986,21-26.[7] 谢金星,邢文训.网络优化[M].北京,清华大学出版社,2000.119-140.[8] 姚恩瑜,何 勇,陈仕平.数学规划与组合优化[M].杭州:浙江大学出版社,2001.124-130.The M i nm i u m Cost Pat hs Prob le m W it h Curfe wsHE C ai-x iang1,HU Jing-xiang2,LI Ru-x i3(1.D ep.t o fM ath.,Yunnan D a li Un i v.,D a li671000,China;2.Dep.t of E lec.t Eng.,Hunan Institute of Eng i neering,X iang tan411101,China3.D ep.t o f Physics,Yunna D aliU niv.,D a li671000,China)Abst ract:Shortest path proble m is a basic are in the co mb i n atorial opti m ization.The objective is ti m e variable. M oreove r,there are curfe w s in so m e nodes in the ne t w ork.The paper developsd the m ode ls fo r ti m e-var y ing m ini-m um cost path prob le m w it h soft and har d curfe w s and t h e algo rith m fo r t h e m.Finall y,a p r actical exa m ple is given. K ey w ords:m ini m um co st path;ti m e-vary i n g;cu rfe w s;labe li n g a l g orit h m76 湖南工程学院学报 2006年。
最短路问题的求解方法最短路问题是图论中一个经典的问题，它在实际生活中有着广泛的应用，比如在交通规划、网络通信、物流配送等领域都有着重要的作用。
在解决最短路问题时，我们通常会采用不同的算法来求解，本文将介绍几种常见的最短路求解方法。
首先，我们来介绍最简单的最短路求解方法——暴力法。
暴力法的思路是枚举所有可能的路径，并找出其中的最短路。
虽然暴力法在理论上是可行的，但在实际应用中，由于其时间复杂度较高，往往不适用于大规模的图。
因此，我们需要寻找更加高效的算法来解决最短路问题。
其次，我们可以考虑使用迪杰斯特拉算法（Dijkstra algorithm）来求解最短路问题。
迪杰斯特拉算法是一种贪心算法，它通过不断地选择距离起点最近的顶点，并更新其邻居顶点的距离，来逐步求解最短路。
迪杰斯特拉算法的时间复杂度为O(V^2)，其中V表示顶点的个数。
这使得它在实际应用中具有较高的效率，尤其适用于稠密图的求解。
除了迪杰斯特拉算法外，我们还可以使用弗洛伊德算法（Floydalgorithm）来解决最短路问题。
弗洛伊德算法采用动态规划的思想，通过不断更新图中任意两点之间的最短路径长度，来逐步求解整个图的最短路。
弗洛伊德算法的时间复杂度为O(V^3)，因此在大规模图的求解中也具有较高的效率。
除了上述算法外，我们还可以考虑使用A算法、贝尔曼-福特算法等其他算法来解决最短路问题。
这些算法各有特点，适用于不同类型的图和不同的应用场景。
总的来说，最短路问题是一个重要且经典的问题，在实际应用中有着广泛的应用。
在求解最短路问题时，我们可以根据具体的情况选择合适的算法来求解，以提高效率和准确性。
希望本文介绍的几种最短路求解方法能够对读者有所帮助，谢谢阅读！。
最短路dijkstra算法详解最短路问题是图论中的一个经典问题，其目标是在给定图中找到从一个起点到其他所有节点的最短路径。
Dijkstra算法是解决最短路问题的一种常用算法，本文将详细介绍Dijkstra算法的原理、实现以及时间复杂度等相关内容。
一、Dijkstra算法的原理Dijkstra算法是一种贪心算法，其基本思想是从起点开始，逐步扩展到其他节点。
具体而言，Dijkstra算法通过维护一个集合S来记录已经找到了最短路径的节点，以及一个数组dist来记录每个节点到起点的距离。
初始时，S集合为空，dist数组中除了起点外所有节点都被初始化为无穷大。
接下来，重复以下步骤直到所有节点都被加入S集合：1. 从dist数组中选择距离起点最近的未加入S集合的节点u；2. 将u加入S集合；3. 更新与u相邻的未加入S集合的节点v的距离：如果从起点出发经过u可以得到更短的路径，则更新v对应位置上dist数组中存储的值。
重复以上步骤直至所有节点都被加入S集合，并且dist数组中存储了每个节点到起点的最短距离。
最后，根据dist数组中存储的信息可以得到起点到任意节点的最短路径。
二、Dijkstra算法的实现在实现Dijkstra算法时，需要使用一个优先队列来维护未加入S集合的节点，并且每次从队列中选择距离起点最近的节点。
由于C++标准库中没有提供优先队列，因此需要手动实现或者使用第三方库。
以下是一个基于STL堆实现的Dijkstra算法代码示例：```c++#include <iostream>#include <vector>#include <queue>using namespace std;const int INF = 0x3f3f3f3f;vector<pair<int, int>> adj[10001];int dist[10001];void dijkstra(int start) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push(make_pair(0, start));dist[start] = 0;while (!pq.empty()) {int u = pq.top().second;pq.pop();for (auto v : adj[u]) {if (dist[u] + v.second < dist[v.first]) {dist[v.first] = dist[u] + v.second;pq.push(make_pair(dist[v.first], v.first));}}}}int main() {int n, m, start;cin >> n >> m >> start;for (int i = 1; i <= n; i++) {dist[i] = INF;}for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;adj[u].push_back(make_pair(v, w));}dijkstra(start);for (int i = 1; i <= n; i++) {if (dist[i] == INF) {cout << "INF" << endl;} else {cout << dist[i] << endl;}}return 0;}```以上代码中，adj数组用于存储图的邻接表，dist数组用于存储每个节点到起点的最短距离。
浙江科技学院学报,第18卷第4期,2006年12月Jo urna l of Zhejiang U nive rsity of Science and T echnology Vo l.18No.4,Dec.2006收稿日期:2006-11-21作者简介:陈建芳(1965— ),男,浙江绍兴人,高级讲师,主要从事应用数学研究。
一种求解时变条件下双目标最短路的算法陈建芳(绍兴托普信息职业技术学院院长办公室,浙江绍兴312000)摘 要:在组合优化过程中,往往需要获得从起点到终点之间的最短路,有时需要同时考虑两个目标,而这些目标可能会随着时间的变化而变化。
为此,提出了一种利用标号法获得时变条件下双目标最短路的方法,考虑了不同的出发时间的情况,并对算法的复杂性进行了分析,最后给出了一个应用算例。
关键词:最短路;双目标;时变;运输网络中图分类号:O 29 文献标识码:A 文章编号:1671-8798(2006)04-0245-05Approach for Bi -Objective Shortest Path with Time -VaryingCH EN Jian -fang(Shaox in T o p Info r.Caree r T ech.College ,Zhejiang Shao xin ,312000China )A bstract :Shortest path pro blem is a basic problem in the combinatorial o ptimization.In gen -eral ,tw o objective w ill be considered in the transpor tation and the objectives are time -varying.The autho r developed the alg orithm for the tw o objectives shortest path w ith time -varying by using the labelling approach ,gave the alg orithm to the problem w ith defferent start time ,and dicussed the computational co mlexity of the algo rithm.At last ,a case w as studied.Key words :sho rtest path ;bi -o bjective ;time -varying ;netw ork 利用标号法求解时变条件下单目标最短路的算法,笔者已作了详细的论述[1]。
第12卷第1期2009年2月 管 理 科 学 学 报J O U R N A LO FM A N A G E M E N TS C I E N C E SI NC H I N AV o l.12N o.1F e b.2009一种求解时变条件下有宵禁限制最短路的算法①魏 航1,2(1.上海财经大学国际工商管理学院,上海200433;2.上海财经大学500强企业研究中心,上海200433)摘要:在组合优化过程中,往往需要获得从起点到终点之间的最短路.由于道路、天气、交通条件等因素的影响,使得网络具有很强的时变特性.同时,对于网络中的节点往往有宵禁的限制.对时变条件下有宵禁限制并有到达时间限制的最短路进行了研究,建立了软、硬宵禁限制下的数学模型,给出并证明了时变条件下获得有宵禁限制最短路的最优条件,并设计了求解的多项式算法,通过此算法可以获得时变条件下有宵禁限制的最短路.同时,算法和模型还考虑了不同的起点出发时间,使路径决策者可以根据自身的情况,选择合适的出发时间和路径.最后给出了一个应用算例,分析了宵禁对于获得的最短路的影响.关键词:最短路;时变;宵禁;算法中图分类号:U116.2 文献标识码:A 文章编号:1007-9807(2009)01-0009-090 引 言在运输过程中,往往需要获得从起点到终点之间的最短问题,对于该问题目前已经有了很多经典的算法,如20世纪50年代的D i j k s t r a算法[1],60年代的F l o y d算法.但是,这些算法均假设网络中的所赋的值是静态的、确定的,而这样的假设在许多应用领域并不适用或是与实际情况有着一定的差距.比如,在实际的车辆行驶过程中,由于交通管理、交通流量、交通事故、天气变化等因素的影响,导致了路网中各个路段上的运行成本、时间、安全性等也相应地发生变化[2],而这些变化往往与车辆行驶时所处的时间密切相关.对于这样与时间因素密切相关的网络称为时变网络,而在这样的网络条件下的最短路问题称为时变条件下的最短路问题.对于时变条件下的最短路问题,目前主要集中在获得最短运输时间的最短路问题的研究上.D r e y f u s S E[3]给出的改进D i j k s t r a算法求解时变条件下最小时间路径问题的方法,并认为该方法会像静态最短路径问题一样有效.K a u f m a nDE 和S m i t h RL[4]给出的D r e y f u s S E算法在时变网络中是不正确的反例,建立了严格的一致性条件来限制“病态”实例的出现.O r d a A和R o mR[5]给出的三种类型的网络模型:提出了不受限制的等待模型;禁止等待模型和源等待模型.M i l l e r-H o o k s E,M a h m a s s a n i H[6]对在随机时变网络的最短时间的最短路进行了研究,提出了两种不同的算法,并对这两种算法进行了比较.M i l l e r-H o o k s E,M a h m a s s a n i H[7]提出了一些在随机时变网络下的不同路径之间进行比较的原则.A t h a n a s i s o Z,D i m i t r i o s K和M a h m a s s a n i H[8]对在时变条件下考虑最短时间的最短路在智能交通系统中的应用进行了分析.谭国真,高文[9]对时间依赖网络下的最小时间问题进行了研究,给出了时变网络与一般网络①收稿日期:2007-03-26;修订日期:2008-10-10.基金项目:国家自然科学基金资助项目(70471039);教育部新世纪优秀人才支持计划资助项目(N C E T-04-0886);国家教育部“十一五”211工程资助项目.作者简介:魏 航(1976—),男,浙江绍兴人,博士,讲师.E m a i l:o d e y w e i@y a h o o.c o m.c n进行求解最短路的差别,并给出了算法.谭国真,柳亚玲,高文[10]研究了随机时间依赖网络下的K 期望最短路径问题,给出了求解的算法.魏航,李军,蒲云[11]对时变条件下有害物品运输的最短路问题进行了研究,在折衷条件下给出了求解的算法.魏航,李军,刘凝子[12]对时变条件下多式联运的最短路问题进行了研究,将网络进行了扩展,并给出了求解的算法.杨烜会,刘震宇[13]研究了结点等待费用、弧费用和弧通过时间均为离散时变函数的最短路径问题,并基于动态规划原理,给出了一种标号更新算法.但是,这些目前已有的研究均没有考虑宵禁限制或时间窗限制的情况.而在现实情况中,对于车辆的运输往往是有宵禁(c u r f e w s)限制,就是说在某一个时段内车辆不能通过某些节点.比如,在夜间12点到早上6点,在中心城市区域车辆不能通过.显然,从某种意义上来说,有宵禁限制的问题是一个“逆”时间窗问题(a n t i-t i m e-w i n d o w s).一般地,有时间窗的最短路问题需要满足的是到达各个节点的时间必须在所规定的时间范围内,而宵禁限制为到达各个节点的时间必须不在所规定的时间范围内.对于有时间窗的最短路问题,目前在静态条件下也已经进行了一定的研究.D e s r o c h e r s M,S o u m i s F[14]给出了一种求解有时间窗的最短路问题的算法.D e s r o c h e r s M,S o u m i s F[15]对原有算法进行了改进,通过重复优化的方法,给出了新的算法.D r o r M[16]对有时间窗最短路问题计算复杂性进行了研究,并证明了其为N P-困难问题.另外,对于有宵禁限制的最短路问题,C o x RG和T u r q u i s t MA[17]在静态网络条件下进行了研究,给出了在宵禁限制对运输网络中的可行路径到达时间延误的分析.本文结合了宵禁限制和时变网络两个方面,并同时考虑了车辆到达时间的限制.建立了时变网络条件下有(软、硬)宵禁限制并有到达时间限制的最短路的数学模型,给出了获得最短路的最优条件并进行了证明,然后设计了求解时变网络条件下有(软、硬)宵禁限制的最短路算法,论了算法的复杂性.最后给出了一个应用算例1 问题描述对于在时变网络条件下有宵禁限制并有到达时间限制的最短路问题,一般地,可以描述为:对于网络G=(N,E),E为节点间的有向边的集合,N为节点集,N=n,E=m.在此,令c(i, j,t D i)为在节点i到节点j之间,在时间t D i出发时的成本,c(i,j,t D i)为一个非负的实数,(i,j)∈E. t(i,j,t D i)为在节点i到节点j之间,在时间t D i出发时所需的时间,t(i,j,t D i)为一个整数,(i,j)∈E.在此,令Z表示宵禁时间区域的数量,并令C u r(z)表示在宵禁时间区域z的节点的集合,z= 1,2,…,Z,C u r(z)∈N.同时,分别令S C u r(z)和E C u r(z)表示宵禁时间区域z的起始时间和终止时间.并令Z i表示属于节点i的宵禁时间区域的集合.S(O)为车辆从起点O允许出发的离散时间的集合,S(O)=S.求在时间T之前到达终点D的(T为整数),满足宵禁限制的从起点O到终点D之间的最短路.2 数学模型类似于有时间窗限制的路径问题,一般地,对于时变网络下有宵禁限制的最短路问题主要分为两类:一类是软宵禁限制的最短路问题;另一类是硬宵禁限制的最短路问题.软宵禁限制的最短路问题与硬宵禁限制的最短路问题的区别在于软宵禁限制的最短路问题的宵禁限制是柔性的,而对于硬宵禁限制的最短路问题,宵禁限制是刚性的.对于有软宵禁限制的最短路,车辆到达某个节点的时间可能会处于此节点的某个宵禁时间区域内,此时就给予一定的惩罚,但是,需要注意的是,此时其出发时间为此宵禁时间区域的终止时间.而对于硬宵禁限制的最短路问题,如果实际到达节点的时间处于该节点的某个宵禁时间区域内即为不可行解.显然,有时在有硬宵禁限制的条件下不一定存在可行解.为了得到时变网络下有宵禁限制并有到达时间限制的最短路模型,首先,定义如下变量和运算i到节点j之间存在运输任务i时处于节点i的宵禁限制区域z内—10—管 理 科 学 学 报2009年2月其中,当x i z =1时,表示车辆违反了宵禁限制,即当车辆到达节点i 的时间t Ai 处于节点i 的某个宵禁限制z 内,其中t Ai 为车辆到达节点i 的时间.其条件为:∑jy i j =1,且有S C u r (z )≤t Ai <E C u r (z ),i ∈C u r (z ),z =1,2,…,Z .对于软宵禁限制,此时仍然为可行解,但需要进行惩罚;而当限制条件为硬宵禁限制时,必须保证车辆不违反宵禁限制,即不能产生x i z =1这样的情况.定义1 ‖·‖为一运算符号,其表示的意义为:当变量δ<0时,则‖δ‖=1;当变量δ≥0时,则‖δ‖=0.对于有软宵禁限制的最短路问题,一般地,若达到节点i 的时间t Ai 不在节点i 的任意一个宵禁时间区域z 内,z =1,2,…,Z ,则到达时间和出发时间相同,即有t A i =t Di .但是,若到达节点i 的时间t Ai 处于节点i的某个宵禁时间区域z 内,即S C u r (z )≤t Ai <E C u r (z ),i ∈C u r (z ),z=1,2,…,Z ,则出发时间为此宵禁时间区域的终止时间,即有t Di =E C u r (z ).这样,时变网络下有软宵禁限制并有到达时间限制的最短路模型可以描述为 m i n C =[∑(i ,j )y i j c (i ,j ,t Di )]+∑i ∑Zz =1[αx i z (t A i - S C u r (z ))+βx i z (E C u r (z )-t Ai )](1) s .t .∑j y i j -∑jy j i = 1若i =O-1若i =D i ∈N 0其他(2)∑jy i j ≤1 i∈N (3)∑zx i z ≤1 i∈N(4)y i j∈{0,1} (i ,j )∈E (5)x i z ∈{0,1} i ∈N ,z =1,2,…,Z (6)x i z =(∑j y i j ‖∏z ∈Z i [t Ai -S C u r (z )]·[t Ai - E C u r (z )]‖ i ∈N ,z =1,2,…, Z ,(i ,j )∈E(7)t D i =(1-x i z )t A i +x i zE C u r (z ) i ∈N ,z =1,2,…,Z ,i ∈N (8)s (O )+∑(i ,j )y i j t (i ,j ,t D i )≤T (i ,j )∈E , s (O )∈S (O ),z =1,2,…,Z(9)其中,目标函数的第1部分表示车辆在行驶过程中的成本;第2部分前面部分表示车辆超过某个宵禁限制区域所给予的惩罚;第2部分后面部分表示车辆等待到某个宵禁限制区域结束所需的等待成本;α为超过某个宵禁时间区域的起点时间到达节点i 所给予单位时间的惩罚值;β为车辆因为超过某个宵禁时间区域的起点时间到达,而需要在节点i 进行等待到此宵禁时间区域结束的单位时间的等待成本;t Ai 表示车辆到达节点i 的时间.约束(2)、(3)和(5)保证了所选择的路径必定为从起点到终点之间的可行路径.约束(7)给出了x i z 计算方法,首先需要判断车辆是否经过节点i ,可以利用∑jy i j的值来判断;然后再判断是否违反宵禁限制,当到达节点i 的时间t Ai 处于节点i 的某个宵禁时间区域z 内时,则必然有t Ai -S C u r (z )>0且t Ai -E C u r (z )<0,而对于其它属于节点i 的宵禁区域均有t Ai -S C u r (z )>0且t Ai -E C u r (z )>0,或t Ai -S C u r (z )<0且t Ai -E C u r (z )<0,z ∈Z i.这样,车辆当违反宵禁限制时,有∏z ∈Z i[t Ai -SC u r (z )]·[t A i-E C u r (z )]<0,相应的,有x i z =1;其次,当到达节点i 的时间t Ai 满足宵禁限制时,则可以得到x i z =0.特别的,当Z i =时,令S C u r (z )=0,E C u r (z )=0,i ∈N .约束(9)保证了车辆到达终点的时间不能超过时间T .由于在有硬宵禁限制条件下,任何到达某个节点的时间处于此节点的某个宵禁限制区域均为不可行解.此时,若有α=β=M (M →∞),则意味着宵禁限制必须被满足.这样,时变网络下有硬宵禁限制的最短路模型可以描述为 m i n C =[∑(i ,j )y i jc (i ,j ,t Di)]+∑i ∑Zz =1[M x i z(t A i- S C u r (z ))+M x i z (E C u r (z )-t Ai )](10) s .t .式(2)—(9)(11)3 算法为了获得时变网络下有宵禁限制并有到达时间限制的最短路算法,本文在C a i X 等[18]算法的基础上,给出了时变网络下有宵禁限制并有到达时间限制的最短路算法.—11—第1期魏 航:一种求解时变条件下有宵禁限制最短路的算法3.1 定义和定理首先给出下面的定义.定义2 若φ=(O=1,2,…,l=D)为从起点O到终点D之间的一条路径,令t A1=s(O),并令t A i为到达节点i的时间,则t A i=t D i-1+t(i-1,i, t D i-1),t D i-1=w(i-1)+t A i-1,t A i-1,为到达节点i-1的时间,t D i-1为从节点i-1出发的时间,w(i-1)为在节点i可能需要等待的时间,当到达节点i的时间违反属于节点i的某个宵禁限制z时,则w(i-1)=E C u r(z)-t A i-1;否则,当满足宵禁限制时,则w(i-1)=0,2≤i≤l,s(O)∈S(O),z=1,2,…,Z.定义3 若φ=(O=1,2,…,l=D)为从起点O到终点D之间的一条路径,令c A1=0,并令c A i 为到达节点i的成本,c A i=c D i-1+c(i-1,i,t D i-1), c D i-1=c(i-1)+c A i-1,c A i-1,为到达节点i-1的成本,c D i-1为从节点i-1出发的成本,c(i-1)为由于在节点i可能产生的惩罚,当到达节点i的时间违反属于节点i的某个宵禁限制z时,则c(i-1)=α(t A i-S C u r(z))+β(E C u r(z)-t A i);否则,当满足宵禁限制时,则c(i-1)=0,c A i-1到达节点i-1的成本,2≤i≤l(当宵禁限制为硬宵禁限制时,当违反宵禁限制时,则c(i-1)=M(t A i-1-S C u r(z))+M(E C u r(z)-t A i-1);否则,当满足宵禁限制时,c(i-1)=0).定义4 d(j,t A j)为在时间t A j到达节点j,从起点O到节点j考虑成本最小化的最短路,j∈N;否则,若在时间t A j不存在这样的路径,则d(j,t A j)=∞.定义5 L(i,j,t A j)为在时间t A j到达节点j并且j的前一个节点为i的,从起点O到节点j考虑成本最小化的路径长度.基于这些定义,可以给出下面的定理.定理1 对网络G=(N,E),令d(O,0)= 0,d(j,0)=∞,当j≠O,j∈N.这样,当t A j>0,j≠O时,有d(j,t A j)=m i n{i(i,j)∈E}m i n{(t Ai,t Di)∈T(i,j,t Aj)}{c(i)+d(i,t A i)+c(i,j,t D i)},其中T(i,j,t A j)={(t A i,t D i) t D i+t(i,j,t D i)=t A j∧t D i-t A i=x i z[E C u r(z)-t A i]}.证明 对于此命题,可以应用数学归纳法进行证明.首先,当t A j=1时,这些节点为起点O以及与起点O相连的节点.对于所有的节点j≠O,j∈N,考虑(O,j)∈E,且t(O,j,0)=1.此时,d(j,t A j)= c(O)+d(O,0)+c(O,j,0).其次,假设当(t A j)′<t A j时,命题成立.当d(j,t A j)=∞时,则没什么可以证明的.这样,设d(j,t A j)为一个有限的实数,j≠O,j∈N,则必然存在某一个i使得L(i,j,t A j)=c(i)+d(i,t A i)+ c(i,j,t D i),其中,t D i+t(i,j,t D i)=t A j,且(t A i,t D i)∈T(i,j,t A j),(i,j)∈E.否则,若不存在这样的i使得L(i,j,t A j)=c(i)+d(i,t A i)+c(i,j,t D i),则d(j, t A j)=∞,与假设矛盾.由于t(i,j,t D i)>0,这样就有t A i<t A j,根据假设,从起点O到节点i之间存在一条可行路径,设为φ′=(O=1,2,…,i),且在时间t A i到达的最短路为d(i,t A i).此时,若车辆不违反宵禁限制,则有t A i=t D i;否则,若车辆违反宵禁限制,则有t D i= E C u r(z),z=1,2,…,Z.由于d(i,t A i)为在时间t A i 到达节点i的最短路,不管是否违反宵禁限制,路径φ′还是一条在时间t D i从节点i出发的从起点O 到节点i之间的可行路径.这样,可以将路径φ′扩展到节点j,得到路径φ=(O=1,2,…,i,i+1= j),由于t D i+t(i,j,t D i)=t A j,这样t A j即为到达节点j的时间.由此可以得到,通过扩展获得的路径φ为从起点O到节点j之间,在时间t A j到达的一条可行路径.由于通向节点j的节点i的数量有限,且其出发时间t D i也为有限个,这样,通过扩展获得的路径也为有限条.对于任何通过扩展获得的路径的长度有:L(i,j,t A j)≥c(i)+d(i,t A i)+c(i,j,t D i)≥d(j,t A j),这样就必然存在某一个L＊(i,j,t A j)= d(j,t A j),即存在φ=(O=1,2,…,i,i+1=j)为从起点O到节点j之间且在时间t A j到达节点j的最短路,且t D i+t(i,j,t D i)=t A j.证毕.3.2 算法步骤在给出定理1的证明之后,就可以给出在时变条件下,获得有宵禁限制并有到达时间限制的最短路的d＊(D)算法,算法的具体步骤如下:步骤1 令d(O,0)=0,且j≠O d(j,t A j)=∞,对t A j=0,1,…,T步骤2 根据给出的宵禁限制的时间区域,计算出所有的t D i=t A i+w(i),并同时获得c(i), t A i=1,…,T—12—管 理 科 学 学 报2009年2月步骤3 利用获得的t D i ,计算出所有的t Di +t (i ,j ,t D i )=t Aj步骤4 s =m i n {s (O )}步骤5 t Aj =s步骤6 对所有的有向边(i ,j )∈E 、j ∈N ,且对所有的t D i 满足t D i +t (i ,j ,t D i )=t Aj ,令d s (j ,t Aj )∶=m i n {i (i ,j )∈E }m i n{(t A i ,t D i )∈T (i ,j ,t A j)}{c (i )+ d s (i ,t Ai )+c (i ,j ,t Di )}步骤7 t A j =t Aj +1步骤8 若t Aj ≤T ,则转步骤6,否则转步骤9步骤9 从S (O )删去s ,若S (O )≠Υ,则令s =m i n {s (O )}令,转步骤4;否则转步骤10步骤10 d ＊(D )=m i n s ∈S (O )m i n 0≤t A D≤Td s (D ,t AD ).当约束为软宵禁时,此时获得的d ＊(D )即为所获得的最优解;当约束为硬宵禁时,若获得的d ＊(D )为一个相当大的数(M 为量纲),则表明此时无可行路径3.3 算法复杂性分析定理2 时变网络条件下,O (S T (Z n+m+n )).证明 对于每一个s (O )∈S (O ),都有首先,O (T n ).然后,对于每一个时间t A i=1,…,T ,计算t Di=t A i+w (i )并获得c (i ),到达时间t Ai 均需考虑是否满足宵禁限制,限制的个数为Z 个,需要时间O (Z T n );然后要对每一条有向边的进行计算t D i +t (i ,j ,t Di t Aj ,需要时间O (T m ).这样对于所有的1≤t Aj 计算各个成本,需要的时间为O (T (Z n+m )这样,将两部分进行合并,其O (T (Z n +m +n )).因此,对于整个问题,其计算复杂O (S T (Z n+m+n )).4 算 例下面给出一个算例,运输网络如图1所示含20个节点和45条有向边).间区域分别如表1所示,其中Y 域有宵禁限制,而N 表示无宵禁限制.表2给出了在运输过程中,各个节点之间在不同时间条件下,运输过程中的运输成本和运输时间.假设车辆可以在时间0从起点O 出发,并每隔2个小时整点出发一次.在此,假设在软宵禁限制条件下,超过宵禁时间区域到达的单位惩罚成本为5,而需要等待到宵禁时间区域结束的单位时间的等待成本为2.现希望获得在时间35之前到达终点D 的最短路.图1 运输网络F i g .1T h e t r a n s p o r t a t i o n n e t w o r k 表1 各节点的宵禁时间区域T a b l e 1T h e c u r f e wf o r e a c hn o d e—13—第1期魏 航:一种求解时变条件下有宵禁限制最短路的算法表2 各条有向边在不同时间条件下的运输成本和运输时间T a b l e 2T h e c o s t a n d t i m e o f e a c hl i n k w i t hd i f f e r e n t t i m e p e r i o d—14—管 理 科 学 学 报2009年2月 分别选取不同的出发时间,并应用给出的算法,可以获得在不同出发时间条件下,有软、硬宵禁限制和无宵禁限制条件下的最短路分别如表3所示.从表3中可以看出,不同出发时间条件下,不管在有软宵禁、硬宵禁还是在无宵禁条件下,最短路会有所不同,且成本也会有所不同.从总体上看,在有软、硬宵禁时间限制时,起点出发时间选择为12时,路径选择为O-1-6-11-16-D 时,成本最小;当出发时间为18时,在硬宵禁限制条件下,此时无可行路径;当出发时间超过18时,由于到达时间超过35,无可行路径.表3 不同出发时间条件下最短路T a b l e 3T h e s h o r t e s t p a t hw i t hd i f f e r e n t d e p a r t u r e t i m e出发时间最短路软宵禁限制成本硬宵禁限制成本无宵禁限制成本0O -2-7-11-16-D 73O-2-7-11-16-D 73O-4-3-8-12-16-D 702O -1-6-11-16-D 71O-4-9-13-17-D 85O-1-6-11-16-D 704O -1-6-11-16-D 79O-4-9-13-17-D 80O-1-6-11-16-D 626O -1-6-11-16-D 62O-1-6-11-16-D 62O-1-6-11-16-D 628O-1-6-11-16-D /O -2-7-11-16-D 55O-1-6-11-16-D/O-2-7-11-16-D 55O-1-6-11-16-D /O-2-7-11-16-D 5510O -1-6-11-16-D 57O-2-7-11-16-D 60O-1-6-11-16-D 5012O -1-6-11-16-D 50O-1-6-11-16-D 50O-1-6-11-16-D 5014O -4-9-13-17-D 59O-2-7-11-16-D 75O-4-9-13-17-D 5516O -2-7-11-16-D 69O-4-3-8-12-16-D74O-2-7-11-16-D 6518O-4-3-8-12-16-D69——O-4-9-13-17-D70 对于宵禁限制对于成本的影响,图2给出了有软宵禁限制情况和无宵禁限制时所获得的最短路的成本对比,图3给出了其中一条可行路径O-1-6-11-16-D 在有软宵禁限制和无宵禁限制条件下的成本对比.从给出的图形可以明显地看到有宵禁限制对成本的影响.5 结 论在组合优化过程中,往往需要获得从起点到终点之间的最短路.由于道路、天气、交通条件等因素的影响,使得网络具有很强的时变特性.对于时变条件下有宵禁限制并有到达时间限制的最短路问题,目前基本上还没有进行研究.由于时间因素会影响目标值,使得时变网络下最短路的求解过程相对比较困难.同时,对于网络中的一些节点往往有宵禁限制并且对于到达终点的时间可能会有一定的限制.本文对时变条件下有宵禁限制并有到达时间限制的最短路进行了研究,建立了软、硬宵禁限制—15—第1期魏 航:一种求解时变条件下有宵禁限制最短路的算法下的数学模型,给出并证明了时变条件下获得有宵禁限制最短路的最优条件,并设计了求解的多项式算法,通过此算法可以获得时变条件下有宵禁限制的最短路.同时,算法和模型还考虑了不同的起点出发时间,使路径决策者可以根据自身的情况,选择合适的出发时间和路径.从给出的实例来看,宵禁限制对于最短路的选择和所获得最短路的成本是有一定影响的.该算法的提出和设计,为时变条件下的路径选择问题的理论和算法进行了补充和加强,同时,该算法还可以进行变形,用以求解时变条件下有时间窗限制情况下的最短路问题.参考文献:[1]D i j k s t r a EW.An o t e o nt w o p r o b l e m s i n c o n n e c t i o nw i t hg r a p h s [J ].N u m e r .M a t h ,1959,1:269—271.[2]郭耀煌,钟小鹏.动态车辆路径问题排队模型分析[J ].管理科学学报,2006,9(1):33—37.G u o Y a o h u a n g ,Z h o n g X i a o p e n g .A n a l y s i s o f t h e q u e u i n g m o d e l o f d y n a m i c v e h i c l e r o u t i n g p r o b l e m [J ].J o u r n a l o f M a n a g e -m e n t S c i e n c e s i n C h i n a ,2006,9(1):33—37.(i n C h i n e s e )[3]D r e y f u s S E .A na p p r a i s a l o f s o m e s h o r t e s t p a t ha l g o r i t h m s [J ].O p e r a t i o n s R e s e a r c h ,1969,17:395—412.[4]K a u f u m a n DE .M i n i m u m t r a v e l t i m ep a t hi nd y n a m i c n e t w o r k s w i t ha p p l i c a t i o n t o i n t e l l i g e n t v e h i c l e /h i g h w a ys y s t e m s [J ].I V H S J o u r n a l ,1993,1(1):1—19.[5]O r d a A ,R o m R .S h o r t e s t p a t h a n dm i n i m u m -d e l a y a l g o r i t h m s i nn e t w o r k s w i t ht i m e -d e p e n d e n t e d g e -l e n g t h [J ].J .A C M ,1990,37(3):607—625.[6]M i l l e r -H o o k s E ,M a h m a s s a n i H .L e a s t p o s s i b l e t i m e p a t h s i ns t o c h a s t i c ,t i m e -v a r y i n g n e t w o r k s [J ].C o m p u t e r s a n dO p e r a -t i o n s R e s e a r c h ,1998,25(12):1107—1125.[7]M i l l e r -H o o k s E ,M a h m a s s a n i H .P a t hc o m p a r i s o n s f o r ap r i o r i a n dt i m e -a d a p t i v e d e c i s i o n s i ns t o c h a s t i c ,t i m e -v a r y i n gn e t -w o r k s [J ].E u r o p e a nJ o u r n a l o f O p e r a t i o n a l R e s e a r c h ,2003,146:67—82.[8]A t h a n a s i s o Z ,D i m i t r i o s K ,M a h m a s s a n i H .D e s i g na n di m p l e m e n t a t i o n o f p a r a l l e l t i m e -d e p e n d e n t l e a s t t i m e p a t h a l g o r i t h mf o r i n t e l l ig e n t t r a n s p o r t a t i o n s y s t e m s a p p l i c a t i o n s [J ].T r a n s p o r t a t i o nR e s e a r ch ,P a r t C ,1997,5(2):95—107.[9]谭国真,高 文.时间依赖的网络中最小时间路径算法[J ].计算机学报,2002,25(2):165—172.T a n G u o z h e n ,G a o W e n .S h o r t e s t p a t h a l g o r i t h mi n t i m e -d e p e n d e n t n e t w o r k s [J ].C h i n e s e J o u r n a l o f C o m p u t e r s ,2002,25(2):165—172.(i n C h i n e s e )[10]谭国真,柳亚玲,高 文.随机时间依赖网络的K 期望最短路径[J ].计算机学报,2003,26(3):323—331.T a n G u o z h e n ,L i uY a l i n g ,G a oWe n .K E x p e c t e ds h o r t e s t p a t hi ns t o c h a s t i ca n dt i m e -d e p e n d e n t n e t w o r k [J ].C h i n e s e J o u r n a l o f C o m p u t e r s ,2003,26(3):323—331.(i nC h i n e s e )[11]魏 航,李 军,蒲 云.时变条件下有害物品运输的路径问题研究[J ].系统工程理论与实践,2006,10:107—112.We i H a n g ,L i J u n ,P u Y u n .R o u t e p l a n n i n g f o r h a z a r d o u s m a t e r i a l s t r a n s p o r t a t i o n i n t i m e -v a r y i n g n e t w o r k [J ].S y s t e mE n -g i n e e r i n g T h e o r y a n d P r a c t i c e ,2006,10:107—112.(i n C h i n e s e )[12]魏 航,李 军,刘凝子.一种求解时变网络下多式联运最短路的算法[J ].中国管理科学,2006,14(4):56—63.We i H a n g ,L i J u n ,L i u N i n g z i .A n a l g o r i t h mf o r s h o r t e s t p a t h w i t hm u l t i -m o d a l i n t i m e -v a r y i n g n e t w o r k [J ].C h i n e s e J o u r -n a l o f M a n a g e m e n t S c i e n c e ,2006,14(4):56—63.(i n C h i n e s e )[13]杨烜会,刘震宇.含结点等待费用的离散时变最短路径[J ].系统工程理论与实践,2007,1:113—117.Y a n g X u a n h u i ,L i u Z h e n y u .D i s c r e t e t i m e d e p e n d e n t s h o r t e s t p a t h s c o n s i d e r i n g n o d e -w a i t i n g c o s t [J ].S y s t e mE n g i n e e r i n g T h e o r y a n dP r a c t i c e ,2007,1:113—117.(i nC h i n e s e )[14]D e s r o c h e r s M ,S o u m i s F .Ag e n e r a l i z e d p e r m a n e n t l a b e l i n g a l g o r i t h mf o r t h e s h o r t e s t p a t h p r o b l e mw i t ht i m e w i n d o w s [J ].I N F O R ,1988,26:191—212.[15]D e s r o c h e r s M ,S o u m i s F .Ar e o p t i m i z a t i o na l g o r i t h mf o r t h e s h o r t e s t p a t h p r o b l e mw i t h t i m e w i n d o w s [J ].E u r o p e a n J o u r n a lo f O p e r a t i o n a l R e s e a r c h ,1988,35:242—254.[16]D r o r M .N o t e o n t h e c o m p l e x i t yo f t h es h o r t e s t p a t hm o d e l s f o r c o l u m ng e n e r a t i o ni nV R P T W[J ].O p e r a t i o n s R e s e a r c h ,—16—管 理 科 学 学 报2009年2月1994,42:977—978.[17]C o x R G ,T u r q u i s t M A .S c h e d u l i n g t r u c ks h i p m e n t o f H a z a r d o u s M a t e r i a l s i nt h ep r e s e n t o f c u r f e w s [J ].T r a n s p o r t a t i o nR e s e a r c h R e c o r d ,1986,1063:21—26.[18]C a i X ,K l o k s T ,Wo n g CK .T i m e v a r y i n gs h o r t e s t p a t hp r o b l e m s a l g o r i t h m f o r p r o b l e m s w i t hc o n s t r a i n t s [J ].N e t w o r k s ,1998,31:193—204.A n a p p r o a c hf o r t i m e -v a r y i n g s h o r t e s t p a t h p r o b l e m w i t h c u r f e w s W E I H a n g1,21.S c h o o l o f I n t e r n a t i o n a l B u s i n e s s A d m i n i s t r a t i o n ,S h a n g h a i U n i v e r s i t y o f F i n a n c e a n d E c o n o m i c s ,S h a n g h a i200433,C h i n a ;2.T h e F o r t u n e 500C o m p a n y R e s e a r c h C e n t e r i nS h a n g h a i U n i v e r s i t y o f F i n a n c e a n dE c o n o m i c s ,S h a n g h a i 200433,C h i n aA b s t r a c t :S h o r t e s t p a t h p r o b l e mi s a b a s i c p r o b l e mi n t h e c o m b i n a t o r i a l o p t i m i z a t i o n .I n d y n a m i c t r a n s p o r t a -t i o n n e t w o r k s ,t h e a r c t r a v e l t i m e s a n d c o s t s a r e t i m e -v a r y i n g d e p e n d i n g o n r o a d c o n d i t i o n ,w e a t h e r a n d t r a f f i c c o n d i t i o n .M o r e o v e r ,t h e r e w i l l b e c u r f e w s i n s o m e n o d e s i n t h e n e t w o r k b e c a u s e o f r e s t i n g ,c o n g e s t i o n a n d s o o n .T h e p a p e r d e v e l o p e dm o d e l s f o r t i m e -v a r y i n g s h o r t e s t p a t hp r o b l e m s w i t hb o t hs o f t a n dh a r dc u r f e w s .T h e n ,t h e o p t i m a l c o n d i t i o n f o r g e t t i n g t h e s h o r t e s t p a t h w i t h c u r f e w s w a s p r o v e d .B a s e d o n t h i s c o n d i t i o n ,t h e a l g o r i t h m w a s p r o p o s e d .I n o r d e r t o d e c r e a s e t h e o b j e c t i v e v a l u e ,t h e a l g o r i t h ma l s o c o n s i d e r e d t h e m u l t i -d e -p a r t u r e -t i m e a n d c o m p a r e d w i t h t h e v a l u e i n d i f f e r e n t d e p a r t u r e t i m e s .T h e p a p e r a l s o d i s c u s s e d t h e c o m p l e x i t y o f t h e a l g o r i t h m .A t t h e e n d ,a c a s e w a s s t u d i e d .K e y w o r d s :s h o r t e s t p a t h ;t i m e -v a r y i n g ;c u r f e w s ;a l g o r i t h m—17—第1期魏 航:一种求解时变条件下有宵禁限制最短路的算法。
