A result on projection for the Vehicle Routing Problem

In this paper we present a result on projection for the Vehicle Routing Problem (VRP). The VRP is closely related to delivery-type problems and appears in a large number of practical situations concerning the distribution of commodities. The present work focuses on a commodity flow formulation presented by Gavish and Graves. This formulation includes two sets of variables and, hence, it also must include coupling constraints between the two sets of variables. These coupling constraints can be defined in several ways. The main result of this work establishes that when the strongest form of the coupling constraints is used in the flow formulation, the equivalent formulation using only the Xij variables satisfies the so called multistar constraints which, for certain parameters, induce facets of the non-directed VRP polytope. Using an idea taken from Gouveia, we show how to derive a more compact representation, in the number of constraints, of the multistar constraints. Some consequences of our projection result are also discussed.