堵塞点可恢复型在线运输车辆的调度策略研究①.pdf-淘文阁

资源描述

《堵塞点可恢复型在线运输车辆的调度策略研究①.pdf》由会员分享，可在线阅读，更多相关《堵塞点可恢复型在线运输车辆的调度策略研究①.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、堵塞点可恢复型在线运输车辆的调度策略研究胡茂林1,2,徐寅峰2,徐维军3(1.宁夏师范学院数学系,宁夏固原756000;2.西安交通大学管理学院,陕西西安710049;3.华南理工大学工商管理学院,广东广州510641)摘要:针对现实物流配送中所遇到的无法预测的突发性线路堵塞问题,以在线车辆行驶的时间最短为优化目标,用竞争分析的方法研究了堵塞点可恢复型在线车辆的调度策略.充分地考虑到堵塞点的动态特征,分别介绍了在线运输车辆调度的贪婪策略、复位策略和等待策略等方案,并系统分析了这三种基本策略在竞争性能上的利弊,给出了选择策略及其算法模型.通过对选择策略的竞争比和竞争性能的分析,结果表明选择

2、策略实现了对在线运输车辆的优化调度.关键词:在线问题;贪婪策略;复位策略;等待策略;选择策略;竞争比;竞争性能中图分类号:TB114.1 文献标识码:A 文章编号:1000-5781(2006)05-0484-06Study on the scheduling strategies for online vehiclewith the recoverable congested verticesHU Mao2lin1,2,XU Yin2feng2,XU Wei2jun3(1.Department of Mathematics,Ningxia Normal University,Guyuan 7

3、56000,China;2.School of Management,Xianjiaotong University,Xian 710049,China;3.School of Management,South China University of Technology,Guangzhou 510641,China)Abstract:Concerning about the problemof the unforeseen congested vertices in the actual transportation ofmaterials,the paper,using a method

4、of competitive analysis,studies the scheduling strategies for onlinevehicle with the recoverable congested vertices to realize the aimof a less2minimum2time for the online ve2hicle traveling.T aking into account the dynamic matters of the congested vertices,we introduce the threestrategiesof the gre

5、edy strategy,reposition strategy and waiting strategy respectivly,systematically introducethe advantages and disadvantages of the three strategies on their competitive performances,and then givethe selection strategy and its algorithmic model.Through analyzing the competitive ratio and competitivepe

6、rformance of the selection strategy,the results clearly show that the selection strategy realcges the opti2mization scheduling of online vehicle well.Key words:online problem;greedy strategy;reposition strategy;waiting strategy;selection strategy;competitive ratio;competitive performance0 引言随着经济的发展

7、,人口的不断增加,车辆越来越多,现有运输网络的负荷量愈来愈大;现代工业的飞速发展,使自然环境日益恶化,洪水,泥石流和山体滑坡等自然灾害已屡见不鲜.运输网络的第21卷第5期2006年10月系统工程学报JOURNAL OF SYSTEMS ENGINEERINGVol.21 No.5Oct.2006收稿日期:2005-04-12;修订日期:2005-11-07.基金项目:国家自然科学基金重点项目(19731001;70471035);宁夏高等学校科学研究项目(2004070).超负荷运行和频繁的自然灾害常常会引起交通事故,道路塌方等突发性交通堵塞现象.因此,对于突发性交通堵塞问题,研究如

8、何科学地调度运输车辆,最大限度地降低运输成本,缩短运输时间,具有一定的理论意义和现实意义.关于突发性交通堵塞问题,朱志军等1具体地考虑了一个物流公司在一个已知的交通网络图上用货车把货物从初始点O(origin)运送到目的点D(destination)所花的费用问题.他们以运输车辆花费的费用最少为优化目标,用竞争分析28的方法研究了堵塞点不可恢复型的在线车辆的调度策略,分别给出了贪婪策略和复位策略竞争算法.本文在文献1所述问题和策略的基础上以在线车辆行驶的时间最短为优化目标,同样用竞争分析的方法考虑堵塞点可恢复型的在线车辆的调度策略.1 数学模型本文所有讨论都在一个已知连通的赋权无向平面有限图G

