A pricing algorithm for the vehicle routing problem with Soft Time Windows
Contributo in Atti di convegno
Data di Pubblicazione:
2010
Citazione:
A pricing algorithm for the vehicle routing problem with Soft Time Windows / F. Liberatore, G. Righini, M. Salani - In: Innovations in distribution logistics / [a cura di] J.A.E.E. Nunen, M.G. Speranza, L. Bertazzi. - Berlin : Springer, 2010. - ISBN 9783540929437. - pp. 251-266 (( convegno International Workshop on Distribution Logistics tenutosi a Brescia nel 2006 [10.1007/978-3-540-92944-4_13].
Abstract:
The Vehicle Routing Problem with Soft Time Windows consists in computing a
minimum cost set of routes for a fleet of vehicles of limited capacity that must visit a given set of customers with known demand, with the additional feature that each customer expresses a
preference about the time at which the visit should occur. If a vehicle serves the customer out of its specified time window, an additional cost is incurred. Here we consider the case with
penalties linearly depending on the time windows violation. We present an exact optimization algorithm for the pricing problem which arises when the vehicle routing problem with soft time windows is solved by column generation. The algorithm exploits bi-directional and bounded dynamic programming with decremental state space relaxation.
Tipologia IRIS:
03 - Contributo in volume
Keywords:
Column generation; Combinatorial optimization; Dynamic programming; Time windows; Vehicle routing
Elenco autori:
F. Liberatore, G. Righini, M. Salani
Link alla scheda completa:
Titolo del libro:
Innovations in distribution logistics