年12月交通运输工程学报.pdf

《年12月交通运输工程学报.pdf》由会员分享，可在线阅读，更多相关《年12月交通运输工程学报.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8卷 第6期2008年12月交 通 运 输 工 程 学 报Journal of Traffic and Transportation EngineeringVol18No16Dec.2008收稿日期:2008209209基金项目:国家自然科学基金项目(70525004,70121001,60736027);中国博士后科学基金项目(20060401003);陕西省教育厅基金项目(06J K099)作者简介:苏 兵(19702),女,山西大同人,西安交通大学博士后,从事运输管理研究。导师简介:徐寅峰(19622),男,吉林东丰人,西安交通大学教授。文章编号:167121637(2008)0620

2、110206方格路网车辆路径在线选择模型及竞争分析苏 兵1,2,徐寅峰1,3,余 水4(11 西安交通大学 管理学院,陕西 西安 710049;21 西安工业大学 经济与管理学院,陕西 西安 710021;31 西安交通大学 机械制造系统工程国家重点实验室,陕西 西安 710049;41 迪肯大学信息技术与工程学院,维多利亚州 墨尔本 3125)摘 要:为分析城市方格路网遭遇突发性堵塞下的车辆路径选择问题,应用在线问题与竞争策略的方法建模,设计了2种在线路径选择竞争策略,即方向贪婪策略和多选择移动策略,计算了2种策略的竞争性能比。通过策略竞争分析得出:在发生突发性堵塞的情形下,方向贪婪策略下的

3、费用为最优费用的3倍;利用多选择移动策略在对网络具有实际意义约束条件下的部分情形能够得到最优费用,且在最坏情形下的费用为最优费用的2倍;2种策略的竞争性能比优于以往研究给出的堵塞不可恢复问题竞争比的下界。关键词:交通运输;方格路网;车辆路径;在线问题;竞争分析中图分类号:U492 文献标识码:AOnline selection model and competitive analysis ofvehicle routing in grid transportation networkSU Bing1,2,XU Yin2feng1,3,YU Shui4(1.School of Managemen

4、t,Xian Jiaotong University,Xian 710049,Shaanxi,China;2.School of Economics andManagement,Xian Technological University,Xian 710021,Shaanxi,China;3.State Key Laboratory forManufacturing Systems Engineering,Xian Jiaotong University,Xian 710049,Shaanxi,China;4.School ofEngineering and Information Techn

5、ology,Deakin University,Melbourne 3125,Victoria,Australia)Abstract:In order to analyze the vehicle routing problem under sudden road blockage in gridtransportation network,a vehicle routing model was proposed by using the methods of onlineproblem and competitive strategy,direction greedy strategy an

6、d multi2alternative moving strategywere designed,and the competitive ratios of two strategies were computed.Analysis resultindicates that the cost of direction greedy strategy is 3 times than the optimal cost under suddenroad blockage state,multi2alternative moving strategy has a good performance wi

7、th practicalrestriction for different cases,the cost of multi2alternative moving strategy is 2 times than theoptimal cost in the worst case,the competitive ratios of two strategies are not more than the infimumof the competitive ratio for unexpected blockage problem in general networks.3 figs,17 ref

8、s.Key words:traffic transportation;grid transportation network;vehicle routing;online problem;competitive analysisAuthor resumes:SU Bing(19702),female,PhD,+86229282665034,subing684 ;XUYin2feng(19622),male,professor,+86229282665034,yfxu .0 引 言随着汽车经济的发展,城市交通运输拥堵现象日益突出,因此,如何制定最优的突发性堵塞在线路径选择策略,有效降低运输费用成

