高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ

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

赵灿华 侍洪波

赵灿华, 侍洪波. 基于自适应变邻域搜索的大规模电动车辆路径优化[J]. 华东理工大学学报(自然科学版), 2020, 46(5): 694-701. doi: 10.14135/j.cnki.1006-3080.20190730001
引用本文: 赵灿华, 侍洪波. 基于自适应变邻域搜索的大规模电动车辆路径优化[J]. 华东理工大学学报(自然科学版), 2020, 46(5): 694-701. doi: 10.14135/j.cnki.1006-3080.20190730001
ZHAO Canhua, SHI Hongbo. Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search[J]. Journal of East China University of Science and Technology, 2020, 46(5): 694-701. doi: 10.14135/j.cnki.1006-3080.20190730001
Citation: ZHAO Canhua, SHI Hongbo. Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search[J]. Journal of East China University of Science and Technology, 2020, 46(5): 694-701. doi: 10.14135/j.cnki.1006-3080.20190730001

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

doi: 10.14135/j.cnki.1006-3080.20190730001
基金项目: 国家自然科学基金(61703161,61673173);中央高校基本科研基金(222201714031,222201717006);上海国家自然科学基金(19ZR1473200)
详细信息
    作者简介:

    赵灿华(1995-),男,河南商丘人,硕士生,主要研究方向为车辆路径问题。E-mail:canhua_zhao@163.com

    通讯作者:

    侍洪波,E-mail:hbshi@ecust.edu.cn

  • 中图分类号: O221.7; U116.2

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

  • 摘要: 针对变邻域搜索后期出现的在某些邻域内长时间无法找到更优的可行解的情况,提出了一种基于邻域选择概率自适应的变邻域搜索算法。该算法能够自适应调整在某个邻域进行搜索的概率,进而提高优化效率。对城市配送中的大规模电动车辆路径问题进行了建模分析,根据客户的地理位置、时间窗等信息设计了高效的初始解生成算法。使用片段交换、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.  Select probability vector convergence curves under one step update

    图  6  阶段更新AVNS下的选择概率收敛曲线

    Figure  6.  Select probability vector convergence curves under phase update

    表  1  车型信息

    Table  1.   Vehicle type information

    VehicleMaximum volume /m3Maximum mass /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 typeMass /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 scaleLogistics cost/CNY
    ACSSAVNSAVNS 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[EB/OL]. arxiv. org. 2015-05-31 [2019-07-15]. arxiv.org/abs/1506.00211.
    [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
  • 加载中
图(6) / 表(3)
计量
  • 文章访问数:  3567
  • HTML全文浏览量:  1510
  • PDF下载量:  58
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-07-30
  • 网络出版日期:  2019-12-16
  • 刊出日期:  2020-10-30

目录

    /

    返回文章
    返回