Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Multiple Deliverymen

doi:10.12005/orms.2022.0041

Operations Research and Management Science ›› 2022, Vol. 31 ›› Issue (2): 42-47.DOI: 10.12005/orms.2022.0041

• Theory Analysis and Methodology Sludy • Previous Articles Next Articles

Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Multiple Deliverymen

SU Xin-xin^1,2, WANG Hong-wei², QIN Hu², WANG Kai³

1. School of Management Engineering, Qingdao University of Technology, Qingdao 266000, China;
2. School of Management,Huazhong University of Science and Technology, Wuhan 430074, China;
3. Economics and Management School, Wuhan University, Wuhan 430000, China

Received:2020-03-25 Online:2022-02-25 Published:2022-03-11

混合启发式算法求解多配送人员车辆路径问题

苏欣欣^1,2, 王红卫², 秦虎², 王恺³

1.青岛理工大学管理工程学院,山东青岛 266000;
2.华中科技大学管理学院,湖北武汉 430074;
3.武汉大学经济与管理学院,湖北武汉 430000

通讯作者: 秦虎(1980-),男,湖北武汉人,教授,研究方向:车辆路径优化
作者简介:苏欣欣(1991-),女,河北沧州人,副教授,研究方向:车辆路径优化;王红卫(1966-),男,浙江宁波人,教授,研究方向:物流与供应链系统;王恺(1980-),男,河北沧州人,教授,研究方向: 复杂系统建模与优化。
基金资助:
国家自然科学基金创新研究群体项目(71821001);国家自然科学基金面上项目(71971090,71671131)

Abstract

Abstract: To solve the vehicle routing problem with time windows and multiple deliverymen, we adopt a hybrid heuristic algorithm, which is characterized by the hybridization of the integer programming recombination, the local search (LS) algorithm and the simulated annealing (SA) algorithm. In the proposed algorithm, the integer programming recombination is capable of providing better solutions for further improvement, and LS and SA make a good balance between exploration and exploitation. Computational results indicate the proposed algorithm is more effective than CPLEX and the tabu search algorithm.

Key words: vehicle routing problem, time windows, multiple deliverymen, hybrid heuristic algorithm

摘要： 为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。

关键词: 车辆路径问题, 时间窗, 多配送人员, 混合启发式算法

CLC Number:

U116.2

SU Xin-xin, WANG Hong-wei, QIN Hu, WANG Kai. Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Multiple Deliverymen[J]. Operations Research and Management Science, 2022, 31(2): 42-47.

苏欣欣, 王红卫, 秦虎, 王恺. 混合启发式算法求解多配送人员车辆路径问题[J]. 运筹与管理, 2022, 31(2): 42-47.

[1]	HU Hui, LIU Fu-xin, WANG Yu-qin, FENG Zhi-yu, WANG Rui. Coordinated Optimization of Push Production and Distribution Based on Improved Simulated Annealing Algorithm [J]. Operations Research and Management Science, 2022, 31(2): 15-22.
[2]	GE Xian-long, SONG Chun-bing. Vehicle Routing Problem with Outsourced Services [J]. Operations Research and Management Science, 2022, 31(2): 29-35.
[3]	FAN Hou-ming, XU Zhen-lin, LI Yang, YANG Xiang. Chaos Genetic Simulated Annealing Algorithm for the Open Multi-depot Split Delivery Vehicle Routing Problem [J]. Operations Research and Management Science, 2022, 31(1): 92-98.
[4]	WANG Yu-qin, HU Hui, LIU Fu-xin, WANG Yan-hui, ZHAO Jiao, HAN Yi. Optimization of Unmanned Vehicle Distribution Path under Intelligent Network Connection [J]. Operations Research and Management Science, 2021, 30(8): 52-58.
[5]	XIANG Ting, LI Yan-feng. A Bi-objective Home Health Care Scheduling Problem: Based on Costs and Overtime [J]. Operations Research and Management Science, 2021, 30(8): 233-239.
[6]	ZHANG Xiao-nan, FAN Hou-ming. Hybrid Memetic Algorithm for Vehicle Routing Problem with Time Windows [J]. Operations Research and Management Science, 2021, 30(7): 128-135.
[7]	WANG Xin, WANG Zheng, XU Wei. Vehicle and Drone Joint Distribution Routing Problem with Multiple Drone Hubs [J]. Operations Research and Management Science, 2021, 30(5): 31-37.
[8]	XUE Gui-qin, WANG Zheng. Dynamic Vehicle Routing Problem with Inventory Synergetic [J]. Operations Research and Management Science, 2021, 30(11): 19-25.
[9]	LIU Chang-shi, WANG Song, LUO Liang, DENG Sheng-qian. Open Vehicle Routing Problem Based on Joint Distribution Mode under Time-dependent Road Networks [J]. Operations Research and Management Science, 2021, 30(11): 26-33.
[10]	BIAN Zhan, ZHANG Qian, XU Qi, JIN Zhi-hong. Hybrid Algorithms for the Pickup and Delivery Problem with Time Windows [J]. Operations Research and Management Science, 2020, 29(2): 99-115.
[11]	CHEN Ping, DONGWen-zhe, YU Xin-yao. Studyon Routing Problemfor New Energy Mobile Charging Vehicles [J]. Operations Research and Management Science, 2020, 29(2): 12-18.
[12]	CAO Ping, ZHANG Jian, XIONG Yan. Research onPayment Scheduling Problems with Different Quality ——Take a Software Project as Example [J]. Operations Research and Management Science, 2019, 28(9): 192-199.
[13]	ZHANG Jian-tong, DING Ye. Simulated Annealing with Variable Neighborhood for Time-Dependent Vehicle Routing Problem with Time Window [J]. Operations Research and Management Science, 2019, 28(11): 77-84.
[14]	PAN Li-jun, FU Zhuo, LIU Xi-mei. Bike Sharing Rebalancing Problem and Capacity Range Length Insertion Heuristic Algorithm [J]. Operations Research and Management Science, 2019, 28(10): 26-32.
[15]	XU Guo-xun, LI Yan-feng, LI Jun, XU Guan-yu. A Multi-type Bike Repositioning Problem [J]. Operations Research and Management Science, 2019, 28(1): 116-124.

Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Multiple Deliverymen

混合启发式算法求解多配送人员车辆路径问题

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics