On the capacitated vehicle routing problem

On the capacitated vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor20041077
Country: Germany
Volume: 94
Issue: 2/3
Start Page Number: 343
End Page Number: 359
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors: , , ,
Keywords: programming: travelling salesman, vehicle routing & scheduling
Abstract:

We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY.

Reviews

Required fields are marked *. Your email address will not be published.