Article ID: | iaor20113657 |
Volume: | 9 |
Issue: | 1 |
Start Page Number: | 49 |
End Page Number: | 82 |
Publication Date: | Mar 2011 |
Journal: | 4OR |
Authors: | Righini Giovanni, Salani Matteo, Liberatore Federico |
Keywords: | penalty functions, time windows |
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.