基于两阶段求解策略的动态电动车辆路径优化研究
2022-09-13葛显龙竹自强金渊智
葛显龙, 竹自强, 金渊智
(1.重庆交通大学 经济与管理学院,重庆 400074; 2.重庆交通大学 智能物流网络重庆市重点实验室, 重庆 400074; 3.西南交通大学 经济管理学院,四川 成都 610031; 4.三门峡职业技术学院 信息传媒学院,河南 三门峡 472000)
0 引言
电动车具有节能、清洁以及低噪音的特点。近年来,一些物流企业开始使用电动车进行配送,比如,京东、中国邮政以及菜鸟物流。但是,与传统燃油车不同,电动车由于其续航限制,往往需要进行途中充电或者换电,在一定程度上增加时间成本及路径成本,因此需要制定合理的充/换电策略,以保证配送成本最小化。此外,还有一些现实因素应该被考虑,(1)客户的动态需求,在实际配送过程中,客户的订单需求可能发生变化,此时企业能否在保证经济性的基础上做出快速响应以提升客户体验将变得至关重要。(2)充/换电站的拥堵情况,由于目前公共充/换电设施的数量和密度较小,易引发拥堵而提高时间成本,因此如何结合当前充/换电站设施制定合理的配送计划是电动汽车在物流配送作业中的关键。
动态车辆路径问题[1](Dynamic Vehicle Routing Problem,DVRP)的研究主要集中在新增客户的动态问题。此类问题的研究已比较成熟,Kuo等[2]将服务客户数量最大化和客户平均等待时间最小化作为优化目标建立了DVRP模型。Okulewicz和Madziuk[3]将DVRP扩展为多配送中心的动态车辆路径问题,建立带容量和工作时间约束的数学模型。Ghannadpour等[4]针对带模糊时间窗的DVRP建立了一种最小化车队规模、路径成本及等待时间的多目标模型。Huang等[5]研究了确定性和随机流量条件下建立了TDVRP-PF模型;Çimen和Soysal[6]研究了具有随机车速的时变车辆路径问题。动态需求的车辆路径问题常常采用定期更新策略,将每个工作日划分为若干时间周期,按时间周期将动态需求问题转化成一系列静态需求问题[2~4],从而将动态问题静态化。为了保证问题求解的高效性,已有文献多采用遗传算法[7,8]、粒子群算法、蚁群算法[9,10]等启发式算法求解此类问题。
关于电动车辆路径问题(Electric Vehicle Routing Problem,EVRP)的研究主要集中在非线性能耗、充电策略以及考虑换电站选址的EVRP,Lin等[11]建立了最小化旅行时间、能耗成本以及车辆使用成本为目标函数的EVRP模型。Desaulniers等[12]研究了四种充电策略。Goeke和Schneider[13]提出了一种非线性放电模型,并考虑了车辆速度、装载量等对电池放电的影响。Yang和Sun[14]建立了最小化路径成本和选址成本的BSS-EV-LRP模型。Hof等[15]设计了改进的自适应变邻域搜索(AVNS)算法来求解BSS-EV-LRP模型,并发现AVNS平均解的质量具有较强的鲁棒性,能够较好地减少解中构造的BSSs的数量。Zhang等[16]提出了基于随机需求的BSS-EV-LRP模型。
综上,大部分动态车辆路径问题的研究集中在传统燃油车辆,而在电动车辆路径问题忽视了客户需求的动态性、电池续航以及充/换电设施的拥堵成本等现实因素。为此,提出了基于分阶段求解策略,并建立两阶段的EVRP模型,其中第一阶段针对静态客户建立了静态EVRP模型,第二阶段建立DEVRP模型以更新路径。提出了换电站及动态客户插入成本公式,并设计CW-TS混合启发式算法来求解静态模型,贪婪算法求解动态模型。最后,通过算例验证了模型与算法的可行性与有效性。
1 问题描述
基于分阶段求解策略的DEVRP,可以描述如下:第一阶段静态调度,根据初始的静态客户订单,规划出初始配送方案,0时刻车辆从配送中心出发按此路径依次访问客户点并开始接收新订单,接收时长为t(即信息中心会在时间窗[0,t]接收新的客户需求)。第二阶段动态调度,在t时刻由于所有的动态客户信息已知,可将动态网络转换成静态网络,此时根据车辆当前的状态插入相应的动态客户从而完成路径更新。为了体现客户信息随时间的变化,引入时间轴的概念,如图1(a)~(b),图1(a)表示第一阶段,系统在0时刻根据静态客户需求规划了初始路径,同时开始接受新的客户请求。图1(b)表示t时刻车辆的状态以及新增的所有动态客户,此时网络的所有信息均已知,因此动态网络坍缩成静态网络,并将t时刻车辆即将达到或正好位于的那些客户点、换电站、配送中心称为关键点,如图1(b)中的客户点9、3、6。第二阶段将关键点作为新的起点,将剩余的未服务的静态客户以及动态客户作为新的客户集合,重新规划路径,得到结果如图1(c)。由于动态客户2距离路径r2较远使得其插入会引起新增换电次数至少两次,因此路径2在该服务日内拒绝服务该动态客户点,而将服务时间推迟到下一服务日。对于路径1和路径3,都接受了新增动态需求客户,结果如图1(d)。
2 数学模型
2.1 符号说明
2.2 建立静态电动车辆路径问题模型
现以最小化路径成本及车辆使用成本为目标函数,建立EVRP混合整数规划模型如下:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
xijk,yki,xok∈{0,1},∀i,j,o∈V,∀k∈K
(15)
式(1)为目标函数;式(2)保证节点流入等于流出;式(3)限制车辆使用数量,保证派出的车辆数不大于配送中心拥有量;式(4)车辆服务的客户数不大于总客户数;式(5)保证每条路线上客户的总需求不大于车辆的最大装载;式(6)闭环约束,保证车辆从配送中心出发且最终回到配送中心;式(7)每个客户只能被访问一次;式(8)当电动车离开配送中心时为满装载;式(9)表示电动车离开i点时的剩余装载;式(10)表示电动车到达i点时的剩余装载;式(11)电动车在客户点停留时不损耗电量;式(12)保证车辆离开配送中心和换电站时电池为满电;式(13)和(14)表示车辆在个节点之间的电量约束;式(15)为0-1变量。
2.3 建立动态EVRP数学模型
以配送成本最小化为目标,建立t时刻配送优化的混合整数规划模型,具体如下:
(16)
式(16)表示目标函数,即使得插入路径成本最小化。式(17)表示对动态距离属性的约束,即单独插入某个动态客户时不能引起新的换电次数超过一次。式(18)和(19)表示关键点只能发出车辆并最后回到配送中心。式(20)表示需求约束,即插入的动态客户的需求不能超过该条路径车辆的剩余装载。式(21)表示未服务的静态客户及动态客户的流平衡。式(22)电动车离开换电站时处于满电。式(23)和(24)表示车辆在个节点之间的电量约束。式(25)每个动态客户或者未服务静态客户只能被访问一次。式(26)表示电动车离开i点时的剩余装载。式(27)表示电动车到达i点时的剩余装载。
3 求解算法设计
针对静态EVRP模型,设计了改进的节约里程算法与禁忌搜索算法(CW-TS)的两阶段混合启发式算法,其中由CW得到静态阶段初始解,再通过TS优化初始解,从而获得静态阶段的最优解。第二阶段由贪婪算法来插入动态客户,生成动态EVRP模型的最优解。
3.1 第一阶段模型求解算法
(1)节约里程算法生成初始解
为了方便矩阵运算采用自然数编码,如:[0-1-2-3-4-12-0-5-6-7-8-11-0-9-10-0],表示第一阶段的一个可行解,其中0为配送中心,1-10为静态客户,11-12为换电站,而[0-1-2-3-12-4-13-0-5-6-7-11-8-14-0-9-15-10-0]表示第二阶段的一个可行解,13-15表示动态客户。利用CW算法在不考虑装载约束、需求约束及车辆里程约束的条件下得到配送中心与所有静态客户点的旅行商问题(TSP)解,与传统的节约里程算法不同,我们在得到TSP解后还需采用两边逐次修正算子对其进行再优化;设计一种分车算子将TSP转化为传统车辆路径问题的解(VRP),此时在不考虑车辆里程约束的条件下得到了配送中心与所有静态客户点的VRP解,对于每条子路径采用两边逐次修正算子对其进行再优化。
(2)TS算法输出第一阶段的解
将由CW得到的VRP解记为S,通过换电站插入规则将S变为可行解后计算其目标函数值并赋值给初始解SS,当前解DS和最优解BS;设定最大迭代次数L和最优解连续未变化次数P;给出禁忌表长度TL;每一代产生的邻域候选解个数N。
采用了新的邻域产生方法,每一次迭代随机选择四种邻域交换算子(逆序邻域交换算子、1-opt、2-opt、3-opt)中的一种对S做邻域变换产生N个候选解,对每一个候选解用换电站插入规则使其变得可行并计算其目标函数,选择其中的最小值与BS对比,若其小于BS则触发特赦准则,并更新S,DS及BS,否则将产生该解的移动加入禁忌表,并更新S和DS,开始下一次迭代。迭代次数达到L或最优解连续未变化次数达到P,终止程序输出最优解。
3.2 贪婪算法求解第二阶段模型
在第二阶段的T0时刻,识别出每条子路径rk的关键点pk,记录每个pk的剩余载量及剩余电量。剔除关键点后的换电站并识别出潜在的动态客户插入位置,根据信息中心在时间窗[0,T0]内接收的动态需求先后顺序,依次尝试将动态客户插入到当前各子路径。
在T0时刻,首先将每条子路径rk中关键点Pk之后的换电站剔除,将剔除换电站后的路径称为krouting,对于krouting,关键点、未服务客户点以及配送中心之间形成动态客户潜在插入集M。将动态客户点i依次插入到这些潜在位置,并选取插入成本最小的位置为动态客户的插入点,每成功接受一个动态客户则相应的krouting会被更新,定义每条krouting的初始路径长度为L,L也会随之更新。
(28)
其中β1+β2+β3=1,β1,β1,β3≥0
(29)
(30)
(31)
4 算例分析
本节包括一个仿真实验及其结果分析。实验环境基于MATLAB R2013a平台。随机生成一个包含25个静态客户(编号1~25)、10个动态客户(编号32~41)以及6个换电站(编号26~31)的算例,来对比单独使用CW和TS得到的结果,与使用CW-TS混合启发式算法得到的结果。算法使用的具体参数见表1,客户详细信息见附表1。
表1 算法参数
针对每种算法运行10次程序得到结果如表1。路径长度用L表示,车辆数用K表示,总成本用C表示,计算时间用T(S)表示。
表2 算法对比分析
由表1,三种算法得到的最优解均用黑体突出。对于L,CW-TS算法给出解的路径长度最短,其解的平均值较CW结果降低了19.6%,较TS结果降低了17.4%;对于K,CW-TS与TS得到的结果均为4辆车,而CW得到的结果均为5辆车;对于C,CW-TS算法求得了最小值并且其解的平均值较CW结果降低了19.6%,较TS结果降低了16.7%;而计算时间,由于CW没有领域搜索的过程其计算时间最短且结果稳定,TS由于有禁忌搜索过程且初始解随机产生,造成其计算时间最长,CW-TS虽然也具有禁忌搜索过程,但是其初始解质量较好,使得其计算时间能保持在可行的范围。综上,CW-TS算法较CW、TS算法得到的结果在各方面都有明显优势,因此验证了CW-TS算法的可行性与有效性。动态客户加入前路径轨迹见图2(a),动态客户加入后的最终路径轨迹见图2(b),0表示配送中心,1~25表示静态客户,26~31表示换电站,32~41表示动态客户。
加入动态客户前的路径总长度为:655,总成本为:6953;加入动态客户后的最终路径长度为:747,总成本为:7872。如图所示,15、19、20、23为关键点,还存在26、27、29换电站未被使用,说明换电站插入策略是有效的。
5 总结
针对基于分阶段求解策略的动态电动车辆路径优化问题,建立了以最小化路径成本及车辆使用成本为目标函数的静态EVRP数学模型和动态EVRP数学模型,并设计了改进的CW-TS混合启发式算法以及贪婪算法对两阶段的模型进行求解。为了验证算法的有效性与可行性,首先通过中等规模的算例,并单独使用CW和TS得到的结果,与使用CW-TS混合启发式算法得到的结果进行对比,结果显示本文设计的算法获得了较优结果。