A new approximation algorithm for the capacitated vehicle routing problem on a tree

This paper presents a new approximation algorithm for a vehicle routing pro blem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity . It is assumed that the demand of a customer is splittable, i.e., it can b e served by more than one vehicle. The problem we are concerned with in thi s paper asks to find a set of tours of the vehicles with minimum total leng ths. Each tour begins at the depot, visits a subset of the customers and re turns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, (root 41 - 1)/4), which is an improvement over the existing 1.5-approximation.