|
Consider a set of objects which would be transported from their
initial positions to their destinations. A vehicle is used to
transport these objects. The problem of finding a minimum cost
for transporting all objects to their destinations is the so
called vehicle routing problem. There are many different
versions about the vehicle routing problem. This thesis
discusses the case that no object can be dropped before
arriving its destination and the capacity of the vehicle is
greater than one. If the underlying graph is a path, Guan has
proved that the problem is NP-complete. Hence, we present an
approximation algorithm for this case, which generates a
transportation of cost at most c+1 times the cost of the
optimal transportation, where c is the capacity. Furthermore,
let lambda be the number of minimum times the vehicle traverses
the edge, if the values of lambda's of the edges on the path
are monotone or first decreasing and then increasing, we
present efficient algorithms for these problems to generate
optimal transportations. And if the values of lambda's are
first increasing and then decreasing, we present an
approximation algorithm which generats a transportation of cost
at most 3/2 times as large as the cost of the optimal
transportation.
|