|
|||||
|
|
A column generation algorithm for the vehicle routing problem with soft time windows |
|
| Authors: | Federico Liberatore Giovanni Righini Matteo Salani |
| Affiliation: | 1. Dipartimento di Tecnologie dell??Informazione, Universit?? degli Studi di Milano, Via Bramante 65, 26013, Crema, Italy 3. Kent Business School, University of Kent, Canterbury, Kent, CT2 7PE, UK 2. TRANSP-OR, ??cole Polytechnique F??d??rale de Lausanne, Station 8, 1015, Lausanne, Switzerland 4. IDSIA, Istituto Dalle Molle di Studi sull??Intelligenza Artificiale, Galleria 2, 6928, Manno-Lugano, Switzerland |
| Abstract: | The Vehicle Routing Problem with Time Windows consists of computing a minimum cost set of routes for a fleet of vehicles of limited capacity visiting a given set of customers with known demand, with the additional constraint that each customer must be visited in a specified time window. We consider the case in which time window constraints are relaxed into “soft” constraints, that is penalty terms are added to the solution cost whenever a vehicle serves a customer outside of his time window. We present a branch-and-price algorithm which is the first exact optimization algorithm for this problem. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |