A Tight Approximation Algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line

In this paper, the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand. The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint. The authors show that this problem has no polynomial-time algorithm with performance ratio less than 2 on condition that P ≠ NP, and then provide a 2-approximation algorithm.