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

1、ITS中车辆调度问题研究河南省高速公路联网收费工作领导小组办公室 (E-mail: lwb)摘要：在智能交通系统（ITS，Intelligent Transportation Systems）的各个子系统中，车辆调度应用非常广泛，但目前大都是针对物流企业车辆动态调度问题，很少应用ITS问题上。本文首先根据实际情况，提出ITS中车辆调度问题，并分析了运输网络的特点，建立了模型。本文综合运用多种运筹技术，提出一种动态规划方法，为车辆调度问题提供了较好的解决方案。最后分析了现实中运输网络状态改变的类型与形式，并针对不同的状况，提出有效的对策。关键词：智能交通系统(ITS)；车辆调度；运输网络；原子规

2、划0 引 言智能交通系统（ITS，Intelligent Transports Systems）就是将先进的信息技术、传感器技术、数据通讯技术、自动控制技术、运筹学、图像分析技术、计算机网络和人工智能等有效地综合运用于整个交通管理体系,在系统工程综合集成思想指导下,建立起实时、准确、高效的交通运输综合体系。在ITS的各个子系统中，车辆调度问题（VSP，Vehicle Scheduling Problem）具有重要地位和作用，比如公交车辆调度、交通信息发布、智能路径调度等。车辆调度问题(Vehicle Scheduling Problem)首先由Dantzig和Ramser于1959年提出，它主

3、要探讨：组织的行车路线，能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下，有序地通过一系列供应点或需求点，达到诸如路程最短、费用最小，耗费时间尽量少等目的1 7。本文综合应用多种运筹技术，提出一种快速搜索方法，为集货和送货一体化、多供应点、多需求点、多运力点（车场）、单车型条件下的车辆调度问题提供了较好的解决方案，并且分析了现实中运输网络状态改变的类型与形式，并提出有效的对策2 8。1提出问题并分析建模1.1 提出问题设某运输网络有M个供应点（即S点，下同），N个需求点（即R点，下同），L个运力点（即C点，下同），每个运力点只能接受自己发出去的车。每个S

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

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

6、M （1） j=1，2，N （2） （3） （4） j=1，2，N （5）0或1 i，j=1，2，M+N+L；p=1，2，L；q=1，2，cp （6） i=1，2，M；j=1，2，N （7）说明：dij表示从i点到j点的距离。约束（1）表示供应点i的总供应量小于等于其可供应量；约束（2）表示需求点j从各供应点的供货量之和等于其总需求量；约束（3）表示任何一个网络结点向其它结点发出的车辆总数等于接收的车辆总数；约束（4）表示运力点的存有车辆数大于等于其向供应点和需求点发出的车辆之和；约束（5）表示需求点接收的车辆数与载重的积大于等于其需求量5 6 10。2 解决方案2.1 为需求点分配运输车辆的

7、原则分析从总行驶里程最少的角度来考虑，如果给某些需求点都选定了一个运力点，那么从该运力点只派一辆车给这些需求点最经济。但实际上很难按时完成运输任务，也是对运输能力的浪费。所以，这里我们将每个需求点都至少分配一辆车，并根据任务量的大小和时间的紧迫程度来分配车辆的数量。如果某需求点的需求量太少，且任务时间宽裕，也可不分配，等其它需求点的车辆完成任务后，再完成该需求点任务11。2.2 单车运输情况下的行车路线规划1) 为需求点选择运力点：1. 找出各未分配车辆的需求点的包含一个一般状态的供应点和一个有运输能力的运力点的最短初等圈或环；2. 对所有初等圈或环进行比较，找出总行程最短的初等圈或环，这样确

8、定了一个需求点的运力点。3. 设该运力点已经派出一辆汽车完成向该需求点的第一次运输，将此时各结点的状态设为运输网络的最新状态，重复步骤1，直到对所有的需求点都分配完成为止。2) 整车运输部分。设各车辆都向需求点完成第一次运输，那么此时的运输网络达到运输规划的标准状态，可以通过运输规划来确定下一步的运输任务。以下两条原则可以帮助寻找最佳的行车路线：1. 整数倍原则：如某个供应点向某个需求点的运输量超过是汽车载重量的一倍或者几倍，那么运输量除以汽车载重量的整数部分要优先运输。2. 距离优先原则：距离较近运输任务的优先运输。因为运输网络是动态的，随时可能出现意外情况，我们应在最短的时间内完成更多的任

9、务。由于这两条原则在某些时候是矛盾的，我们主张根据运输网络出现意外情况的频率来安排这两条原则的先后次序。如果意外情况出现频率较高则适用距离优先原则；反之则适用整数倍原则。一般情况下，应该在整数倍原则下使用距离优先原则。3） 非整车运输部分。经过上一步，此时的运输网络状况是yij<Q，当然yij（j=1，2，N）可能大于等于Q，yij（i=1，2，M）也可能大于等于Q，那是由于它们所对应的结点的数量可能很多，比如一个S点可能要供给好几个R点，一个R点也可能要从好几个S点取货。下面，我们先介绍在规划中需要用的理论和一些规定：1. 节约公式。见参考文献9。2. 运输网络结点状态改变假设。在从R

10、点开始向S点行进的过程中，虽然还没有到S点装车，但是该S点应该有一部分货物已经预分配给该车辆，所以此时S点的状态应处于预变的状态。这种状态改变（有可能是数量上的改变或真正的状态发生变化）是随着车辆从R点发出就已经确定的了。同理，在S点装车的过程中，此时R点也处于预变的状态。在这里，我们假设车辆在R点开始向S点出发时的瞬间同时改变S点和R点的状态，并在状态改变的瞬间做出车辆此次运输路线的规划。3. 原子规划假设。运输车辆的一次运输过程可能在几个S点上货，并向很多R点送货，因此可能影响到很多网络结点的状态。为了消除这种影响，我们把车辆从R点发出到送货回到R点作为一次原子规划，这期间不对其它R点的车

11、辆进行规划，该车辆此次运输任务完成前，也不再对它分配新的运输任务，网络状态也变为规划后的状态。在轮到其它需求点车辆进行规划时，以变化后的状态为准。以上三点是行车路线规划中主要应用的理论，下面给出一个求可接受解的方法（以下图中供应点为S点，需求点为R点），这个方法是在考虑到各运输车辆的任务均衡，在此条件下，对行车路线进行最优规划：1） 规划运输车辆的顺序。按当前车辆计划行驶里程排队，选择最先完成过去任务的车优先进行规划。规划后车辆重新进入排队系统。一次只对一辆车进行规划，都采用原子规划的形式。2） 设某车在R1点，需向m个S点取货。任选某Si点（i=1，2，m），标为Si点，装车后车载货量为yi

12、1。设此时已找到n个S点，搜索其它S点，若某Sj点使Qyi1> yj1，（i=1，2，n），则标为Sj点。设共找到n个S点。3） 任意排列n个S点，每一种排列作为一种策略。1 若在某Sj点（j<n），有yjkQyp1（p=1，2，j），且yjk+yp1+yj1Qyq1（p=1，2，j1；j<qn），则装上yjk，且将Rj点加入到Sj+1，Sq中，进行排列组合规划；2 在某Si点，有yijQyk1（k=1，2，n；yk1为在Si点实际装车量），则装上yij，且Rj点加入到剩余的ni个S点中，进行排列组合规划，若排列后Rj为最后，且n=m，那么将Rj与R1进行排列组合规划，找到最

13、优路径，最后回到C点。4） 一次规划完成后，车辆重新进入排队队列，等待下一次规划。5） 车辆运输任务均衡调整。目的是平衡运输任务量，也可以省略。如各车辆之间的任务量差距很大，说明分配给某个R点的车辆太少了，应多分配一些车辆。也可通过对行车路线进行调整来平衡运输任务，但这样做有时会造成总行驶里程的增加。我们的原则是在不造成的总行驶里程增加的条件下的调整各车辆运输任务的均衡。如任务量仍很不均衡，则可以通过调整运输车辆的数量来平衡运输任务。可以调整且不造成总行驶里程增加的情况如下例：C1的行车路线：C->R1->S1->R1->R2->C，C2的行车路线：C->R

14、2->S2->R2->S2->R2->S2->R2->C，可以调整为：C1的行车路线：C->R1->S1->R1->R2->S2->R2->C，C2的行车路线：C->R2->S2->R2->S2->R2->C。下面以一个最简单情况下的例子来说明一次行车路线规划方法：设运输网络中有两个供应点（S1，S2），两个需求点（R1，R2），一个运力点（C），其中每个供应点向需求点的供应量都小于Q，数据如表2.1、2.2：表2.2 结点距离表S1S2R1R2CS10S2800R17050

15、0R23050800C40600表2.1 供应量表R1R2S115S221目前各需求点的运输车辆都只有一辆，分别为C1，C2，汽车载重量都为6，各辆车的已规划的行驶里程分别为：200，300，求此时的行车路线规划。解：最先完成已规划任务的C1，则从R1开始规划，括号中的数为该点的状态，第一个数是车辆的总行驶里程，第二个数是当前该车的载重量：S1S2R2R1R1R2CCR2R2S1S1R2R2CC（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）（80

16、0|0）（520|0）R1（200|0）CCR2R1R1R2S1S1S1R2R2CCR2R2（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）选择行车路线的方法：选择总行程最短的行车路线；当行车里程相同时，则比较在行驶过程中的载重量，计算方法是，将括号中的第二项相加，选择和最小的做

17、为行车路线。如还无法比较出行车路线，则可任选其一。根据以上分析，本例的行车路线为：C1：R1->S2->R2->S1->R1->C，C2：R2->S1->R2->C。总行驶里程860，其中C1行驶里程为440，C2为420。若依经验安排行车路线，则总行驶里程1000，仅第3）步节约里程140，可见节约量还是很大的。以上是按照均衡安排运输任务的原则安排运输任务。如果想得到总运输里程最小的行车路线，那么还需先对C2进行规划，规划方法同上，将规划结果与上述结果比较，选择最优解。2.3 多车运输情况下的行车路线规划现实中向某个需求点派出的运输车辆一般多于

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

19、的行驶里程为200，求此时的行车路线规划。 解： 经过规划得出行车路线：R1->S1->R1->S1->S2->R1->S3->R1。将各原子规划分配给各车辆，得出各车辆行车路线。C1：R1->S1->R1，C2：R1->S1->S2->R1，C3 ：R1->S3->R1。3 运输网络的意外处理在运输过程中，常会出现某些意外情况，对运输任务的顺利完成产生影响。大致可分为两种：一种是自然灾害。如：恶劣的天气、道路堵塞、车辆故障等，只能通过人为的调整、补充运输车辆、路线等方法，进行补救；另一种是运输网络结构的改变。

20、如：突然出现一个新的供应点或需求点，或一个有优先供应权的需求点，这时需要采取措施重新规划运输任务。下面将主要讨论第二种情况下的意外处理12 13。3.1 出现新的供应点或需求点情况下的意外处理出现新的供应点或需求点将会使运输网络结构发生变化，必将会导致现有运输任务的重新排定。应用前文的运输网络结点状态改变假设，原有的网络结点一律按照本次任务完成之后的状态作为现在的状态。将原有结点和新的网络结点综合起来，根据2.2节和2.3节提供的方法，统一规划。3.2 出现有优先供应权的需求点情况下的意外处理由于对需求点需求量的估计错误，需求点可能出现一种有优先供应权的状态。此时应将有优先供应权的需求点作为供

21、应点，原供应点变为需求点，原运力点仍为运力点，每个已经分配的运输车辆的处于一般状态的需求点都是同时是一个运力点。完成这次规划之后，按规划完之后的状态（有优先供应权的需求点肯定已经消失），重新进行行车路线规划。4 结论本文通过对ITS中车辆调度问题建立数学模型，并提出一种简便易行的搜索算法，为车辆调度问题提供了较好的解决方案，但还有许多限制条件需要解决，如没有考虑到时间窗的限制、多车型问题、汽车满载/空载时耗油量的不同等等，这也是我们继续研究的方向。参考文献1 F. Baita, R. Pesenti, W. Ukovich, D. Favaretto. A comparison of diff

22、erert solution approaches to the vehicle scheduling problem in a practical caseJ. Computer & Operations Research,2000,27:1249-1269.2 Yang-Byung Park. A hybrid genetic algorithm for the vehicle scheduling problem with due tmes and time deadlinesJ. International. Journal. Production Economics,2001

23、,73:175-188.3 Sotiris P. Gayialis, Ilias P. Tatsiopoulos. Design of an IT-driven decision support system for vehicle routing and schedulingJ. European Journal of Operational Research,2004,152:382-398.4 M. Desrochers, C.V.Jones, J.K. Lenstra, M.W.P. Savelsbergh, L. Stougie. Towards a model and algorithm management system for vehicle routing and scheduling problemsJ. Decision Support Systems,1999,25:109-133.5 Alan Slater. Specification for a dynamic vehicle r