9、为决策者备为关注的热点问题。对于一个完整的运输过程而言,运输车辆在行进过程中如果遇到一系列无法预知的突发性堵塞,决策者需要针对每一个当前堵塞做出路径选择,从而需要在整个运输过程中做出一系列决策。对于这类动态特征较强的路径选择问题,传统的优化方法是将其转化为静态问题,采用各种启发式方法,包括遗传算法1、禁忌搜索算法2、模拟退火算法3、空间填充曲线法4、节约算法5及混合算法6等进行求解。这样求解的路径选择方案一旦条件发生变化,如遭遇突发性堵塞,所求出的结果就会失去最优性,甚至是无意义的,因此,必须寻求一种新的方法对这类问题进行研究。本文从在线问题与竞争策略的新角度,讨论了城市方格路网突发性堵塞路径

10、选择问题,并设计了两种在线路径选择竞争策略,对具有限制条件网络的堵塞路径选择策略的制定进行探索,并结合实际中城市方格路网的结构特征对策略的执行效果进行分析,从而为运输决策者提供更贴近实际的路径选择决策依据。1 文献综述在线问题与竞争策略是近年来国际上关注的一种新方法,为解决受不确定因素影响较大的系列决策问题提供了一种新思路,尤其适用于决策者对未来的因素变化难于预测甚至一无所知的决策问题,其在变化因素的每一个特例中都能给出一个策略,使用这一策略得到的解离最优解总在一定的比例(比值)之内728。这种方法不强调决策过程对风险发生的经验分析,更注重风险应对策略的制定,从而能够做到快速应对突发事件,同时

11、注重策略竞争性能的分析和改进,以提高策略的执行效果。近年来,在计算机理论科学与管理科学等领域,在线问题与竞争策略的研究均取得了较好的理论和实际成果,如经典的k2服务器猜想7、雪橇租赁问题9,以及目前的研究热点在线金融10与在线订单处理11问题等。运输过程中遭遇突发性堵塞情形下的路径选择问题(加拿大旅行者问题)由PAPADIMITRIOU等在1989年提出,证明了在被堵塞路段数量不确定的情形下该问题是PSPACE2complete问题,不存在常数竞争比12。2003年,文献13 提出了在线问题函数竞争比的定义,讨论了堵塞不可恢复的路径选择问题的两种竞争策略:贪婪策略和复位 策略,策 略 相应 的

12、 竞 争性 能 比 为2k+1和2k+1-1,并证明了对于不可恢复的路径选择问题,不存在竞争性能比小于2k+1的策略,同时给出了贪婪策略优于复位策略的条件。文献14216对可恢复堵塞路径选择问题进行了研究,给出了一般网络上的几种路径选择策略,并分析了策略的竞争性能。文献13216的研究工作是针对一般网络进行的,给出的策略具有一般性,因此,有些策略的竞争性能较差。即便是堵塞不可恢复问题竞争比的下界2k+1,如果堵塞只出现1次,其竞争比为3,即该策略下的费用至少是最优费用的3倍,策略的执行效果仍然不是很好。2 模型和离线最优费用下界城市路网的布局通常为方格网式、环形放射式、自由式和混合式4种基本类

13、型。方格式路网是最常见的一种形式,通常是沿南北和东西方向按一定间距平行、均等地排列城市干路和支路,将城市用地划分成大小合适的矩形街坊,见图1。图1 城市方格路网Fig.1City grid transportation networks2.1 基本定义和模型为讨论方便,将城市方格路网抽象成一个有m+1行、n+1列节点的平面无向方格网络G,G中边的集合为E=e(vi,j,vi,j+1)e(vi,j,vi+1,j)i=0,1,m;j=0,1,nG中每条边的通过时间为1。运输车辆需从一个节点出发抵达另一个节点,其在行进过程中可能遇到一系列的突发性堵塞,堵塞造成路段(边)中断且不可开通。研究问题是决策

