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.
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].
A pricing algorithm for the vehicle routing problem with Soft Time Windows
G. Righini;
2010
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.