|
Routing problems are of great importance in practice. Common
examples of such problems include mail delivery and schoolbus
routing. The goals of such problems are cost minimization and
service improvement. These problems can be modeled easily and
naturally with graphs. Consider an undirected weighted graph
with objects located at various vertices. Associated with each
object is a destination vertex, to which that object is to be
moved by a vehicle that traverses the edges of the graph. In
the case that the underlying graph is a path with a vehicle of
capacity greater than one, it has been shown that if objects
cannot be dropped at the intermediate vertices, then the
problem is NP-complete. We focus on the case that the
underlying graph is a path and give an approximation algorithm
for the nonpreemptive version with a vehicle of capacity 2 and
starting from the terminuses of the path. We present an
algorithm which generates a tour of cost at most 3 times as
large as the minimum-cost for the case $C=2$.
|