Authors: Stanojević, Milan
Stanojević, Bogdana 
Vujošević, Mirko
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Enhanced savings calculation and its applications for solving capacitated vehicle routing problem
Journal: Applied Mathematics and Computation
Volume: 219
Issue: 20
First page: 10302
Last page: 10312
Issue Date: 15-Jun-2013
Rank: M21
ISSN: 0096-3003
DOI: 10.1016/j.amc.2013.04.002
The vehicle routing problem (VRP) is one of the most explored combinatorial problems in operations research. A very fast and simple algorithm that solves the VRP is the well known Clarke-Wright savings algorithm. In this paper we introduce a new way of merging routes and the corresponding formula for calculating savings. We also apply the enhanced merging to develop a new heuristic - Extended Savings Algorithm (ESA) that dynamically recalculates savings during iterations. Computational results show that, on average ESA gives better solutions than the original savings algorithm. Implementing randomization of some steps of our heuristic we obtained even better results which competes with more complex and well known heuristics. The ESA is further used to generate good routes as part of a set-covering-based algorithm for the Capacitated VRP (CVRP). The numerical results of our experiments are reported.
Keywords: Greedy heuristic | Set-covering-based algorithm | Vehicle routing problem
Publisher: Elsevier
Project: Multimodal Biometry in Identity Management 
Scientific-technological support to enhancing the safety of special road and rail vehicles 
Optimization of Distributive and Reverse Flows in Logistic Systems 

Show full item record


checked on May 22, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




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