The pyramidal capacitated vehicle routing problem

This paper introduces the pyramidal capacitated vehicle routing problem (PCVRP) as a restricted version of the capacitated vehicle routing problem (CVRP). In the PCVRP each route is required to be pyramidal in a sense generalized from the pyramidal traveling salesman problem (PTSP). A pyramidal route is defined as a route on which the vehicle first visits customers in increasing order of customer index, and on the remaining part of the route visits customers in decreasing order of customer index. Moreover, this paper develops an exact branch-and-cut-and-price (BCP) algorithm for the PCVRP. A main feature of the algorithm is that exact pricing over elementary routes are done in pseudo-polynomial time. Computational results suggest that PCVRP solutions are highly useful for obtaining near-optimal solutions to the CVRP. Furthermore, pricing of pyramidal routes may prove to be very useful in column generation for the CVRP.