Analyses of Advanced Iterated Tour Partitioning Heuristics for Generalized Vehicle Routing Problems

Theoretical analyses of a set of iterated-tour partitioning vehicle routing algorithms applicable to a wide variety of commonly-used vehicle routing problem variants are presented. We analyze the worst- case performance of the algorithms and establish tightness of the derived bounds. Among other variants we capture the cases of pick-up and delivery, and multiple depots. We also introduce brand new concepts such as mobile depots, partitioning of customer nodes into groups, and potential opportunistic under-utilization of vehicle capacity by only partially loading the vehicle, among others, which arise from a printed circuit board application. The problems studied are of critical importance in many practical applications.