|
 
|
[WF18] Taxi-sharing: Parameterized complexity and approximability of the dial-a-ride problem with money as an incentive
Revue Internationale avec comité de lecture : Journal Theoretical Computer Science, vol. publication en cours, pp. p1-22, 2018, (doi:https://doi.org/10.1016/j.tcs.2018.06.006)Mots clés: Parameterized complexity Approximability Dial-a-ride problem Taxi-sharing
Résumé:
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 capa 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 α, capa 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 capa 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.
BibTeX
| @article { | |||
| WF18, | |||
| title | = | "{Taxi-sharing: Parameterized complexity and approximability of the dial-a-ride problem with money as an incentive }", | |
| author | = | "D. Watel and A. Faye", | |
| journal | = | "Theoretical Computer Science", | |
| year | = | 2018, | |
| volume | = | publication en cours, | |
| pages | = | "p1-22", | |
| doi | = | "https://doi.org/10.1016/j.tcs.2018.06.006", | |
| } | |||