9、=(V,E)上进行,其中V=v1,v2,vn为图G的所有顶点的集合,E=e1,e2,em为图的所有边的集合.为了讨论方便,还给出如下的一些基本记号,假设和概念.1)对于任一条边el=vivjE,它的权重T(vivj)表示运输车辆沿着路径vivj从vi行驶到vj所用的时间,并且权重满足对称性T(vivj)=T(vjvi).2)当要考虑一项从顶点vi到vj的运输任务时,把vi记为O,把vj记为D.3)假定运输车辆从初始点O出发到目的点D无论选择什么样的行驶路线,一路上都会遇到k(k 0)个堵塞点,堵塞点可能发生在图G的顶点上也可能发生在边上,并假定这k个堵塞点依次为序列(r1,r2,rk),简记为

10、Rk,它的前i项构成的子序列(r1,r2,ri)(0ik)记为Ri,R0表示车辆没有遇到堵塞点.4)如果当车辆行驶到图上的某点vp时遇到了第i(i1)个堵塞点ri,就另记vp为Oi;如果当车辆行驶到图的某条边eq上的某个位置时遇到了第i个堵塞点ri,就记边eq上的这个位置为Oi点.5)每个堵塞点的恢复时间记为t(ri),i=1,2,k,所有堵塞点恢复时间的总和为T(Rk)=ki=1t(ri),记作T(Rk)=(t(r1),t(r2),t(rk),称为堵塞恢复时间序列,堵塞点恢复后,在车辆完成运输任务之前不会再次被堵塞.6)在图G中去掉堵塞点所在的结点后得到的图G 仍是连通的.7)用Topt(O

11、D|Ri)(0ik)表示在事先已知r1,r2,ri点会发生堵塞的情况下,车辆不等待堵塞点恢复而是在图G 上选择最优路径绕道而行,最终把货物从初始点O运送到目的点D所花费的最短时间,当i=0时简记为Topt(OD).8)如果当运输车走到点Oi(1ik)后,发现前方的点ri发生堵塞然后不等待其恢复而是重新选择路径绕道而行,用Topt(OiD|Ri)表示在事先已知r1,r2,ri点会发生堵车的情况下在图G 上把货物从点Oi运送到目的点D所花费的最短时间.9)用CTALG(OD|Ri)(1ik)表示在算法ALG下运输车在行进的过程中会遇到r1,r2,ri发生堵塞的情况下最终将货物从O点运输到D点所花费

12、的运输时间.10)假定Topt(OD)+T(Rk)Topt(OD|Rk),因为若Topt(OD)+T(Rk)Topt(OD|Rk),则当运输车每次遇到堵塞点时只需等待其恢复后继续行驶,便可在最短时间内到达目的点D.由以上约定,下面的引理1是熟知的:引理1Topt(OD)Topt(OD|R1)Topt(OD|R2)Topt(OD|Rk)2基本策略分析贪婪策略不管将来的堵塞点序列如何,在现有的已知条件下求出此时的最短路径,然后调度车辆沿此路径行进1.引理2设算法A是基于贪婪策略的一种算法,则算法A对于堵塞点序列为Rk=(r1,r2,rk)的在线车辆选线问题的竞争比为2k+1-11.引理2表明,按

13、这一算法在最坏情况下1辆运584第5期胡茂林等:堵塞点可恢复型在线运输车辆的调度策略研究输车完成1个从初始点到目的点的运输任务花费的时间竟可能高达到此离线问题所花费的时间的2k+1-1倍,在此情况下,这一策略显然不可取.但是若在每次遇到堵塞点时所选择的最优路径的用时都“比较短”,则应用这一策略是十分经济的.当然在通常情况下,就所有堵塞点而言,所选择的最优路径中,既有用时“比较少”的路径(好路径),也有用时“比较多”的路径(坏路径).自然,沿着“好路径”行进是比较经济的,沿着“坏路径”行进用时是相当多的.这一策略正是所谓“弃之可惜,用之则风险太大”.因此,这一策略的竞争性能是积极的但是有风险的

