POLYHEDRAL STUDY OF THE CAPACITATED VEHICLE-ROUTING PROBLEM

The capacitated vehicle routing problem (CVRP) considered in this pape r occurs when goods must be delivered from a central depot to clients with known demands, using k vehicles of fixed capacity. Each client mu st be assigned to exactly one of the vehicles. The set of clients assi gned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the veh icles is large enough, this problem reduces to the famous traveling sa lesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxa tion of CVRP. Our approach for CVRP and GVRP is to extend the polyhedr al results known for TSP. For example, the subtour elimination constra ints can be generalized to facets of both CVRP and GVRP. Interesting c lasses of facets arise as a generalization of the comb inequalities, d epending on whether the depot is in a handle, a tooth, both or neither . We report on the optimal solution of two problem instances by a cutt ing plane algorithm that only uses inequalities from the above classes .