کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4628730 | 1340564 | 2013 | 11 صفحه PDF | دانلود رایگان |
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.
Journal: Applied Mathematics and Computation - Volume 219, Issue 20, 15 June 2013, Pages 10302–10312