14、.复位策略在车辆每次遇到堵塞点后,先回到起初点,然后重新选择在此情况下的最优路径.1引理3设算法B是基于复位策略的一种算法,则算法B对于堵塞点序列为Rk=(r1,r2,rk)的在线车辆选线问题的竞争比为2k+11.引理3表明,按照复位策略,1辆运输车完成1个从起初点到目的点的运输任务所花费的时间可以达到此离线问题所花费的时间的2k+1倍.把复位策略和贪婪策略相比较,复位策略避免了贪婪策略走“坏路径”的风险,但也错失了走“好路径”机会.可以说复位策略的竞争性能是“没有风险的但是保守的”.等待策略在车辆每次遇到堵塞点后,在原地等待直到堵塞点恢复后再沿原定路线继续前进.设算法C就是基于等待策略的

15、一种算法,则在线时间为CTC(OD|Rk)=Topt(OD)+T(Rk),而该问题的离线时间为Topt(OD|Rk).由于CTC(OD|Rk)Topt(OD|Rk)=Topt(OD)+T(Rk)Topt(OD|Rk),所以等待策略的竞争比不仅和堵塞点的个数k有关还与等待时间T(Rk)有关:当T(Rk)很小时,竞争比就会趋于1;而当T(Rk)很大时,竞争比就会很大.因此,等待策略的竞争比是随着T(Rk)的增大而不断增大的一个无上界的量,等待策略的竞争性能是经济性和风险性并存的.既然贪婪策略,复位策略,等待策略各有优劣,那么物流公司到底应按哪一种策略来调度运输车辆呢?为此,先看一个简单的例子:设在

16、图1中,车辆从初始点O到目的点D不论怎样行驶,从O出发以后都会在途中的节点Oi(1i18)处连续遇到3个堵塞点R3(r1,r2,r3)并且t(r1)=2,t(r2)=1,t(r3)=0.5,但事先并不知道会产生3个堵塞点,也不知道这3个堵塞点到底会发生在哪3个节点处,更不知道其恢复时间是多少.现考虑车辆如何选路行驶使所花的时间较少.图1竞争性能分析图1)若车辆按贪婪策略选路行驶,则在沿最优路径OO1O2O3D行驶到O1点处遇到堵塞点r1;在已知r1的前提下,可求得O1到D的最优路径O1O4O5D,于是车辆沿这条路径行驶,行驶到O4点处遇到堵塞点r2;在已知r1,r2的前提下,可求得O4到D的最

17、优路径O4O6D,于是车辆沿这条路径行驶,行驶到O6点处遇到堵塞点r3,在已知r1,r2,r3的前提下,可求得O6到D的最优路径O6O19D,于是车辆沿这条路径行驶直到目的点D.因此车辆的行驶路线为OO1O4O6O19D,容易算出,车辆沿这条路径行驶花费的时间为9.1个单位时间.2)若车辆按复位策略选路行驶,则在沿最优路径OO1O2O3D行驶到点O1处遇到堵塞点r1,就沿O1O返回;在已知r1的前提下,沿最优路径OO7O8O9D行驶到点O7处遇到堵塞点r2,就沿O7O返回;在已知r1,r2的前提下,沿最优路径OO13O14O15D行驶到点O13处遇到堵塞点r3,就沿O13O返回;在已知r1,r

18、2,r3的前提下,沿最优路径OO16O17O18D行驶直到目的点684系统工程学报第21卷D.因此车辆的行驶路线为OO1OO7OO13OO16O17O18D,容易算出,车辆沿这条路径行驶花费的时间为5.4个单位时间.3)若车辆按等待策略行驶,则在沿最优路径OO1O2O3D行驶到点O1处遇到堵塞点r1,在等待2个单位时间后,堵塞点r1恢复,继续沿着原路径行驶到点O2处遇到堵塞点r2,在等待1个单位时间后,堵塞点r2恢复,继续沿着原路径行驶到点O3处遇到堵塞点r3,在等待0.5个单位时间后,堵塞点r3恢复,继续沿着原路径行驶直到目的点D.容易算出,车辆这样走走停停到目的点所花费的时间为

