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
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.