Information Technology Reference
In-Depth Information
Fig. 1.
A “park-and-ride lot” at a roundabout
a feasible plan we have an instance
I
such that the algorithm computes a plan
with cost at least (1 +
)
OPT
(
I
)where
OPT
(
I
) is the cost of an optimal plan
(unless NP = P).
1.1 Related Work
Even though the literature on computational logistics is huge (we refer to the
survey by Parragh et al. [13,14]) we have not been able to find literature that
deals specifically with the computational complexity of the problem we focus at
in this paper. Our problem is related to the “dial-a-ride”-problem where some
portables
have to be transported by
mobiles
from a given source to a given desti-
nation (the portables may have different sources and destinations). Our problem
is also related to the special case of this problem where the mobiles are placed at
a
depot
. A typical argument for the hardness of the problems mentioned above is
that they are NP-hard because they generalize the traveling salesman problem
(TSP). The key property making our problem special is that we have a mobile
(car) placed at the location of each portable (person) for every instance which
makes it impossible for us to use an argument similar to the TSP-argument
mentioned above. Helmert [10] studies the computational complexity of the gen-
eral case where mobiles can have arbitrary initial locations and the portables can
have arbitrary sources and destinations and Helmert proves NP-completeness for
several variants of the problem - Helmert also uses portables having no mobiles
