高速公路联网收费ITS中车辆调度问题研讨

1、Evaluation Warning: The document was created with Spire.Doc for .NET.当前文档修改密码：8362839 HYPERLINK ITS中车车辆调度度问题研研究河南省高速速公路联联网收费费工作领领导小组组办公室室 (E-mmaill: )摘要：在智智能交通通系统（ITS，Intelligent Transportation Systems）的各个子系统中，车辆调度应用非常广泛，但目前大都是针对物流企业车辆动态调度问题，很少应用ITS问题上。本文首先根据实际情况，提出ITS中车辆调度问题，并分析了运输网络的特点，建立了模型。本文综合运

2、用多种运筹技术，提出一种动态规划方法，为车辆调度问题提供了较好的解决方案。最后分析了现实中运输网络状态改变的类型与形式，并针对不同的状况，提出有效的对策。关键词：智智能交通通系统(ITSS)；车车辆调度度；运输输网络；原子规规划0 引 言言智能交通系系统（IITS，Inttellligeent Traanspportts SSysttemss）就是是将先进进的信息息技术、传传感器技技术、数数据通讯讯技术、自自动控制制技术、运运筹学、图图像分析析技术、计计算机网网络和人人工智能能等有效效地综合合运用于于整个交交通管理理体系,在系统统工程综综合集成成思想指指导下,建立起实实时、准准确、高高效的交交

3、通运输输综合体体系。在在ITSS的各个个子系统统中，车车辆调度度问题（VSP，Vehicle Scheduling Problem）具有重要地位和作用，比如公交车辆调度、交通信息发布、智能路径调度等。车辆调度问问题(VVehiiclee Scchedduliing Proobleem)首首先由DDanttzigg和Rammserr于19559年提提出，它它主要探探讨：组组织的行行车路线线，能否否使车辆辆在满足足一定的的约束条条件(如需求求量、发发送量、车车载容量量限制、行行程限制制、时间间限制等等)下，有有序地通通过一系系列供应应点或需需求点，达达到诸如如路程最最短、费费用最小小，耗费费时间尽

4、尽量少等等目的1 7。本文综合应应用多种种运筹技技术，提提出一种种快速搜搜索方法法，为集集货和送送货一体体化、多多供应点点、多需需求点、多多运力点点（车场场）、单单车型条条件下的的车辆调调度问题题提供了了较好的的解决方方案，并并且分析析了现实实中运输输网络状状态改变变的类型型与形式式，并提提出有效效的对策策2 88。1提出问题题并分析析建模1.1 提提出问题题设某运输网网络有MM个供应应点（即即S点，下下同），N个需求点（即R点，下同），L个运力点（即C点，下同），每个运力点只能接受自己发出去的车。每个S点可供应量为si（i=1，2，M），每个R点的需求量为rj（j=1，2，N），每个C点可发

5、出车辆数为ck（k=1，2，L），车型均相同，载重量都为Q，求满足货运需求的路程最短的车辆行驶路线；运输网络中随时可能出现新的S点或R点，求此时的行车路线规划；由于R点的需求量是由经验估计确定的，可能会发生估计需求量大于实际需求量的情况，需要将已经运往该R点的货物运回到其它S点或R点3 4。1.2 物物流网络络结点分分析运输网络结结点有三三类：供供应点、需需求点和和运力点点。各种种结点有有如下状状态：供应点有三三种状态态：一般般状态、无存货状态、有需求状态（只有当出现有优先供应权的需求点时，供应点对该需求点表现出这种状态）。需求点也有有三种状状态：一一般状态态、已满满足状态态、有优优先供应应权

6、状态态（由于于对需求求点需求求量的估估计错误误，导致致向该需需求点的的运输数数量超过过实际需需求量，由由于需求求点货物物的存储储条件差差等原因因，需尽尽快将多多余货物物运回，此此时，运运输网络络中的供供应点和和其它处处于一般般状态的的需求点点，对于于该需求求点来说说都是需需求点）。运力点有两两种状态态：有运运输能力力状态、无无运输能能力状态态。1.3 模模型建立立先对一般情情况下的的车辆调调度问题题建模，而而暂不考考虑运输输网络的的突发情情况。设设：1，第p个运力点的1，第p个运力点的q号车从i点行驶到j点0，第p个运力点的q号车不从i点行驶到j点为从供应点点i点到需需求点jj点的供供货量，则

