Taxi-sharing: Parameterized complexity and approximability of the dial-a-ride problem with money as an incentive.

Abstract We study, in this paper, a taxi-sharing problem, called Dial-a-Ride problem with money as an incentive (DARP-M). This problem consists in defining a set of taxis that will be shared by different clients in order to reduce their bill by a given factor α < 1. To achieve this, each client shares the cost of the ride with other passengers. More precisely, the fragments of the ride in which the client is alone is fully paid by this client and, for each fragment in which the client shares the taxi with other passengers, the cost is equally divided between the passengers. In addition to this cost constraint, the taxi must satisfy a time window constraint for each passenger and a capacity constraint. We define three versions of the problem: max-DARP-M where the objective is to drive the maximum number of clients with an arbitrarily large number of taxis; max-1-DARP-M in which we want to drive the maximum number of clients with one taxi; and 1-DARP-M which consists in deciding whether it is possible to drive at least one client while satisfying the constraints. We study the parameterized complexity and approximability of those problems with respect to four parameters: the factor α , the capacity c a p a of the taxis, the maximum size TW of the time windows of the clients, and the value S of an optimal solution. Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-1-DARP-M cannot be approximated in polynomial time to within any variable ratio even if α , c a p a and TW are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where c a p a and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1 n -polynomial approximation for max-DARP-M. [ABSTRACT FROM AUTHOR]