Bounds for the general capacitated routing problem

This paper presents heuristics that are based on a tour splitting of a general routing tour for solving the general capacitated routing problem (GCRP). This problem is a generalization of the vehicle routing problem (VRP) and the capacitated arc routing problem (CARP). For the VRP, heuristics that consist of an optimum partitioning of a TSP tour generated by Christofides are known and have a worst‐case error of 7/2 − 3/ q for even q , where q is the capacity of the vehicles. If we apply a partitioning to an optimum TSP tour, the worst‐case error becomes 3 − 2/ q for even q . We generalize these results to the GCRP and give also some lower bounds. © 1993 John Wiley & Sons, Inc.