Polyhedral Analysis of the Vehicle Routing Problem

A successful technique for tackling combinatorial optimization problems is "branch-and-cut", a fusion of the classical cutting plane and branch-and-bound methods. The key to the success of a branch-and-cut code is an understanding of certain integer polyhedra. This talk will give an overview of current knowledge about polyhedra associated with vehicle routing problems, with an emphasis on the capacitated VRP. It will be seen that vehicle routing polyhedra are more complex, and less well understood, than traveling salesman polyhedra. As a result, branch-and-cut codes for the VRP are not yet capable of dealing with truly large-scale instances.