Back to Search
Start Over
CAPACITATED VEHICLE ROUTING ON TREES.
- Source :
- Operations Research; Jul/Aug91, Vol. 39 Issue 4, p616, 7p
- Publication Year :
- 1991
-
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[sub 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0030364X
- Volume :
- 39
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 4487843
- Full Text :
- https://doi.org/10.1287/opre.39.4.616