调派车辆四要点动态路径规划研究

调派车辆四要点动态路径规划研究

0随机动态车辆路径邮政服务是快递公司从发件员处接收尽可能快的文件、货物或货物的服务。在“关闭”（即离开）的发送方式下，物流总监必须首先将货物送到收件员的路上，并将货物运到收件站，最后将其发送给收件员。在揽收快件的动态车辆调度过程中,调度中心应用GPS技术实时跟踪车辆,并通过GIS构造一个有向网络图(网络图中,结点包括:始发车场、收发站、发件人和车辆的位置,弧表示从始端点到末端点的可通行道路),然后在此基础上动态调整行车路径,执行迄今为止所产生的快件揽收任务.在一个运营周期内,快件是随机产生的,包括产生的时刻和收发件人的地址等.当快递公司接收一个快件时,需即刻调派车辆在较短的时间上门揽收,此时,快递公司的部分或全部车辆正按照之前编排的行车路径揽收前期产生的快件,而调度中心无法获知之后产生的快件信息.因此,派车揽收快件是一个需实时(在线)编排车辆行车路径的动态决策过程.在各类随机动态车辆路径问题中,其不确定性和动态性特征最为显著.求解这类问题的通行方法是采用启发式算法,包括使用一些简单的分派策略,如先到先服务(First-ComeFirstServed,FCFS)的顺序服务策略、近邻服务策略(NearestNeighbor,NN)、中点重定位策略(StochasticQueueMedian,SQM)等;还包括使用最优插入法,以及禁忌搜索算法(TabuSearch)、适应性记忆法(AdaptiveMemory,AM)、可变邻域搜索法(VariableNeighborhoodSearch,VNS)等一些优化方法.关于随机动态车辆路径问题的优化目标,一般是结合问题的动态性特征来设立的:当动态性较强时,一般采用顾客平均等待时间最短的目标;否则,采用车辆行车路径最短的目标.对于本文研究的快件揽收车辆路径问题,其优化目标包括:(1)揽收所有快件的最后时刻最早.在一个运营周期内,将最后一个快件的揽收时刻提前,从而可推迟快件的截止揽收时刻.它体现了快递公司为顾客提供更高效率的服务.(2)总行车路径最短.缩短行车路径,一是直接降低了运输成本,二是提高了车辆的利用率,使车辆能揽收更多快件.它体现了快递公司更高效率的车辆调度管理.(3)尽可能平衡车辆揽收快件数.保持车辆的工作量平衡,是快递公司基于管理的公平性而提出的要求.如果片面追求效率与成本最优,一般都会出现车辆工作量的分配严重不平衡的情况.为解决由此引发的矛盾,必然会增加公司的管理成本.本文采用以上多目标,应用最优插入法,分派车辆揽收新产生的快件,并应用2-opt方法对行车路径进行优化改进.该算法被用于动态的决策情景中,针对未揽收的快件,进行当前约束下的路径寻优,是一种贪婪算法.1行车时间约束用K表示给定区域内执行快件揽收任务的车辆集合,它们从同一始发车场vstart出发,揽收所有快件之后,最终在截止时刻T之前将其运送到同一收发站vend.在一个固定周期内,快件的产生时刻及发件人地址都是随机生成的.设在现在时刻tnow新产生一个快件inew.此时,需要将inew的揽收任务分派给车辆并对其行车路径进行重新编排.记v(k)0(k)0为车辆k(k∈K)在tnow时刻所在位置,它将处于三种可能状态,即等待状态、行驶状态、揽收状态.车辆k在点v(k)0(k)0处需滞留时间hv(k)0后方可离开,在揽收状态时,hv(k)0表示在揽收快件时继续滞留的时间,在等待状态或行驶状态时hv(k)0=0.在将inew的揽收任务分派给车辆之前,记P(k)为车辆k接下来的行车路径,lk为其路长,Ik表示包含于P(k)中的快件集合.在SQM策略下,P(k)的最后一个点为收发站vend.假定快件揽收任务一旦被分派后便不能被改派给其它车辆,则将快件inew的揽收任务被分派给车辆k时,该车在tnow时刻之后的行车路径须满足如下约束条件:∑j∈Ι′k∑j∈I′kxv(k)0,j=1(1)∑j∈Ι′k∑j∈I′kxi,j=1,i∈I′k(2)∑i∈Ι′k∑i∈I′kxi,u-∑j∈Ι′k∑j∈I′kxu,j=0,u∈I′k(3)∑i∈Ι′k∑i∈I′kxi,vend=1(4)tnow+hv(k)0+t(v(k)0,j)-M(1-xv(k)0,j)≤s(k)j(k)j,j∈I′k(5)s(k)i(k)i+hi+t(i,j)-M(1-xi,j)≤s(k)j(k)j,i∈I′k,j∈I′k(6)s(k)i(k)i≥0,i∈I′k(7)s(k)i(k)i+hi+t(i,vend)-M(1-xi,vend)≤s(k)vend(k)vend,i∈I′k(8)0≤s(k)vend(k)vend≤T(9)xi,j∈{0,1},xi,vend∈{0,1},xvk0,j∈{0,1},i,j∈I′k(10)其中,I′k=Ik∪{inew},s(k)j(k)j为车辆k揽收快件j的开始时刻,s(k)vend(k)vend为车辆k返回收发站vend的时刻,hi为快件i的揽收受理时间,t(i1,i2)为从点i1直达点i2的行车时间,M为充分大的正数.约束(1)—(4)表示车辆k从点v(k)0(k)0开始,在揽收I′k中的所有快件后,最后返回收发站vend;约束(5)—(7)为车辆k揽收快件j的时间约束;约束(8)—(9)为车辆返回收发站vend的时间约束;约束(10)定义决策变量为0-1变量.该问题的最小化目标函数为:λ1z1+λ2z2+λ3z3(11)z1=max{0,s(k)vend(k)vend-tlast}(12)z2=l′k-lk(13)z3=maxv∈Κ{nv}-minv∈Κ{nv}(14)式(11)中,λ1、λ2、λ3为非负权重;式(12)中,tlast表示在插入inew之前所有车辆返回收发站vend的最后时刻;式(13)中,z2表示在车辆k的行车路径中插入inew后所增加的路长,其中l′k=∑j∈Ι′kd(v(k)0,j)xv(k)0,j+∑j∈Ι′kd(i,j)xi,j+∑i∈Ι′kd(i,vend)xi,vend,d(i1,i2)表示从i1点直达点i2的路长;式(14)中,z3表示将inew分派给车辆k之后,在所有车辆中分派给各辆车的快件数的最大偏差,其中nv表示分派给车辆v的快件数.如果分派车辆k(k∈K)揽收快件inew时不存在满足约束(5)—(9)的行车路径,则定义z1=∞,z2=∞,z3=∞.2最优模型的确定上述问题的算法分为两个阶段:第一阶段,分派车辆揽收快件inew;第二阶段,应用2-opt法,以路径最短的目标对揽收快件inew的行车路径进行优化调整.式(11)是通过对三项完全不同的内容进行加权组合而构成的.对于这类权重,很难做出具有实际意义的解释,因而不容易操作.为此,本文改用分层次多目标优化方法.分层次多目标优化中,只有在高层目标已满足的基础上,才能考虑低层目标;在考虑低层目标时,则不允许违背已满足的高层目标.这种不同层次目标间的优先性可用优先因子Pl来表示,其关系为Pl≫Pl+1,即Pl层目标优先于Pl+1层目标.确定z1、z2和z3优先因子的步骤如下:第1步,对车辆k(k∈K),应用最小成本插入法(即路径最短准则)将快件inew插入p(k),计算z1、z2和z3,其值分别记为z(k)1、z(k)2和z(k)3.记K0={k|z(k)1<∞,k∈K},它表示快件inew的可分派车辆集合.第2步,如果K0=ϕ,表明添加快件inew的揽收任务将使揽收所有快件的最后时刻要晚于截止时刻T,此时,要么放弃该快件,要么将其推迟到下一个周期;否则,进入第3步.第3步,记Kg={k|z(k)g≤αg,k∈K0},g=1,2,3,α1、α2和α3为预设正参数.然后,根据图1所示的规则,确定z1、z2和z3的优先因子.记与优先因子P1、P2和P3相对应的目标分别为zr1、zr2和zr3,揽收快件inew的车辆为k*,其中,{r1,r2,r3}为{1,2,3}的某个排列.根据分层次多目标优化准则,则有k*∈{k|z(k)r3=minv∈≈Κz(v)r3,k∈≈Κ},其中≈Κ={k|z(k)r3=minv∈≈Κz(v)r3k∈∼Κ},˜Κ={k|z(k)r1=minv∈Κ0z(v)r1k∈Κ0}.3路长和无道距离选取Solomon针对带时间窗的车辆路径问题(VRPTW)而设计的100个点规模的56个问题实例,用于测试检验相关算法的计算效果,被国际上所公认.这些问题实例包括3类:R类、C类和RC类.其中,R类实例的顾客点按均匀分布产生;C类实例的顾客点首先被等分为多个组,每组顾客点在一个子区域内按均匀分布产生;RC类实例首先将一部分顾客点在整个区域内按均匀分布生成,再将剩余的顾客点等分为多个组,每组顾客点在一个子区域内按均匀分布产生.与VRPTW相比较,快件揽收车辆路径问题中的快件对应于顾客点、快件的产生时刻对应于顾客点的服务时间窗下限,并且有两个约束是不用考虑的,即车辆载重限制和顾客点的服务时间窗约束.现取参数,α1=20,α2=20、α3=5分析路长和揽收所有快件的最后时刻对|K|的敏感性.表1显示计算结果(说明:为了便于比较分析,计算中忽略了车辆行车时间窗的约束,避免出现一些快件由于无法在规定时限内揽收而被抛弃的情况).在|K|的不同取值下,应用上述算法求出快件揽收车辆路径问题实例的启发式解.表1中,对每一类实例,列出了路长和快件揽收最后时刻的平均值,其中后者用斜体字表示.结果表明:随着|K|的增大,路长和快件揽收最后时刻分别呈上升和下降的趋势;路长的趋势特征随|K|的增大逐渐由强变弱,其上升幅度由最初的24%逐步降到3%;快件揽收最后时刻的趋势特征在|K|较小时下降幅度较大,并随|K|的增大趋于平缓,其下降幅度由最初的44%降到7%.这主要是由于当车辆增多时,一方面可将快件揽收的最后时刻提前,另一方面则由于快件数相对较少而造成车辆需要多次往返于收发站,直接增加了路长.另外,车辆工作量平衡的要求也将在车辆数较多时导致路长的增加.当车辆过多时,继续增加车辆数就不再使路长和快件揽收最后时刻发生显著变化.据此,可确定出一个合适的车辆数.