Capacitated vehicle routing on trees

Capacitated vehicle routing on trees

0.00 Avg rating0 Votes
Article ID: iaor19931009
Country: United States
Volume: 39
Issue: 4
Start Page Number: 616
End Page Number: 622
Publication Date: Jul 1991
Journal: Operations Research
Authors: , ,
Keywords: graphs
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 v1. 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. The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.