We give a survey of integer programming formulations for the Capacitated Vehicle Routing Problem (CVRP). These include two- and three-index vehicle flow formulations, set partitioning formulations, and various one-, two- and multi-commodity flow formulations. We then show how these various formulations can be compared theoretically using polyhedral projection. Our main results are: 1. The three-index vehicle flow formulation, augmented by certain families of valid inequalities, gives the same lower bound as the two-index vehicle flow formulation, augmented by certain simpler families of valid inequalities, 2. The two-commodity flow formulation of Baldacci et al.~gives the same lower bound and the same multistar inequalities as the one-commodity Gavish and Graves formulation, 3. A certain non-standard multi-commodity flow formulation, with one commodity per customer, implies by projection certain `hypotour-like' inequalities in the two-index space, 4. The set partitioning formulations imply by projection both multistar and hypotour-like inequalities in the two-index space. Using these results, we will argue that the best way to solve the CVRP is to use branch-cut-and-price, based on a combination of the two-index vehicle flow and set partitioning formulations.

We consider the vehicle routing problem with time windows focussing on an exact method solved by relaxation. New Lagrangean multipliers are determined by a trust region method. To obtain integer solutions branch and bound is applied. In order to reduce the number of nodes in the branch and bound tree and in order to speed up the solution process we are introducing new valid inequalities: Infeasible path elimination constraints, Odd CAT constraints and precedence constraints. In this presentation we will in particular focus on precedence constraints. Computational experience indicates a considerable computational improvement.

In Arcs-States models for the VRPC, the variables correspond to the resources used on arcs. The size is pseudo-polynomial and column and row generations are used. The Dates-Only model lies on a relaxation where a resource is removed from the states. We illustrate our results on Solomon's benchmark.

In this talk, we propose some new refinements to improve the capabilities of column generation approaches in the context of the Vehicle Routing Problem with Time Windows (VRPTW). We first introduce the notion of Limited Discrepancy Search (LDS) known in Constraint Programming (CP) to the field of Dynamic Programming. We also discuss how the state graph of the dynamic program used to solve the subproblem can be manipulated in order to simulate local search during label extension. Finally we present some lower bounds that allow the elimination of a substantial number of labels during the search. The proposed refinements were tested on the well-known Solomon instances for the VRPTW. Computational results demonstrate the considerable impact of these refinements in term of computing time.