19、4.4个单位时间.4)现在来考虑这样一种行驶方案:当车辆从O出发沿着最优路径T(OO1O2O3D)=0.9行驶到O1处遇到堵塞点r1;在已知r1的前提下,可分别求得O到D的最优路径的2倍2T(OO7O8O9D)=2与T(OO1O2O3D)=0.9的差为1.1,O1到D的最优路径T(O1O4O5D)=1.4及在O1处的等待时间t(r1)=2与r1恢复后继续要走的路径T(O1O2O3D)=0.3之和2.3,但这三者之中最小的是2T(OO7O8O9D)-T(OO1O2O3D)=1.1,于是决定从O1返回到O再沿OO7O8O9D行驶;当行驶到O7处遇到堵塞点r2,在已知r1,r2的前提下,可分别求得O

20、到D的最优路径的3倍3T(OO13O14O15D)=3.3与2T(OO7O8O9D)=2的差为1.3,O7到D的最优路径T(O7O10O11D)=0.5及在O7处的等待时间t(r2)=1与r2恢复后继续要走的路径T(O7O8O9D)=0.3之和1.3,但这三者之中最小的是T(O7O10O11D)=0.5,于是决定沿O7O10O11D行驶;当行驶到O10处遇到堵塞点r3;在已知r1,r2,r3的前提下,可分别求得O到D的最优路径的4倍4T(OO13O14O15D)=4.4与3T(OO13O14O15D)=3.3的差为1.1,O10到D的最优路径T(O10O12D)=1.3及在O10处的等待时间t

21、(r3)=0.5与r3恢复后继续要走的路径T(O10O12D)=0.2之和0.7,但这三者之中最小的是t(r3)+T(O10O11D)=0.7,于是决定在O10处等待0.5个单位时间后,堵塞点r3恢复,继续沿着路径O10O11D行驶直到目的点D.容易算出,车辆这样行驶到目的点所花费的时间为2.9个单位时间.通过这个例子可以看出,正如上所述的那样:贪婪策略的竞争性能是“积极的但是有风险的”;复位策略虽然是“保守的但是安全的”;等待策略的优劣直接和T(Rk)有关;而方案4)既采用了复位的方式以避免车辆走“坏路径”的风险,又采用了贪婪的方式以把握车辆走“好路径”的机会,还采用了等待适当的一段时间后以

22、继续沿着最优路径行驶,致使它在实际应用中比其它策略优越得多.自然地,受方案4)的启发,应当以降低竞争比,提高竞争性能为目标将贪婪策略、复位策略和等待策略有机地结合起来,使得当车辆每次遇到堵塞点时,能够在贪婪策略、复位策略和等待策略之间做出最佳选择,从而为物流公司设计出一种更加经济,可行的调度策略选择策略.3选择策略及其竞争比选择策略当车辆在行驶过程中遇到第i个堵塞点ri(i=1,2,k)时,求Ti=min(i+1)Topt(OD|Ri)-iTopt(OD|Ri-1),Topt(OiD|Ri),t(ri)+Topt(OiD|Ri-1)1)若Ti=Topt(OiD|Ri),则按贪婪策略选路行驶

