硬时间窗VRP的混合变邻域禁忌搜索算法

doi:10.3778/j.issn.1002-8331.2208-0431

摘要/Abstract

摘要： 为了寻求带硬时间窗的车辆路径优化问题的高质量近似解，针对现有数学模型对时间窗约束考虑不充分，建立了最小化车辆数和总行驶距离的双目标非线性优化模型，提出了一种混合变邻域禁忌搜索求解算法。一方面，采用改进的节约算法生成初始解，设计了3种删除算子和一种插入算子对初始解进行扰动优化，为后续禁忌搜索提供优良的初始解；另一方面，基于4种邻域构造算子进行禁忌迭代搜索，利用禁忌搜索的灵活存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则有效摆脱局部最优解，最终实现全局优化。在56个Solomon和18个Homberger基准算例上的实验结果表明，该算法的求解质量优于文献中两种同类型搜索算法，具有良好的收敛性和稳定性，且在42个基准实例上获得了比当前已知最好解更低的车辆总行驶距离。

关键词: 车辆路径优化, 时间窗, 禁忌搜索, 变邻域搜索

Abstract: To find a high-quality approximate solution to the vehicle routing optimization problem with hard time window, a dual objective nonlinear optimization model is established to minimize the number of vehicles and the total driving distance, because the insufficient consideration of time window constraints in the existing mathematical models, and a hybrid variable neighborhood tabu search algorithm is proposed to solve it. On the one hand, an improved saving algorithm is used to generate the initial solution. And three deletion operations and one insertion operation are designed to optimize the number of vehicles in the initial solution, so as to provide an excellent initial solution for the subsequent tabu search. On the other hand, four neighborhood construction operators are designed in the tabu search process. The flexible storage structure, tabu criterion for avoiding repeated searches and amnesty criterion for enhancing diversity search can effectively get rid of local optimal solution, and finally achieve global optimization. Finally, the experimental analysis is carried out on 56 benchmark examples of Solomon and 18 benchmark examples of Homberger. This algorithm has good convergence and stability, and its solutions are better than the two similar search algorithms in the literature. Moreover, the total driving distance is lower than the currently known best solution on 42 examples.

Key words: vehicle routing optimization, time window, tabu search, variable domain search

贺琪, 官礼和, 崔焕焕. 硬时间窗VRP的混合变邻域禁忌搜索算法[J]. 计算机工程与应用, 2023, 59(13): 82-91.

HE Qi, GUAN Lihe, CUI Huanhuan. Hybrid Variable Neighborhood Tabu Search Algorithm for Vehicle Routing Problem with Hard Time Window[J]. Computer Engineering and Applications, 2023, 59(13): 82-91.

参考文献

[1] VIGO D，TOTH P.Vehicle routing：problems，methods，and applications，Second Edition[M].[S.l.]：Society for Industrial and Applied Mathematics，2014.
[2] ZHANG H，GE H，YANG J，et al.Review of vehicle routing problems：models，classification and solving algorithms[J].Archives of Computational Methods in Engineering，2022，29：195-221.
[3] DIXIT A，MISHRA A，SHUKLA A.Vehicle routing problem with time windows using meta-heuristic algorithms：a survey[M]//Harmony Search and Nature Inspired Optimization Algorithms.Singapore：Springer，2019：539-546.
[4] LENSTRA J K，KAN A H G R.Complexity of vehicle routing and scheduling problems[J].Networks，2019，11（2）：221-227.
[5] QI Y，HOU Z，LI H，et al.A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows[J].Computers & Operations Research，2015，62：61-77.
[6] MAY A T，JARIYAVAJEE C，POLVICHAI J.An improved genetic algorithm for vehicle routing problem with hard time windows[C]//Proceedings of 2021 International Conference on Electrical，Computer and Energy Technologies（ICECET），2021：1-6.
[7] VILLALBA A，ROTTA E.Clustering and heuristics algorithm for the vehicle routing problem with time windows[J].International Journal of Industrial Engineering Computations，2022，13（2）：165-184.
[8] 刘小兰，郝志峰，汪国强，等.有时间窗的车辆路径问题的近似算法研究[J].计算机集成制造系统，2004，10（7）：825-831.
LIU X L，HAO Z F，WANG G Q，et al.Improved large neighborhood search algorithm for vehicle routing problem with time windows[J].Computer Integrated Manufacturing Systems，2004，10（7）：825-831.
[9] 潘帅，陈钰成，高元，等.带软时间窗的多种服务需求车辆调度问题及其禁忌搜索算法研究[J].武汉理工大学学报（交通科学与工程版），2020，44（6）：1123-1128.
PAN S，CHEN Y C，GAO Y，et al.Research on vehicle scheduling problem of multiple service demands with soft time window and its taboo search algorithm[J].Journal of Wuhan University of Technology（Traffic Science and Engineering Edition），2020，44（6）：1123-1128.
[10]   陈久梅，李英娟，胡婷，等.开放式带时间窗车辆路径问题及变邻域搜索算法[J].计算机集成制造系统，2021，27（10）：3014-3025.
CHEN J M，LI Y J，HU T，et al.Solving open vehicle routing problem with time windows based on variable neighborhood search algorithm[J].Computer Integrated Manufacturing Systems，2021，27（10）：3014-3025.
[11]   KUO R J，LU S H，LAI P Y，et al.Vehicle routing problem with drones considering time windows[J].Expert Systems with Applications，2022，191：116264.
[12]   SUN J.An improved simulated annealing algorithm for fleet size and mix vehicle routing problem with time windows[C]//Proceedings of 2021 IEEE International Conference on Emergency Science and Information Technology（ICESIT），2021：39-43.
[13]   李国明，李军华.基于混合禁忌搜索算法的随机车辆路径问题[J].控制与决策，2021，36（9）：9-15.
LI G M，LI J H.Random vehicle routing problem based on hybrid tabu search algorithm[J].Control and Decision，2021，36（9）：9-15.
[14]   李珺，段钰蓉，郝丽艳，等.混合优化算法求解同时送取货车辆路径问题[J].计算机科学与探索，2022，16（7）：1623-1632.
LI J，DUAN Y R，HAO L Y，et al.Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery?pickup[J].Journal of Frontiers of Computer Science and Technology，2022，16（7）：1623-1632.
[15] LIN B，GHADDAR B，NATHWANI J.Deep reinforcement learning for the electric vehicle routing problem with time windows[J].IEEE Transactions on Intelligent Transportation Systems，2022，23（8）：11528-11538.
[16]   LI B，WU G，HE Y，et al.An overview and experimental study of learning based optimization algorithms for the vehicle routing problem[J].IEEE/CAA Journal of Automatica Sinica，2022，9（7）：1115-1138.
[17]   GLOVER F.Future paths for integer programming and links to artificial intelligence[J].Computers & Operations Research，1986，13（5）：533-549.
[18]   MLADENOVI? N，HANSEN P.Variable neighborhood search[J].Computers & Operations Research，1997，24（11）：1097-1100.
[19] SADATI M E H，AKSEN D，ARAS N.The r-interdiction selective multi-depot vehicle routing problem[J].International Transactions in Operational Research，2020，27（2）：835-866.
[20]   CHAIEB M，SASSI D B.Measuring and evaluating the home health care scheduling problem with simultaneous pick-up and delivery with time window using a tabu search metaheuristic solution[J].Applied Soft Computing，2021，13：107957.
[21]   GENDREAU M，POTVIN J Y.Handbook of metaheuristics[M].[S.l.]：Springer Publishing Company，Incorporated，2019.
[22] PAUL A，KUMAR R S，ROUT C，et al.Designing a multi-depot multi-period vehicle routing problem with time window：hybridization of tabu search and variable neighbourhood search algorithm[J].Sādhanā，2021，183：1-11.
[23]   SADATI M，ATAY B，AKSEN D.An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems[J].Computers and Operations Research，2021，133：105269.
[24]   ZHOU H，QIN H，ZHANG Z，et al.Two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery[J].Soft Computing，2022，26：3345-3360.
[25] CLARKE G，WRIGHT J W.Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research，1964，12（4）：568-581.
[26]   SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research，1987，35（2）：254-265.
[27]   HOMBERGER J，GEHRING H.A two-phase hybrid metaheuristic for the vehicle routing problem with time windows[J].European Journal of Operational Research，2005，162（1）：220-238.