Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems
by
Maria Teresa Godinho
Instituto Politécnico de Beja, Portugal
Coauthors: Luis Gouveia (Universidade de Lisboa, DEIO, CIO) Thomas L. Magnanti (Department of Electrical Engineering and Computer Science and Sloan School of Management MIT, Cambridge, MA USA)

We consider two types of hop-indexed models for the unit-demand

asymmetric Capacitated Vehicle Routing problem:

(a) capacitated models guaranteeing that the number of commodities

(paths) traversing any given arc does not exceed a specified capacity;

and (b) hop-constrained models guaranteeing that any route length (number of nodes)

does not exceed a given value. The later might, in turn, be divided

into two classes: (b1) those restricting the length of the path from

the depot to any node k, and (b2) those restricting the length of the

circuit passing through any node k. Our results indicate that

formulations based upon circuit lengths (b2) lead to models with a

linear programming relaxation that is tighter than the linear

programming relaxation of models based upon path lengths (b1) and

that combining features from capacitated models together with

those of circuit lengths can lead to formulations for the CVRP with a

tight linear programming bound. Computational results on a small

number of problem instances with up to 41 nodes and 440 edges show

that the combined model with capacities and circuit lengths produce

average gaps of less than one percent. We also briefly examine the

asymmetric travelling salesman problem, showing the potential use of

the ideas developed for the vehicle routing problem to derive models

with a linear programming relaxation bound that is tighter than the

linear programming relaxation bound of the standard Dantzig, Fulkerson

and Johnson (1954) formulation.

Date received: July 11, 2006