рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

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
  1. 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)
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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

Full text (russian)