Premium
Bounds for the general capacitated routing problem
Author(s) -
Jansen Klaus
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230304
Subject(s) - arc routing , heuristics , vehicle routing problem , routing (electronic design automation) , mathematical optimization , generalization , computer science , travelling salesman problem , mathematics , combinatorics , computer network , mathematical analysis
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.