混合变邻域搜索算法求解大规模电动车辆路径优化问题

doi:10.16182/j.issn1004731x.joss.21-1133

系统仿真学报 ›› 2022, Vol. 34 ›› Issue (4): 910-919.doi: 10.16182/j.issn1004731x.joss.21-1133

混合变邻域搜索算法求解大规模电动车辆路径优化问题

王伟权^1,³(), 丁鼎¹(), 曹淑艳²

^1.对外经济贸易大学国际经济贸易学院, 北京 100029
^2.对外经济贸易大学统计学院, 北京 100029
^3.对外经济贸易大学网络安全和信息化处, 北京 100029

收稿日期:2021-11-05 修回日期:2021-12-23 出版日期:2022-04-30 发布日期:2022-04-19
通讯作者: 丁鼎 E-mail:wangweiquan@uibe.edu.cn;dingd@uibe.edu.cn
作者简介:王伟权(1991-)，男，博士生，研究方向为电动车辆路径优化。E-mail：wangweiquan@uibe.edu.cn
基金资助:
北京市社会科学基金(17GLB026);对外经济贸易大学中央高校基本科研业务费专项资金(16JQ01)

Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem

Weiquan Wang^1,³(), Ding Ding¹(), Shuyan Cao²

^1.School of International Trade and Economics, University of International Business and Economics, Beijing 100029, China
^2.School of Statistics, University of International Business and Economics, Beijing 100029, China
^3.Department of Information Management, University of International Business and Economics, Beijing 100029, China

Received:2021-11-05 Revised:2021-12-23 Online:2022-04-30 Published:2022-04-19
Contact: Ding Ding E-mail:wangweiquan@uibe.edu.cn;dingd@uibe.edu.cn

摘要/Abstract

摘要：

基于真实的物流场景，研究了带时间窗的多车型和多循环电动车辆路径问题。建立了一个基于路径的混合整数线性规划模型，可精确求解小规模算例。提出了将变邻域搜索算法和标签算法相结合的混合启发式算法，用以求解大规模情形。该算法提出了一种带随机因子的启发式算法构造初始解，并对时间窗和里程约束进行了松弛，使用邻域算子进行变邻域搜索，使用标签算法精确求解了固定商户配送顺序下的路径最优充电决策问题。测试结果表明：混合变邻域搜索算法可在极短时间内找到最优解，能大幅度降低物流成本。

关键词: 多车型, 多循环, 电动车辆路径优化问题, 变邻域搜索算法, 标签算法

Abstract:

Based on the real business practice, the multi-trip and heterogeneous-fleet electric vehicle routing problem (MTHF-EVRP) with time windows in green logistics is studied. A path-based mixed-integer linear model is built for the precise solution to the small-scale instances. A hybrid variable neighborhood search algorithm (Hybrid VNS) combined the variable neighborhood search algorithm with the labeling algorithm is proposed for the large-scale instances. The algorithm generates a modified insertion heuristic with random factor to construct the initial solution, allows the time window and range violation, adopts the neighborhood operators for the local search, and applies a labeling algorithm to solve the fixed-route recharging problem precisely. The methods are tested on the real-world benchmark instances for MTHF-EVRP. The results on the small-scale instances show that Hybrid VNS can find the optimal solutions in a very short time. Compared with the state-of-the-art algorithm on the large-scale instances, the algorithm can significantly reduce the logistics cost and the great competitiveness of Hybrid VNS is showed.

Key words: heterogeneous-fleet, multi-trip, electric vehicle routing problem, variable neighborhood search, labeling algorithm

中图分类号:

TP391.9

王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.

Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2022, 34(4): 910-919.

图/表 2

参考文献 31

