Authors: | Matijević, Luka Ilin, Vladimir Davidović, Tatjana Jakšić Kruger, Tatjana Pardalos, Panos M. |
Affiliations: | Computer Science Mathematical Institute of the Serbian Academy of Sciences and Arts |
Title: | General VNS for asymmetric vehicle routing problem with time and capacity constraints | Journal: | Computers and Operations Research | Volume: | 167 | First page: | 106630 | Issue Date: | 1-Jul-2024 | Rank: | ~M21 | ISSN: | 0305-0548 | DOI: | 10.1016/j.cor.2024.106630 | Abstract: | We consider a real-life transportation problem from a hypermarket company in Serbia that consists of delivering online ordered and possibly perishable goods from a single depot to multiple customers. It can be modeled as an asymmetric vehicle routing problem that requires visiting and serving all customers using a limited number of homogeneous vehicles and taking into account time and capacity constraints. The objective function to be minimized is the total distance traveled. We provide a mixed-integer programming (MIP) formulation of the problem and develop several Local Search based metaheuristic methods exploring combinatorial formulation of the considered problem: Multistart Local Search (MLS), Greedy Randomized Adaptive Search Procedure (GRASP), and several variants of General Variable Neighborhood Search (GVNS) methods. All methods are compared on real-life instances provided by the hypermarket company and benchmark instances from the relevant literature. The obtained results show the superiority of GVNS-based methods with respect to both solution quality and running time, confirming that systematic search procedures have more success when dealing with hard optimization problems. |
Keywords: | Local search | Metaheuristics | Minimization of total distance | Multiple neighborhoods | Routing homogeneous vehicles | Single depot | Publisher: | Elsevier | Project: | Project no. 451-03-47/2023-01/200156 “Innovative scientific and artistic research from the FTS (activity) domain ” and Contract No. 451-03-47/2023-01/ 200029 |
Show full item record
SCOPUSTM
Citations
1
checked on Nov 8, 2024
Page view(s)
22
checked on Nov 8, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.