14、者应如何制定在线路径选111第6期 苏 兵,等:方格路网车辆路径在线选择模型及竞争分析择策略,不同策略具有怎样的执行效果。为了使讨论更具有实际意义,所有的讨论均基于以下假设。(1)网络上发生堵塞的次数不超过k次,在运输过程中遇到的堵塞序列为R=(e1,e2,el,ek)(2)堵塞均发生在路段上而不发生在节点上。(3)路段e(vi,j,vi,j+1)和e(vi,j,vi+1,j)不同时出现在堵塞序列里;路段e(vi,j,vi,j+1)和e(vi+1,j,vi+1,j+1)不同时出现在堵塞序列里;路段e(vi,j,vi+1,j)和e(vi,j+1,vi+1,j+1)不同时出 现在 堵 塞序列里。(

15、4)出发节点和目的节点的关联路段均不发生堵塞。用Copt(R)表示在线问题对应的离线问题从起始节点到目标节点的最优费用,即决策者预先知道堵塞路段的全部信息情形下问题的最短路径的费用(最优费用);CA(R)表示无法预知堵塞发生时间和位置情形下在线策略A下从出发地到目的地的路径总费用。如果存在一个与堵塞发生序列无关的常数,使得如下关系式成立CA(R)Copt(R)则称为策略A的竞争性能比,即在线问题采用策略A的费用在与之对应的离线问题最优费用的倍之内。竞争性能比是对在线问题策略效用的衡量,对于同一在线问题,采用策略不同,策略相应的竞争性能比也不同,如果竞争性能比较大,说明所采用策略的费用同与之对应

16、的离线问题的最优费用的偏离可能较大。对于同一假设的成本费用问题来讲,越接近于1,策略的竞争性能越好。2.2 离线最优费用下界(1)起始节点和目标节点在同一条直线上令起始节点为v0,0,目标节点为v0,n。如果网络上没有堵塞发生,运输车辆的最优路径为P=(v0,0,v0,1,v0,j,v0,n)最优费用为n。当G中有堵塞出现时,运输车辆的最短路径应为G中去掉堵塞边后从v0,0到v0,n的最短路径。当堵塞边的位置均出现在P上或P的同一侧时,在G中去掉堵塞边,求得运输车辆的最优行驶路径P,即运输车辆从v0,0到v0,n的最优费用为n+2。当堵塞出现在P上及P两侧时,运输车辆从v0,0到v0,n的最优

17、费用大于等于n+2,因此,当起始节点和目标节点在同一条直线上时,n+2为离线最优费用的下界。(2)起始节点和目标节点不在同一条直线上令起始节点为v0,0,目标节点为vm,n(0 mn)。如果网络上无堵塞发生,运输车辆从出发节点v0,0到目的节点vm,n拥有多条最短路径,最短路径的通过时间为m+n。如果网络上有堵塞出现,运输车辆的最优费用大于等于m+n,因此,m+n为起始节点和目标节点不在同一条直线情形下离线最优费用的下界。3 方向贪婪策略及其竞争分析根据城市方格路网的结构特征,首先给出一种方向贪婪策略,这种策略在实际中经常被决策者使用,这里给出方向贪婪策略定义及其规则,并对策略的竞争性能进行分

18、析。3.1 方向贪婪策略方向贪婪策略指运输车辆尽可能地沿着一个方向移动,遇到堵塞不能按照原方向移动时改变方向并尽可能地沿着新方向移动直到抵达目的地。具体规则定义如下。令出发节点为v0,0,目标节点为vm,n,假设mn。第1步:从v0,0开始任选一个方向移动,检查每一个经过的节点vi,j,如果关联边e(vi,j,vi,j+1)不发生堵塞,运输车辆以vi,jvi,j+1的方式移动;如果vi,j的关联边e(vi,j,vi,j+1)发生堵塞,运输车辆以vi,jvi+1,j的方式移动。当vi,j中的i=m但jn时,如果vm,j的关联边e(vm,j,vm,j+1)不发生堵塞,运输车辆以vm,jvm,j+1

