Polyhedral results for a vehicle routing problem (Q1176821)

Let \(G=(V,E)\) be the complete, undirected graph on \(n\) vertices. With any vertex we can associate a demand: 0 for vertex 1, the depot, and 1 for every other vertex. For any edge \(\{i,j\}\) we are given a distance \(c_{ij}\), and, finally, a fleet of \(K\) identical vehicles of integer capacity \(q\geq 2\) and based at the depot is available. The vehicle routing problem (VRP) considered in this paper is the following: Determine \(k\) routes for the vehicles such that: (1) every route begins and ends at the depot; (2) each vertex \(i\neq 1\) is visited exactly once and by only one vehicle; (3) the number of vertices visited by a vehicle never exceeds its capacity \(q\); (4) the total distance is minimized. This problem can be formulated as a 0-1 linear programming problem, involving degree, subtour-elimination and capacity constraints. The vehicle routing polytope \(P_{\hbox{VRP}}\) is defined to be the convex hull of all feasible solutions of this 0-1 problem. The authors determine the dimension of \(P_{\hbox{VRP}}\) depending on the number of customers, the number of vehicles and their capacity. They study the facial structure of \(P_{\hbox{VRP}}\) and establish conditions under which the trivial, the subtour elimination and the capacity constraints are facet-defining for \(P_{\hbox{VRP}}\).