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

doi:10.12005/orms.2022.0041

运筹与管理 ›› 2022, Vol. 31 ›› Issue (2): 42-47.DOI: 10.12005/orms.2022.0041

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

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

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

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

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

摘要/Abstract

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

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

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

中图分类号:

U116.2

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

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.

[1]	胡卉, 刘富鑫, 王愚勤, 冯芷郁, 王瑞. 基于改进模拟退火算法的推动式生产-配送协调优化[J]. 运筹与管理, 2022, 31(2): 15-22.
[2]	葛显龙, 宋纯冰. 考虑外协服务的车辆路径优化问题[J]. 运筹与管理, 2022, 31(2): 29-35.
[3]	范厚明, 徐振林, 李阳, 杨翔. 开放式多中心需求可拆分VRP及混沌遗传模拟退火算法[J]. 运筹与管理, 2022, 31(1): 92-98.
[4]	王愚勤, 胡卉, 刘富鑫, 王艳慧, 赵姣, 韩毅. 智能网联下无人车配送路径优化[J]. 运筹与管理, 2021, 30(8): 52-58.
[5]	向婷, 李妍峰. 基于成本和加班时长的双目标家庭护理人员调度问题[J]. 运筹与管理, 2021, 30(8): 233-239.
[6]	张晓楠, 范厚明. 求解带时间窗车辆路径问题的混合Memetic算法[J]. 运筹与管理, 2021, 30(7): 128-135.
[7]	王新, 王征, 徐伟. 面向多个无人机站点的车辆与无人机联合配送路径问题研究[J]. 运筹与管理, 2021, 30(5): 31-37.
[8]	刘国山, 王敏, 张转霞. 基于时间窗延迟的资源约束项目调度双层优化研究[J]. 运筹与管理, 2021, 30(12): 6-12.
[9]	薛桂琴, 王征. 带客户协同分仓的动态车辆路径问题研究[J]. 运筹与管理, 2021, 30(11): 19-25.
[10]	刘长石, 王松, 罗亮, 邓胜前. 时变路网条件下联合配送的开放式车辆路径问题[J]. 运筹与管理, 2021, 30(11): 26-33.
[11]	边展, 张倩, 徐奇, 靳志宏. 带时间窗取送货问题的混合算法[J]. 运筹与管理, 2020, 29(2): 99-115.
[12]	陈萍, 董文哲, 于信尧. 新能源移动充电车路径优化问题研究[J]. 运筹与管理, 2020, 29(2): 12-18.
[13]	曹萍, 张剑, 熊焰. 具有质量差异的项目支付进度问题研究——以软件项目为例[J]. 运筹与管理, 2019, 28(9): 192-199.
[14]	潘立军, 符卓, 刘喜梅. 共享单车再平衡问题及其容差插入启发式算法[J]. 运筹与管理, 2019, 28(10): 26-32.
[15]	徐国勋, 李妍峰, 李军, 徐冠宇. 多类型公共自行车调运问题[J]. 运筹与管理, 2019, 28(1): 116-124.

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

Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Multiple Deliverymen

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics