Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees

In this paper Q Iterated Optimal Tour Partitioning, and Best Optimal Tour Partitioning algorithms are studied and analyzed for their worst case error. Both algorithms are based on partitioning an optimal traveling salesman tour in order to generate a feasible solution to the unit weight delivery problem. They have a worst case error bound of 2 − 1/Q where Q is the maximal number of customers a vehicle could visit and N is the total number of customers. Similar worst case error bounds are shown when the algorithms are applied to an α-optimal traveling salesman tour.