19、的方式移动;如果vi,j的关联边e(vm,j,vm,j+1)发生堵塞,运输车辆以vm,jvm-1,j的方式移动。当vi,j中的j=n但im时,如果关联边e(vi,n,vi+1,n)不发生堵塞,运输车辆以vi,nvi+1,n的方式移动;如果vi,j的关联边e(vi,n,vi+1,n)发生堵塞,运输车辆以vi,nvi,n-1的方式移动。第2步:重复第1步,直到i=m,j=n时终止。策略的可达性指在满足上节对问题所做的假设条件下,当vi,j中im且jn时,无论车辆遇到堵塞或不遇到堵塞的情形下,运输车辆按照方向贪婪策略每移动1次,到目标节点的距离减少1。当vi,j中的i=m但jn时或vi,j中的j=n

20、但im时,会出现vi,j与vm,n位于同一条直线的情形,如果在vm,j的关联边e(vm,j,vm,j+1)发生堵塞,车辆会以vm,jvm-1,j的方式移动1次,到目标节点的距离增加1,根据假设条件(3),e(vm-1,j,vm-1,j+1)不发生211交 通 运 输 工 程 学 报 2008年堵塞,车辆可以到达vm-1,j+1,到目标节点的距离增加1,而vm-1,j+1满足im且jN(i+1,j),则vi,j+1到vm,n的最短路径数量大于vi+1,j到vm,n的最短路径数量,具体证明见文献17。根据这个性质,可以设计一种在突发性堵塞发生情形下,让在线决策者拥有更多的路径选择方案,从而有效地对

21、抗堵塞,在此给出一种多选择移动策略并分析这种策略的执行效果。4.1 多选择移动策略多选择移动策略指运输车辆尽可能多地经过具有m-i=n-j的节点vi,j直至到达目的地。具体规则定义如下。令出发节点为v0,0,目标节点为vm,n,假设mn。第1步:从v0,0开始依次检查每一个经过的节点vi,j,如果m-in-j且vi,j的关联边e(vi,j,vi+1,j)不发生堵塞,运输车辆以vi,jvi+1,j的方式移动;如果vi,j的关联边e(vi,j,vi+1,j)发生堵塞,运输车辆以vi,jvi,j+1的方式移动。如果m-i=n-j,运输车辆以vi,jvi+1,j或vi,jvi,j+1的方式移动。第2步

22、:重复第1步,直到i=m,j=n时终止。在满足对问题所有假设的条件下,运输车辆按照多选择移动策略可以从出发节点到达目标节点,具体分析与方向贪婪策略相近。4.2 策略的竞争性能分析定理2:在一个平面方格网络上,当运输车辆能311第6期 苏 兵,等:方格路网车辆路径在线选择模型及竞争分析够到达vi,j且m-i=n-j时,多选择移动策略的竞争比为1;当运输车辆不能到达vi,j且m-i=n-j时,多选择移动策略的竞争比为2。证明:分以下2种情形进行讨论。(1)起始节点和目标节点在同一条直线上。运输车辆从v0,0欲抵达v0,n,则只有v0,n-1是满足vi,j且m-i=n-j的节点,则策略的竞争性能比与

23、定理1在情形(1)下对方向贪婪策略竞争性能比的证明类似,这里不再赘述。(2)起始节点和目标节点不在同一条直线上。在多选择移动策略下,运输车辆的行驶路径可能出现2种情形。一种情形为车辆能够到达点vi,j且m-i=n-j,在这种情形下,运输车辆从v0,0到vm,n的总费用为m+n,其为问题的最优解。具体如下:假设车辆到达了vm-1,n-1,根据假设(4),出发节点和目的节点的关联路段均不发生堵塞,车辆一定能够到达vm,n;如 果 车 辆 到 达 了vm-2,n-2且e(vm-2,n-2,vm-1,n-2)发生了堵塞,车辆可向vm-2,n-1移动,根据假设(3),e(vm-2,n-1,vm-1,n-

24、1)不发生堵塞,所以车辆可以到达vm-1,n-1,如前所述,车辆可以到达vm,n;依此类推,如果车辆能够到达vi,j且m-i=n-j,运输车辆从v0,0到vm,n的总费用为m+n,并形成图3(a)中PM的行走路径,因此,在多选择移动策略下,如果车辆能够到达vi,j且m-i=n-j,策略下的费用与最优费用的比值为1,即策略的竞争性能比为1。图3 多选择移动策略竞争分析Fig.3Competitive analysis for multi2alternative moving strategy另一种情形为,如果运输车辆在通过出发点v0,0的关联边后,就开始遇到堵塞边,而且堵塞边出现的次数频繁,运输

