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

2
checked on Dec 4, 2024

Page view(s)

25
checked on Dec 6, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.