On the capacitated vehicle routing problem |
| |
Authors: | TK Ralphs L Kopman WR Pulleyblank LE Trotter |
| |
Institution: | (1) Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18017, e-mail: tkralphs@lehigh.edu, http://www.lehigh.edu/∼tkr2, US;(2) School of OR&IE, Cornell University, Ithaca, NY 14853, US;(3) Exploratory Server Systems and The Deep Computing Institute, IBM Research, Yorktown Heights, NY 10598, US;(4) School of OR&IE, Cornell University, Ithaca, NY 14853, e-mail: ltrotter@cs.cornell.edu, US |
| |
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.
Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002
Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut
Mathematics Subject Classification (2000): 20E28, 20G40, 20C20 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|