考虑载重成本与时间窗的集送货问题的自适应大邻域搜索算法

doi:10.3969/j.issn.1007-7375.2023.02.014

摘要/Abstract

摘要： 物流配送需求的快速增长使得集送货问题的应用越来越广泛。针对配送过程中货物载重影响运输成本的情况，研究考虑载重成本的有时间窗的集送货问题。构建该问题的最小化车辆数量和总运输成本的双目标混合整数规划模型，在该模型中，运输成本为车辆载重量与车辆行驶距离的函数。设计两阶段自适应大邻域搜索算法对其求解，通过设计基于模型特点的多种高效的破坏算子和修复算子，引入模拟退火接受准则避免陷入局部最优解来提高算法性能。测试不同规模及特点的标杆算例，结果表明，所提出的两阶段自适应大邻域搜索算法能够高效求解小规模、中等规模和大规模算例，并分析了货物载重以及不同运量系数对运输成本的影响，为物流企业的集送货车辆路径优化提供参考。

关键词: 集送货问题, 载重成本, 时间窗, 自适应大邻域搜索算法

Abstract: The rapid growth of logistics distribution demand makes an increasing wide application of pickup and delivery. A pickup and delivery problem with time windows and weight-related cost is studied, considering that the cargo weight has an effect on the transportation cost in the distribution process. A bi-objective mixed integer programming model of the problem is formulated to minimize the number of vehicles and the total transportation cost, in which the transportation cost is a function of vehicles’ load capacities and travel distances. A two-stage adaptive large neighborhood search algorithm is designed to solve the model, where the performance is improved by designing multiple efficient destroy and repair operators and introducing a simulated annealing strategy to avoid local optimal. Instances with different scales and characteristics are tested, showing that the proposed two-stage adaptive large neighborhood search algorithm can solve small-scale, middle-scale and large-scale instances effectively. Also, the impact of cargo weight and different transport coefficients on transportation cost is analyzed, providing reference for logistics enterprises to optimize the route of pickup and delivery vehicles.

Key words: pickup and delivery problem, weight-related cost, time window, adaptive large neighborhood search algorithm

中图分类号:

U121

吴廷映, 王晨秀, 孙灏. 考虑载重成本与时间窗的集送货问题的自适应大邻域搜索算法[J]. 工业工程, 2023, 26(2): 123-131.

WU Tingying, WANG Chenxiu, SUN Hao. An Adaptive Large Neighborhood Search Algorithm for Pickup and Delivery Problem with Time Windows and Weight-related Cost[J]. Industrial Engineering Journal, 2023, 26(2): 123-131.

参考文献

[1] ROPKE S, CORDEAU J F, Laporte G. Models and branch-and-cut algorithms for pickup and delivery problems with time windows[J]. Networks, 2007, 49(4): 258-272
[2] 徐东洋, 李昆鹏, 郑飘, 等. 多车场多车型多品类供需未匹配与可任意拆分取送货车辆路径问题优化[J]. 管理学报, 2020, 17(7): 127-137
XU Dongyang, LI Kunpeng, ZHENG Piao, et al. The optimization research of multi-category unpaired supply-demand and arbitrary split pickup and delivery vehicle routing problem with multi-depot and multi-type trucks[J]. Chinese Journal of Management, 2020, 17(7): 127-137
[3] LI Y, CHEN H, PRINGS C. Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests[J]. European Journal of Operational Research, 2016, 252(1): 27-38
[4] PENG Z, CHAMI Z A, MANIER H, et al. A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers[J]. Engineering Applications of Artificial Intelligence, 2019, 85(10): 99-111
[5] BENT R, VAN H P. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[J]. Computers & Operations Research, 2006, 33(4): 875-893
[6] 潘震东, 唐加福, 韩毅. 带货物权重的车辆路径问题及遗传算法[J]. 管理科学学报, 2007, 10(3): 23-29
PAN Zhendong, TANG Jiafu, HAN Yi. Vehicle routing problem with weight coefficients[J]. Journal of Management Sciences in China, 2007, 10(3): 23-29
[7] 唐加福, 孔媛, 潘震东, 等. 基于划分的蚁群算法求解货物权重车辆路径问题[J]. 控制理论与应用, 2008, 25(4): 699-702
TANG Jiafu, KONG Yuan, PAN Zhendong, et al. An ant colony optimization algorithm for vehicle routing problem with cargo coefficient[J]. Control Theory & Applications, 2008, 25(4): 699-702
[8] SHEN C H, HU Q, LIM A. A capacitated vehicle routing problem with toll-by-weight rule[J]. Studies in Computational Intelligence, 2009, 214(1): 311-316
[9] ZHANG J, TANG J, FUNG R. A scatter search for multi-depot vehicle routing problem with weight-related cost[J]. Asia-Pacific Journal of Operational Research, 2011, 28(3): 323-348
[10] ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. transportation science, 2006, 40(4): 455-471
[11] SHAW P. Using constraint programming and local search methods to solve vehicle routing problems[J]. Principles and Practice of Constraint Programming, 1998, 1520(1): 417-431
[12] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms[J]. Journal of the Operational Research Society, 2001, 42(9): 816-817
[13] LI H, LIM A. A metaheuristic for the pickup and delivery problem with time windows[J]. International Journal on Artificial Intelligence Tools, 2008, 12(2): 173-186

[1]	董海, 雷凤达. 基于萤火虫算法的动态车辆路径规划[J]. 工业工程, 2022, 25(6): 110-119,125.
[2]	曹紫萱, 林宇鹏, 吴植英, 毛宁, 陈庆新, 余龙水. 客舱清洁人员调度及时间窗冲突的影响分析[J]. 工业工程, 2022, 25(5): 120-127.
[3]	王玖河, 安聪琢, 郭田宇. 时变路网下电动冷藏车配送路径优化研究[J]. 工业工程, 2022, 25(4): 60-69,107.
[4]	闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
[5]	王宁, 张玉萍, 赵姣, 金子阳. 考虑碳排放及时间窗的LIRP模型与算法研究[J]. 工业工程, 2021, 24(2): 34-42.
[6]	李玉民, 邱梦, 黑柏林, 方曾利. 考虑高铁时间窗和客户满意度的生鲜品公铁联运路径选择[J]. 工业工程, 2021, 24(2): 49-56.
[7]	李博威, 户佐安, 贾叶子, 唐诗韵. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
[8]	冯春, 秦冰芳, 叶露. 共享电动车电池配送问题研究[J]. 工业工程, 2019, 22(3): 52-56.
[9]	户佐安, 贾叶子, 李博威, 刘陆. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107.
[10]	王维军, 罗伟. 基于改进智能水滴算法的冷链物流配送路径优化问题研究[J]. 工业工程, 2017, 20(2): 38-43.
[11]	朱婷1，王旭磊2，赵来军1. 带时间窗的时变多目标危险化学品道路运输路径优化[J]. 工业工程, 2016, 19(2): 62-67.
[12]	任盼，刘冉，江志斌，董蕊. 考虑油耗的车辆调度问题模型与算法[J]. 工业工程, 2015, 18(5): 134-140.
[13]	张帆1,2，汤兵勇1. 顾客时间窗和维修需求变动下车辆维修的干扰管理优化[J]. 工业工程, 2015, 18(5): 148-153.
[14]	谢天保1，张晓雯1，仵凯博2，胡丹1. 电子商务下基于协同配送的配送中心选址研究[J]. 工业工程, 2015, 18(3): 75-81.
[15]	雷卫东，车阿大 . 带时间窗口的自动化混流生产线调度方法[J]. 工业工程, 2011, 14(5): 110-115.