您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 交通运输 > 物流网点分为供应点,需求点,运输点(货车),
2005交通信息化论坛论文1ITS中车辆调度问题研究河南省高速公路联网收费工作领导小组办公室(E-mail:lwb@hncd.gov.cn)摘要:在智能交通系统(ITS,IntelligentTransportationSystems)的各个子系统中,车辆调度应用非常广泛,但目前大都是针对物流企业车辆动态调度问题,很少应用ITS问题上。本文首先根据实际情况,提出ITS中车辆调度问题,并分析了运输网络的特点,建立了模型。本文综合运用多种运筹技术,提出一种动态规划方法,为车辆调度问题提供了较好的解决方案。最后分析了现实中运输网络状态改变的类型与形式,并针对不同的状况,提出有效的对策。关键词:智能交通系统(ITS);车辆调度;运输网络;原子规划0引言智能交通系统(ITS,IntelligentTransportsSystems)就是将先进的信息技术、传感器技术、数据通讯技术、自动控制技术、运筹学、图像分析技术、计算机网络和人工智能等有效地综合运用于整个交通管理体系,在系统工程综合集成思想指导下,建立起实时、准确、高效的交通运输综合体系。在ITS的各个子系统中,车辆调度问题(VSP,VehicleSchedulingProblem)具有重要地位和作用,比如公交车辆调度、交通信息发布、智能路径调度等。车辆调度问题(VehicleSchedulingProblem)首先由Dantzig和Ramser于1959年提出,它主要探讨:组织的行车路线,能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下,有序地通过一系列供应点或需求点,达到诸如路程最短、费用最小,耗费时间尽量少等目的[1][7]。本文综合应用多种运筹技术,提出一种快速搜索方法,为集货和送货一体化、多供应点、多需求点、多运力点(车场)、单车型条件下的车辆调度问题提供了较好的解决方案,并且分析了现实中运输网络状态改变的类型与形式,并提出有效的对策[2][8]。2005交通信息化论坛论文21提出问题并分析建模1.1提出问题设某运输网络有M个供应点(即S点,下同),N个需求点(即R点,下同),L个运力点(即C点,下同),每个运力点只能接受自己发出去的车。每个S点可供应量为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物流网络结点分析运输网络结点有三类:供应点、需求点和运力点。各种结点有如下状态:供应点有三种状态:一般状态、无存货状态、有需求状态(只有当出现有优先供应权的需求点时,供应点对该需求点表现出这种状态)。需求点也有三种状态:一般状态、已满足状态、有优先供应权状态(由于对需求点需求量的估计错误,导致向该需求点的运输数量超过实际需求量,由于需求点货物的存储条件差等原因,需尽快将多余货物运回,此时,运输网络中的供应点和其他处于一般状态的需求点,对于该需求点来说都是需求点)。运力点有两种状态:有运输能力状态、无运输能力状态。1.3模型建立先对一般情况下的车辆调度问题建模,而暂不考虑运输网络的突发情况。设:ijpqx1,第p个运力点的q号车从i点行驶到j点0,第p个运力点的q号车不从i点行驶到j点2005交通信息化论坛论文3ijy为从供应点i点到需求点j点的供货量,则可得车辆优化调度的数学模型如下:pcqijpqijLpLNMjLNMixdz1111min说明:dij表示从i点到j点的距离。约束(1)表示供应点i的总供应量小于等于其可供应量;约束(2)表示需求点j从各供应点的供货量之和等于其总需求量;约束(3)表示任何一个网络结点向其他结点发出的车辆总数等于接收的车辆总数;约束(4)表示运力点的存有车辆数大于等于其向供应点和需求点发出的车辆之和;约束(5)表示需求点接收的车辆数与载重的积大于等于其需求量[5][6][10]。2解决方案2.1为需求点分配运输车辆的原则分析从总行驶里程最少的角度来考虑,如果给某些需求点都选定了一个运力点,那么从该运力点只派一辆车给这些需求点最经济。但实际上很难按时完成运输任务,也是对运输能力的浪费。所以,这里我们将每个需求点都至少分配一辆车,并根据任务量的大小和时间的紧迫程度来分配车辆的数量。如果某需求点的需求量太少,且任务时间宽裕,也可不分配,等其他需求点的车辆完成任务后,再完成该需求点任务[11]。2.2单车运输情况下的行车路线规划1)为需求点选择运力点:iNjijsy1i=1,2,…,M(1)jMiijry1j=1,2,…,N(2)jcqijpqLpLNMirQxp111j=1,2,…,N(5)ijy0i=1,2,…,M;j=1,2,…,N(7)pcqijpqLpNMjcxp111(4)ppcqijpqLpLNMjcqijpqLpLNMixx111111(3)ijpqx0或1i,j=1,2,…,M+N+L;p=1,2,…L;q=1,2,…cp(6)2005交通信息化论坛论文41.找出各未分配车辆的需求点的包含一个一般状态的供应点和一个有运输能力的运力点的最短初等圈或环;2.对所有初等圈或环进行比较,找出总行程最短的初等圈或环,这样确定了一个需求点的运力点。3.设该运力点已经派出一辆汽车完成向该需求点的第一次运输,将此时各结点的状态设为运输网络的最新状态,重复步骤1,直到对所有的需求点都分配完成为止。2)整车运输部分。设各车辆都向需求点完成第一次运输,那么此时的运输网络达到运输规划的标准状态,可以通过运输规划来确定下一步的运输任务。以下两条原则可以帮助寻找最佳的行车路线:1.整数倍原则:如某个供应点向某个需求点的运输量超过是汽车载重量的一倍或者几倍,那么运输量除以汽车载重量的整数部分要优先运输。2.距离优先原则:距离较近运输任务的优先运输。因为运输网络是动态的,随时可能出现意外情况,我们应在最短的时间内完成更多的任务。由于这两条原则在某些时候是矛盾的,我们主张根据运输网络出现意外情况的频率来安排这两条原则的先后次序。如果意外情况出现频率较高则适用距离优先原则;反之则适用整数倍原则。一般情况下,应该在整数倍原则下使用距离优先原则。3)非整车运输部分。经过上一步,此时的运输网络状况是yijQ,当然∑yij(j=1,2,…N)可能大于等于Q,∑yij(i=1,2,…M)也可能大于等于Q,那是由于它们所对应的结点的数量可能很多,比如一个S点可能要供给好几个R点,一个R点也可能要从好几个S点取货。下面,我们先介绍在规划中需要用的理论和一些规定:1.节约公式。见参考文献[9]。2.运输网络结点状态改变假设。在从R点开始向S点行进的过程中,虽然还没有到S点装车,但是该S点应该有一部分货物已经预分配给该车辆,所以此时S点的状态应处于预变的状态。这种状态改变(有可能是数量上的改变或真正的状态发生变化)是随着车辆从R点发出就已经确定的了。同理,在S点装车的过程中,此时R点也处于预变的状态。在这里,我们假设车辆在R点开始向S点出发时的瞬间同时改变S点和R点的状态,并在状态改变的瞬间做出车辆此次运输路线的规划。3.原子规划假设。运输车辆的一次运输过程可能在几个S点上货,并向很多R点送货,2005交通信息化论坛论文5因此可能影响到很多网络结点的状态。为了消除这种影响,我们把车辆从R点发出到送货回到R点作为一次原子规划,这期间不对其他R点的车辆进行规划,该车辆此次运输任务完成前,也不再对它分配新的运输任务,网络状态也变为规划后的状态。在轮到其他需求点车辆进行规划时,以变化后的状态为准。以上三点是行车路线规划中主要应用的理论,下面给出一个求可接受解的方法(以下图中供应点为S点,需求点为R点),这个方法是在考虑到各运输车辆的任务均衡,在此条件下,对行车路线进行最优规划:1)规划运输车辆的顺序。按当前车辆计划行驶里程排队,选择最先完成过去任务的车优先进行规划。规划后车辆重新进入排队系统。一次只对一辆车进行规划,都采用原子规划的形式。2)设某车在R1点,需向m个S点取货。任选某Si点(i=1,2,…m),标为S’i点,装车后车载货量为yi1。设此时已找到n’个S点,搜索其他S点,若某Sj点使Q-∑yi1yj1,(i=1,2,…n’),则标为S’j点。设共找到n个S’点。3)任意排列n个S’点,每一种排列作为一种策略。1.若在某S’j点(jn),有yjk≤Q-∑y’p1(p=1,2,…j),且yjk+∑y’p1+yj1>Q-∑yq1(p=1,2,…j-1;jq≤n),则装上yjk,且将Rj点加入到Sj+1,…Sq中,进行排列组合规划;2.在某S’i点,有yij≤Q-∑y’k1(k=1,2,…n;y’k1为在S’i点实际装车量),则装上yij,且Rj点加入到剩余的n-i个S’点中,进行排列组合规划,若排列后Rj为最后,且n=m,那么将Rj与R1进行排列组合规划,找到最优路径,最后回到C点。4)一次规划完成后,车辆重新进入排队队列,等待下一次规划。5)车辆运输任务均衡调整。目的是平衡运输任务量,也可以省略。如各车辆之间的任务量差距很大,说明分配给某个R点的车辆太少了,应多分配一些车辆。也可通过对行车路线进行调整来平衡运输任务,但这样做有时会造成总行驶里程的增加。我们的原则是在不造成的总行驶里程增加的条件下的调整各车辆运输任务的均衡。如任务量仍很不均衡,则可以通过调整运输车辆的数量来平衡运输任务。可以调整且不造成总行驶里程增加的情况如下例:C1的行车路线:C-R1-S1-R1-R2-C,C2的行车路线:C-R2-S2-R2-S2-R2-S2-R2-C,可以调整为:2005交通信息化论坛论文6C1的行车路线: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:目前各需求点的运输车辆都只有一辆,分别为C1,C2,汽车载重量都为6,各辆车的已规划的行驶里程分别为:200,300,求此时的行车路线规划。解:最先完成已规划任务的C1,则从R1开始规划,括号中的数为该点的状态,第一个数是车辆的总行驶里程,第二个数是当前该车的载重量:选择行车路线的方法:选择总行程最短的行车路线;当行车里程相同时,则比较在行驶过程中的载重量,计算方法是,将括号中的第二项相加,选择和最小的做为行车路线。如还无法比较出行车路线,则可任选其一。根据以上分析,本例的行车路线为:C1:R1-S2-R2-S1-R1-C,C2:R2-S1-R2-C。总行驶里程860,其中C1行驶里程为440,C2为420。若依经验安排行车路线,则总行驶里程1000,仅第3)步节约里程140,可见节约量还是很大的。以上是按照均衡安排运输任务的原则安排运输任务。如果想得到总运输里程最小的行车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)(800|0)(520|0)R1(200|0)CCR2R1R1R2S1S1S1R2R2CCR2R2(840|0)(810|5)(780|0)(480|0)(440|0)(360|3)(400|1)(
本文标题:物流网点分为供应点,需求点,运输点(货车),
链接地址:https://www.777doc.com/doc-233133 .html