On the Complexity of Computing Optimal Private Park-and-Ride Plans - Computational Logistics - page 73

On the Complexity of Computing Optimal
Private Park-and-Ride Plans
Martin Olsen
AU Herning
Aarhus University, Denmark
[e-mail]
Abstract. We consider the problem where a group of people scattered
in a weighted graph G ( V,E ) has to travel by car to a common destina-
tion (the number of vertices may be much bigger than the number of
people) where the weight of an edge is the cost of traveling along the
edge with a car. Every member of the group has a car at their disposal
and the objective is to minimize the total cost for getting all the mem-
bers to the common destination. The members have the possibility of
meeting and parking at the vertices and continue the journey sharing a
car. We examine the computational complexity of the problem. Among
other things, we show that the problem is APX-complete for the realis-
tic setting where the cars have capacity 4 even restricted to undirected
graphs where all edges have cost 1.
1 Introduction
In today's era of environmental awareness the concept of “ridesharing” where
people share rides in private cars gains more and more attraction. The rising
prices on fuels and the implementation of road pricing also pushes people in
the direction of ridesharing and the activity of web services for coordinating
ridesharing like, for example, www.carpooling.com is growing rapidly. When the
author of this paper drives to work he passes a roundabout with a so-called
“park-and-ride lot” seen in Fig. 1 where people driving can meet and park in
order to continue their journey in one car (or fewer cars). This triggered the
question: “How hard is it to compute an optimal scheme for private ridesharing?”
In this paper we focus on the problem of computing an optimal plan for the
situation where several people want to travel to the same destination and where
they all have a car at their disposal and are willing to “park-and-ride” (using, e.g.,
dedicated “park-and-ride” lots) as just described. If we could solve this problem
eciently we could lower the cost for every participant. We will refer to this
problem as the PRIVATE-PARK-AND-RIDE problem since no public transport
is involved unless the common destination is a train station, bus station, airport,
etc. The main contribution of this paper is a theorem stating that this problem
is APX-complete even restricted to cars with capacity 4 and simple undirected
graphs where the cost of driving along an edge with a car is 1. This shows that
a constant > 0 exists such that for any polynomial time algorithm computing