Capacitated vehicle routine problem: Some new cutting planes

The Capacitated Vehicle Routing Problem is concerned with the delivery of a single commodity from a single depot to a set of customers with known individual demands. The objective is to find vehicle routes satisfying the vehicle capacity and minimizing the total distance travelled by all the vehicles. Partial enumeration methods such as Branch and Cut methods are common approaches to solve such hard problems. The success of the Branch and Cut methods in solving the Capacitated Vehicle Routing Problem is highly dependent upon cutting planes used in the description of the polytope. In this paper, we present eight new cutting planes which provide an improved description of the solution space. Using a Branch and Cut algorithm we demonstrate the usefulness of these cuts by generating good lower bounds for 14 large literature benchmark problems. A 100 city problem is solved at the root node.