Capacitated Vehicle Routing on Trees

Martine Labbé, Gilbert Laporte and Hélène Mercure
Additional contact information
Martine Labbé: Erasmus University, Rotterdam, The Netherlands
Gilbert Laporte: University of Montreal, Montreal, Quebec, Canada
Hélène Mercure: University of Montreal, Montreal, Quebec, Canada

Operations Research, 1991, vol. 39, issue 4, 616-622

Abstract: T = ( V , E ) is a tree with nonnegative weights associated with each of its vertices. A fleet of vehicles of capacity Q is located at the depot represented by vertex v 1 . The Capacitated Vehicle Routing Problem on Trees (TCVRP) consists of determining vehicle collection routes starting and ending at the depot such that: the weight associated with any given vertex is collected by exactly one vehicle; the sum of all weights collected by a vehicle does not exceed Q ; a linear combination of the number of vehicles and of the total distance traveled by these vehicles is minimized. The TCVRP is shown to be NP-hard. This paper presents lower bounds for the TCVRP based on the solutions of associated bin packing problems. We develop a linear time heuristic (upper bound) procedure and present a bound on its worst case performance. These lower and upper bounds are then embedded in an enumerative algorithm. Numerical results follow.

Keywords: transportation:; vehicle; routing (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.4.616 (application/pdf)

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:inm:oropre:v:39:y:1991:i:4:p:616-622

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().