Time-window relaxations in vehicle routing heuristics - Archive ouverte HAL Access content directly
Journal Articles Journal of Heuristics Year : 2015

Time-window relaxations in vehicle routing heuristics

(1) , (2) , (2) , (3)
1
2
3

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.
Not file

Dates and versions

hal-02521881 , version 1 (27-03-2020)

Identifiers

Cite

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

Collections

CNRS UTT LOSI
12 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More