7、则可得车车辆优化化调度的的数学模模型如下下： i=1， i=1，2，M （1） j=1 j=1，2，N （2） （3） （4） j=1 j=1，2，N （5）00或1 i，j=1，2，M+N+L；p=1，2，L；q=1，2，cp （6） i=1 i=1，2，M；j=1，2，N （7）说明：diij表示示从i点到j点的距距离。约约束（11）表示示供应点点i的总供供应量小小于等于于其可供供应量；约束（2）表示需求点j从各供应点的供货量之和等于其总需求量；约束（3）表示任何一个网络结点向其它结点发出的车辆总数等于接收的车辆总数；约束（4）表示运力点的存有车辆数大于等于其向供应点和需求点发出的车辆之和

8、；约束（5）表示需求点接收的车辆数与载重的积大于等于其需求量5 6 10。2 解决方方案2.1 为为需求点点分配运运输车辆辆的原则则分析从总行驶里里程最少少的角度度来考虑虑，如果果给某些些需求点点都选定定了一个个运力点点，那么么从该运运力点只只派一辆辆车给这这些需求求点最经经济。但但实际上上很难按按时完成成运输任任务，也也是对运运输能力力的浪费费。所以以，这里里我们将将每个需需求点都都至少分分配一辆辆车，并并根据任任务量的的大小和和时间的的紧迫程程度来分分配车辆辆的数量量。如果果某需求求点的需需求量太太少，且且任务时时间宽裕裕，也可可不分配配，等其其它需求求点的车车辆完成成任务后后，再完完成该

9、需需求点任任务111。2.2 单车运输输情况下下的行车车路线规规划为需求点选选择运力力点：找出各未分分配车辆辆的需求求点的包包含一个个一般状状态的供供应点和和一个有有运输能能力的运运力点的的最短初初等圈或或环；对所有初等等圈或环环进行比比较，找找出总行行程最短短的初等等圈或环环，这样样确定了了一个需需求点的的运力点点。设该运力点点已经派派出一辆辆汽车完完成向该该需求点点的第一一次运输输，将此此时各结结点的状状态设为为运输网网络的最最新状态态，重复复步骤11，直到到对所有有的需求求点都分分配完成成为止。整车运输部部分。设设各车辆辆都向需需求点完完成第一一次运输输，那么么此时的的运输网网络达到到运

10、输规规划的标标准状态态，可以以通过运运输规划划来确定定下一步步的运输输任务。以以下两条条原则可可以帮助助寻找最最佳的行行车路线线：整数倍原则则：如某某个供应应点向某某个需求求点的运运输量超超过是汽汽车载重重量的一一倍或者者几倍，那那么运输输量除以以汽车载载重量的的整数部部分要优优先运输输。距离优先原原则：距距离较近近运输任任务的优优先运输输。因为为运输网网络是动动态的，随随时可能能出现意意外情况况，我们们应在最最短的时时间内完完成更多多的任务务。由于这两条条原则在在某些时时候是矛矛盾的，我我们主张张根据运运输网络络出现意意外情况况的频率率来安排排这两条条原则的的先后次次序。如如果意外外情况出出

11、现频率率较高则则适用距距离优先先原则；反之则则适用整整数倍原原则。一一般情况况下，应应该在整整数倍原原则下使使用距离离优先原原则。3） 非整整车运输输部分。经过上一步，此时的运输网络状况是yij yj11，（i=1，2，n），则则标为SSj点。设设共找到到n个S点。任意排列nn个S点，每每一种排排列作为为一种策策略。若在某Sj点（jn），有有yjkQyp1（p=11，2，j），且且yjk+yp1+yj1Qyq1（p=11，2，j1；jR1-SS1-RR1-RR2-CC，C2的行车车路线：C-R2-SS2-RR2-SS2-RR2-SS2-RR2-CC，可以以调整为为：C1的行车车路线：C-R1-

