Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 5, Issue 2, Pages 213-231Publisher
KLUWER ACADEMIC PUBL
DOI: 10.1023/A:1011461300596
Keywords
capacitated vehicle routing; approximation algorithm
Ask authors/readers for more resources
This paper presents a new approximation algorithm for a vehicle routing problem 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 be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available