1	国务院. 北京打赢蓝天保卫战三年行动计划[EB/OL].(2018-09-15)[2021-11-05]..
2	Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research (S0030-364X), 1987, 35(2): 254-265.
3	Erdoğan S, Miller-Hooks E. A Green Vehicle Routing Problem[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2012, 48(1): 100-114.
4	Roberti R, Wen M. The Electric Traveling Salesman Problem with Time Windows[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2016, 89: 32-52.
5	Schneider M, Stenger A, Goeke D. The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations[J]. Transportation Science (S0041-1655), 2014, 48(4): 500-520.
6	Desaulniers G, Errico F, Irnich S, et al. Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows[J]. Operations Research (S0030-364X), 2016, 64(6): 1388-1405.
7	Hiermann G, Puchinger J, Ropke S, et al. The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations[J]. European Journal of Operational Research (S0377-2217), 2016, 252(3): 995-1018.
8	Golden B, Assad A, Levy L, et al. The Fleet Size and Mix Vehicle Routing Problem[J]. Computers & Operations Research (S0305-0548), 1984, 11(1): 49-66.
9	Hiermann G, Hartl R F, Puchinger J, et al. Routing a Mix of Conventional, Plug-In Hybrid, and Electric Vehicles[J]. European Journal of Operational Research (S0377-2217), 2019, 272(1): 235-248.
10	Macrina G, Laporte G, Guerriero F, et al. An Energy-Efficient Green-Vehicle Routing Problem with Mixed Vehicle Fleet, Partial Battery Recharging and Time Windows[J]. European Journal of Operational Research (S0377-2217), 2019, 276(3): 971-982.
11	赵灿华, 侍洪波. 基于自适应变邻域搜索的大规模电动车辆路径优化[J]. 华东理工大学学报(自然科学版), 2020, 46(5): 694-701.
	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 (Natural Science Edition), 2020, 46(5): 694-701.
12	Zhao M, Lu Y. A Heuristic Approach for a Real-World Electric Vehicle Routing Problem[J]. Algorithms (S1999-4893), 2019, 12(2): 45.
13	Zhou Y, Huang J, Shi J, et al. The Electric Vehicle Routing Problem with Partial Recharge and Vehicle Recycling[J]. Complex & Intelligent Systems (S2199-4536), 2021, 7(3): 1-14.
14	Li H, Li Z, Cao L, et al. Research on Optimization of Electric Vehicle Routing Problem with Time Window[J]. IEEE Access(S2169-3536), 2020, 8: 146707-146718.
15	Liu H, Zhang Z, Guo X. Restricted Neighborhood Search for Large Scale Vehicle Routing Problems[C]//2019 IEEE 16th International Conference on Networking, Sensing and Control (ICNSC). IEEE, 2019: 98-103.
16	Goeke D, Schneider M. Routing a Mixed Fleet of Electric and Conventional Vehicles[J]. European Journal of Operational Research (S0377-2217), 2015, 245(1): 81-99.
17	Schiffer M, Walther G. The Electric Location Routing Problem with Time Windows and Partial Recharging[J]. European Journal of Operational Research (S0377-2217), 2017, 260(3): 995-1013.
18	揭婉晨, 杨珺, 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践, 2016, 36(7): 1795-1805.
	Wanchen Jie, Yang Jun, Yang Chao. Branch-and-price Algorithm for Heterogeneous Electric Vehicle Routing Problem[J]. Systems Engineering-Theory & Practice, 2016, 36(7): 1795-1805.
19	李得成, 陈彦如, 张宗成. 基于分支定价算法的电动车与燃油车混合车辆路径问题研究[J]. 系统工程理论与实践, 2021, 41(4): 995-1009.
	Li Decheng, Chen Yanru, Zhang Zongcheng. A Branch-and-Price Algorithm for Electric Vehicle Routing Problem with Time Windows and Mixed Fleet[J]. Systems Engineering-Theory & Practice, 2021, 41(4): 995-1009.
20	Montoya A, Guéret C, Mendoza J E, et al. The Electric Vehicle Routing Problem with Nonlinear Charging Function[J]. Transportation Research Part B: Methodological (S0191-2615), 2017, 103: 87-110.
21	Bruglieri M, Mancini S, Pezzella F, et al. A Path-Based Solution Approach for the Green Vehicle Routing Problem[J]. Computers & Operations Research (S0305-0548), 2019, 103: 109-122.
22	Froger A, Mendoza J E, Jabali O, et al. Improved Formulations and Algorithmic Components for the Electric Vehicle Routing Problem with Nonlinear Charging Functions[J]. Computers & Operations Research (S0305-0548), 2019, 104: 256-294.
23	Schiffer M, Walther G. An Adaptive Large Neighborhood Search for the Location-Routing Problem with Intra-route Facilities[J]. Transportation Science (S0041-1655), 2018, 52(2): 331-352.
24	Keskin M, Çatay B. Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows[J]. Transportation Research Part C: Emerging Technologies (S0968-090X), 2016, 65: 111-127.
25	Felipe Á, Ortuño M T, Righini G, et al. A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2014, 71: 111-128.
26	Wen M, Linde E, Ropke S, et al. An Adaptive Large Neighborhood Search Heuristic for the Electric Vehicle Scheduling Problem[J]. Computers & Operations Research (S0305-0548), 2016, 76: 73-83.
27	Vidal T, Crainic T G, Gendreau M, et al. A Hybrid Genetic Algorithm with Adaptive Diversity Management for a Large Class of Vehicle Routing Problems with Time-Windows[J]. Computers & Operations Research (S0305-0548), 2013, 40(1): 475-489.
28	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-Depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
29	范双南, 陈纪铭, 高为民, 等. 基于改进智能水滴算法的动态车辆配送路径优化[J]. 系统仿真学报, 2020, 32(9): 1808-1817.
	Fan Shuangnan, Chen Jiming, Gao Weimin, et al. Dynamic Vehicle Distribution Path Optimization Based on Improved Intelligent Water Drop Algorithm[J]. Journal of System Simulation, 2020, 32(9): 1808-1817.
30	Irnich S, Desaulniers G. Shortest Path Problems with Resource Constraints[M]// Column generation. Springer, Boston: MA, 2005: 33-65.
31	Hansen P, Mladenović N. Variable Neighborhood Search: Principles and Applications[J]. European Journal of Operational Research (S0377-2217), 2001, 130(3): 449-467.

[1]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[2]	王伟权, 丁鼎, 颜林莎. 线性充电策略下多车型电动车辆路径模型研究[J]. 系统仿真学报, 2022, 34(3): 614-623.

混合变邻域搜索算法求解大规模电动车辆路径优化问题

Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 31

相关文章 2

编辑推荐

Metrics

本文评价