12、SS1-RR1-RR2-SS2-RR2-CC，C2的行车车路线：C-R2-SS2-RR2-SS2-RR2-CC。下面以一个个最简单单情况下下的例子子来说明明一次行行车路线线规划方方法：设运输网络络中有两两个供应应点（SS1，S2），两两个需求求点（RR1，R2），一一个运力力点（C），其其中每个个供应点点向需求求点的供供应量都都小于QQ，数据据如表22.1、2.22：表表2.2 结点距离表S1S2R1R2CS10S2800R170500R23050800C40600表表2.1 供应量表R1R2S115S221目前各需求求点的运运输车辆辆都只有有一辆，分分别为CC1，C2，汽车车载重量量都为66

13、，各辆辆车的已已规划的的行驶里里程分别别为：2200，3000，求此此时的行行车路线线规划。解：最先完完成已规规划任务务的C1，则从从R1开始规规划，括括号中的的数为该该点的状状态，第第一个数数是车辆辆的总行行驶里程程，第二二个数是是当前该该车的载载重量：S1S1S2R2R1R1R2CCR2R2S1S1R2R2CC（480|0）（400|3）（350|4）（270|1）（960|0）（900|0）（870|5）（840|0）（540|0）（480|0）（400|1）（920|0）（860|0）（830|5）（800|0）（520|0）R1（200|0）CCR2R1R1R2S1S1S1R2R2C

14、CR2R2（840|0）（810|5）（780|0）（480|0）（440|0）（360|3）（400|1）（330|4）（480|0）（540|0）（840|0）（870|5）（900|0）（960|0）（900|0）（250|3）S2S1R2（300|2）R2S1R2R1CC（400|0）（440|0）（740|0）（770|5）（800|0）（860|0）（330|3）选择行车路路线的方方法：选选择总行行程最短短的行车车路线；当行车车里程相相同时，则则比较在在行驶过过程中的的载重量量，计算算方法是是，将括括号中的的第二项项相加，选择和最小的做为行车路线。如还无法比较出行车路线，则可任选其

15、一。根据以上分分析，本本例的行行车路线线为：CC1：R1-SS2-RR2-SS1-RR1-CC，C2：R2-SS1-RR2-CC。总行行驶里程程8600，其中中C1行驶里里程为4440，C2为4200。若依依经验安安排行车车路线，则则总行驶驶里程110000，仅第第3）步节节约里程程1400，可见见节约量量还是很很大的。以上是按照照均衡安安排运输输任务的的原则安安排运输输任务。如如果想得得到总运运输里程程最小的的行车路路线，那那么还需需先对CC2进行规规划，规规划方法法同上，将将规划结结果与上上述结果果比较，选选择最优优解。2.3 多车运运输情况况下的行行车路线线规划现实中向某某个需求求点派出

16、出的运输输车辆一一般多于于一辆。根根据需求求点需求求量的大大小和时时间紧迫迫程度来来决定调调用车辆辆的多少少。我们们同样采采取均衡衡原则，依依次分配配运输任任务。为需求点选选择运力力点调动动车辆及及整车运运输部分分的方法法同单车车规划。在在非整车车运输部部分，我我们将对对每个原原子规划划产生的的小运输输任务进进行依次次分配。由由于之前前该需求求点的各各运输车车辆的行行驶里程程相同，所所以它们们同时被被激活，依依次安排排任务，并并同时出出发，完完成各自自的任务务。例如：需求求点R1有三辆辆运输车车辆C1，C2，C3，共有有三个供供应点SS1，S2，S3，数据据如表22.3、2.44：表2.4 结

17、点距离表表2.4 结点距离表 S1S2S3R1S10S2300S390700R15060500表2.3 供应量表S1S2S3R1825汽车载重量量都为66，各辆辆车的已已规划的的行驶里里程为2200，求求此时的的行车路路线规划划。 解解： 经过规规划得出出行车路路线：RR1-SS1-RR1-SS1-SS2-RR1-SS3-RR1。将各各原子规规划分配配给各车车辆，得得出各车车辆行车车路线。C1：R1-S1-R1，C2：R1-S1-S2-R1，C3 ：R1-S3-R1。3 运输网网络的意意外处理理在运输过程程中，常常会出现现某些意意外情况况，对运运输任务务的顺利利完成产产生影响响。大致致可分为为

