快递服务动态车辆路径问题的多目标优化模型

快递服务动态车辆路径问题的多目标优化模型

近年来，动态车辆路径问题（dap）成为研究的热点。v浦模型可以用于包裹邮件、出租车服务、急救维修、急救等。车辆驾驶员应随时根据当前信息调整线路，并随时根据当前信息调整线路。20世纪90年代以前的研究已经结束。chen等人研究了基于时间窗口的动态车辆生成方法。伯里等人研究了基于在线交通信息的dvp。基于flaischmann等人的研究开发基于在线交通信息的dvp。bent等人提出了基于场景的随机信息计划方法。胡明伟等人提出了基于纪念场景的高效启动算法。刘世新等人研究了基于dvp的局部搜索算法。本文以与快递服务相关的动态车辆路径问题为研究对象,将其描述成带时间窗口的动态旅行修理员问题,提出包含最大化服务客户数、最小化客户等待时间和最小化总旅行时间的多目标优化模型,开发了改进的ChainedOr-opt局部搜索算法.1dvrp的特性,主要体现依照Psaraftis的定义,如果问题的信息(输入)是在决定路径的同时才为决策者所知晓或者更新,VRP就是动态的;相反,如果所有输入在决定路径之前就都已知并且随后不发生变化,VRP就是静态的.DVRP的特性主要体现在如下方面:①时变性和随机性显著.DVRP的输入信息都是时间的函数,即客户需求、车辆位置和状态、路网交通状况等都是随时间变化的,而且其变化规律是随机的,无法事先预知,已制定的路径计划需要实时优化和调整;②信息实时更新.DVRP中的信息实时更新且反映在优化进程中,路线计划需根据更新的信息做出重新优化;③目标函数复杂.DVRP的目标函数要复杂得多,需要根据具体问题选择适当的目标函数;④实时响应.DVRP要求实时响应,路线重新优化过程要求在很短的时间内完成,并将新的任务指派到司机,因此对优化算法和支撑技术提出了比静态VRP更高的要求.1.1节点市场的drp体本文重点研究与快递服务相关的动态车辆路径问题,即带时间窗口的动态旅行修理员问题(dynamictravelingrepairmanproblemwithtimewindows,DTRPTW).其实际应用背景是快递员从客户所在位置收集信件和小包裹,然后将其运回到邮件处理站.其动态体现在并非所有客户都在路线构造前为决策者所知,而且在任务执行过程中新出现的服务请求必须被立即安排到已有的服务路线中.DTRPTW定义为,有向图G=(N,A)上,N={0,1,2,...,n}代表包括车场0和客户位置(N0})的点集;A为N内每对节点最短路径的弧集;弧(i,j)∈A的最短路径旅行时间为tij;对每一个节点i∈N,都有一个时间窗口[ei,li];ei和li分别为窗口的开放和关闭时间.定义D⊂N0}为动态客户集,要求提取货物的位置和时间窗口只有在其请求到达后才知道.定义P⊆N0}为优先客户集,希望提取货物的时间与时间窗口的开放时间尽可能接近,即愿意当时间窗口开放后有最短的等待时间.令发出请求事先已知的客户为已知客户,记作(N-D)0},DTRPTW找到一个起点和终点都是车场0的旅行线路τ,满足:①在节点i∈N0}初始,提取服务满足时间窗口[ei,li],即服务开始的时间bi满足ei≤bi≤li;②在每个节点i∈N0},如果车辆到达的时间ai比ei早,只能等待时间窗口开始,在每个点有一定的当场服务时间si;③车辆路线只能在客户位置点更新,即车辆不能在两个节点间旅行的时候变更目的地.DTRPTW要优化多目标包括:①最小化总旅行时间O1.采用总旅行时间衡量运营费用,以寻找具有最小旅行时间的路径,即O1=min∑(i‚j)∈τAtij(1)Ο1=min∑(i‚j)∈τAtij(1)其中,τA是一个组成车辆路径τ的弧集.②最小化客户等待时间O2.客户等待时间直接关系到对服务质量的感受,因此要安排访问客户的顺序以保证所有客户的总等待时间最短,即O2=min∑i∈P(bi−ei)(2)Ο2=min∑i∈Ρ(bi-ei)(2)其中,P是N0}的子集或等于N0}.③最大化服务客户的总数O3.受系统限制,某客户可能被拒绝服务,因此提升客户满意度需要增加服务客户的总数,O3=max|τC|(3)Ο3=max|τC|(3)其中,τC为被车辆路线τ访问的客户集合.1.2基于最晚行动策略的车辆路线改进考虑到快递服务的特性,多目标DTRPTW采用基于词典式的排序方法来构造求解算法.最小化被拒绝的客户数给予最高优先级(或者最大化服务的客户数),最小化优先客户的等待时间给予次高优先级,最后是最小化总旅行时间,也就是O3优先于O2,O2优先于O1.采用这样的排序策略是考虑到快递服务行业的现状,就是客户的满意度(服务的客户数最大化并且客户等待时间降低)比单纯的运营费用最小化(最小化旅行时间)更重要.求解多目标DTRPTW采用基于事件驱动的算法,如图1,即只有当新的事件产生,即出现新的客户请求时,路径方案才进行更新.流程由如下步骤组成:①根据已知客户的信息创建初始路线方案.利用已知客户的信息创建初始车辆路径降级为一个多目标的TSPTW(travelingsalesmanproblemwithtimewindows).客户等待时间最小化和旅行时间最小化各自按照词典式的顺序得到考虑,先通过一个修改的I1插入过程创建初始路线,然后通过ChainedOr-opt过程进行改进;②根据该客户提出服务的时间更新当前的路线方案.车辆路径依据最晚行动策略更新,如果驾驶员在下一个计划的目的地预计要等待一些时间(也就是如果立刻离开当前位置,将会在下一位置时间窗口开始前到达),就安排驾驶员在当前位置等待;③为纳入新客户进行局部改进.如果新动态客户的服务请求不能被直接插入到已有的车辆路线中,就需要启动局部的改进过程修改车辆路线,使其可被纳入.这一局部改进过程按如下方法操作:随机从车辆路线中去掉一些计划停靠点,然后重新在路线方案不同位置安排(尽量不同于去掉前所在位置),检查动态客户能否被插入到当前的车辆路线中,如果能够则终止,否则继续;用ChainedOr-opt改进当前的车辆路线,如果动态客户能被插入则停止,否则拒绝这个动态客户;④ChainedOr-opt改进过程.在多目标优化改进车辆路线的步骤⑤中(如图1),迭代地运用改进的Or-opt局部搜索,若局部最优达到,程序就产生一个小扰动以脱离局部最优.步骤为:置迭代指标q=0和经典Or-opt过程一样,在当前的车辆路线中检查3个、2个或1个连续节点改变位置,如果从时间窗口约束这种改变位置可行,且从多目标评价角度改进了当前的车辆路线,就确认.若局部最优到达,即不能通过Or-opt改变来得到改进,则令q:=q+1;若q>α(事先设定参数),输出当前最好的解,否则继续执行下一步;随机从车辆路线中去掉一些计划停靠点,重新安排在不同位置(尽量不同于去掉前所在位置),继续前述操作.通过修改解的评价函数,改进ChainedOr-opt过程能处理多目标DTRPTW中词典式的目标排序模型,与VRP中经常使用的禁忌搜索算法相比,ChainedOr-opt在计算上更有优势,其计算量可用参数α控制(若希望算法迭代次数为20次,则令α=20),且该法可得到与禁忌搜索算法同样高质量的解.2计算和分析2.1客户时间窗口生成为检验多目标DTRPTW优化模型及算法,设计了两组实验,如表1.这些实验在两类基准问题的数据上进行.第一类由TSPTW的rbg现实世界数据组成,由Norbert等引入.第二类由Solomon为VRPTW提供的基准问题得来,由于Solomon数据为多辆车设计,其时间窗口不适合单车路径问题的实验场景,这里只采用Solomon数据的旅行时间和服务时间,客户时间窗口的生成基于Mingozzi等研究对称TSPTW提出的方法.为仿真动态路径场景,动态和优先的客户以及动态客户出现的时间都是随机生成的.动态客户集D在N0}中随机选择,概率上偏向那些有较晚开始时间的,优先客户P在(N(D)0}中随机选择,动态客户i发出服务请求的时间ri根据在区间(c1×ei,c2×ei]的均匀分布随机生成,c1和c2(0≤c1≤c2≤1)是两个参数.2.2实验与结果分析2.2.1基于等待时间的旅行时间生成第一组实验设计用来检验对时间窗口约束较松的DTRPTW多目标优化模型及算法,由于时间窗口足够宽,将没有任何客户被拒绝服务,因此对这一组实验只需要检验优先客户的等待时间和总旅行时间两个目标.表1创建了两类数据,第一类基于不对称的rbg问题,即rbg92a,其旅行时间、服务时间和时间窗口都未作改变,第二类源于Solomon的基准问题,包括6组数据集,即R1、R2、C1、C2、RC1和RC2,由于R1和R2、RC1和RC2中的旅行时间与服务时间相同,分别命名为R和RC.C1和C2的旅行时间和服务时间虽然不同,但以同样手段生成,只选择C1,命名为C.基于Solomon问题构造的时间窗口根据前面实验设计部分所述的方法随机生成.表1中rbg和Solomon问题的动态客户和优先客户也是根据前面实验设计部分所述的方法随机选择.对于每一个子类问题,例如在rbg92a中,|D|=20‚|P|=20|D|=20‚|Ρ|=20,又随机生成5个例子.表1为对5次运行的平均值.为检验多目标优化算法的质量,这些结果又与“后验”的TSPTW解进行比较.“后验”的解基于旅行时间最小化的目标用ChainedOr-opt启发式算法得到,假定所有与问题有关的信息都已知,而在动态场景下当计划路径在执行过程中动态客户才出现.因此,TSPTW的解就提供了动态场景下的总旅行时间的下界.表1中,总旅行时间表示相应解的路径的总旅行时间,等待时间为优先客户的总等待时间.由表1可见,多目标优化的总旅行时间仅有少许增长,而客户等待时间得到明显改进.对rbg92a类问题,平均等待时间的平均值由6579下降至558.8,降幅为91.5%;对R、C和RC类问题,平均等待时间的平均值由9651.7下降至712.7,降幅为92.6%.2.2.2动态车辆路径模型第二组实验用来检验高度动态和时间窗口约束较紧的多目标DTRPTW优化,半数例子的动态客户出现的时间比时间窗口开始时间的80%晚,也就是[c1,c2]=[0.8,1],相当于很紧的时间窗口.用多目标优化方法得到的DTRPTW的解与通过单目标最小化旅行时间得到的解在表2中进行了比较.表2显示,在动态车辆路径问题中考虑多目标的效益非常明显.例如,在Solomon问题的例子中,平均的多目标DTRPTW结果中只有0.2个被拒绝客户,而在旅行时间最小化的单目标模型中平均被拒绝的客户达到4.4个.且多目标模型平均降低等待时间超过34%,尽管旅行时间稍有增长.对于rbg类问题从被拒绝的客户的角度没有出现明显的不同,因为rbg类问题例子的时间窗口对高度动态的场景仍然足够宽.基于事件驱动的多目标优化模型和算法本文以与快递服务相关的动态车辆路径问题为研究对