Skip to Main content Skip to Navigation
Journal articles

Time-window relaxations in vehicle routing heuristics

Abstract : The contribution of infeasible solutions in heuristic searches for vehicle routing problems (VRP) is not a subject of consensus in the metaheuristics community. Infeasible solutions may allow transitioning between structurally different feasible solutions, thus enhancing the search, but they also lead to more complex move-evaluation procedures and wider search spaces. This paper introduces an experimental assessment of the impact of infeasible solutions on heuristic searches, through various empirical studies on local improvement procedures, iterated local searches, and hybrid genetic algorithms for the VRP with time windows and other related variants with fleet mix, backhauls, and multiple periods. Four relaxation schemes are considered, allowing penalized late arrivals to customers, early and late arrivals, returns in time, or a flexible travel time relaxation. For all considered problems and methods, our experiments demonstrate the significant positive impact of penalized infeasible solution. Differences can also be observed between individual relaxation schemes. The “returns in time” and “flexible travel time” relaxations appear as the best options in terms of solution quality, CPU time, and scalability.
Document type :
Journal articles
Complete list of metadatas
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, March 27, 2020 - 4:31:06 PM
Last modification on : Monday, July 20, 2020 - 12:34:52 PM





Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Christian Prins. Time-window relaxations in vehicle routing heuristics. Journal of Heuristics, Springer Verlag, 2015, 21 (3), pp.329-358. ⟨10.1007/s10732-014-9273-y⟩. ⟨hal-02521881⟩



Record views