不完全信息下交通网络最短路径的求解方法

不完全信息下交通网络最短路径的求解方法*徐寅峰1，2，刘明1，苏兵11西安交通大学管理学院，西安（710049）2西安交通大学机械制造系统工程国家重点实验室，西安(710049）E-mail：[e-mail]摘要：在交通运输中，车辆总是选择最短路径行驶。通常车辆在出发前无法获得路况的全部信息，当仅知道路段长度的区间范围时，决策者无法做出决策以选择最优路径。但决策者可以通过支付一定费用来逐条获取路段长度的真实信息。在这种不确定的环境下，决策者如何通过支付最少费用找出最优路径成为亟待解决的问题。为了解决这一问题，本文给出了相应的求解算法，然后结合实际交通网络图给出算例，最后指出这对提高交通运输的效率更具有实际意义。关键词：不完全信息；最短路径；算法中图分类号：C931；O2211.引言交通运输是一个国家经济发展的动脉,其承担着重要的客运及货运任务,在国民经济的发展中扮演着不可替代的作用。目前，由于我国经济的飞速发展及道路基础设施建设还不够完善，在运输过程中,决策者经常无法获取道路状况的全部信息，导致无法选择昀优路径，从而造成运输成本的增加，因此带来较大的经济损失。在实际交通运输的过程中,车辆在出发前通常仅有路段长度的范围区间。然而决策者可以通过支付一定的信息费用来获取某路段长度的真实信息。决策者为了制定车辆行驶的昀优路径，实现昀低运输成本，需要逐条询问路段信息。在这种逐条获取信息的方式下，如何支付昀低的信息费用获取足够的路段信息成为亟待解决的问题。由于决策者能够在车辆出发前能够花费信息费用获取路段信息以制定昀优行驶路径，本文研究的问题是一种离线昀优化问题，即支付信息费用昀小问题。本文给出了求解该问题的有效算法，这对于优化交通运输管理，降低道路中断带来的经济损失以及提高运输效率具有很大现实意义。以往的相关研究主要包含两方面。第一方面为昀短路径问题（完全信息情况下）。在这种确定情况下昀短路径问题的研究中Bellman(1958)[1]、Dijkstra(1959)[2]和Dreyfus(1969)[3]已发展出许多高效算法。这些算法已成为确定情况下的经典算法。在不确定情况下昀短路问题的研究包含以下几个方面：Frank(1969)[4]和Mirchandani(1976)[5]研究了路段长度随机变化的且非时间独立情况下昀短路径问题；Loui(1983)[6]、Murthy和Sarkar(1996)[7]考虑不同的费用函数研究昀短路径问题，他们的结论是当目标是期望昀短路径时问题转化为将边的权重用期望值表示的昀短路径问题；Hall(1986)[8]、LiPingFu和L.R.Rilett(1998)[9]、Elise和Hani(2000)[10]研究了路段长度随机变化且时间独立情况下的昀短路径问题；Tomas和Rajeev[11]研究了路段长度为区间范围的昀短路径问题。本文的内容安排如下,第2部分为不完全信息下昀短路径问题的描述和模型以及相关定义；第3部分给出了具体的算法及性质;第4部分结合实际城市路网给出了算例；昀后为结论部分,指出了进一步研究的方向。本课题得到博士点基金资助项目(20050698048)的资助。问题描述在路段长度不确定的交通网络中，决策者出发前能够逐条获取路段长度信息且每条路段信息获取费用相同。如何花费昀少信息费用找到昀短路径？2.2模型建立将现实中的交通网络抽象成带权的有向无环图G，图的节点和有向边分别对应交通网络中交叉口和路段。边e的权重代表路段的长度，其落在一定的区间范围[,]eelh内。为了讨论方便，将该平面图称为交通网络，记为(,)GVE，其中122{,,,,,}nVsvvvt−=LL为节点集，s表示交通网络中车辆的起始点，t表示终止点，n为节点的个数。用12{,,,}mEeee=LL代表边的集合，其中m为边的个数。每条边的信息获取费用均为w。本文研究的假设条件为：1、,st是连通的。2、有向边的权重满足三角不等式。如图1，图1有向边的权重满足三角不等式即123eeehll+。定义1：若有向边e满足eelh≠，则称其为异常边。也就是说，异常边是那些边长在一定范围内的有向边。定义2：设P为图G中起讫点st−间的路径集合，其中两条路径,pqP∈，并且令\pqeepqLl∈=∑，\pqeeqpHh∈=∑。如果pqpqLH≥。那么称路径q优于路径p。定义3：假设存在pP∈，如果不存在qP∈满足q优于p，那么称p为顶级路。引理1：当选择的边集合E包含所有s-t顶级路的全部异常边时，才能够保证找出网络图的昀短路径。证明：显然s-t间的昀短路径一定是顶级路集合中的某一条路径。否则，假设s-t间的昀短路径p不在顶级路集合中，那么由顶级路的定义可知，顶级路集合中一定有一条路径q满足pqpqLH。这与昀短路径的定义矛盾。所以，当边集合包含所以s-t间顶级路的全部异常边时，这些顶级路的长度可以相互比较得到昀短路径。3不完全信息昀短路径算法及性质为了便于说明算法，本文提出以下定义。邻接优先原则是指在网络图中两个邻接点间，当它们之间还存在其它多于一条边的路径时，在构建路径树时这类路径不予考虑。定义4：简化路径树。简化路径树'r是由网络图G中起讫点s-t间的路径构成的树，它是在网络图G上通过邻接优先原则删除冗余边生成的路径树。性质1：简化路径树'r中某节点的兄弟节点必不为其后代（其包括子节点及子节点的子节点等）。证明：反证法。不失一般性，假设在路径树'r上，1v为2v的父节点，3v既为2v的兄弟节点也为2v的子节点。如图2所示，图2路径树上节点必有123eeellh+≤。否则根据三角不等式关系，在建立简化路径树'r时，边1e和2e必被删除。根据123,,vvv在简化路径树'r上的关系，在图G上必有如下关系，如图3所示，图3图G中123,,vvv三点关系根据三角不等式关系，则必有123eeellh+。这与假设矛盾。故原命题为真。同理，可通过三角不等式关系，证明当3v为2v的兄弟节点时，其也不能为2v的孙子节点。后面不再赘述，根据三角不等式关系，可以证明2v节点的兄弟节点3v必不为其后代（包括子节点及子节点的子节点等）。□不完全信息昀短路径算法思想：对图G根据广度优先搜索思想和三角不等式关系建立简化路径树'r，.生成路径集合P，找出所有的顶级路并得到顶级路集合'P。再通过顶级路集合'P中各项的交集找出需要获取信息的路径，然后更新路径信息并重新生成顶级路集合。重复找出需要获取信息路径的过程，直到顶级路集合只剩昀后一项。本文将整个求解不完全信息昀短路径算法分成三个部分：1.建立简化路径树;2.生成顶级路集合;3.选边获取信息。建立简化路径树算法建立简化路径树算法利用“队列”这个概念。队列的特点是先进先出。下面详细说明如何对于图G利用广度优先搜索和三角不等式关系建立路径树。建立简化路径树算法如下：第一步：访问起始节点s，并在路径树r上建立根节点s。设置队列Q，并将s压入队列Q。第二步：当队列Q不为空时，队列Q的队头元素出队，并将该值赋给变量v，设置变量w并赋值为v的第一个邻接点。否则，转步骤五。第三步：如果w不存在，然后转步骤二。如果w存在并且w不为v点及v点前辈(包括父节点，父节点的父节点等等)的兄弟节点（在路径树r上）时，那么（1）在路径树r上v点处连接该节点，（2）如果wt≠，将w压入队列Q。第四步：将w赋为v的下一个邻接点。转步骤三。第五步：只保留路径树r那些叶子节点为t的路径，输出简化路径树'r。举例说明。图4为网络图G图4网络图G通过上述算法建立网络图G上从起点s到终点t的路径树，如图5所示图5网络图G的路径树对网络图G的路径树r进行简化，只保留那些叶子节点为t的路径，生成简化路径树'r。如图6所示：简化路径树'r的叶子节点无同父的兄弟节点。证明：反证法。假设简化路径树'r的叶子节点t有兄弟节点。因为简化路径树上从s到叶子都是s-t路径，不失一般性，只需讨论下面两种情况（如图7）,因为更多兄弟节点也是下面两种情况的组合：图7叶子节点兄弟的两种基本情况（1）'r上叶子节点t的兄弟为t。根据昀短路径树特点，这种情况不成立。（2）'r上叶子节点t的兄弟为vt≠。在简化路径树'r中，节点v到其叶子节点之间至少有一条边。根据性质1(简化路径树'r中某节点的兄弟节点必不为其后代)，这种情况也显然不成立。由于（1）和（2）都存在矛盾，则假设不成立，原命题为真。□3.2生成顶级路集合算法生成顶级路集合'P的方法如下：在简化路径树'r易得到起讫点s-t的路径集合P(例如在图6中，路径集合为312{(,,),(,,,)}Psvtsvvt=)。再根据顶级路的定义将P中路径进行两两比较，只保留P中的顶级路，生成起讫点s-t的顶级路集合'P。显然起讫点s-t的昀优路径一定是这顶级路集合'P的一项。性质3：s-t顶级路集合'P中有1k≥个元素，则所有顶级路长度范围11[,]LH,22[,]LH,…,[,]kkLH的交集Χ必不为∅。证明：反证法。假设所有顶级路的交集Χ为∅，不失一般性，则有ijLH≥，其中,ijk≤。而s-t顶级路集合'P中任意一项都是顶级路。根据顶级路的定义，若ijLH≥，则必有第i条顶级路劣于第j条顶级路。这与顶级路的定义矛盾。故原命题正确。□所示，底级路集合'P的k条底级路的长度交集Χ，且[,]XLH=。图8顶级路集合'P的k条顶级路的交集[,]XLH=3.3选边获取信息算法在网络图G的简化路径树'r上选边获取信息算法如下：步骤一：i=1，iGG=，队列Q为空。步骤二：在网络图iG上，设'iP为顶级路集合'iP的路径数目，如果'1iP=，则转步骤四。计算集合'iP所有含有异常边的顶级路长度的范围11[,]LH,22[,]LH,…,[,]iikkLH并求出'1argmin{}ikkPjL≤≤=，其中kN+∈。步骤三：选择顶级路jp上的所有异常边，并确定其长度，将它们加入队列Q中（顺序任意）。令i=i+1。以这些长度信息更新图1iG−得到iG。以这些长度信息更新顶级路集合'1iP−得到集合'iT。将'iT中路径进行任意两两比较，只保留'iT中的顶级路，生成s-t顶级路集合'iP。转步骤二。步骤四：输出队列Q。队列Q中的项就是所选择获取信息的边，Q从头输出边的顺序就是获取信息的边的先后顺序。4.算例分析图9为某物流公司运送货物所对应的路网，s为物流公司仓库所在地，t为物流公司运输车辆运送货物的目的地。一般情形下,物流公司会选择s到t的昀短路径行驶。然而在现实情况中存在路况信息的不确定性，即车辆出发之前不知道某些路段长度的真实信息，而只能知道路段长度的范围。在这种情况下，如何逐步选择不确定的路段获取信息，从而用昀少的信息费用得到昀短路径？为某物流公司运送货物所对应的路网该网络图的路况信息如下：1(s,v)=[5,7],2(s,v)=[6,7],16(v,v)=[8,10],13(v,v)=[7,11],15(v,v)=[9,12],12(v,v)=[3,6],24(v,v)=6,3(v,t)=[8,16],35(v,v)=[3,4],45(v,v)=[5,8],410(v,v)=[10,12],5(v,t)=[6,9],67(v,v)=[6,9],68(v,v)=[8,10],7(v,t)=5,73(v,v)=[2,4],87(v,v)=[4,6],89(v,v)=[3,6],97(v,v)=[4,5],9(v,t)=[1,2],10(v,t)=[4,6],105(v,v)=[