25、车辆每走过一条边就遇到1次堵塞,运输车辆会形成图3(b)中PM的行走路径。在这种情形下,运输车辆不能到达vi,j且m-i=n-j,而是到达vm,j且jn或vi,n且im,即会出现出发节点和目的节点位于同一条直线的情形。以车辆到达vm,j为例,在最坏情形下,从v0,0抵达vm,j的过程中,运输车辆遇到的堵塞次数为m次,即vm,j中的j=m;在从vm,j抵达vm,n的过程中,运输车辆在多选择移动策略下的费用比无堵塞出现时所需费用增加了n-m,使得运输车辆从v0,0到vm,n的总费用为2n,因此,当运输车辆不能到达vi,j且m-i=n-j时,多选择移动策略下的费用与最优费用的比值为2nm+n,当mn

26、时,2nm+n的值趋近于1,当m的值较小时,2nm+n的值接近于2,即多选择移动策略的竞争性能比为2,证毕。通过对道路系列突发性堵塞2种应对策略的执行效果分析可知,多选择移动策略的执行效果优于方向贪婪策略。因为多选择移动策略的目的在于使运输车辆尽可能到达vi,j且m-i=n-j,从而达到问题的最优解,并尽可能避免出现出发节点和目的节点位于同一条直线的情形,从而具有更多可供选择的路径策略;而方向贪婪策略易于出现出发节点和目的节点位于同一条直线的情形,较难实现最优解。5 结 语在线问题与竞争策略的方法为道路系列突发性堵塞的路径选择问题提供了一种新的研究思路。以往的相关研究中的竞争策略是基于一般网络

27、给出的,缺乏与实际城市路网的结合,策略的执行效果较差。本文以城市路网的典型结构 方格网络为基础,从在线问题与竞争策略的角度对具有限制条件网络的突发性堵塞路径选择策略进行了研究,设计了2种在线路径选择策略:方向贪婪策略和多选择移动策略,并对策略的竞争性能进行了分析。研究结果表明,方向贪婪策略的竞争性能比为3,多选择移动策略的竞争性能优于方向贪婪策略的竞争性能,在一些情形下,该策略的竞争性能比为1,即能够达到问题的最优解;在最坏情形下,该策略的竞争性能比为2,因此,多选择移动策略的执行效果优于方向贪婪策略。实际中的城市方格路网(非标准方格)与本文的假设有差异,但其特征与方格网络近似,对竞争比分析的

28、影响不大,因此,本文的研究结果有较强的适用性。如何对方格网络的假设进行修正使其更加接近现实,从而制定更为有效的竞争策略,是本文进一步努力的方向。参 考 文 献:References:1 贺竹磬,孙林岩.动态交通下车辆路径选择模型及算法J .411交 通 运 输 工 程 学 报 2008年交通运输工程学报,2007,7(1):1112115.HE Zhu2qing,SUN Lin2yan.Model and algorithm of vehiclerouting problem under dynamic trafficJ.Journal of Trafficand Transportation

29、 Engineering,2007,7(1):1112115.(inChinese)2 THANGIAH S R,OSMAM I H,SUN T.Hybrid geneticalgorithm simulated annealing and tabu search met hods forvehicle routing problem with time windows R.SlipperyRock:Slippery Rock University,1994.3 张 波,叶家玮,胡郁葱.模拟退火算法在路径优化问题中的应用J.中国公路学报,2004,17(1):79281.ZHANGBo,YE

