A PTAS for Minimum Makespan Vehicle Routing in Trees
share
We consider a variant of the vehicle routing problem on trees in which the goal is to route a fleet of vehicles to serve a set of clients so that the makespan, the longest distance traveled by one of the vehicles, is minimized. This is referred to as the Minimum Makespan Vehicle Routing problem on trees. We present a polynomial time approximation scheme (PTAS) for this problem. Our main insight is that we can restrict the set of potential solutions without adding too much to the optimal makespan. This simplification relies on partitioning the tree into clusters such that there exists a near-optimal solution in which every tour that visits a given cluster takes on one of a few forms. In particular, there are at most two tours serving clients in any cluster. Our dyamic program then finds a near-optimal set of tours using these simple building blocks within each cluster rather than making decisions for covering each leaf in the tree. This limits the amount of rounding error incurred by the dynamic program, yielding the PTAS.
READ FULL TEXT