18、两种：一种是是自然灾灾害。如如：恶劣劣的天气气、道路路堵塞、车车辆故障障等，只只能通过过人为的的调整、补补充运输输车辆、路路线等方方法，进进行补救救；另一一种是运运输网络络结构的的改变。如如：突然然出现一一个新的的供应点点或需求求点，或或一个有有优先供供应权的的需求点点，这时时需要采采取措施施重新规规划运输输任务。下下面将主主要讨论论第二种种情况下下的意外外处理12 113。3.1 出现新新的供应应点或需需求点情情况下的的意外处处理出现新的供供应点或或需求点点将会使使运输网网络结构构发生变变化，必必将会导导致现有有运输任任务的重重新排定定。应用用前文的的运输网网络结点点状态改改变假设设，原有有

19、的网络络结点一一律按照照本次任任务完成成之后的的状态作作为现在在的状态态。将原原有结点点和新的的网络结结点综合合起来，根根据2.2节和和2.33节提供供的方法法，统一一规划。3.2 出现有有优先供供应权的的需求点点情况下下的意外外处理由于对需求求点需求求量的估估计错误误，需求求点可能能出现一一种有优优先供应应权的状状态。此此时应将将有优先先供应权权的需求求点作为为供应点点，原供供应点变变为需求求点，原原运力点点仍为运运力点，每每个已经经分配的的运输车车辆的处处于一般般状态的的需求点点都是同同时是一一个运力力点。完完成这次次规划之之后，按按规划完完之后的的状态（有有优先供供应权的的需求点点肯定已

20、已经消失失），重重新进行行行车路路线规划划。4 结论本文通过对对ITSS中车辆辆调度问问题建立立数学模模型，并并提出一一种简便便易行的的搜索算算法，为为车辆调调度问题题提供了了较好的的解决方方案，但但还有许许多限制制条件需需要解决决，如没没有考虑虑到时间间窗的限限制、多多车型问问题、汽汽车满载载/空载时时耗油量量的不同同等等，这这也是我我们继续续研究的的方向。参考文献1 FF. BBaitta, R. Pessentti, W. Ukoovicch, D. Favvareettoo. AA coompaarisson of diffferrertt sooluttionn appprooach

21、hes to thee veehiccle schheduulinng pprobblemm inn a praactiicall caaseJ. CCompputeer & Opperaatioons Ressearrch,20000,227:112499-12269.2 YYangg-Byyungg Paark. A hybbridd geenettic alggoriithmm foor tthe vehhiclle sscheedullingg prrobllem witth ddue tmees aand timme ddeaddlinnesJ. IInteernaatioonall

22、. JJourrnall. PProdducttionn Ecconoomiccs,220011,733:1775-1188.3 SSotiiriss P. Gaayiaaliss, IIliaas PP. TTatssioppoullos. Deesiggn oof aan IIT-ddrivven deccisiion suppporrt ssysttem forr veehiccle rouutinng aand schheduulinngJJ. Euuroppeann Joournnal of Opeerattionnal Ressearrch,20004,1152:3822-3998

23、.4 MM. DDesrrochherss, CC.V.Jonnes, J.K. Lennstrra, M.WW.P. Saavellsbeerghh, LL. SStouugiee. TTowaardss a moddel andd allgorrithhm mmanaagemmentt syysteem ffor vehhiclle rrouttingg annd sscheedullingg prrobllemssJ. Deccisiion Suppporrt SSysttemss,19999,25:1099-1333.5 AAlann Sllateer. Speecifficaatioon ffor a ddynaamicc veehiccle rouutinng aand schheduulinng ssysttemJ. IInteernaatioonall Joournnal of Traanspportt Maanaggemeent,20002,11:299-400.6 GGuy Dessaullnieers, Juune Lavvignne, Fraancoois Souumiss. MMultti-d