多车程多时间窗车辆路径问题研究

doi:10.3969/j.issn.1007-7375.220254

摘要/Abstract

摘要： 针对末端物流中配送车辆多趟次运输、客户对配送服务时间的多样化需求，研究多车程多时间窗车辆路径问题。构造该问题的最小化车辆数量和总运输成本的双目标混合整数规划模型，设计改进的自适应大邻域搜索算法对其求解；构建了基于路径、车程及客户点3个层级上的多种高效的破坏算子和修复算子来扩大解的搜索空间；使用自适应策略选择高效的搜索算子，以及引入模拟退火新解接受准则避免陷入局部最优解来提高搜索效率。通过多种规模算例实验结果分析，验证了改进的自适应大邻域搜索算法的优越性，并分析了考虑多车程的模型对总运输成本的影响。

关键词: 多车程, 多时间窗, 车辆路径问题, 自适应大邻域搜索

Abstract: Focusing on the multi-trip transportation of terminal logistics and the diverse demand of customers for service time, a vehicle routing problem with multiple trips and multiple time windows is studied. A bi-objective mixed integer programming model is established to minimize the number of vehicles and the total transportation cost, while an improved adaptive large neighborhood search algorithm is designed to solve the problem. In this algorithm, a variety of efficient destroy and repair operators based on three levels of routes, travel distances and customer points are constructed to expand the search space of solutions. An adaptive strategy is used to select efficient search operators and a simulated annealing rule is introduced to avoid the solution from falling into local optimum and improve the search efficiency. By analyzing the experimental results of instances with various scales, the advantages of the improved adaptive large neighborhood search algorithm are verified, and the positive impact of the model considering multiple trips on the total transportation cost is analyzed.

Key words: multiple trips, multiple time windows, vehicle routing problem, adaptive large neighborhood search

中图分类号:

吴廷映, 鲁佳琪, 夏洋. 多车程多时间窗车辆路径问题研究[J]. 工业工程, 2024, 27(2): 147-157.

WU Tingying, LU Jiaqi, XIA Yang. Vehicle Routing with Multiple Trips and Multiple Time Windows[J]. Industrial Engineering Journal, 2024, 27(2): 147-157.

参考文献

[1] 李珍萍, 赵菲, 刘洪伟. 多时间窗车辆路径问题的智能水滴算法[J]. 运筹与管理, 2015, 24(6): 1-10
LI Zhenping, ZHAO Fei, LIU Hongwei. Intelligent water drops algorithm for vehicle routing problem with multiple time windows[J]. Operations Research and Management Science, 2015, 24(6): 1-10
[2] BELHAIZA S, HANSEN P, LAPORTE G. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J]. Computers & Operations Research, 2014, 52: 269-281
[3] BEHESHTI A K, HEJAZI S R, ALINAGHIAN M. The vehicle routing problem with multiple prioritized time windows: a case study[J]. Computers & Industrial Engineering, 2015, 90: 402-413
[4] 闫芳, 王媛媛. 多模糊时间窗车辆路径问题的建模及求解[J]. 交通运输系统工程与信息, 2016(6): 182-188
YAN Fang, WANG Yuanyuan. Modeling and solving the vehicle routing problem with multiple fuzzy time windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2016(6): 182-188
[5] MAO H, SHI J, ZHOU Y, et al. The electric vehicle routing problem with time windows and multiple recharging options[J]. IEEE Access, 2020, 8: 114864-114875
[6] 李博威, 户佐安, 贾叶子, 等. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81
LI Bowei, HU Zuoan, JIA Yezi, et al. A research on vehicle routing problem with simultaneous pick-up and delivery and soft time windows[J]. Industrial Engineering Journal, 2020, 23(5): 75-81
[7] 张瑾, 洪莉, 戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学, 2021, 43(8): 1479-1487
ZHANG Jin, HONG Li, DAI Erzhuang. An improved bat algorithm for the vehicle routing problem with time windows and capacity constraints[J]. Computer Engineering and Science, 2021, 43(8): 1479-1487
[8] 闫军, 常乐, 王璐璐, 等. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76
YAN Jun, CHANG Le, WANG Lulu, et al. A solution algorithm for the problem of taking delivery vehicle path at the same time with time window[J]. Industrial Engineering Journal, 2021, 24(5): 72-76
[9] FANG W, GUAN Z, YUE L, et al. Heterogeneous-vehicle distribution logistics planning for assembly line station materials with multiple time windows and multiple visits[J]. International Journal of Industrial Engineering Computations, 2022, 13(4): 473-490
[10] FLEISCHMANN B. The vehicle routing problem with multiple use of vehicles[R/OL]. (1980-01)[2022-12-19]. https://www.researchgate.net/publication/221704650_The_vehicle_routing_problem_with_multiple_use_of_vehicles.
[11] WASSAN N, WASSAN N, NAGY G, et al. The multiple trip vehicle routing problem with backhauls: formulation and a two-level variable neighbourhood search[J]. Computers & Operations Research, 2017, 78(C): 454-467
[12] 张晓楠, 范厚明. 带时间窗偏好的多行程模糊需求车辆路径优化[J]. 计算机集成制造系统, 2018, 24(10): 2461-2477
ZHANG Xiaonan, FAN Houming. Optimization for multi-trip vehicle routing problem with fuzzy demands considering time window preference[J]. Computer Integrated Manufacturing System, 2018, 24(10): 2461-2477
[13] 宋强. 改进混合遗传算法在MTVRPTW中的建模与优化[J]. 重庆交通大学学报 (自然科学版) , 2018, 37(9): 79-86,134
SONG Qiang. Application of improved hybrid genetic algorithm in the modeling and optimization of multi-trip vehicle routing problem with time windows[J]. Journal of Chongqing Jiaotong University (Natural Science) , 2018, 37(9): 79-86,134
[14] 刘虹, 傅晓敏. 考虑同时取送随机需求的多行程车辆路径研究[J]. 西安电子科技大学学报 (社会科学版) , 2019, 29(3): 87-95
LIU Hong, FU Xiaomin. Study on multi-trip vehicle routing problem with stochastic simultaneous pickup-delivery demand[J]. Journal of Xidian University (Social Science Edition) , 2019, 29(3): 87-95
[15] RAHMANI A. The multiple trip vehicle routing problem with backhauls in random fuzzy environment: using (α, β) -cost minimization model under the Hurwicz criterion[J]. International Journal of Computer Mathematics, 2019, 96(12): 2548-2566
[16] LI W, WU Y, KUMAR P N R, et al. Multi-trip vehicle routing problem with order release time[J]. Engineering Optimization, 2020, 52(8): 1279-1294
[17] CATTARUZZA D, ABSI N, FEILLET D. Vehicle routing problems with multiple trips[J]. Annals of Operations Research, 2018, 271(1): 127-159