List of issues > Series «Mathematics». 2024. Vol 48
Models and Local Search Algorithms for Vehicle Routing
with Returns and Time Windows
Author(s)
Lidia A. Zaozerskaya1
,
Yulia V. Zakharova1


1Sobolev Institute of Mathematics SB RAS, Omsk, Russian Federation
Abstract
A vehicle routing problem for servicing objects with the possibility of distributing work between vehicle taking into account time windows is considered. We
discuss approaches to constructing integer linear programming models and their modifications. A large neighborhood search algorithm is proposed to find approximate solutions.
Here an improving solution is constructed using the “destroy” and “repair” methods
at each step. A series of instances with various structures are proposed, in particular
demonstrating the reason of returns to objects for vehicles. The results of an experimental
evaluation of models and algorithms are presented.
About the Authors
Lidia A. Zaozerskaya, Cand. Sci. (Phys.Math.), Assoc. Prof., Sobolev Institute of Mathematics SB RAS, Omsk, 644090, Russian Federation, zaozer@ofim.oscsbras.ru
Yulia V. Zakharova, Cand. Sci. (Phys.Math.), Sobolev Institute of Mathematics SB RAS, Omsk, 644090, Russian Federation, yzakharova@ofim.oscsbras.ru
For citation
Zaozerskaya L. A., Zakharova Yu. V. Models and Local Search Algorithms for Vehicle Routing with Returns and Time Windows. The Bulletin of Irkutsk State University. Series Mathematics, 2024, vol. 48, pp. 95–110. (in Russian)
https://doi.org/10.26516/1997-7670.2024.48.95
Keywords
vehicle routing, local search, integer programming, model
UDC
519.8+519.6
MSC
90C59, 68W20
DOI
https://doi.org/10.26516/1997-7670.2024.48.95
References
- Eremeev A.V., Zaozerskaya L.A., Zakharova Yu.V. Investigation of integer programming models for rig routing problem with returns and time windows. PREPRINTS.RU, 2022, https://doi.org/10.24108/preprints-3112582 (in Russian)
- Kulachenko I.N., Kononova P.A. A hybrid algorithm for the drilling rig routing problem. Journal of Applied and Industrial Mathematics, 2021, vol. 15, iss. 2, pp. 261–276. https://doi.org/10.33048/daio.2021.28.703
- Bezerra S.N., Souza M.J.F., de Souza S.R. A variable neighborhood search-based algorithm with adaptive local search for the Vehicle Routing Problem with Time Windows and multi-depots aiming for vehicle fleet reduction. Comp. & Oper. Res., 2023, vol. 149. 106016. https://doi.org/10.1016/j.cor.2022.106016
- Blum C., Eremeev A.V., Zakharova Y.V. Hybridizations of evolutionary algorithms with Large Neighborhood Search. Comp. Sci. Rev., 2022, vol. 46. 100512. https://doi.org/10.1016/j.cosrev.2022.100512
- Borisovsky P., Eremeev A., Kovalenko Y., Zaozerskaya L. Rig routing with possible returns and stochastic drilling times. Proc. of Mathematical Optimization Theory and Operations Research. MOTOR 2021. LNCS, 2021, vol. 12755, pp. 51–66.https://doi.org/10.1007/978-3-030-77876-7_4
- Borisovsky P. A parallel greedy approach enhanced by genetic algorithm for the stochastic rig routing problem. Opt. Let. OnLine-First, 2023, 15 p.https://doi.org/10.1007/s11590-023-01986-x
- Groer C., Golden B., Wasil E. A library of local search heuristics for the vehicle routing problem. Math. Prog. Comp., 2010, vol. 2, pp. 79–101.https://doi.org/10.1007/s12532-010-0013-5
- Nguyen V.S., Pham Q.D., Nguyen T.H., Bui Q.T. Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints. Comp. and Ind. Eng., 2022, vol. 172, part A. 108597.https://doi.org/10.1016/j.cie.2022.108597
- Sadati M.E.H., Akbari V., ¸Catay B. Electric vehicle routing problem with flexible deliveries. Int. Jour. of Prod. Res., 2022, vol. 60, no. 13, pp. 4268–4294.https://doi.org/10.1080/00207543.2022.2032451
- Shang Q., Huang Y., Wang Y. et al. Solving vehicle routing problem by memetic search with evolutionary multitasking. Memetic Comp., 2022, vol. 14, pp. 31–44.https://doi.org/10.1007/s12293-021-00352-7
- Yu V.F., Susanto H., Jodiawan P., Ho T.-W., Lin S.-W., Huang Y.- T. A simulated annealing algorithm for the vehicle routing problem with parcel lockers. IEEE Access, 2022, vol. 10, pp. 20764–20782.https://doi.org/10.1109/ACCESS.2022.3152062