23、;2)若Ti=(i+1)Topt(OD|Ri)-iTopt(OD|Ri-1),则按复位策略选路行驶;3)若Ti=t(ri)+Topt(OiD|Ri-1),则按等待策略选路行驶.定理1设算法D是基于选择策略的一种算法,则算法D对于堵塞点序列Rk=(r1,r2,rk)及其恢复时间T(Rk)=(t(r1),t(r2),t(rk)784第5期胡茂林等:堵塞点可恢复型在线运输车辆的调度策略研究求Ti时,若Topt(OiDRi),(i+1)Topt(ODRi)-iTopt(ODRi-1)与t(ri)+Topt(OiDRi-1)三者相等,或其中两者相等,则优先取t(ri)+Topt(OiDRi-1),其次

27、,用时12 11(因为返回时在上次等待过的堵塞点处不需要再等待).至此,车辆行驶的时间1满足1=11+122i1opt(OD|Rk)(b)车辆第2次从起初点出发,在车辆行驶至堵塞点ri2前,要么按贪婪策略选路行驶要么按等待策略行驶,由1)和3),所用时间21满足21CTD(OD|Ri2-1)(i2-i1)Topt(OD|Rk)这时由于Ti2=(i2+1)Topt(OD|Ri2)-i2Topt(OD|Ri2-1),根据选择策略,车辆须按原路返回到初始点,用时22 21(因为返回时在上次等待过的堵塞点处不需要再等待).至此,车辆完成第2次往返所用时间j满足2=21+222(i2-i1)Topt(O

29、-ij+1)Topt(OD|Rk)=(k+ij+1)Topt(OD|Rk)884系统工程学报第21卷综合1),2),3),4),根据竞争比的定义,可知基于选择策略的算法D对于堵塞点序列Rk=(r1,r2,rk)及恢复时间T(Rk)=(t(r1),t(r2),t(rk)的在线车辆选线问题的竞争比为2k+1.4结论由以上的讨论可以看出,虽然选择策略和复位策略有相同的竞争比2k+1,但选择策略在竞争性能上得到了最大限度的提升:它充分地利用了贪婪策略、复位策略和等待策略的优点,克服了各自的不足.在不同的情形下有不同的对策,使得当车辆每次遇到堵塞点时,都能在贪婪策略、复位策略和等待策略之间做

30、出最佳选择选择贪婪的方式,以充分地把握车辆走好路径的机会;不得已选择复位的方式以避免车辆或者走坏路径或者长时间等待的风险;选择短时间的等待,为了继续沿着最优路径行驶,同时也为了避免车辆走坏路径的风险,还为了避免车辆作不必要的保守的复位.因此选择策略是一种进退有度的策略,是贪婪策略、复位策略和等待策略的有机结合与高度统一.堵塞点无法预测的路径选择问题是物流配送的难题,如何将理论结果更好地应用到实际中是一个值得深入讨论的问题.本文就此做出了初步探讨,当然,讨论还有待于继续深入,如考虑随时间变化堵塞点可恢复的情形下,如何进行路径选择,才能既节省费用又节省时间的研究等.参考文献:1朱志军,徐寅峰.局

31、内车辆选线问题和竞争策略分析J.系统工程学报,2003,18(4):324330.2Manasse M S,McGeoch L A,Sleator D D.Competitive algorithms for server problemsJ.Journal of Algorithms,1990,11(2):208230.3David S B,Borodin A.A new measure for the study of the on2line algorithmJ.Algorithmica,1994,11(1):7391.4K outsoupias E,Papadimitriou C.On

32、 thek2server conjectureJ.Journal of ACM,1995,42(5):971983.5Alon N,Karp P M,Peleg D,et al.A graph2theoretic game and its application to thek2server problemJ.SIAMJournal on Com2puter,1995,24(1):78100.6Pinnoi A,Tung D T.Vehicle routing2schedulingfor waste collection in HanoiJ.EuropeanJournal of Operati

33、onal Research,2000,125(3):449468.7Xu Y Y,Wang KL,Zhu B H.On thek2taxi problemJ.Journal of Information,1999,2(4):429434.8堵丁柱.k车服务问题与竞争算法J.数学的实践与认识,1991,4(1):3640.作者简介:胡茂林(1963),男,宁夏固原人,硕士,宁夏师范学院数学系教授,研究方向:在线算法,humaolin2000 ;徐寅峰(1962),男,吉林长春人,西安交通大学管理学院战略与决策研究所教授,博士生导师,研究方向:运筹学与控制;徐维军(1975),男,宁夏固原人,西安交通大学管理学博士,华南理工大学工商管理学院博士后,研究方向:在线金融算法.984第5期胡茂林等:堵塞点可恢复型在线运输车辆的调度策略研究

展开阅读全文