Article ID: | iaor2005205 |
Country: | Spain |
Volume: | 11 |
Issue: | 2 |
Start Page Number: | 325 |
End Page Number: | 336 |
Publication Date: | Dec 2003 |
Journal: | TOP |
Authors: | Dullaert W., Brysy O. |
Keywords: | heuristics |
This paper presents a modification of the well-known Solomon sequential insertion heuristic I1 for the Vehicle Routing Problem with Time Windows (VRPTW). VRPTW involves servicing customers within a pre-specified service time window by homogeneously capacitated vehicles from a single depot. By using two new measures for the additional time needed to insert a customer in the route, significantly better solutions are obtained for relatively short routes, compared to the original Solomon sequential insertion heuristic I1. Because high-quality initial heuristics often allow local searches and metaheuristics to achieve better solutions more quickly, the new approach is likely to help generate better solutions to practical routing problems.