30、Jia2wei,HU Yu2cong.Application of opti2mizing the path by simulated annealingJ.China Journal ofHighway and Transport,2004,17(1):79281.(in Chinese)4 胡大伟,胡 勇,朱志强.基于空间填充曲线和动态规划解的定位路线问题J.长安大学学报:自然科学版,2006,26(3):80283.HU Da2wei,HU Yong,ZHU Zhi2qiang.Solving locationrouting problem based on space filling

31、curve and dynamic pro2gramming J.Journal ofChangan University:NaturalScience Edition,2006,26(3):80283.(in Chinese)5 李 兵,郑四发,曹剑东,等.求解客户需求动态变化的车辆路径规划方法J.交通运输工程学报,2007,7(1):1062110.LI Bing,ZHENG Si2fa,CAO Jian2dong,et al.Method ofsolving vehicle routing problem with customersdynamicrequests J.Journalof

32、TrafficandTransportationEngineering,2007,7(1):1062110.(in Chinese)6 杨瑞臣,周永付,云庆夏.寻找车辆最优路径的混合算法J.交通运输工程学报,2005,5(1):1022105.YANG Rui2chen,ZHOU Yong2fu,YUN Qing2xia.Hybridalgorithm for vehicles optimal routeJ.Journal of Trafficand Transportation Engineering,2005,5(1):1022105.(inChinese)7 MANASSE M S,MC

33、GEOCH L A,SLEATOR D D.Com2petitive algorithms for server problemsJ.Journal of Algo2rithms,1990,11:2082230.8 DAVID S B,BORODIN A.A new measure for the study ofthe on2line algorithmJ.Algorithmica,1994,11:73291.9 EI YANIV R,KNAIEL R,LINEAL N.Competitive optimalon2line leasingJ.Algorithmica,1999,25:1162

34、140.10EI YANIV R,FIAT A,KARP R M,et al.Optimal searchand one2way trading online algorithm J.Algorithmica,2001,30:1012139.11KESKINOCAK P,RAVI R,TAYUR S.Scheduling and re2liable lead2time quotation for orders with availability intervalsand lead2time sensitive revenues J.Management Science,2001,47(2):2

35、642279.12PAPADIMITRIOU C H,YANNAKAKIS M.Shortest pathswithout a map J.Lecture Notes in Computer Science,1989,372:6102620.13XU Yin2feng,HU Mao2lin,SU Bing,et al.The Canadiantraveller problem and its competitive analysisJ.Journal ofCombinatorial Optimization,2008,15(3):223222714SU Bing,XU Yin2feng,ZHU

36、 Zhi2jun.Online recoverableCanadian traveler problem on a roadJ.Information,2004,7(4):4772486.15 苏 兵,徐寅峰.连续网络上的占线可恢复加拿大旅行者问题J.系统工程,2004,22(8):10213.SU Bing,XU Yin2feng.Online recoverable Canadian travelerproblem on a continuous networkJ.Systems Engineering,2004,22(8):10213.(in Chinese)16 苏 兵,徐寅峰.堵塞恢

37、复时间随机的在线加拿大旅行者问题J.系统工程理论与实践,2005,25(10):1082113.SU Bing,XU Yin2feng.Online Canadian traveler problemwith stochastic blockages recovery time J.Systems Engi2neering2theory and Practice,2005,25(10):1082113.(inChinese)17 苏 兵,徐寅峰.居住和单位小区对方格网络交通便捷度的影响分析J.系统工程,2006,24(12):33239.SU Bing,XU Yin2feng.Influence analysis of square block fortransportation convenience capability on grid networkJ.SystemEngineering,2006,24(12):33239.(in Chinese)511第6期 苏 兵,等:方格路网车辆路径在线选择模型及竞争分析