Heuristics for unequal weight delivery problems with a fixed error guarantee (Q1095815)

This paper presents heuristics that are based on optimal partitioning of a travelling salesman tour, for solving the unequal weight delivery problem. The worst case error performance is given as a bound on the worst case ratio of the cost of the heuristic solution to the cost of the optimal solution. A fully polynomial procedure which consists of applying the optimal partitioning to a travelling salesman tour generated by Christofides' heuristic has a worst case error bound of 3.5-3/Q where Q is the capacity limit of the vehicles. When optimal partitioning is applied to an optimal travelling salesman tour, the worst case error bound becomes 3-2/Q.