A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

Tetsuo Asano (), Naoki Katoh () and Kazuhiro Kawashima ()
Additional contact information
Tetsuo Asano: JAIST
Naoki Katoh: Kyoto University
Kazuhiro Kawashima: JAIST

Journal of Combinatorial Optimization, 2001, vol. 5, issue 2, No 4, 213-231

Abstract: Abstract 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, $$\left( {\sqrt {41} - 1} \right)/4$$ ), which is an improvement over the existing 1.5-approximation.

Keywords: capacitated vehicle routing; approximation algorithm (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1023/A:1011461300596 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:2:d:10.1023_a:1011461300596

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011461300596

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().