高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

基于自适应变邻域搜索的大规模电动车辆路径优化

    作者简介: 赵灿华(1995-),男,河南商丘人,硕士生,主要研究方向为车辆路径问题。E-mail:canhua_zhao@163.com;
    通讯作者: 侍洪波, hbshi@ecust.edu.cn
  • 中图分类号: O221.7; U116.2

Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search

    Corresponding author: Hongbo SHI, hbshi@ecust.edu.cn
  • CLC number: O221.7; U116.2

  • 摘要: 针对变邻域搜索在后期出现的在某些邻域内长时间无法找到更优的可行解的情况,提出了一种基于邻域选择概率自适应的变邻域搜索算法。该算法能够自适应调整在某个邻域进行搜索的概率,进而提高优化效率。对城市配送中的大规模电动车辆路径问题进行了建模分析,根据客户的地理位置、时间窗等信息设计了高效的初始解生成算法。使用片段交换、2-opt、relocation等邻域算子进行自适应变邻域搜索。最后使用不同规模的实际数据对算法进行仿真验证,相比于传统的变邻域搜索算法,本文算法能更有效地跳出局部最优解,降低物流成本。
  • 图 1  AVNS算法流程图

    Figure 1.  Flow chart of AVNS algorithm

    图 2  路径片段交换

    Figure 2.  Route segment exchange

    图 3  交叉操作

    Figure 3.  Cross operation

    图 4  重定位操作

    Figure 4.  Relocation operation

    图 5  一步更新AVNS下的概率向量收敛曲线

    Figure 5.  Probability vector convergence curves under one stepupdate

    图 6  阶段更新AVNS下的概率向量收敛曲线

    Figure 6.  Probability vector convergence curves under phase upalate

    表 1  车型信息

    Table 1.  Vehicle type information

    VehicleMaximum volume /m3Maximum weight /kgMaximum recharge mileage /kmFixed cost /CNYUnit cost /(CNY·km−1
    Type 1122 00010020012
    Type 2162 50012030014
    下载: 导出CSV

    表 2  客户样例

    Table 2.  Customer sample

    Customer IDLocation/kmService typeWeight /kgVolume/m3Time window/h
    1(10,10)Pick151[8.5,9.0]
    2(20,15)Delivery400.45[14.2,15.0]
    下载: 导出CSV

    表 3  实验结果

    Table 3.  Experimental result

    Customer scaleACSSAVNSAVNS with one step updateAVNS with phased update
    1 100275 699.87243 005.19242 097.10241 317.22(0.32%)241 274.73(0.34%)
    1 200308 882.92273 290.14271 857.66270 673.45(0.44%)271 039.10(0.30%)
    1 300305 021.27269 940.70269 681.19267 968.52(0.64%)268 770.87(0.34%)
    1 400397 603.40357 417.85356 075.16355 452.63(0.17%)354 097.12(0.56%)
    1 500407 020.35362 772.20362 595.07361 568.38(0.28%)361 694.37(0.25%)
    下载: 导出CSV
  • [1] DAVIS B A, FIGLIOZZI M. A methodology to evaluate the competitiveness of electric delivery trucks[J]. Transportation Research Part E: Logistics and Transportation Review, 2013, 49(1): 8-23. doi: 10.1016/j.tre.2012.07.003
    [2] FENG W, FIGLIOZZI M. An economic and technological analysis of the key factors affecting the competitiveness of electric commercial vehicles: A case study from the USA market[J]. Transportation Research Part C: Emerging Technologies, 2013, 26: 135-145. doi: 10.1016/j.trc.2012.06.007
    [3] HORI Y. Future vehicle driven by electricity and control-research on four-wheel-motored UOT electric march II[J]. IEEE Transactions on Industrial Electronics, 2004, 51(5): 954-962. doi: 10.1109/TIE.2004.834944
    [4] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. doi: 10.1287/mnsc.6.1.80
    [5] LENSTRA J K, KAN A H G R. Complexity of vehicle routing and scheduling problems[J]. Networks, 1981, 11(2): 221-227. doi: 10.1002/net.3230110211
    [6] LAPORTE G, HÉLÈNE MERCURE, NOBERT Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks, 1986, 16(1): 33-46. doi: 10.1002/net.3230160104
    [7] CHRISTOFIDES N, MINGOZZI A, TOTH P. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[J]. Mathematical Programming, 1981, 20(1): 255-282. doi: 10.1007/BF01589353
    [8] PAESSENS H. The savings algorithm for the vehicle routing problem[J]. European Journal of Operational Research, 1988, 34(3): 336-344. doi: 10.1016/0377-2217(88)90154-3
    [9] 于坤杰, 王昕, 王振雷. 基于反馈的精英教学优化算法[J]. 自动化学报, 2014, 40(9): 1976-1983.
    [10] TAILLARD E. A tabu search heuristic for the vehicle routing problem with soft time windows[J]. Networks, 1996, 44(3): 469-477.
    [11] 张海刚, 顾幸生, 吴燕翔. 改进的粒子群算法及其在带软时间窗车辆调度问题中的应用[J]. 华东理工大学学报(自然科学版), 2009, 35(5): 774-778. doi: 10.3969/j.issn.1006-3080.2009.05.022
    [12] 刘志硕, 申金升, 柴跃廷. 基于自适应蚁群算法的车辆路径问题研究[J]. 控制与决策, 2005, 20(5): 562-566. doi: 10.3321/j.issn:1001-0920.2005.05.018
    [13] JIANG D. A study on the genetic algorithm for vehicle routing problem[J]. Systems Engineering-Theory & Practice, 1999, 19(6): 40-45.
    [14] 吴胜昔, 刘威, 卢文建, 等. 一类面向仓库车辆路径优化的改进禁忌搜索算法及其应用[J]. 华东理工大学学报(自然科学版), 2018, 44(4): 581-587.
    [15] HANSEN P, MLADENOVIĆ N. Variable neighborhood search: Principles and applications[J]. European Journal of Operational Research, 2001, 130(3): 449-467. doi: 10.1016/S0377-2217(00)00100-4
    [16] SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520. doi: 10.1287/trsc.2013.0490
    [17] SCHNEIDER M, STENGER A, HOF J. An adaptive VNS algorithm for vehicle routing problems with intermediate stops[J]. OR Spectrum, 2015, 37(2): 353-387. doi: 10.1007/s00291-014-0376-5
    [18] WEI L, ZHANG Z, LIM A. An adaptive variable neighborhood search for a heterogeneous fleet vehicle routing problem with Three-dimensional loading constraints[J]. IEEE Computational Intelligence Magazine, 2014, 9(4): 18-30. doi: 10.1109/MCI.2014.2350933
    [19] BRUGLIERI M, PEZZELLA F, PISACANE O, et al. A matheuristic for the electric vehicle routing problem with time windows[J]. Mathematics, 2015.
    [20] KYTÖJOKI J, NUORTIO T, BRÄYSY O, et al. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems[J]. Computers & Operations Research, 2007, 34(9): 2743-2757.
    [21] POLACEK M, BENKNER S, DOERNER K F, et al. A cooperative and adaptive variable neighborhood search for the multi depot vehicle routing problem with time windows[J]. Business Research, 2008, 1(2): 207-218. doi: 10.1007/BF03343534
    [22] PARASKEVOPOULOS D C, REPOUSSIS P P, TARANTILIS C D, et al. A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows[J]. Journal of Heuristics, 2008, 14(5): 425-455. doi: 10.1007/s10732-007-9045-z
    [23] BRIMBERG J, HANSEN P, MLADENOVIC N. Attraction probabilities in variable neighborhood search[J]. Journal of Operation Research, 2010, 8(2): 181-194.
    [24] STUTZLE T, HOOS H. The MAX-MIN ant system and local search for the traveling salesman problem[C]//Proceedings of IEEE International Conference on Evolutionary Computation and Evolutionary Programming. USA: IEEE, 1997: 309-314.
    [25] KIRKPATRICK S, JR G C, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680. doi: 10.1126/science.220.4598.671
  • [1] 王学武夏泽龙顾幸生 . 基于事件触发的自适应邻域多目标进化算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181120005
    [2] 张逸秋吴诗勇吴幼青黄胜高晋生 . 城市污泥水热液化过程及特征. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190107001
    [3] 张剑超杜文莉覃水 . 基于新型自适应采样算法的催化重整过程代理模型. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180915001
    [4] 杨祺刘士荣 . 多自主车辆队列跟随控制器设计. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190118001
    [5] 徐震浩周畅张凌波顾幸生 . 柔性作业车间的成套订单调度问题. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181109001
    [6] 曹移林余炜 . 平行三阶段流水作业问题的近似算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180206001
    [7] 殷飞宇金晶王行愚 . 基于多相关性的导联前向搜索算法用于运动想象分类. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190901002
    [8] 黄佳琳张丫丫顾幸生 . 基于改进生物地理学优化算法的分布式装配置换流水车间调度问题. 华东理工大学学报(自然科学版), doi: 10.14133/j.cnki.1006-3080.20190828001
  • 加载中
图(6)表(3)
计量
  • 文章访问数:  1336
  • HTML全文浏览量:  340
  • PDF下载量:  6
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-07-30
  • 网络出版日期:  2019-12-16

基于自适应变邻域搜索的大规模电动车辆路径优化

    作者简介:赵灿华(1995-),男,河南商丘人,硕士生,主要研究方向为车辆路径问题。E-mail:canhua_zhao@163.com
    通讯作者: 侍洪波, hbshi@ecust.edu.cn
  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237

摘要: 针对变邻域搜索在后期出现的在某些邻域内长时间无法找到更优的可行解的情况,提出了一种基于邻域选择概率自适应的变邻域搜索算法。该算法能够自适应调整在某个邻域进行搜索的概率,进而提高优化效率。对城市配送中的大规模电动车辆路径问题进行了建模分析,根据客户的地理位置、时间窗等信息设计了高效的初始解生成算法。使用片段交换、2-opt、relocation等邻域算子进行自适应变邻域搜索。最后使用不同规模的实际数据对算法进行仿真验证,相比于传统的变邻域搜索算法,本文算法能更有效地跳出局部最优解,降低物流成本。

English Abstract

  • 随着国家对电动汽车的大力推广,越来越多的物流车辆开始采用电动车。与常规的燃油车相比,电动车具有较低的污染排放和噪音,但同时也面临着续航里程短、充电时间长、充电桩少等问题[1-3],这使得电动车辆路径问题(Electric Vehicle Routing Problem, EVRP)的求解更加复杂。

    VRP[4]是典型的NP-hard问题[5]。在精确式算法研究方面,文献[6]使用分支定界法对VRP进行了建模求解,可求解260点的VRP。文献[7]使用k度中心树算法将原问题转化为3个易求解的子问题,然后进行求解。文献[8]提出了一种节约值计算方法,能够较好地生成车辆路径。对于组合优化问题,精确式算法常常无法在合理的时间内给出满意解,因此多采用启发式算法求解。文献[9]提出了一种反馈精英教学优化算法,通过引入反馈机制提高了算法的全局搜索能力,并将算法成功应用于背包问题。文献[10]使用禁忌搜索算法对带有随机需求的动态车辆路径问题进行了建模求解。文献[11]针对粒子群算法容易陷入局部极值的缺陷,提出了一种多相粒子群优化算法(Multi-phases Particle Swarm Optimization, MPSO),对带软时间窗的车辆路径问题进行了建模求解。文献[12]构造了一种求解VRP的自适应蚁群算法,能够有效地解决小规模的VRP。文献[13]在充分分析了既有启发式算法的基础上,构造了新型的染色体结构及操作算子,使用遗传算法对VRP进行了有效求解。文献[14]面向仓库车辆路径问题,对禁忌搜索算法进行了改进及应用。对于大规模的车辆路径问题,由于可行解空间极大,通常使用多种搜索算法混合的策略对问题进行求解,其中变邻域搜索(Variable Neighborhood Search,VNS)[15]是解决大规模车辆路径问题的有效方法。文献[16]将变邻域搜索和禁忌搜索算法结合起来,采用动态惩罚机制,求解了带时间窗的电动车辆路径问题。文献[17]将自适应大规模邻域搜索与变邻域搜索算法相结合,提出了一种自适应变邻域搜索算法求解带中间站的电动车辆路径问题,根据在不同抖动过程中的搜索表现来自适应调整抖动的邻域算子选择。文献[18]使用变邻域搜索对三维装箱问题下的车辆路径问题进行了求解。文献[19]研究了部分充电的EVRP-TW,提出了一种变邻域搜索分支的元启发式算法。文献[20]使用了一种改进的变邻域搜索算法对客户规模达到两万的超大规模车辆路径问题进行求解,其中利用引导局部搜索算法来跳出局部最优。文献[21]提出了两种并行协作方案,使用了一种协作自适应变邻域搜索算法求解了多车场带时间窗的车辆路径问题。文献[22]对混合车型的带时间窗的车辆路径问题进行了建模,并使用反应式变邻域搜索算法进行了求解。

    本文以京东物流为案例背景,对大规模带时间窗可回程取货的电动车辆路径问题(Electric Vehicle Routing Problem with Backhauls and Time Window, EVRP-BTW)进行了建模分析。利用客户时间窗、地理位置等信息构造了高效的初始解生成算法;针对传统变邻域搜索算法在后期出现优化效率降低的情况,提出了一种高效的自适应变邻域搜索算法(Adaptive Variable Neighborhood Search,AVNS),设计了新的邻域搜索算子,并结合经典的2-opt、relocation、cross-change等算子进行了变邻域搜索。最后,使用不同规模的实际脱敏数据验证了本文算法的有效性。

    • EVRP-BTW可以描述为:某城市配送中心有若干辆电动汽车,需要向$N$个客户进行服务,其中需要上午送货,下午回程取货。此外,城市中共有${N_{\rm c}}$个充电站,充电站的充电车位充足。设车辆访问地点为$i$,访问的地点可能是客户所在地、充电站或配送中心;每个地点$i$均有访问的时间窗$\left[ {{t_{{\rm s}i}},{t_{{\rm e}i}}} \right]$,时间窗为硬时间窗,若车辆提前到达则需要进行等待,每小时等待成本为${P_{\rm w}}$,对于充电站及配送中心则无时间窗约束;每个地点待装载的货物的质量和体积分别为${w_i}$${v_i}$,若地点$i$为充电站或配送中心,则对应货物的质量和体积都为0;地点$i$与地点$j$之间的距离为${d_{ij}}$。配送中心车辆数充足,车辆分为大小两种车型,大车型的车辆的载重、容积及行驶里程上限分别为${W_{\rm l}}$${V_{\rm l}}$${L_{\rm l}}$,小车型的车辆的最大载重、容积、行驶里程分别为${W_{\rm s}}$${V_{\rm s}}$${L_{\rm s}}$,大小车型充满电所用时间固定,均为Tc,每小时充电成本为${P_{\rm c}}$,每辆大、小车型的固定调度成本分别为${P_{\rm l}}$${P_{\rm s}}$,每千米行驶成本分别为${D_{\rm l}}$${D_{\rm s}}$

      用向量${{ r}_k}$表示$k$号车的行驶路径,其中元素${r_{ki}}$表示访问地点在路径${r_k}$中的顺序为$i$,令${r_{k0}} = 0$表示配送中心;${N_r}$为调用的车辆数目,也是路径的总数;${N_{rk}}$为路径$k$包含的地点总数(含客户、配送中心、充电站);${m_k}$k号车在上午服务的最后一个客户的顺序;${T_{{\rm C}k}}$$k$号车的总充电时间,${C_{kj}}$表示路径$k$中的第$j$个充电站在路径中的顺序;${l_k}$取值为0或1,若为1则说明$k$号车为大车型,若为0,则说明$k$号车为小车型;${b_{ik}}$取值为0或1,当$i$地点表示客户所在地时,若$i$地点被$k$号车服务,则${b_{ik}}{\rm{ = }}1$,反之${b_{ik}}{\rm{ = 0}}$;若$i$地点表示充电站或配送中心,则${b_{ik}}{\rm{ = }}0$;路径规划的总成本包含车辆固定调度成本、行驶成本、充电成本以及等待成本,以总成本最小为目标,可建立如下的数学模型:

      上述模型中,式(1)为目标函数;式(2)表明所有的客户需要被访问;式(3)保证了每名客户只能被一辆车服务一次;式(4)、式(5)为车辆上午送货行驶路径的质量和体积约束;式(6)、式(7)为车辆下午取货行驶路径的质量和体积约束;式(8)为电动车辆的里程约束,保证了车辆能够在电量耗尽之前到达下一个充电站;式(9)为每个客户的服务时间窗约束。

    • VNS算法是一种改进的局部搜索算法,尤其适合解决大规模的组合优化问题,它可以在搜索过程中通过邻域变换尽可能多地探索解空间,有效地跳出局部最优解。算法主要由两个部分组成:抖动过程(Shaking Procedure)和变邻域深度搜索过程(Variable Neighborhood Descent,VND)。Shaking的主要作用是使得算法能够在每次迭代之初,随机地从一个新的解出发进行搜索寻优,有利于算法跳出局部最优解。而在变邻域深度搜索过程中,算法会系统地改变搜索的邻域结构,不断地优化目标值。设Shaking所用的邻域集合为$\left\{ {{N^s}_1,{N^s}_2, \cdots ,{N^s}_{{n_s}}} \right\}$;变邻域深度搜索过程所用的邻域集合为$\left\{ {{N^v}_1,{N^v}_2, \cdots ,{N^v}_{{n_v}}} \right\}$$f\left( x \right)$表示可行解为$x$时的目标函数值。VNS算法的基本流程如下(最小化目标函数值):

      (1)构造初始解${x_0}$,令最优解${x_{\rm best}} = {x_0}$

      (2)若满足终止条件,转步骤(7);否则,随机地从${x_{\rm best}}$的某一邻域${N^s}$中选取解${x'}$作为变邻域深度搜索的初始解。

      (3)设$i = 0$,开始进行变邻域深度搜索。

      (4)在${x'}$${N^v}_i$邻域中进行局部搜索,得到局部最优解${x^{''}}$

      (5)若$f\left( {{x^{''}}} \right) < f\left( {{x_{\rm best}}} \right)$,则${x_{\rm best}} = {x^{''}}$$i = 0$;否则,$i + + $

      (6)若$i < {n_v}$,转到步骤(4);否则,转到步骤(2)。

      (7)输出${x_{\rm best}}$$f\left( {{x_{\rm best}}} \right)$

      在上述流程中,步骤(3)~步骤(7)为变邻域深度搜索过程;终止条件为是否达到最大无改进次数或者是否超过最长运行时间/最大迭代次数。

    • 在变邻域搜索的后期,往往会出现在某些邻域内长时间无法找到更优可行解的情况,此时对这些邻域过多地重复搜索会降低算法的优化效率。针对上述问题,本文提出的AVNS算法能够根据每个邻域的优化情况,自适应调整选择在某个邻域进行搜索的概率,从而减少算法在一些长时间无改进邻域的搜索时间,提高算法的优化效率。AVNS算法包括一步更新和阶段更新两种概率更新方式。

    • 设选择概率向量为${ P}$,其中元素${P_i}$为选择在邻域${N^v}_i$进行局部搜索的概率,初始值为1。一步更新AVNS算法使用如下规则更新选择概率向量:若解$x$经过邻域${N^v}_i$搜索后得到了改进,则增大${P_i}$,反之减小${P_i}$,即

      式中:${x^{''}}$为在邻域${N^v}_i$局部搜索后得到的局部最优解;$\Delta $为概率的增量,通常取值较小;${P_{\max }}$为概率的最大取值,一般设为1。为了避免出现${P_i}$取值为0的情况,保证邻域结构的多样性,将${P_i}$的最小取值限制为${P^i}_{\min }$$0 < {P^i}_{\min } < 1$;设${{ P}_{\min }}$为最小概率向量概率,每个${P_i}$都对应一个${P^i}_{\min }$;在优化后期,算法任意一个邻域的改进次数往往会小于无改进次数,故最终的概率选择向量${ P}$会收敛于${{ P}_{\min }}$,因此${{ P}_{\min }}$的设定对优化结果有较大的影响。一般地,邻域越大,充分进行局部搜索的耗时越长,因此${P^i}_{\min }$的取值大小应参考对应邻域${N^v}_i$大小进行设定,即对应邻域${N^v}_i$越大,${P^i}_{\min }$的设定值越大。

    • 阶段更新AVNS算法会记录一次变邻域深度搜索过程中邻域${N^v}_i$的改进次数${b_i}$和无改进次数${w_i}$,然后在每次变邻域深度搜索结束后,利用${b_i}$${w_i}$对选择概率进行更新。为了避免在参数更新过程中出现选择概率向量小于等于0的情况,保证邻域的多样性,同样设置${P_0}$作为所有选择概率向量的最小值,即

      由VNS的搜索机制可知,在每一次的变邻域深度搜索中,邻域的顺序越靠前,其局部搜索的次数就会越多,故在计算得到概率的变化量$\left( {{b_i} - {w_i}} \right) \cdot \Delta $之后,需要除以搜索次数$\left( {{b_i}{\rm{ + }}{w_i}} \right)$以实现概率更新的均衡性。在完成对${ P}$的更新后,以${ P}$中的最大元素值为基准对${P_i}$进行归一化:

      由式(12)可知,每一次更新结束后,${ P}$中都会至少有一个元素的取值为1。可以看出,与一步更新方式相比,阶段更新只需要设定${P_0}$一个参数,对参数的依赖性较低。

    • 文献[23]对VNS算法的全局收敛性进行了论证说明,本文AVNS算法的邻域结构以及Shaking的过程与基本VNS算法完全一致。由于设置了最小邻域选择概率,AVNS算法在收敛到全局最优解之前,每次迭代后的改进概率可以始终保证大于0,故AVNS算法的全局收敛性依旧可由文献[23]中关于VNS算法的全局收敛性证明方法得出。图1为一步更新和阶段更新方式下的AVNS算法流程图。

      图  1  AVNS算法流程图

      Figure 1.  Flow chart of AVNS algorithm

    • 在构造初始解时,利用客户的地理位置和时间窗信息作为启发信息,通过概率选择的方式生成初始解。设车辆当前访问的客户为$i$,待插入且满足车辆载重及容积约束的客户集合为$C$,对于$C$中的每一个客户$j$,使用式(13)计算客户$i$和客户$j$的节约值信息${s_{ij}}$[8]。设车辆离开客户$i$的时间为${t_i}$,从客户$i$行驶到客户$j$的时间为${t_{ij}}$,则车辆到达客户$j$的时间为${t_{\rm arrj}} = {t_i} + {t_{ij}}$,使用式(14)计算客户$i$和客户$j$的时间匹配程度$\Delta {t_{ij}}$。用时间窗的宽度$\Delta {t_{wj}}{\rm{ = }}{t_{ej}} - {t_{sj}}$来表示客户$j$的服务时间窗的宽松程度,时间窗越窄,既$\Delta {t_{wj}}$越小,则表示客户$j$的服务时间窗越不宽松,此时基于这样一种先验知识:客户的时间窗越窄,则车辆在访问该客户时越容易出现违反时间窗情况,同时客户在后续调整中的代价也会越高,因此我们希望车辆尽可能在不违反时间窗约束的情况下,优先访问服务时间窗更窄的客户。

      此外,还要判断待访问的客户$j$是否满足里程约束,此时不仅要考虑车辆离开客户$i$时的剩余可行驶里程${L_{\rm left}}$是否大于客户$i$到客户$j$的距离${d_{ij}}$,还要对车辆到达客户$j$后是否能到达距离客户$j$最近的充电站进行判断。车辆离开客户$i$选择下一个访问的客户时,我们希望车辆更倾向于选择节约值更大、时间匹配程度更高、时间窗更窄的客户。为实现上述目的,通过式(15)来计算车辆离开客户$i$后选择客户$j$的可能性。

      式中:$\alpha $$\beta $$\eta $分别为节约值、时间匹配程度及时间窗宽松程度信息的重要性因子;${d_{\min j}}$表示距离客户$j$最近的充电站到客户$j$的距离。在选择下一个车辆要访问的客户时,先计算待插入客户的集合$C$中的每一个客户$j$${p_{ij}}$,然后使用轮盘赌的方式进行概率选择。在进行车型选择时,同样使用了概率选择的方式,即当需要新增车辆以满足运输需要时,以概率${P_{\rm s}}$选择小车型,以概率$1{\rm{ - }}{P_{\rm s}}$选择大车型,参数${P_{\rm s}}$可调。充电策略为:当车辆的剩余里程不足以到达距离最近可服务客户时,则前往最近的充电站进行充电,直到电量充满后,才会继续对客户进行配送服务。

    • 在进行自适应变邻域搜索时,按照送取货路径片段交换、基于空间邻近性的路径片段交换、2-opt算子、Cross算子以及Relocation算子的邻域顺序进行搜索,同时这些邻域也在抖动过程中使用。在使用邻域算子对路径进行变换之前,会先删除路径中的充电站;完成变换后,使用4.1节的充电策略将充电站插入到变换后的路径中,最后计算得出变换前后的成本变化。

      (1)送取货路径片段交换(Part-change)。送取货路径片段交换是指利用车辆上午送货、下午回程取货的特点,随机选取已生成的两条路径,将两条路径各自上下午的行驶路径进行交换,若交换后的两条路径均路径合法且总成本下降,则进行路径覆盖;否则,取消交换。

      (2)基于空间邻近性的路径片段交换(Seg-change)。基于空间邻近性的路径片段交换的基本思想是利用路径片段的两个端点客户的空间邻近性,有针对性地进行路径片段的交换,操作示例如图2所示。

      图  2  路径片段交换

      Figure 2.  Route segment exchange

      (3)2-opt算子。2-opt算子是指随机地选择两条路径,从两条路径中各自选择一个客户进行互换,若交换后的路径合法且总成本出现下降,则进行路径覆盖;否则,取消交换。

      (4)Cross算子。在Cross算子中,先随机选择两条路径,然后从两条路径中各自选择一个客户作为路径的断点,每一条路径被分成了两段,最后进行交叉,操作示例如图3所示。

      图  3  交叉操作

      Figure 3.  Cross operation

      (5)Relocation算子。Relocation是指从一条路径中随机选择一个客户,随机地插入到其他路径中的某个客户之前,若执行上述操作后的路径合法且总成本出现下降,则进行路径覆盖;否则,不进行插入操作。操作示例如图4所示。

      图  4  重定位操作

      Figure 4.  Relocation operation

    • 以京东某城配物流中心已脱敏的实际数据作为实验数据。城配物流中心每天要使用电动车辆为分布在本城区的1 000余名客户进行城市配送。本文分别对客户规模为1 100、1 200、1 300、1 400、1 500的数据进行了实验分析,充电站的数量为200个,每小时充电成本为100元,每小时等待成本为24元,最早发车时间为早上8点,回配送中心最晚时间为当日24点,充电站里的充电桩没有数量限制。具体的车型信息以及客户样例如表1表2所示。

      VehicleMaximum volume /m3Maximum weight /kgMaximum recharge mileage /kmFixed cost /CNYUnit cost /(CNY·km−1
      Type 1122 00010020012
      Type 2162 50012030014

      表 1  车型信息

      Table 1.  Vehicle type information

      Customer IDLocation/kmService typeWeight /kgVolume/m3Time window/h
      1(10,10)Pick151[8.5,9.0]
      2(20,15)Delivery400.45[14.2,15.0]

      表 2  客户样例

      Table 2.  Customer sample

      生成初始解时,节约值、时间匹配程度及时间窗宽松程度信息的重要性因子的参数设置如下:$\alpha = 5$$\beta = 10$$\eta = 10$,小车型的选择概率${P_{\rm s}} = 0.9$;一步更新方式中的最小选择概率向量${{ P}_{\min }} \!=\! \left[ {0.3,0.6,0.8,0.8,0.8} \right]$,阶段更新方式中的最小选择概率${P_0} = 0.3$,一步更新下的概率增量${\Delta _{\rm one}} = 0.002$,阶段更新方式下的概率增量${\Delta _{\rm phase}} = 0.01$

      分别使用基于精英策略的max-min蚁群算法 (Ant Colony System,ACS)[24]、模拟退火算法 (Simulated Annealing,SA)[25]、VNS算法、一步更新和阶段更新下的AVNS算法对5种不同规模的数据进行求解优化,每次运行的最大迭代时间${t_{\max }}$为300 s,在每种数据规模下重复运行100次,相应的物流成本平均值作为衡量算法性能的指标。实验环境为MATLAB 2016b,Xeon®W-2133处理器,实验结果如表3所示(单位:元),括号中的数据为AVNS相比于VNS的成本降低百分比。

      Customer scaleACSSAVNSAVNS with one step updateAVNS with phased update
      1 100275 699.87243 005.19242 097.10241 317.22(0.32%)241 274.73(0.34%)
      1 200308 882.92273 290.14271 857.66270 673.45(0.44%)271 039.10(0.30%)
      1 300305 021.27269 940.70269 681.19267 968.52(0.64%)268 770.87(0.34%)
      1 400397 603.40357 417.85356 075.16355 452.63(0.17%)354 097.12(0.56%)
      1 500407 020.35362 772.20362 595.07361 568.38(0.28%)361 694.37(0.25%)

      表 3  实验结果

      Table 3.  Experimental result

      由实验结果可以看出,蚁群算法计算效率较低,较容易陷入局部最优,故效果较差;而使用模拟退火算法进行仿真时,由于充分利用了本文提出的邻域结构,因此其优化结果VNS较为接近;一步更新AVNS算法和阶段更新AVNS算法的结果最好,从5种客户规模优化后的最终成本的角度分析,两种概率更新方式下的AVNS算法的性能表现没有显著差别。

      以客户规模为1 500的数据为例,图5图6分别示出了一步更新AVNS和阶段更新AVNS下进行拟合之后的5种邻域的选择概率收敛曲线。对于一步更新AVNS,由于算法在优化后期的无改进次数多于改进次数,故各邻域的选择概率会在优化后期收敛到本文设置的最小选择概率${{ P}_{\min }} = \left[ {0.3,0.6,0.8,0.8,0.8} \right]$,其算法性能比较依赖于${{ P}_{\min }}$的设定。从阶段更新AVNS的概率向量收敛曲线可以看出,邻域越小,其对应的选择概率在迭代过程中逐渐收敛到较小的值,也侧面验证了一步更新AVNS中的最小选择概率向量设置的合理性。从仿真结果可以看出,相比于VNS算法,本文提出的AVNS算法能够更有效地跳出局部最优解,找到质量更好的解。

      图  5  一步更新AVNS下的概率向量收敛曲线

      Figure 5.  Probability vector convergence curves under one stepupdate

      图  6  阶段更新AVNS下的概率向量收敛曲线

      Figure 6.  Probability vector convergence curves under phase upalate

    • 本文提出了一种有效的自适应变邻域搜索算法,在算法中为每个邻域都设置了一个选择概率,并使用一步更新和阶段更新两种方式对选择概率向量进行了更新,提高了算法优化效率。该算法部署方便,具有较强的通用性。建立了大规模带时间窗可回程取货的电动车辆路径问题的数学模型,利用时间窗宽度、客户地理位置等信息生成了高质量的初始解;使用2-opt、Relocation、Cross-change等算子进行了自适应变邻域搜索。通过对5组不同客户规模的实际脱敏数据的仿真计算表明,AVNS算法能够更有效地降低物流成本,验证了算法的有效性。

(6)  表(3) 参考文献 (25) 相关文章 (8)

目录

    /

    返回文章