|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||Abstract:||
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 Mar 30, 2023
checked on Mar 31, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.