Abstract
The vehicle routing problem is a classic NP-hard problem in modern logistics industry. The aim of this paper is to propose a repetitive grouping Max-Min Ant System (MMAS) to solve multi-depot vehicle routing problem with time window. The whole algorithm adopts the framework of decomposition. Firstly, the algorithm defines boundary customers and groups them into corresponding depot groups repeatedly for sub-problem optimization. Secondly, the algorithm uses adaptive range technique to determine the size of boundary customers, so as to balance the convergence and resource consumption of the algorithm. Finally, local search operator is integrated into the sub-problem optimization to improve the search ability. The algorithm is tested on several benchmark problems. Experimental results show that the proposed algorithm can effectively improve the performance in most cases compared with several state-of-the-art evolutionary algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Bae, H., Moon, I.: Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles. Appl. Math. Model. 40(13–14), 6536–6549 (2016)
Bettinelli, A., Ceselli, A., Righini, G.: A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transport. Res. Part C: Emerg. Technol. 19(5), 723–740 (2011)
Brandão, J.: A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. Eur. J. Oper. Res. 284(2), 559–571 (2020)
Cordeau, J.F., Laporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Society 52(8), 928–936 (2001)
Cordeau, J.F., Laporte, G., Mercier, A.: Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows. J. Oper. Res. Society 55(5), 542–546 (2004)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)
Desaulniers, G., Lavigne, J., Soumis, F.: Multi-depot vehicle scheduling problems with time windows and waiting costs. Eur. J. Oper. Res. 111(3), 479–494 (1998)
Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst., Man, Cybern., Part B (Cybernetics) 26(1), 29–41 (1996)
Erdoğan, G.: An open source spreadsheet solver for vehicle routing problems. Comput. Oper. Res. 84, 62–72 (2017)
Fan, H., Yang, X., Li, D., Li, Y., Liu, P., Wu, J.: Half-open multi-depot vehicle routing problem based on joint distribution mode of fresh food. Comput. Integ. Manufact. Syst 25, 256–266 (2019)
Gao, J., Gu, F., Hu, P., Xie, Y., Yao, B.: Automobile chain maintenance parts delivery problem using an improved ant colony algorithm. Adv. Mech. Eng. 8(9), 1687814016665297 (2016)
Kallehauge, B., Larsen, J., Madsen, O.B., Solomon, M.M.: Vehicle routing problem with time windows. In: Column generation, pp. 67–98. Springer (2005). https://doi.org/10.1007/0-387-25486-2_3
Koç, Ç., Bektaş, T., Jabali, O., Laporte, G.: The fleet size and mix location-routing problem with time windows: formulations and a heuristic algorithm. Eur. J. Oper. Res. 248(1), 33–51 (2016)
Li, J., Li, Y., Pardalos, P.M.: Multi-depot vehicle routing problem with time windows under shared depot resources. J. Comb. Optim. 31, 515–532 (2016)
Mancini, S.: A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based matheuristic. Transp. Res. Part C: Emerg. Technol. 70, 100–112 (2016)
Martins, L.d.C., Bayliss, C., Juan, A.A., Panadero, J., Marmol, M.: A savings-based heuristic for solving the omnichannel vehicle routing problem with pick-up and delivery. Transport. Res. Proc. 47, 83–90 (2020)
Nan, W., Shiqi, L., Junfeng, W.: Vehicle routing with time windows in material delivery for automobile general assembly line. Ind. Eng. J. 15(2), 94 (2012)
Niu, M., Liu, R., Wang, H.: A max-min ant system based on decomposition for the multi-depot cumulative capacitated vehicle routing problem. In: 2021 IEEE Congress on Evolutionary Computation (CEC), pp. 620–627. IEEE (2021)
Noori, S., Ghannadpour, S.F.: High-level relay hybrid metaheuristic method for multi-depot vehicle routing problem with time windows. J. Math. Modell. Algorithms 11(2), 159–179 (2012)
Polacek, M., Hartl, R.F., Doerner, K., Reimann, M.: A variable neighborhood search for the multi depot vehicle routing problem with time windows. J. Heuristics 10(6), 613–627 (2004)
Rahimi-Vahed, A., Crainic, T.G., Gendreau, M., Rei, W.: Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm. Comput. Oper. Res. 53, 9–23 (2015)
Thangiah, S.R., Osman, I.H., Sun, T.: Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. Computer Science Department, Slippery Rock University, Technical Report SRU CpSc-TR-94-27 69 (1994)
Toth, P., Vigo, D.: The vehicle routing problem. SIAM (2002)
Acknowledgements
This work was supported by the Provincial Natural Science Foundation of Shaanxi of China (No. 2019JZ-26).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Chen, W., Liu, R., Guo, Q., Niu, M. (2023). A Repetitive Grouping Max-Min Ant System for Multi-Depot Vehicle Routing Problem with Time Window. In: Tan, Y., Shi, Y., Luo, W. (eds) Advances in Swarm Intelligence. ICSI 2023. Lecture Notes in Computer Science, vol 13969. Springer, Cham. https://doi.org/10.1007/978-3-031-36625-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-031-36625-3_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-36624-6
Online ISBN: 978-3-031-36625-3
eBook Packages: Computer ScienceComputer Science (R0)