Enhanced savings calculation and its applications for solving capacitated vehicle routing problem

摘要

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.