<figure><img src="image_1.png" /></figure>

HAL
open science

# Taxi-Sharing: Parameterized Complexity and Approximability of the Dial-a-ride problem with money as an incentive

Dimitri Watel, Alain Faye

<figure><img src="image_2.png" /></figure>

## To cite this version:

Dimitri Watel, Alain Faye. Taxi-Sharing: Parameterized Complexity and Approximability of the Dial-a-ride problem with money as an incentive. Theoretical Computer Science, 2018, 745, pp.202-223. 10.1016/j.tcs.2018.06.006. hal-01488042v2

HAL Id: hal-01488042

https://hal.science/hal-01488042v2

Submitted on 24 Jan 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Taxi-Sharing: Parameterized Complexity and Approximability of the Dial-a-ride problem with money as an incentive.

Alain Faye<sup>a,c</sup>, Dimitri Watel<sup>a,b</sup>,

<sup>a</sup>ENSIIE, 1 square de la Résistance, 91025, Evry, FRANCE

<sup>b</sup>SAMOVAR, Telecom SudParis, 9 Rue Charles Fourier, 91000, Évry, FRANCE

<sup>c</sup>CEDRIC, CNAM, 2 rue Conté, 75003, Paris, FRANCE

## 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 $\alpha < 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 $\alpha$, 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 $\alpha$, *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 $\frac{1}{\sqrt{n}}$-polynomial approximation for max-DARP-M.

**Keywords:** Parameterized complexity, Approximability, Dial-a-ride problem, Taxi-Sharing
# 1. Introduction

The Dial-a-Ride problem (DARP) consists in the search for an optimal route for many vehicles in order to drive people from their respective origin to their respective destination. This model is used, for example, to determine an optimized route for taxis in order to pick up passengers. We focus in this article on the complexity of a version of this taxi-sharing problem in which the price paid by each passenger is shared. Such a version, called Dial-a-Ride problem with money as an incentive, was previously introduced and studied in [20, 21].

Ride-sharing, including Taxi-sharing, has been massively studied for the last fifteen years due to the economical impact and the ecological impact of such a research. Indeed, optimizations reducing the number of vehicles or the number of travels is an obvious way to reduce the costs and the greenhouse gas emissions. DARP can be seen as a subproblem of the general pickup and delivery problem (GPDP) described in [22] in which the goal is to transport a resource from different pickup locations to drop off locations. In DARP, we consider a human resource (the clients) and each pickup or drop off location is associated with exactly one client. The consequence of this specific resource is that one must be aware of the user inconvenience.

## 1.1. Related work on the DARP problem

DARP can hardly be defined as a unique problem. The feasible and optimal solutions of a Dial-a-Ride problem depend on the measure, the fleet parameters and the clients constraints. Thus, the variety of studies about DARP is not surprising.

Considering the measure, one may optimize the vehicle travel cost, see for example [3, 16, 19], the total travel time [10] or the profit [7]. Another option is to maximize the number of satisfied requests or a combination of all those parameters [20, 21, 23].

Some constraints modelize the user convenience. A usual option is to search for a feasible solution considering time windows [4, 10, 19, 23] as it has been done for the more general pickup and delivery problem [8]. This last problem is solved with a column generation scheme where columns define admissible routes. In [10, 19], the authors develop a similar approach merging a branch-and-cut algorithm with column generation. In [4, 23], the problem is solved using a Tabu search heuristic. Another option to modelize the user convenience is to tend to minimize the excess ride time [2, 11, 14].

Finally one can consider either the static problem in which all the requests are known in advance or the dynamic version in which the requests may occur at any time [1, 6, 11, 20, 21], this problem is usually solved using a local search heuristic.

A recent review about the Dial-a-Ride problem and some of its generalizations may be found in [15]. We refer the reader to [5, 10] for a more specific review about DARP.
## 1.2. DARP with Money as an incentive

We focus on a problem where the goal is to find a feasible solution satisfying a client cost constraint. Few papers focused on that constraint. In [20, 21], the authors study the version of the problem in which each client, traveling by taxi, may share 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. On the contrary, for each fragment in which the client shares the taxi with other passengers, the cost is equally divided between the passengers. The problem consists in the search for a ride in which every client does not pay more than the cost he would pay alone in a taxi traveling directly from his origin to his destination. Note that a client can be served by being assigned to a private ride but each client must also satisfy a time window constraint. The objective is to maximize the number of served clients. This problem is called Dial-a-Ride problem with Money as Incentive and is denoted by DARP-M.

In [21], the authors give a reduction from the Traveling salesman problem to DARP-M, based on the sole time windows constraint. However, no taxi is shared, all the clients are driven in a private ride. It proves that serving all the clients and satisfying a time windows constraint is NP-Complete. Considering this reduction, DARP-M can be seen as a generalization of TSP in which we add a sharing cost constraint. Although this reduction clearly shows that DARP-M is strongly NP-Complete, it does not reflect the hardness of determining if at least two clients can be served by sharing a taxi while satisfying the cost constraint. That simpler question is not insignificant as it leads to a natural greedy algorithm for DARP-M in which we group clients who can share a taxi until all of them have to be assigned to private rides.

Furthermore, it was shown by [18] that searching for a (not elementary) shortest path between a source and a sink satisfying a time windows constraint is weakly NP-Complete as it can be solved in polynomial time if the width of the time windows is polynomially bounded. Consequently, as the reduction of [21] uses only the time windows constraint and as it is from the strongly NP-Complete problem TSP, it seems that it cannot be easily adapted to prove the hardness of determining if at least two clients can share a taxi.

## 1.3. Our contributions

We focus on the parameterized complexity and the parameterized approximability of three problems derived from DARP-M defined by [20, 21]. The purpose of this paper is mainly to investigate how hard the cost constraint is. Particularly, we point out the fact that every hardness result we give is true even if we do not take into account the time windows.

We now formally define the problems we study. We work in a directed graph $G = (V, A)$. We are given a set of $n$ clients arbitrarily numbered in $[1; n]$. A *client* is attached to two nodes which are respectively the origin and the destination of the client. In order to avoid any ambiguity, a node cannot be the origin or the destination of two clients. If two clients books from and/or for the same place, we can simply duplicate the node in the graph. There are,
in this paper, two ways to refer to a client and its associated nodes. Either we
know the number *i* of the client and, in that case, we refer to the client with *the*
client *i* and to its origin and destination nodes with *v*ᵢ and *v*'<sub>i</sub>; or we know the
origin node *v* of the client and we refer to the client and the destination node
with respectively *cv* and *v*'. We respectively define *V*_c and *V*'<sub>c</sub> as {*v*ᵢ, *i* ≤ *n*}
and {*v*'<sub>i</sub>, *i* ≤ *n*}. A route *P* of a taxi is defined by a list (*u*₁, *u*₂, . . . , *u*₂·*s*(*P*)) of
nodes in *V*_c ∪ *V*'<_c> where *s*(*P*) is the number of clients traveling in *P*. A taxi must
satisfy four constraints.

*Precedence constraint.* For each client *i*, *v*ᵢ ∈ *P* if and only if *v*'<sub>i</sub> ∈ *P*. In that case, if *v*ᵢ = *u*ⱼ and *v*'<sub>i</sub> = *u*ₖ, then *j* < *k*. We say the client *i* *travels* in that taxi, or that the taxi *drives* the client *i*.

*Capacity constraint.* We consider that each taxi has the same number of seats. This number is defined as the capacity capa of the taxis. This capacity is at least 2 and is no more than *n*. For each node *u*<sub>j</sub> ∈ *P*, let *n*<sub>j</sub> = |{*u*<sub>*k*</sub> ∈ *V*<sub>*c*</sub>, *k* ≤ *j*}| − |{*u*<sub>*k*</sub> ∈ *V*'<sub>*c*</sub>, *k* ≤ *j*}|. This value is the number of clients in the taxi immediately after *u*<sub>j</sub>. For every *j*, *n*<sub>j</sub> ≤ *capa*. In addition, if *j* ≠ 2 · *s*(*P*), *n*<sub>j</sub> ≥ 1: a taxi cannot be emptied before the end of the ride.

*Time constraint.* Each arc $a = (u, v) \in A$ is weighted with a non-negative integer $\tau(a)$, corresponding to the time that a taxi spends to go from $u$ to $v$. We extend this function to every couple of nodes in $G$: $\tau(u, v)$ is the weight of a shortest path in $G$ from $u$ to $v$. Each client $i$ is associated with two moments (and integers) $b_i$ and $e_i$ between which a taxi driving that client must pick him up and deliver him. The taxi can start at any moment of the time window of its first client. We respectively define $B_c$ and $E_c$ as the sets containing all the values $b_i$ and $e_i$ for all the clients.

*Cost constraint.* Each arc $a = (u, v) \in A$ is weighted with a non-negative integer $\omega(a)$, corresponding to the cost that a client would pay alone in a taxi driving from $u$ to $v$. We extend this function to every couple of nodes in $G$: $\omega(u, v)$ is the cost of a shortest path in $G$ from $u$ to $v$. We define the *desired gain* $\alpha < 1$ as the minimum factor reducing the bill of each client. The cost paid is divided between the passengers traveling on the same arc: for each client $i$ traveling in $P$, if $v_i = u_j$ and $v'_i = u_k$, the cost paid by that client is
$$ \omega_i = \sum_{l=j}^{k-1} \frac{\omega(u_l, u_{l+1})}{n_l} $$
This cost must satisfy $\omega_i \le \alpha \cdot \omega(v_i, v'_i)$. In that case, we say the taxi $P$ *satisfies* the client $i$.

Note that there would not be any feasible solution if the capacity of the taxi
is 1. This is why this case is forbidden.

**Remark 1.** A taxi *P* is only defined by waypoints in the road network: the origins where it picks up clients and the destinations where it delivers them. In order to draw the route of the taxi in the network, we follow the shortest paths in *G* from *u*<sub>*j*</sub> to *u*<sub>*j*+1</sub> for every *j* < 2 · *s*(*P*). (We assume that a shortest path over the costs *ω* is also a shortest path over the weights *t*.) That route is a path of *G* that can contain intermediate nodes that are neither an origin nor a destination of a client driven by *P*.
We can now define the problems max-DARP-M, max-1-DARP-M and 1-DARP-M.

**Definition 1.** Given a directed graph $G = (V, A)$ with non-negative weights $\omega$ over the arcs, $n$ clients with their origin $V_c$, their destinations $V'_c$ and their time windows $B_c$ and $E_c$, a capacity capa $\le n$ of the taxis, a desired gain $\alpha < 1$,

* the max-DARP-M problem consists in finding a set $\mathcal{P}$ of taxis satisfying the precedence constraint, the capacity constraint, the time constraint and the cost constraint maximizing $\sum_{P \in \mathcal{P}} s(P)$ such that for each client there is a unique taxi of $\mathcal{P}$ in which that client travels;

* the max-1-DARP-M problem consists in finding a taxi $P$ satisfying the four constraints and maximizing $s(P)$;

* the 1-DARP-M problem consists in deciding whether a taxi $P$ satisfying the four constraints exists.

We define also define two decision problems max-DARP-M$_{=}$ and max-1-DARP-M$_{=}$ in which, given an instance of max-DARP-M or max-1-DARP-M and an integer $S$, we search for a solution for which the objective value equals $S$. We finally define the parameter $TW$ as $\max_{i \in [1; n]} (e_i - b_i) + 1$, the maximum width of a time window.

The results are summarized in Table 1. In some of the results, $TW$ is marked as *polynomially bounded* resulting in pseudo-polynomial algorithms. By polynomially bounded, we mean that $TW$ is a unary encoded number or, equivalently, that there exists a polynomial $p$ such that, for each instance $(G, (V_c, V'_c, B_c, E_c), \tau, \omega, capa, \alpha)$, $TW$ is no more than $p(size)$ where $size$ is the maximum of the size of $G$, the number of clients, and the logarithm of every other numerical value such as $\tau(a), \omega(a), capa$ and $\alpha$.

**Remark 2.** We studied the problems in two main cases: planar and acyclic graphs. If the first may seem relevant considering the application, the second is clearly not as a road network hardly is acyclic. However, there exists parameterized algorithms for the three problems in that case. It could be used if the circuits of the graph are removed (by defining a priority order over the nodes of the graph using, for example, the time windows of the clients, as discussed in Section 3). Of course, by doing this, some routes cannot be used anymore by the driver and this may deteriorate the value of an optimal solution. However, according to Table 1, none of the feasible solutions in the original instance may be computed in polynomial or FPT time by any parameterized algorithm.

**Remark 3.** Note that, on every hardness result where $TW$ is fixed, the reduction first consists in setting the durations $\tau$ to 0 and the time windows to $[0, 0]$, so that the time constraint is trivially satisfied and that $TW = 1$. This means that the same hardness results occur even if we remove the time constraint.
<table><caption>Table 1: This table summarizes the set of results in the paper. The *Parameters* column specifies which parameter is fixed or polynomially bounded (denoted by (poly)). The *Comp.* and the *Approx.* columns tell whether the problem is NP-Hard (NP-H), NP-Complete (NP-C), APX-Hard (APX-H), not approximable to within any ratio (not approx.) or if it belongs to the class XP or if it W[1]-Hard (W[1]-H) with respect to the fixed parameters. For instance, max-1-DARP-M is XP with respect to *capa* when the graph is a DAG and when *TW* is polynomially bounded. An hyphen in the approximability column means that the cell does not make sense, either because the problem is polynomial (or XP), or because the line is about a decision problem. The last column indicates in which theorem/corollary the result is proven.</caption><thead><tr><th>Graphs</th><th>Problem</th><th>Parameters</th><th>Comp.</th><th>Approx.</th><th>Result</th></tr></thead><tbody><tr><td rowspan="3">Planar<br>graphs</td><td>max-DARP-M</td><td>α, TW, capa</td><td>NP-H</td><td>No approx.</td><td>Cor. 2.1</td></tr><tr><td>max-1-DARP-M</td><td>α, TW, capa</td><td>NP-H</td><td>No approx.</td><td>Cor. 2.1</td></tr><tr><td>1-DARP-M</td><td>α, TW, capa</td><td>NP-C</td><td>-</td><td>Th. 2.1</td></tr><tr><td rowspan="2">All<br>graphs</td><td>max-DARP-M<sub>=</sub></td><td>S</td><td>XP</td><td>-</td><td>Sect. 3.1.3</td></tr><tr><td>max-1-DARP-M<sub>=</sub></td><td>S</td><td>XP</td><td>-</td><td>Sect. 3.1.3</td></tr><tr><td rowspan="8">DAG</td><td rowspan="4">max-DARP-M</td><td>TW</td><td>NP-H</td><td>No approx.</td><td>Th 3.3</td></tr><tr><td>TW (poly), capa</td><td>NP-H</td><td><sup>1</sup>&frasl;<sub>&radic;n</sub>-approx</td><td>Cor. 3.2</td></tr><tr><td>α, TW, capa</td><td>NP-H</td><td>APX-H</td><td>Th. 3.1</td></tr><tr><td>α, capa</td><td>NP-H</td><td>No approx.</td><td>Cor. 3.1</td></tr><tr><td rowspan="2">max-DARP-M<sub>=</sub></td><td>S, α, TW, capa</td><td>W[1]-H</td><td>-</td><td>Th. 3.3</td></tr><tr><td>TW</td><td>NP-H</td><td>No approx.</td><td>Th 3.3</td></tr><tr><td rowspan="2">max-1-DARP-M</td><td>TW (poly), capa</td><td>XP</td><td>-</td><td>Th. 3.5</td></tr><tr><td>α, capa</td><td>NP-H</td><td>No approx.</td><td>Cor. 3.1</td></tr><tr><td>max-1-DARP-M<sub>=</sub></td><td>S, α, TW, capa</td><td>W[1]-H</td><td>-</td><td>Th 3.3</td></tr><tr><td rowspan="4">1-DARP-M</td><td rowspan="4">max-1-DARP-M</td><td>TW</td><td>NP-C</td><td>-</td><td>Th. 3.3</td></tr><tr><td>TW (poly), capa</td><td>XP</td><td>-</td><td>Th. 3.5</td></tr><tr><td>α, capa</td><td>NP-C</td><td>-</td><td>Th. 3.2</td></tr><tr><td>α, TW, capa</td><td>W[1]-H</td><td>-</td><td>Th. 3.3</td></tr></tbody></table>

## 2. Planar graphs

This section is dedicated to proving that 1-DARP-M is NP-Complete and that max-DARP-M and max-1-DARP-M are NP-Hard and cannot be approximated to within any constant or variable ratio, even if *capa*, *α* and *TW* are fixed and if the graph is planar.

In this proof, we fix *capa* = 2 and $\alpha \in ]0.5, 1[$. Note that it is possible to adapt the result for any fixed values of *capa* and *α*. This adaptation is not trivial and make the proof harder to read. That is why we present in this section only the simple case. We also consider that we remove the time constraint by setting $\tau(a) = 0$ for every arc $a \in A$ and $b_i = e_i = 0$ for all $i$ and, in that case, $TW = 1$.

*Belonging to NP.* We consider the decision version of max-1-DARP-M and max-DARP-M in which, given an instance of the optimization problems and an
integer *K*, we search for a set of taxis or a unique taxi satisfying at least *K* clients.

Those problems and 1-DARP-M belong to NP as, given a taxi, we can easily
determine whether the capacity, the cost and the precedence constraints are
satisfied for every client in the taxi and count how many clients are satisfied by
the taxi.

NP-hardness: the reduction. In this part, we prove a reduction from the 3-partition problem to 1-DARP-M. We then deduce the hardness of approximation results for the optimization problems.

Given $n$ positive integers $X = [x_1, x_2, \dots, x_n]$, with $n = 3m$, the 3-partition problem consists in the search for a partition $S_1 \uplus S_2 \uplus \dots \uplus S_m$ of $X$ such that $|S_j| = 3$ and $m \cdot \sum_{x \in S_j} x = \sum_{x \in X} x$ for all $j \le m$. Let $B = \frac{1}{m} \sum_{x \in X} x$. The 3-partition problem is NP-Complete even if $x_i \in [B/4; B/2]$ for each $i \le n$ [9].

We define two real values $1 \le \phi \le \Omega$. We set those variables later in this proof. Let $n \ge 9$ be a multiple of 3 and $X = [x_1, x_2, \dots, x_n]$ be an instance of 3-partition such that $x_i \in [B/4; B/2]$ for each $i \le n$. We build an instance $\mathcal{J} = (G, (V_c, V'_c, B_c, E_c), \tau, \omega, \text{capa}, \alpha)$ of 1-DARP-M as follows. As it was previously said, we fix $\text{capa} = 2$, $\alpha \in [0.5, 1[$, $\tau(a) = 0$ for every arc $a$ and $b_i = e_i = 0$ for every client $i$.

We formally describe the instance hereinafter.

There are 3 categories of clients :

• the *main* clients: $m$ clients $cu_j$, for $j \in [1; m]$, going from $u_j$ to $u'_j$;

• 2 clients $cv_1$ and $cv_m$, going respectively from $v_1$ to $v'_1$ and $v_m$ to $v'_m$.

• $m * n$ clients $cw_j^i$, for $i \in [1; n]$, $j \in [1; m]$ going from $w_j^i$ to $w_j^{i'}$.

In addition to the origins and destinations, we add $n+1$ intermediate nodes to $G$: INP, OUT, $int_1$, $int_2$, and, $int_{n-1}$. We add the arcs

• $(u_j, u'_j)$ of cost $2\Omega$ for each $j \in [1; m]$;

• $(u_{j+1}, u'_j)$ of cost $\Omega$, $(u'_j, \text{INP})$ of cost 0 and $(\text{OUT}, u_{j+1})$ of cost 0 for each $j \in [1; m-1]$;

• $(v_1, v'_1)$ and $(v_m, v'_m)$ of cost $\Omega$

• $(u_1, v_1)$, $(v'_1, \text{INP})$, $(\text{OUT}, v_m)$, $(v'_m, u'_m)$ of cost 0

• $(w_i^1, w_i^{1'})$ of cost $\phi + x_i$ and $(w_i^j, w_i^{j'})$ of cost $\phi$ for each $i \in [1; n]$ and $j \in [1; m]$;

• $(\text{INP}, w_1^j)$ and $(w_n^{j'}, \text{OUT})$ of cost 0 for each $j \in [1; m]$;

• $(w_i^{j'}, int_i)$ and $(int_i, w_{i+1}^j)$ of cost 0 for each $i \in [1; n]$ and $j \in [1; m]$.

Figure 1 illustrates the graph $G$ and the costs $\omega$. Note that, for each client $cu_j$, the cost of a private ride is $2\Omega$. For the clients $cv_1$ and $cv_m$, the cost is $\Omega$. For the clients $cw_j^i$ for $j \neq 1$, the cost is $\phi$ and for the clients $cw_1^i$ the cost is $\phi + x_i$. Note also that the graph is planar.
<figure><img src="image_4.png" /><figcaption>Figure 1: A reduction from 3-partition to max-1-DARP-M. Note that this graph can be drawn planar if we move $u_1$ and $v_1$ above $u_2$ and $v'_1$ above $u'_1$. Each non specified cost is 0.</figcaption></figure>

We set $\Omega$ and $\phi$ as follows:

$$ \phi \geq B + 1 \qquad (1) $$

$$ \Omega = \frac{n\phi + B + \frac{1}{2}}{4\alpha - 2} \qquad (2) $$

We start by proving useful properties on $\phi$ and $\Omega$.
**Lemma 2.1.** Ω and φ satisfy the following properties :

$$ \frac{2\Omega + n\phi + B + 1}{2} > 2\alpha\Omega \qquad (3) $$

$$ \frac{2\Omega + n\phi + B}{2} \le 2\alpha\Omega \qquad (4) $$

$$ \frac{3}{2}\Omega + \frac{n\phi}{2} > 2\alpha\Omega \qquad (5) $$

$$ \frac{\Omega}{2} > \alpha \cdot (\phi + B) \qquad (6) $$

*Proof.* Equation (2) proves that

$$ \frac{n\phi + B}{4\alpha - 2} \le \Omega < \frac{n\phi + B + 1}{4\alpha - 2} $$ $$ n\phi + B + 2\Omega \le 4\alpha\Omega < n\phi + B + 1 + 2\Omega $$

and this proves Equations (3) and (4).

We now prove Equation (6). As $\alpha < 1$,

$$ 4\alpha(4\alpha - 2) < 8 \text{ and } 2\alpha(4\alpha - 2) < 4 $$

We recall that $n \ge 7$ and $B > 0$,

$$ 0 < (n + 1 - 4\alpha(4\alpha - 2))B + (n - 2\alpha(4\alpha - 2)) + \frac{1}{2} $$ $$ 0 < (n - 2\alpha(4\alpha - 2))(B + 1) + (1 - 2\alpha(4\alpha - 2))B + \frac{1}{2} $$

By Equation (1)

$$ 0 < (n - 2\alpha(4\alpha - 2))\phi + (1 - 2\alpha(4\alpha - 2))B + \frac{1}{2} $$ $$ 2\alpha(4\alpha - 2)(\phi + B) < n\phi + B + \frac{1}{2} $$

By Equation (2)

$$ \alpha \cdot (\phi + B) < \frac{\Omega}{2} $$

Finally, we can similarly prove Equation (5). As $n \ge 7$, $\alpha < 1$ and $B > 0$,

$$ 0 < (n - (4\alpha - 3))(B + \frac{1}{2}) $$

By Equation (1)

$$ 0 < n\phi + (3 - 4\alpha)(B + \frac{1}{2}) $$ $$ 0 < (4\alpha - 2)n\phi + (3 - 4\alpha)(n\phi + B + \frac{1}{2}) $$
By Equation (2)

$$0 < n\phi + (3 - 4\alpha)\Omega$$
$$2\alpha\Omega < \frac{n\phi}{2} + \frac{3}{2}\Omega$$

□

NP-hardness: from X to J.

**Lemma 2.2.** We now assume X is a YES-instance, then, J is a YES-instance.

*Proof.* Let $I_1 \uplus I_2 \uplus \cdots \uplus I_m$ be a partition of $\llbracket 1; n \rrbracket$ such that $\sum_{i \in I_j} x_i = B$ for all $j \le m$.

A feasible taxi satisfying every client has the following route:

* it picks up the client $cu_1$ at $u_1$;

* it goes to $v_1$ and drives the client $cv_1$ from $v_1$ to $v'_1$;

* for $j \in \llbracket 1; m \rrbracket$

* it drives to INP,

* for $i \in \llbracket 1; n \rrbracket$

* if $i \in I_j$ it drives $cw_i^1$ from $w_i^1$ to $w_i^{1'}$,

* otherwise it drives $cw_i^k$ from $w_i^k$ to $w_i^{k'}$ for some $k$ such that client $cw_i^k$ was not already driven,

* it drives to $int_i$ if $i \neq n$,

* it drives to OUT,

* if $j \neq m$, it drives to $u_{j+1}$ and picks up the client $cu_{j+1}$,

* otherwise it goes to $v_m$ and drives client $cv_m$ from $v_m$ to $v'_m$,

* it drives to $u'_j$ to deliver the client $cu_j$.

The client $cu_j$ pays $\frac{\Omega}{2} + \frac{n\phi+B}{2} + \frac{\Omega}{2}$. By Equation (4), the client $cu_j$ satisfies his cost constraint. Each other client pays exactly half of the price he would have pay alone. As $\alpha > 0.5$, it is a feasible solution for J satisfying every client. □

NP-hardness: from J to X. In order to prove the converse of Lemma 2.2, we first prove six intermediate results from Lemma 2.3 to 2.7.

**Lemma 2.3.** A feasible solution must start at $u_1$.

*Proof.* By enumerating every case, we prove that a taxi starting at any other position should pick up a client that could not satisfy the cost constraint.
1. If the taxi starts at $w_1^i$, the client $cw_1^i$ must pay $\phi + x_i$ alone, and then, cannot satisfy his cost constraint. Similarly the taxi cannot start at $w_j^i$ for any $j > 1$.

2. If the taxi starts at $v_1$, the client $cv_1$ must pay $\Omega$ alone, and then, cannot satisfy his cost constraint. Similarly, the taxi cannot start at $v_m$.

3. If the taxi starts at $u_i$, for any $i \ge 2$, the client $cu_i$ must firstly pay at least $\Omega$ to reach position INP. Then he pays at least $\frac{n\phi+\Omega}{2}$ from INP to his destination. By Equation (5), he cannot satisfy his cost constraint.

☐

**Lemma 2.4.** All the following cases are not possible :

1. The taxi drives a client $cw_i^j$ to a node which is not $w_i^{j'}$.

2. The taxi drives the client $cv_1$ to a node which is not $v_1'$.

3. The taxi drives the client $cv_m$ to a node which is not $v_m'$.

4. the taxi drives through an arc $(u_j, u_j')$

5. the taxi drives $cu_i$ to the node $u_j$, for $j \neq i + 1$

6. the taxi drives $cu_i$ to the node $u_i'$ but does not deliver it

7. the taxi drives $cu_i$ to the node $u_i'$ alone, for $i \neq m$

8. the taxi never picks up $cv_1$ while driving $cu_1$

9. the taxi never picks up $cv_m$ while driving $cu_m$

*Proof.* We first prove the case 1. If the taxi drives the client $cw_i^j$ to any node different from $w_i^{j'}$, that client must go through at least one arc of cost $\Omega$ in order to reach his destination. By equation (6), even if there is another client in the taxi with $cw_i^j$, he has to pay at least $\alpha \cdot (\phi + B)$. However, in a private drive, $cw_i^j$ pays $\phi$ or $\phi + x_i$ depending on whether $j = 1$ or not. As $x_i \in [\frac{B}{4}; \frac{B}{2}]$ for every $i$, $cw_i^j$ cannot satisfy his cost constraint. A similar argument proves the two next cases.

If Case 4 is true, then, by the three first cases, the taxi can drive only one client $cu_j$ or two clients $cu_j$ and $cu_k$ through that arc. Because a client alone in the taxi would have to pay at least $2\Omega > 2\alpha\Omega$, he would not satisfy his cost constraint. Consequently, there are two clients $cu_j$ and $cu_k$. One of them is not $cu_i$. Without loss of generality, we assume that $k \neq i$. That client would have then to pay at least $\Omega$ through the arc $(u_i, u_i')$, then to reach position INP, then to pay at least $\frac{n\phi}{2}$ to reach position OUT and, finally, to pay at least $\frac{\Omega}{2}$ to reach $u_k'$. By Equation (5), he cannot satisfy his cost constraint.

If the taxi goes to $u_j$ with the client $cu_i$, he pays at least $\frac{\Omega}{2} + \frac{n\phi}{2}$ to go to $u_j$ from $u_i$. In order to reach his destination, he has to pay at least twice $\frac{\Omega}{2}$,
through the arc $(u_j, u'_{j-1})$ and through the arc $(u_{i+1}, u'_i)$. By Equation (5), he cannot satisfy his cost constraint, this proves that the case 5 is not possible. The cases 6 to 9 can be similarly proven. □

**Lemma 2.5.** *While driving the client $cu_j$ from his origin to his destination, the taxi drives exactly $n$ clients $cw_i^k$ from their respective origin to their respective destination.*

*Proof.* By the fourth statement of Lemma 2.4, in order to reach $u'_j$, the client $cu_j$ must go from position INP to position OUT. If the taxi reaches position INP with $cu_j$, that client is alone. Indeed, by the three first statements of Lemma 2.4, clients $cv_1$, $cv_m$ and $cw_i^k$ cannot be driven to position INP, and if the taxi drives another client $cu_l$ to position INP from $u_j$, this contradicts one of the statements 4 to 9 of Lemma 2.4. If we assume that strictly less than $n$ clients $cw_i^k$ are driven from their respective origin to their respective destination, $cu_j$ pays at least $\phi + \frac{(n-1)\phi}{2}$ in order to reach position OUT from position INP. As the taxi goes through at least one arc of cost $\Omega$ to reach position INP from $u_j$ and to reach $u'_j$ from position OUT, his ride costs at least $\frac{\Omega}{2} + \phi + \frac{(n-1)\phi}{2} + \frac{\Omega}{2}$. Note that the same occurs if more than $n$ such clients are driven.

By Equation (1)

$$ \Omega + \phi + \frac{(n-1)\phi}{2} \geq \Omega + \frac{(n\phi + B + 1)}{2} $$

By Equation (3)

$$ \Omega + \phi + \frac{(n-1)\phi}{2} > 2\alpha\Omega $$

Consequently, the taxi must picks up and delivers exactly $n$ clients $cw_i^k$ from position INP to position OUT. □

**Lemma 2.6.** *In a feasible solution for $\mathcal{J}$, every client is satisfied.*

*Proof.* By Lemmas 2.3, 2.4, 2.5, if there is a feasible solution, the taxi must start at $u_1$ and drive each client $cu_i$ from his origin to his destination, each one goes from position INP to position OUT and then is driven with exactly $n$ clients $cw_i^k$. As there are $m$ clients $cu_i$ and $n*m$ clients $cw_j^k$, every client $cw_j^k$ is satisfied. Finally, $cv_1$ and $cv_m$ must be picked up and delivered by Lemma 2.4. □

**Lemma 2.7.** *While driving $cu_i$ from his origin to his destination, it must drive exactly three clients $cw_{i_1}^1$, $cw_{i_2}^1$ and $cw_{i_3}^1$ such that $x_{i_1} + x_{i_2} + x_{i_3} \leq B$.*

*Proof.* By Lemma 2.5, the set containing the clients $cw_i^1$ is partitionned into $m$ subsets, one subset $S_j$ for each client $cu_j$, each client of $S_j$ is driven with $cu_j$.

Then the client $cu_j$ pays at least $\frac{\Omega}{2} + \frac{\sum_{i \in S_j} x_i}{2} + \frac{\Omega}{2}$. If $\sum_{i \in S_j} x_i \geq B + 1$, by Equation (3), the client $cu_j$ cannot satisfy his cost constraint.
Moreover, if $|S_j| < 3$, as $n = 3m$, there is a client $cu_k$ such that $|S_k| > 3$. As $x_i \in ]\frac{B}{4}; \frac{B}{2}]$, $\sum_{i \in S_k} x_i \ge B + 1$ and $cu_k$ cannot satisfy his cost constraint. $\square$

**Lemma 2.8.** We now assume $\mathcal{J}$ is a YES-instance then $X$ is a YES-instance.

*Proof.* There exists a taxi satisfying at least one client. By lemma 2.6, every client $cu_i$ is satisfied by that taxi. By Lemma 2.7, such a solution proves the existence of a partition $S_1 \cup S_2 \cup \cdots \cup S_m$ such that $\sum_{x \in S_j} x \le B$. As $\sum_{x \in X} x = mB$, then $\sum_{x \in S_j} x = B$ for all $j$. Consequently, $X$ is a YES-instance. $\square$

By Lemma 2.2 and 2.8, we can deduce the following theorem.

**Theorem 2.1.** 1-DARP-M is NP-Complete even if $G$ is planar and if $\alpha$, capa and TW are fixed.

**Corollary 2.1.** max-DARP-M and max-1-DARP-M are NP-Hard and, unless $P = NP$, cannot be approximated in polynomial time to within any variable ratio, even if $G$ is planar and if capa, $\alpha$ and TW are fixed.

*Proof.* If we assume there exists a polynomial $r$-approximation algorithm $\mathcal{A}$ for max-DARP-M, where $r$ is a function from $\mathbb{N}$ to $\mathbb{Q}^+$ satisfying $0 < r(p) < 1$. Let $\mathcal{J}$ be an instance of 1-DARP-M and max-DARP-M. If no client can be satisfied, the optimal solution of $\mathcal{J}$ is 0. Thus $\mathcal{A}$ returns a solution of value $r(|\mathcal{J}|) \cdot 0 = 0$. If some client is satisfied, the optimal solution of $\mathcal{J}$ is greater than 1 and $\mathcal{A}$ returns a solution of value greater than $r(|\mathcal{J}|) \cdot 1 > 0$. We can then decide in polynomial time whether at least one client can be satisfied or not. There is then a contradiction with Theorem 2.1. The same result occurs for max-1-DARP-M. $\square$

### 3. Directed acyclic graph

In the previous section, we proved hardness results for all the DARP-M problems even if we strongly restrict the instance. The reduction from 3-partition produced an instance in which any taxi must satisfy all the clients by cycling in the graph, driving multiple time through the same roads. Consequently, we study, in this section, the directed acyclic graph case, in order to establish the influence of directed cycles on the complexity of DARP-M.

Obviously, such a case hardly ever occurs on real road networks and finding a polynomial time algorithm does not seem relevant. However, we can arbitrarily build a topological ordering of the nodes of the graph. For example, each client $i$ is associated with a time window $[b_i, e_i]$; we can order the origins and the destinations of the clients using respectively the values of $b_i$ for the origins and $e_i$ for the destination. In that case, the taxi could drive from the origin $v_i$ to the origin $v_j$ only if $b_i < b_j$. Of course, this may delete existing solutions.
In this section, we show some hardness results for the acyclic case, a parameterized pseudopolynomial algorithm for 1-DARP-M and max-1-DARP-M with respect to *capa*, and an parameterized $\frac{1}{\sqrt{n}}$-approximation algorithm in pseudopolynomial time for max-DARP-M parameterized with *capa*.

### 3.1. Hardness results

#### 3.1.1. Hardness of approximation for max-DARP-M

In this section, we prove a hardness of approximation result for max-DARP-M when $G$ is a DAG and when the parameters $\alpha$, *capa* and *TW* are fixed.

*The reduction.* We prove a reduction from the 3-Dimensional Matching problem (3DM). Given three finite disjoint sets $X, Y$ and $Z$, and a subset $S$ of triplets of $X \times Y \times Z$, (3DM) consists in the search for a maximum size subset $M$ of $S$ such that for every couple $(m_1, m_2)$ of $M$, $m_1$ and $m_2$ are disjoint. (3DM) is NP-Complete and APX-Complete. [13]

From an instance $\mathcal{I} = (X, Y, Z, S)$ of (3DM), we now build an instance $\mathcal{J} = (G, (V_c, V'_c, B_c, E_c), \omega, \tau, \text{capa}, \alpha)$ of max-DARP-M where *capa* and $\alpha$ are fixed such that $\mathcal{I}$ has a feasible solution of size $K$ if and only if $\mathcal{J}$ has a feasible solution with $K$ taxis satisfying $7K$ clients. An example is given in Figure 2. We consider that we remove the time constraint by setting $\tau(a) = 0$ for every arc $a \in A$ and $b_i = e_i = 0$ for all $i$ and, in that case, $TW = 1$.

For each set $s = (x, y, z) \in S$, we define four clients $cv_s$, $cv_s^x$, $cv_s^y$ and $cv_s^z$ going respectively from $v_s$, $v_s^x$, $v_s^y$ and $v_s^z$ to $v'_s$, $v_s^{x'}$, $v_s^{y'}$ and $v_s^{z'}$. For each element $x$ of $X$ (respectively $y$ of $Y$ and $z$ of $Z$), we add a client $cw_x$, (respectively $cw_y$ and $cw_z$) going from $w_x$ to $w'_x$ (respectively $w'_y$ and $w'_z$).

We add an arc $(w_x, w'_x)$ of cost 1 for each $x \in X$. We add similar arcs for each $y \in Y$ and each $z \in Z$. For each set $s = (x, y, z) \in S$, we add four arcs $(v_s, v_s^x)$, $(v_s^{x'}, v_s^y)$, $(v_s^{y'}, v_s^z)$ and $(v_s^{z'}, v_s')$ of cost 0. We also add two arcs $(v_s^x, w_x)$ and $(w'_x, v_s^{x'})$ of cost 0. We similarly link the nodes of $cv_s^y$ and $cv_s^z$ to the origin and destination of $cw_y$ and $cw_z$.

Finally, we set *capa* = 3 and $\alpha = \frac{1}{3}$. Consequently, there must be 3 clients in the taxi when it drives through an arc of cost non-zero.

Note that $G$ is a DAG.

### NP-Hardness.

**Theorem 3.1.** *max-DARP-M is NP-Hard and APX-Hard, even if G is a DAG and if $\alpha$ and capa are fixed.*

*Proof.* As $\alpha = \frac{1}{3}$ and *capa* = 3, there must be 3 clients in the taxi while it is driving through an arc of cost 1. Any taxi must then start at a node $v_s$ for some $s = (x, y, z) \in S$ and end at $v'_s$, otherwise, there cannot be enough client in the taxi to satisfy any cost constraint. Let $P_s$ be such a taxi. We now show that there is only one possible path $P_s$ going from $v_s$ to $v'_s$. The taxi must go either to $v_s^x$ or $w_x$ as it cannot reach another node with an arc of cost 0. If the taxi goes to $w_x$ directly, it would have to drive through the arc $(w_x, w'_x)$ of cost
<figure><img src="image_5.png" /><figcaption>Figure 2: Example of reduction from (3DM). Every unspecified cost is 0. An optimal solution of (3DM) is 2: for example the sets A and C. An optimal solution for max-DARP-M is 14 with two taxis, for example the taxi starting at $v_A$ and ending at $v'_A$ and the taxi from $v_C$ to $v'_C$.</figcaption></figure>

at least 1 with at most 2 clients and thus, would not satisfy the cost constraint of the clients $cv_s$ and $cw_x$. Consequently, the taxi $P_s$ must pick up the clients $cv_s$, $cv_s^x$ and $cw_x$, and goes to $w'_x$ and $v'_s$ to deliver $cv_s^x$ and $cw_x$. Similarly, $P_s$ must satisfy $cv_s^y$, $cw_y$, $cv_s^z$ and $cw_z$ before reaching $v'_s$.

A feasible solution can contain two taxis $P_{s_1}$ and $P_{s_2}$ if and only if $s_1 \cap s_2 \neq \emptyset$. Indeed, if, for instance, $s_1 \cap s_2 = \{x\}$, the two taxis would have to pick up the
same client $cw_x$. Consequently, there is a feasible solution for $\mathcal{I}$ of size $K$ if and only if there is a feasible solution of $\mathcal{J}$ with $K$ taxis. As each taxi satisfies 7 clients, the solution satisfies $7K$ clients.

Let $M^* = \{s_1^*, s_2^*, \dots, s_{K^*}\}$ be an optimal solution for $\mathcal{I}$ of size $K^*$. Then, an optimal solution $\mathcal{P}^* = (P_{s_1}^*, P_{s_2}^*, \dots, P_{s_{K^*}}^*)$ for $\mathcal{J}$ has $K^*$ taxis and satisfies $7K^*$ clients. If we assume there is a polynomial $\alpha$-approximation for max-DARP-M, such an algorithm would return a feasible solution $\mathcal{P} = (P_{s_1}, P_{s_2}, \dots, P_{s_K})$ satisfying $7K$ clients such that $\alpha 7K^* \le 7K$. Consequently, we could build in polynomial time a feasible solution $\{s_1, s_2, \dots, s_K\}$ for $\mathcal{I}$ of size $K$ such that $\alpha K^* \le K$. Thus, there is a polynomial $\alpha$-approximation for (3DM). As (3DM) is NP-Complete and APX-Complete and as $G$ is a DAG in the reduction, this concludes the proof. $\square$

**Remark 4.** The previous proof can be adapted to any fixed values of capa and $\alpha$ such that capa $\ge \frac{1}{\alpha} \ge 3$ by replacing every client $cw_x$, $cw_y$ or $cw_z$ by $\lfloor \frac{1}{\alpha} \rfloor - 2$ clients. The nodes $w_x$ and $w'_x$ (similarly $w_y$ and $w'_y$ or $w_z$ and $w'_z$) would be replaced by two paths respectively containing the $\lfloor \frac{1}{\alpha} \rfloor - 2$ origins and the $\lfloor \frac{1}{\alpha} \rfloor - 2$ destinations of those new clients. Every arc of those paths would have a cost 0. And an arc of cost 1 would link the last origin to the first destination.

### 3.1.2. NP-Hardness when TW is not bounded

We give, in this part, a proof that 1-DARP-M is NP-Complete, even if the graph is a DAG and if $\alpha$ and capa are fixed.

*The reduction.* We prove a reduction from the partition problem (PART). Given a finite set of integers $X = \{x_1, x_2, \dots, x_n\}$, is it possible to part $\lfloor 1; n \rfloor$ into two parts $I \uplus J$ such that $\sum_{i \in I} x_i = \sum_{i \in J} x_i$. (PART) is weakly NP-Complete [9].

From an instance $\mathcal{I} = (X)$ of (PART), we now build an instance $\mathcal{J} = (G, (V_c, V_c'), B_c, E_c), \omega, \tau, \text{capa}, \alpha)$ of 1-DARP-M where $G$ is a DAG and where capa and $\alpha$ are fixed. Let $B = \sum_{x \in X} x/2$. We fix capa = 2 and $\alpha = \frac{1}{2}$. We define three main clients $cv_1, cv_2$ and $cv_3$ going respectively from $v_1$ to $v'_1$, $v_2$ to $v'_2$ and $v_3$ to $v'_3$. We also define $2n$ clients $cw_1^1, cw_2^1, \dots, cw_n^1$ and $cw_1^2, cw_2^2, \dots, cw_n^2$. The client $cw_i^j$ goes from $w_i^j$ to $w_i^{j'}$. We finally add $n-1$ intermediate nodes $int_1, int_2, \dots, int_{n-1}$. The arcs of the graph are the following:

* $(v_2, v'_2)$ and $(v_3, v'_3)$ of cost 1 and duration 0.

* $(w_1^1, w_1^{1'})$ of cost 1 and duration $x_i$ for every $i \in \lfloor 1; n \rfloor$.

* $(w_2^2, w_2^{2'})$ of cost 1 and duration 0 for every $i \in \lfloor 1; n \rfloor$.

* $(v_1, v_2), (v_2', w_1^1), (v_2', w_1^2), (w_1^{1'}, v_3), (w_2^{2'}, v_3)$ and $(v_3, v_1')$ of cost 0 and duration 0

* $(w_i^{1'}, int_i), (w_i^{2'}, int_i), (int_i, w_{i+1}^1), (int_i, w_{i+1}^2)$ of cost 0 and duration 0 for every $i \in \lfloor 1; n-1 \rfloor$.
<figure><img src="image_6.png" /><figcaption>Figure 3: Example of reduction from (PART) to 1-DARP-M. On each arc *a*, we write the values ω(*a*) and τ(*a*) in that order. If no number is given, the two values are 0.</figcaption></figure>

The graph $G$, the costs $\omega$ and the times $\tau$ are illustrated on Figure 3.

The time window of $cv_2$ is $[0, 0]$. The time window of $cv_3$ is $[B, B]$. For all the other clients, the time window is $[0, B]$.

**Theorem 3.2.** *1-DARP-M is weakly NP-Complete even if G is a DAG and if α and capa are fixed.*

*Proof.* As $\alpha = \frac{1}{2}$ and capa = 2, there must be 2 clients in the taxi while it is driving through an arc of cost 1. Consequently, the taxi must pick up the client $cv_1$. In order to go to $v'_1$, the taxi must drive through $(v_2, v'_2)$ and, then, must also pick up $cv_2$. Similarly it must pick up $cv_3$ and, for each $i \in [1; n]$, either $cw_i^1$ or $cw_i^2$. Let $I$ be the subset of $[1; n]$ such that $i \in I$ if $cw_i^1$ is picked up.

Due to the time window of $cv_2$, the taxi must arrive at $v_2$ at time 0 otherwise the time constraint cannot be satisfied. Similarly it must arrive at $v_3$ at time $B$. The moment when the taxi reaches $v_3$ is $\sum_{i \in I} \tau(w_i^1, w_i^{1'}) + \sum_{i \notin I} \tau(w_i^2, w_i^{2'}) = \sum_{i \in I} x_i$.

Thus, there exists a feasible taxi if and only if $\sum_{i \in I} x_i = B = \sum_{i \notin I} x_i$. This concludes the proof. □

From Theorem 3.2, we can deduce the following results.

**Corollary 3.1.** *max-DARP-M and max-1-DARP-M are weakly NP-Hard and, unless TW is polynomially bounded or $P = NP$, cannot be approximated in polynomial time to within any variable ratio, even if G is a DAG and if capa and $\alpha$ are fixed.*

### 3.1.3. NP-Hardness and Parameterized Hardness with respect to the number of satisfied clients

If we search for a taxi satisfying exactly $S$ clients, we can enumerate every subset of $S$ clients and check if a taxi only satisfying that subset exists, and this give an XP algorithm for max-1-DARP-M= and max-DARP-M= with respect to $S$. We prove in this subsection that a better algorithm is not likely to exist as max-1-DARP-M= and max-DARP-M= are W[1]-hard in $S$, capa, $\alpha$ and TW.

We also demonstrate that the three problems, max-1-DARP-M, max-DARP-M and 1-DARP-M are NP-Complete and cannot be approximated in polynomial time even if TW is fixed and that 1-DARP-M is W[1]-hard in capa, $\alpha$ and TW.
**_The reduction._** We describe an FPT-Reduction from the partitioned clique problem. Given an undirected graph $G = (V = V_1 \uplus V_2 \uplus \cdots \uplus V_k, E)$ where $V$ is partitioned into $k$ independent sets, the partitioned clique problem consists in the search for a clique of size $k$. Any such clique contains exactly one node in each part $V_i$. This problem is NP-Complete and is $W[1]$-hard with respect to $k$ [17].

From a parameterized instance $(G, k)$ of the partitioned clique problem, we build a parameterized instance $((\mathcal{J}, S), (S, \alpha, \text{capa}, W))$ of max-1-DARP-M= such that the graph is a DAG. Note that this instance is also a parameterized instance for max-DARP-M=, and that $(\mathcal{J}, (\alpha, \text{capa}, W))$ is a parameterized instance of 1-DARP-M. The same reduction proves hardness results for the three problems. We consider that we remove the time constraint by setting $\tau(a) = 0$ for every arc $a \in A$ and $b_i = e_i = 0$ for all $i$ and, in that case, $TW = 1$.

Our goal is to create a directed acyclic graph $H = (W \cup X, A)$.

$W$ contains two nodes $w_u^v$ and $w_v^u$ for each edge $(u, v)$ of $G$. It is partitioned into $k$ layers and each layer is partitioned into $k-1$ sublayers. We write $W_i$ for layer $i$. The sublayers of layer $i$ are numbered from 1 to $k$ except $i$ and we write $W_i^j$ for sublayer $j$ of layer $i$. For each edge $\{u, v\}$ in $E$ such that $u \in V_i$ and $v \in V_j$ and $i < j$, we add a client $cw_u^v$ with the origin $w_u^v \in W_i^j$ and the destination $w_u^{v'} = w_v^u \in W_j^i$.

Each sublayer is a stable set. A node $w_{u_1}^{v_1} \in W_i^j$ is linked to a node $w_{u_2}^{v_2}$ of the next sublayers of $W_i$ ($W_i^{j+1}$ if $j \neq i-1$, $W_i^{i+1}$ otherwise) if $u_1 = u_2$. Note that this common node is necessarily in $V_i$. Note also that each layer is an acyclic graph.

$X$ is a set of $k-1$ paths. For each $i \in [1; k-1]$, we add to $H$ a path $(x_i^1, x_i^2, \dots, x_i^{s_i}, x_i^{1'}, x_i^{2'}, \dots, x_i^{s_i'})$ where $s_i = \frac{(k-1) \cdot k}{2} - i \cdot (k-i)$. We also add $s_i$ clients $CX_i = \{cx_i^1, cx_i^2, \dots, cx_i^{s_i}\}$. Each client $cx_i^l$ goes from $x_i^l$ to $x_i^{l'}$. Let $X_i$ be the set of origins of those clients and $X_i'$ be the set of destinations. All the nodes of the last sublayer of each layer $W_i$, for $i \neq k$, are linked to $x_i^1$, and, similarly, $x_i^{s_i'}$ is linked to all the nodes of the first layer of $W_{i+1}$.

We can easily see that $H$ does not contain a circuit as each layer $W_i$ is acyclic and as it is only connected to the following layer with the path $X_i \cup X_i'$.

The cost of every arc $(x_i^{s_i}, x_i^{1'})$ is 1. For every other arc, the cost is null. Finally, we set $S = \frac{(k-1) \cdot k}{2} + \sum_{p=1}^{k-1} s_p$, $\text{capa} = \frac{(k-1) \cdot k}{2}$ and $\alpha = \frac{1}{\text{capa}}$. Any taxi driving through an arc of cost non-zero must contains capa clients otherwise the cost constraint cannot be satisfied.

**Example 1.** We first describe, in this section, why the reduction works on a simple example, given in Figure 4 and then give the formal proof.

On that example, we have a Partitionned Clique instance with $k=3$ containing for instance the clique $\{2, 5, 7\}$. Thus, in the max-1-DARP-M problem, the graph $H$ contains 3 layers and 2 sublayers per layer and we have $S=5$, $s_1=s_2=1$, capa = 3 and $\alpha = 1/3$. Consequently, a taxi cannot go through an arc of cost 1 if it is not driving exactly 3 clients.
<figure><img src="image_7.png" /><figcaption>Figure 4: Example of reduction from the Partitioned Clique problem. There are 3 stable sets in $G$: $V_1$, $V_2$ and $V_3$; and 6 sublayers in $H$: $W_1^2$, $W_1^3$, $W_2^1$, $W_2^3$, $W_3^1$ and $W_3^2$. Each layer is separated from the other with an horizontal dashed line. The two paths of $X$ are on the right. Note that there are dashed lines joining the origin and the destination of each client $cw_u^v$ for information. Those lines are not edges or arcs of the graph. Every cost which is not specified is 0.</figcaption></figure>

We first explain why any feasible taxi must drive $S$ clients. Due to how the graph $H$ is built, if a taxi drives a client from $W_1^3$, it must reach $W_3^1$ and, then, it must go through the arcs $(x_1^1, x_1^{1'})$ and $(x_2^1, x_2^{1'})$. Similarly, if a taxi drives a client from $W_1^2$ (respectively from $W_2^3$), it must go through $(x_1^1, x_1^{1'})$ (respectively $(x_2^1, x_2^{1'})$). On the other hand, if the taxi goes through the arc $(x_1^1, x_1^{1'})$ with 3 clients, those three clients must be $cx_1^1$ and two clients from $W_1^2$ and $W_1^3$. Similarly, the three clients of a taxi going through $(x_2^1, x_2^{1'})$ must be $cx_2^1$ and two clients from $W_1^3$ and $W_2^3$. As a consequence, any feasible taxi must
drive at least $S = 5$ clients: the clients $cx_1^1$, $cx_2^1$ and three clients from $W_1^2$, $W_1^3$ and $W_2^3$. The taxi cannot drive more than $S$ clients because every sublayer is an independent set and every path connect a sublayer to the next sublayers.

We now explain why this feasible taxi exists if and only if a clique of size $k$ exists in $G$. Each layer $W_i$ is associated with the edges incident to the nodes of the set $V_i$ of node of $G$. For instance, in $W_1$, there are four nodes associated with the four edges incident to node 1 and three nodes associated with the three edges to node 2. The four first nodes are not connected to the three last, it is not possible for a taxi to pick up a client in $W_1^2$ associated with the node 1 and a client in $W_1^3$ associated with the node 2. Thus, in order to go through $W_1$, the taxi must choose either the node 1 or 2 and then choose two incident edges. Similarly, to go through $W_2$ (respectively $W_3$), the taxi must choose the node 3, 4 or 5 (respectively the node 6 or 7). Consequently, the taxi builds a set $C$ of three nodes, one for each set $V_1$, $V_2$ and $V_3$.

If the set $C$ is a clique, for instance $\{2, 5, 7\}$, then the edges (2, 5), (2, 7) and (5, 7) exist and, consequently, the corresponding client exist too. The origins and the destinations of all those clients are connected by a path. This case is illustrated in Figure 4. Note that this also work with the two other cliques of $G$, $\{1, 3, 6\}$ and $\{1, 4, 6\}$.

If the set $C$ is not a clique, for instance $\{2, 4, 7\}$, then at least one of the three edges does not exist. In this case, the edge (4, 7) does not exist, and thus, the client $cw_4^7$ and the nodes $w_4^7$ and $w_7^4$ do not exist. Maybe the taxi can drive $cw_2^4$, $cw_2^7$ and another client from $W_2^3$. However, the precedence constraint must be satisfied. If the clients $cw_2^4$ and $cw_2^7$ are picked up, they must be delivered at $w_4^2$ and $w_7^2$. While leaving $w_4^2$, the taxi has no other choice than going to an edge linking 4 and a node of $V_3$. In this case, the only possibility is the edge (4, 6). As explained previously, the taxi must pick up the client $cw_4^6$ otherwise there cannot be 3 clients in the taxi while going through $(x_2^1, x_2^{1'})$. The taxi must then reach $w_7^2$ and $w_6^4$ and those nodes are not connected. More generally, if $C$ is not a clique, the missing edges must be replaced by edges that are not incident to two nodes of $C$ and this prevents the taxi from being able to satisfy either the cost constraint or the precedence constraint.

We now formally prove the reduction. We first show two intermediate lemmas.

**Lemma 3.1.** *The route of a feasible taxi contains at most one node in each sublayer $W_i^j$.*

*Proof.* As every sublayer $W_i^j$ is either linked to the next sublayer or connected to $W_{i+1}$ with the path $X_i \cup X_i'$, there is no path connecting two nodes of $W_i^j$. Thus, there is at most one node of $W_i^j$ is a path of $H$. $\square$

**Lemma 3.2.** *A feasible taxi picks up a client in $W_i^j$, for some $i < j$, and delivers it in $W_j^i$ if and only if it goes through every path $X_l \cup X_l'$ including the arc $(x_l^{s_l}, x_l^{1'})$ for $l \in [i; j-1]$.*
*Proof.* The necessary condition follows from the fact that any path from $W_i^j$ to $W_j^i$ goes through those paths.

We now assume there is a feasible route of a taxi in $H$ not containing any node of $W_i^j$ and that this taxi goes through $(x_l^{s_i}, x_l^{1'})$ for some $l \in [i; j-1]$. We will show that the taxi cannot contain *capa* clients while going through the arc $(x_l^{s_i}, x_l^{1'})$. By doing this, we prove the taxi does not satisfy the cost constraint as $\alpha = \frac{1}{capa}$ and as the arc has cost 1. This would lead to a contradiction.

If a client is in the taxi while it drives through the arc $(x_i^{s_i}, x_i^{1'})$, the origin of that client is before $x_i^{s_i}$ and its destination is after $x_i^{1'}$ in a topological ordering of $H$. There are two categories of such clients. There are firstly the $s_i$ clients of $CX_i$. There are secondly the clients $cw_u^v$ coming from sublayer $W_p^q$ to sublayer $W_q^p$ where $p \le l$ and $q > l$ except if $p = i$ and $q = j$ because the taxi does not drive any client from $W_i^j$. There are $l$ possible values for $p$ and $(k-l)$ possible values for $q$. As we remove the couple $(p, q) = (i, j)$, there are $l \cdot (k-l) - 1$ such couples of sublayers.

By Lemma 3.1, there is no more than one client per sublayer in a path of $H$, there cannot be more than $s_i + i \cdot (k-i) - 1$ clients in a taxi going through $(x_i^{s_i}, x_i^{1'})$. As $s_i = \frac{(k-1) \cdot k}{2} - i \cdot (k-i)$ and $capa = \frac{(k-1) \cdot k}{2}$, there can be at most $capa - 1$ clients in the taxi. $\square$

**Lemma 3.3.** If there is a clique *C* of size *k* in *G*, there is a feasible solution for *J* satisfying *S* clients.

*Proof.* If there is a clique *C* of size *k* in *G*, then, let $u_i$ be the node of *C* ∩ $V_i$. We define the subgraph *P* of *H* such that, for each *i* < *j* ∈ [1; *k*], *P* contains one node per sublayer, the origin and the destination of the client $cw_{u_i}^{u_j}$, and all the paths $X_i \cup X_i'$. There is always in *P* an arc linking two nodes $w_u^v$ and $w_x^y$ of two consecutive sublayers of $W_i$ because $u = x = u_i$. Thus, *P* is a path.

*P* satisfies the precedence constraints. A similar argument to the one given in the proof of Lemma 3.2 proves that *P* never drives more than *capa* clients at the same time and that *P* satisfies the cost constraint. Finally, *P* satisfies exactly *S* = $\frac{k \cdot (k-1)}{2} + \sum_{i=1}^{k-1} s_i$ clients. $\square$

**Lemma 3.4.** *The route of a feasible taxi contains exactly one node in each sublayer and all the nodes of X.*

*Proof.* By Lemma 3.1, there is at most one node of $W_i^j$ is a path of $H$.

The taxi must go through at least one arc of cost 1, because, for every client, there is such an arc separating its origin to its destination. Thus, by Lemma 3.2, it must satisfy at least one client from $W_1^k$. Consequently, again by Lemma 3.2, it goes through every arc $(x_l^{s_l}, x_l^{1'})$ for $l \in [i; k-1]$ and every node of $X$. Thus, again by Lemma 3.2, the route of the taxi contains one node per sublayer. $\square$

**Lemma 3.5.** If there is a feasible taxi for *J* satisfying *S* clients, there is a clique *C* of size *k* in *G*.
### 3.2.1. A parameterized algorithm for max-1-DARP-M

We consider an instance $\mathcal{I} = (G, (V_c, V'_c, B_c, E_c), \tau, \omega, \text{capa}, \alpha)$ with $n$ clients and where $G$ is a DAG. We assume that, in $G$, there is a path from any origin $v_i \in V_c$ to the corresponding destination $v'_i \in V'_c$: there is no path from $v'_i$ to $v_i$. We finally consider that there is no intermediate point: $V = V_c \cup V'_c$. Every arc $(u, v)$ corresponds to a shortest path from $u$ to $v$ in the road network if such a path exists.

**Definition 2.** We now define an auxiliary graph $S(\mathcal{I})$ in which each node is associated with a state corresponding to the taxi leaving a node $u \in V$ at time $t$ with a set $C$ of at most capa clients and such that $S$ clients already entered the taxi (including the clients who have left the taxi and the clients who have not); we write that state $w(u, t, C, S)$, $u \in V$, $t \in [b_i, e_i]$ if $u = v_i$ or if $u = v'_i$, $C \subset [1; n]$, $|C| \le \text{capa}$, $S \in [1; n]$. An arc is a transition between two states: we add an arc $(w(u_1, t_1, C_1, S_1), w(u_2, t_2, C_2, S_2))$ in $S(\mathcal{I})$ if and only if all the following four properties are true:

1. $C_1 \neq \emptyset$

2. there is a path from $u_1$ to $u_2$ in $G$;

3. $t_2 - t_1 = \tau(u_1, u_2)$

4. either $u_2$ is the origin $v_i$ of client $i$, $C_2 = C_1 \cup \{i\}$ and $S_2 = S_1 + 1$

or $u_2$ is the destination $v'_i$ of client $i$, $C_1 = C_2 \cup \{i\}$ and $S_2 = S_1$

An example is given in Figure 5.

As the existence of an arc between two states $w(u_1, t_1, C_1, S_1)$ and $w(u_2, t_2, C_2, S_2)$ implies that there is a path from $u_1$ to $u_2$ in $G$ and as $G$ is a DAG, we can deduce the following property.

**Property 1.** $S(\mathcal{I})$ is a DAG.

We now introduce Algorithm 1, which solves max-1-DARP-M using the auxiliary graph $S(\mathcal{I})$. We then prove the polynomial time complexity and the correctness of the algorithm.

For each node $w = (v, t, C, S) \in S(\mathcal{I})$, we define a set $\mathcal{P}(w)$ of mappings associating to each client of $C$ a non negative real number: each mapping represents a possible taxi driving the clients of $C$ through $v$ and $p(i)$ is the cost that the client $i$ has already paid for the travel from its origin to $v$ in that taxi.

**Definition 3.** Let $w = (v, t, C, S) \in S(\mathcal{I})$, and $p$ and $p'$ be two mappings of $\mathcal{P}(w)$. We say $p$ dominates $p'$ if, for every client $i$ in $C$, $p(i) \le p'(i)$. We write $p \preceq p'$.

We use Algorithm 1 to compute all the sets of mappings of the auxiliary graph and to deduce a feasible solution for $\mathcal{I}$.

Each set $\mathcal{P}(w)$ is built recursively using the sets of mappings of all predecessors of $w$. In order to simplify Algorithm 1, we define, for each arc
<figure><img src="image_8.png" /><figcaption>Figure 5: Example of transformation from $\mathcal{I}$ to the auxiliary graph $S(\mathcal{I})$. For readability, we do not consider, in this figure, the time windows, and some states like $w(v_3, t, 3, 1)$ or $w(v_4, t, 4, 1)$ are missing. The weight of each arc $a$ on the upper graph is the cost $\omega(a)$. Each state $w(u, t, C, S)$ on the lower graph contains $u, C$ and $S$ respectively on the lower left part, the upper part and the lower right part of the node. The time $t$ is not given.</figcaption></figure>

($w_1, w_2) \in S(\mathcal{I})$, a set of intermediate mappings $\mathcal{P}(w_1, w_2)$ which can be seen as the subset of $\mathcal{P}(w_2)$ built from the state $w_1$ with useful additional information. This set is built with the SUBMAP function, described in Algorithm 2. In addition, a BUILD function is given in Algorithm 3 to build a solution. Table 2 illustrates some iterations of the algorithm on the example given in Figure 5.

*Correctness.* This part is dedicated to proof the correctness of Algorithm 1. The key idea is to prove that any mapping of $\mathcal{P}(w)$, for some node $w = (u, t, C, S)$, corresponds to the part of a taxi from the first origin of its route to $u$, hereinafter called a *partial taxi*.

**Definition 4.** For every node $w = (u, t, C, S) \in S(\mathcal{I})$, we define the set $pP(w)$
**Algorithm 1 Main algorithm**

**Require:** an instance $\mathcal{I} = (G, (V_c, V'_c, B_c, E_c), \tau, \omega, \text{capa}, \alpha)$ of max-1-DARP-M

**Ensure:** an optimal solution for $\mathcal{I}$

1. Build the auxiliary graph $S(\mathcal{I})$

2. **For each** client $i \in [1; n]$ and $t \in [b_i, e_i]$ **Do**

3. $p_i$ ← a mapping associating 0 to the client $i$

4. $\mathcal{P}(w(v_i, t, \{i\}, 1)) \leftarrow \{p_i\}$

5. $\text{pred}(p_i) \leftarrow \text{null}$

6. $L \leftarrow$ a topological ordering of $S(\mathcal{I}) \setminus \{w(v_i, t, \{i\}, 1) | i \in [1; n]\}$

7. **For each** $w = w(v, t, C, S) \in L$ **Do**

8. $\mathcal{P}(w) \leftarrow \emptyset$

9. **For each** predecessor $w^- = w(v^-, t^-, C^-, S^-)$ of $w$ **Do**

10. $\mathcal{P}(w^-, w) \leftarrow \text{SUBMAP}(\mathcal{I}, S(\mathcal{I}), (w^-, w), \mathcal{P}(w^-))$

11. **For each** $(p, w^-, p^-) \in \mathcal{P}(w^-, w)$ **Do**

12. **If** **For all** $p' \in \mathcal{P}(w)$, $p' \not\le p$ **Then**

13. remove from $\mathcal{P}(w)$ every mapping $p'$ such that $p \preceq p'$

14. add $p$ to $\mathcal{P}(w)$

15. $\text{pred}(p) \leftarrow (w^-, p^-)$

16. $T \leftarrow \{w = w(v'_i, t, \emptyset, S) | i, S \in [1; n], \mathcal{P}(w) \neq \emptyset\}$

17. **If** $T = \emptyset$ **Then** **Return** no solution.

18. $w^* \leftarrow \underset{\argmax}{\mathcal{S}|w(v'_i, t, \emptyset, S) \in T}$

19. $p \leftarrow$ a mapping of $\mathcal{P}(w^*)$

20. **Return** $\text{BUILD}(\mathcal{I}, S(\mathcal{I}), \text{pred}, w^*, p)$

**Algorithm 2 SUBMAP Function**

**Require:** an instance $\mathcal{I} = (G, (V_c, V'_c, B_c, E_c), \tau, \omega, \text{capa}, \alpha)$ of max-1-DARP-M, the auxiliary graph $S(\mathcal{I})$, an arc $(w_1 = w(u_1, t_1, C_1, S_1), w_2 = w(u_2, t_2, C_2, S_2)) \in S(\mathcal{I})$, a set $\mathcal{P}(w_1)$ of mappings from $C_1$ to $\mathbb{R}^+$

**Ensure:** a set $\mathcal{P}(w_1, w_2)$ of mappings from $C_2$ to $\mathbb{R}^+$

1. **function** SUBMAP($\mathcal{I}, S(\mathcal{I}), (w_1, w_2), \mathcal{P}(w_1)$)

2. $\mathcal{P}(w_1, w_2) \leftarrow \emptyset$

3. **For each** mapping $p_1 \in \mathcal{P}(w_1)$ **Do**

4. Initialize a mapping $p_2$ of $C_2 \to \mathbb{R}^+$

5. **For each** client $i \in C_1$ **Do**

6. **If** $p_1(i) + \frac{\omega(u_1, u_2)}{|C_1|} \le \alpha \cdot \omega(v_i, v'_i)$ **Then**

7. **If** $i \in C_2$ **Then** $p_2(i) \leftarrow p_1(i) + \frac{\omega(u_1, u_2)}{|C_1|}$

8. **Else**

9. **Continue** loop **For** at Line 3

10. **If** $C_2$ contains a client $i$ not in $C_1$ **Then**, $p_2(i) = 0$

11. Add $(p_2, w_1, p_1)$ to $\mathcal{P}(w_1, w_2)$

12. **Return** $\mathcal{P}(w_1, w_2)$
**Algorithm 3 BUILD Function**: Build a partial solution from a selected node.

**Require**: an instance $\mathcal{I} = (G, (V_c, V'_c, B_c, E_c), \tau, \omega, \text{capa}, \alpha)$ of max-1-DARP-M, the auxiliary graph $S(\mathcal{I})$, a predecessor function $\text{pred}$, a node $w = w(u, t, C, S) \in S(\mathcal{I})$ and a mapping $p$ of $\mathcal{P}(w)$

**Ensure**: a path ending at $u$ in $G$

1. function $\text{BUILD}(\mathcal{I}, S(\mathcal{I}), \text{pred}, w, p)$

2. $P \leftarrow \{u\}$

3. If $\text{pred}(p) \neq \text{null}$ Then

4. $(w^{-}, p^{-}) \leftarrow \text{pred}(p)$

5. $P \leftarrow P \cup \text{BUILD}(\mathcal{I}, S(\mathcal{I}), \text{pred}, w^{-}, p^{-})$

6. Return $P$

<table><caption>Table 2: Example of iterations of the For loops at Lines 7 and 9 of Algorithm 1 on the instance given in Figure 5. We assume that every duration $\tau(a)$ is 0 and that every time window contains 0. The first column gives the iteration numbers of the outer loop. The two last columns give the two lists of mappings $\mathcal{P}(w^{-}, w)$ and $\mathcal{P}(w)$. Each mapping $p$ is written $i \to p(i)$. The first part ends with a state containing two non-dominated mappings whereas the second part ends with an iteration where a mapping is not inserted in $\mathcal{P}(w)$ because it is dominated by an existing mapping.</caption><thead><tr><th>It.</th><th>w</th><th>w<sup>-</sup></th><th>P(w<sup>-</sup>, w)</th><th>P(w)</th></tr></thead><tbody><tr><td>1</td><td>w(v<sub>3</sub>, 0, {1, 3}, 2)</td><td>w(v<sub>1</sub>, 0, {1}, 1)</td><td>1 &rarr; 1, 3 &rarr; 0</td><td>1 &rarr; 1, 3 &rarr; 0</td></tr><tr><td>2</td><td>w(v'<sub>3</sub>, 0, {1}, 2)</td><td>w(v<sub>3</sub>, 0, {1, 3}, 2)</td><td>1 &rarr; 2</td><td>1 &rarr; 2</td></tr><tr><td>3</td><td>w(v<sub>2</sub>, 0, {1, 2}, 3)</td><td>w(v'<sub>3</sub>, 0, {1}, 2)</td><td>1 &rarr; 3, 2 &rarr; 0</td><td>1 &rarr; 3, 2 &rarr; 0</td></tr><tr><td>4</td><td>w(v<sub>2</sub>, 0, {1, 2}, 2)</td><td>w(v<sub>1</sub>, 0, {1}, 1)</td><td>1 &rarr; 1, 2 &rarr; 0</td><td>1 &rarr; 1, 2 &rarr; 0</td></tr><tr><td>5</td><td>w(v<sub>4</sub>, 0, {1, 2, 4}, 3)</td><td>w(v<sub>2</sub>, 0, {1, 2}, 2)</td><td>1 &rarr; 2, 2 &rarr; 1, 4 &rarr; 0</td><td>1 &rarr; 2, 2 &rarr; 1, 4 &rarr; 0</td></tr><tr><td>6</td><td>w(v'<sub>4</sub>, 0, {1, 2}, 3)</td><td>w(v<sub>4</sub>, 0, {1, 2, 4}, 3)</td><td>1 &rarr; 4, 2 &rarr; 3</td><td>1 &rarr; 4, 2 &rarr; 3</td></tr><tr><td>7</td><td>w(v<sub>5</sub>, 0, {1, 2, 5}, 4)</td><td>w(v<sub>2</sub>, 0, {1, 2}, 3)</td><td>1 &rarr; 6, 2 &rarr; 3, 5 &rarr; 0</td><td>1 &rarr; 6, 2 &rarr; 3, 5 &rarr; 0</td></tr><tr><td>7</td><td>w(v<sub>5</sub>, 0, {1, 2, 5}, 4)</td><td>w({1, 2}, 0, v'<sub>4</sub>, 3)</td><td>1 &rarr; 5, 2 &rarr; 4, 5 &rarr; 0</td><td>1 &rarr; 6, 2 &rarr; 3, 5 &rarr; 0<br>1 &rarr; 5, 2 &rarr; 4, 5 &rarr; 0</td></tr><tr><td>8</td><td>w(v<sub>4</sub>, 0, {1, 4}, 2)</td><td>w(v<sub>1</sub>, 0, {1}, 1)</td><td>1 &rarr; 3, 4 &rarr; 0</td><td>1 &rarr; 3, 4 &rarr; 0</td></tr><tr><td>9</td><td>w(v'<sub>4</sub>, 0, {1}, 2)</td><td>w(v<sub>4</sub>, 0, {1, 4}, 2)</td><td>1 &rarr; 6</td><td>1 &rarr; 6</td></tr><tr><td>10</td><td>w(v<sub>5</sub>, 0, {1, 5}, 3)</td><td>w(v'<sub>4</sub>, 0, {1}, 2)</td><td>1 &rarr; 8, 5 &rarr; 0</td><td>1 &rarr; 8, 5 &rarr; 0</td></tr><tr><td>10</td><td>w(v<sub>5</sub>, 0, {1, 5}, 3)</td><td>w(v'<sub>3</sub>, 0, {1}, 2)</td><td>1 &rarr; 9, 5 &rarr; 0</td><td>1 &rarr; 9, 5 &rarr; 0</td></tr></tbody></table>
of partial taxis of w as the set of paths P in G such that:

(i) P starts at an origin $v_i$, for some client $i$, and ends at $u$

(ii) the capacity constraint is satisfied;

(iii) the time constraint is satisfied;

(iv) C is the set $\{i | v_i \in P \text{ and } v'_i \notin P\}$ and S is the value of $|\{i | v_i \in P\}|$.

(v) if $v'_i \in P$, then the precedence and the cost constraints are satisfied for the client $i$;

(vi) if $i \in C$, the cost $\omega(i, P)$ paid by the client $i$ from $v_i$ to $u$ in $P$ is less than $\alpha \cdot \omega(v_i, v'_i)$;

**Remark 5.** If $P$ is a taxi starting at $v_i$, then any subpath of $P$ starting at $v_i$ is a partial taxi. However, there exists partial taxis such that no valid taxi contains them.

**Lemma 3.6.** Let $w = (u, t, C, S) \in S(I)$. We assume $p \in P(w)$ is a mapping that was just added at Line 14. Let $P$ be the result of the BUILD function on $w$ and $p$, then $P \in pP(w)$ and, for each $i \in C$, $p(i) = \omega(i, P)$.

*Proof.* Let $L'$ be the list starting with the nodes of $\{w(v_i, t, \{i\}, 1) | i \in [1; n]\}, t \in [b_i, e_i]\}$ and ending with the list $L$ defined at Line 6 of Algorithm 1. Note that any node $w$ of $\{w(v_i, t, \{i\}, 1) | i \in [1; n]\}, t \in [b_i, e_i]\}$ has no predecessor (otherwise, let $w^- = w(u^-, C^-, S^-)$ be that predecessor, then, according to Definition 2, by the Rule 4 an arc of $S(I)$ must satisfy, $C^- = \emptyset$ and this is not compatible with Rule 1). As a consequence, $L'$ is a topological ordering of $S(I)$.

We prove the lemma by induction on the index of $w$ in $L'$.

**Basis:** We first prove the lemma for the nodes of $\{w(v_i, t, \{i\}, 1) | i \in [1; n]\}, t \in [b_i, e_i]\}$. Let $w = w(v_j, t_j, \{j\}, 1)$ be such a node. The set of mappings of $w$ is initialized at Line 2 of Algorithm 1. The only mapping in $P(w)$ is $p_j$, the mapping associating 0 to the client $j$. By Definition of $pP(w)$, a partial taxi $P$ of that set ends in $v_j$ and satisfies $\{i | v_i \in P \text{ and } v'_i \notin P\} = \{j\}$ and $\{i | v_i \in P\} = 1$ by (i) and (iv). Thus, for all $i \neq j$, $v'_i \in P$ otherwise, by (v), $v_i \in P$ and this would be a contradiction with the fact that $\{i | v_i \in P\} = 1$. Consequently, $pP(w)$ contains only one partial taxi $P = \{v_j\}$. In that taxi, the client $j$ pays 0. The lemma is then proved for $w$.

**Inductive Step:** Let $w = w(u, t, C, S) \in L = L' \setminus \{w(v_i, t, \{i\}, 1) | i \in [1; n]\}, t \in [b_i, e_i]\}$. We now assume that the lemma is true for every node before $w$ in $L'$. Note that $P(w)$ is built in the for loop from line 7 and 15 of Algorithm 1.

Without loss of generality, we assume $u$ is the origin $v_j$ of the client $j$.

Let $p$ be a mapping of $P(w)$, this mapping is added at Line 14 of Algorithm 1. Consequently, there is a predecessor $w^- = (u^-, t^-, C^-, S^-)$ of $w$ and a mapping $p^- \in P(w^-)$ such that $(p, w^-, p^-) \in P(w^-, w)$ at Line 11. By Definition 2, as $u$ is the origin of the client $j$, $C = C^- \uplus \{j\}$. The SUBMAP function is called at
Line 10 of Algorithm 1. In that function, when $p_1 = p^-$, the current iteration is not stopped at Line 9 of Algorithm 2, otherwise $(p, w^-, p^-)$ would not be returned in $\mathcal{P}(w^-, w)$. Consequently, $p(j) = 0$ and, for each client $i \in C^-$,

$$p(i) = p^-(i) + \frac{\omega(u^-, v_j)}{|C^-|} \le \alpha \cdot \omega(v_i, v'_i) \quad (7)$$

Note that the value of $\text{pred}(p^-)$ is never changed after Line 15 of Algorithm 1: if we call the BUILD function with $p^-$ and $w^-$ just after $p^-$ is added to $\mathcal{P}(w^-)$ or if we call it later, the result is the same. By the inductive hypothesis, that function returns a partial taxi $P^- \in pP(w^-)$ such that, for each $i \in C^-$, $p^-(i) = \omega(v_i, P)$.

If we call BUILD after $p$ is added to $\mathcal{P}(w)$, as $\text{pred}(p)$ is set to $(w^-, p^-)$, the result $P$ is the path $P^-$ to which we add the node $v_j$. We now prove $P \in pP(w)$.

* (i) is obviously proved for the path $P$.

* As $P^- \in pP(w^-)$, the capacity constraint is satisfied from the first node of $P$ to $v^-$ by (ii). By (iv), there are $|C^-|$ clients in the taxi when it leaves the node $u^-$. By Definition 2, since the arc $(w^-, w)$ exists in $\mathcal{S}(\mathcal{I})$ and since $u$ is an origin node, $|C^-| \le \text{capa} - 1$. Thus, there are at most capa clients in the taxi when it leaves $v_j$ and (ii) is proved for $P$.

* The time constraint is satisfied for $P^-$. The taxi leaves $u^-$ at time $t^-$ and reaches $u$ at time $t^- + \tau(u^-, u)$. By (iii) Definition 2, $t$ belongs to the time windows associated with $u$ and, since the arc $(w^-, w)$ exists in $\mathcal{S}(\mathcal{I})$, $t = t^- + \tau(u^-, u)$. Consequently, (iii) is proved for $P$.

* $C = C^- \uplus \{j\} = \{i|v_i \in P^- \text{ and } v'_i \notin P^-\} \uplus \{j\}$ and $S^- = |\{i|v_i \in P^-\}|$ by (iv). In $G$, there is no path from $v'_j$ to $v_j$, thus $v'_j \notin P^-$. Consequently, $C = \{i|v_i \in P \text{ and } v'_i \notin P\}$. Moreover, again by Definition 2, since the arc $(w^-, w)$ exists in $\mathcal{S}(\mathcal{I})$ and since $u$ is an origin node, $S = S^- + 1 = |\{i|v_i \in P^-\} \uplus \{j\}| = |\{i|v_i \in P\}|$. Consequently, (iv) is proved for $P$.

* $u$ is an origin node, then, as (v) is true for $P^-$, it is also true for $P$.

* The cost $\omega(i, P)$ paid by any client $i \in C^-$ in the path $P$ from $v_i$ to $v_j$ is $\omega(i, P^-) + \frac{\omega(u^-, v_j)}{|C^-|}$. By the inductive hypothesis, $\omega(i, P^-) = p^-(i)$. Thus, $\omega(i, P) = p^-(i) + \frac{\omega(u^-, v_j)}{|C^-|} = p(i) \le \alpha \cdot \omega(v_i, v'_i)$ by Equation (7). The cost $\omega(j, P)$ paid by the client $j$ is 0, thus $\omega(j, P) = p(j) \le \alpha \cdot \omega(v_j, v'_j)$. Consequently, (vi) is proved for the path $P$.

As a consequence, $P$ belongs to $pP(w)$ and, for each client $i \in C$, $p(i) = \omega(i, P)$. Lemma 3.6 is shown for $w$. By induction, Lemma 3.6 is proved. $\square$

**Lemma 3.7.** For every node $w = (u, t, C, S) \in \mathcal{S}(\mathcal{I})$, for each partial taxi $P \in pP(w)$, there is a mapping $p \in \mathcal{P}(w)$ such that, for each $i \in C$, $p(i) \le \omega(i, P)$.
*Proof.* This proof is similar to the one of Lemma 3.6. We do it by induction on the same list $L'$. The basis is exactly the same in the two proofs.

For the inductive step, a converse argument to the inductive step of Lemma 3.6 proves that there is a mapping $p$ built with the SUBMAP function such that for each client $i \in C$, $p(i) = \omega(i, P)$. When, Algorithm 1 reaches Line 14, either there is a mapping $p' \preceq p$ and, for each client $i \in C$, $p'(i) \le p(i) = \omega(i, P)$ or no such mapping exists and $p$ is added to $\mathcal{P}(w)$. Lemma 3.7 is shown for $w$ and by induction, Lemma 3.7 is proved. $\square$

**Theorem 3.4.** *Algorithm 1 returns an optimal solution for $\mathcal{I}$.*

*Proof.* We prove that Lines 17 and 20 return either no solution if no solution exists or an optimal solution.

If, for some $w = w(v'_j, t, C = \emptyset, S) \in T$, there is no mapping in $\mathcal{P}(w)$, then, by Lemma 3.7, there is no valid taxi from any origin to $v'_j$ in $G$. If $T$ is empty, at Line 17, there is no solution and Algorithm 1 correctly returns no solution.

If such a mapping exists, by Lemma 3.6, the function BUILD at Line 20 returns a path $P \in pP(w^*)$. We recall that $w^*$ is the node $w(v'_j, t, C = \emptyset, S)$ maximizing $S$. As $\{i|v_i \in P \text{ and } v'_i \notin P\} = C = \emptyset$, thus every client of $P$ satisfies the precedence and the cost constraints: $P$ is a valid taxi. In addition, $P$ satisfies $|\{i|v_i \in P\}| = S$ clients. By definition of $w^*$, $P$ is a valid taxi maximizing $|\{i|v_i \in P\}|$, thus $P$ is an optimal solution. $\square$

*Time complexity.* The end of this part is dedicated to proving that, for every node $w = (v, t, C, S) \in S(\mathcal{I})$, the size of $\mathcal{P}(w)$ is polynomial if capa is fixed and if TW is polynomially bounded<fnref n="1" />, and deduce that Algorithm 1 is XP with respect to capa when TW is polynomially bounded.

**Definition 5.** Let $w = (v, t, C, S) \in S(\mathcal{I})$, for every subset $I \subset C$, we define $p_I$ as the subvector of $p$ restricted to every client of $I$. The set $\mathcal{P}(w, I)$ is the subset of non-dominated vectors of $\{p_I, p \in \mathcal{P}(w)\}$, i.e. for any two distinct mappings $p$ and $p'$ of $\mathcal{P}(w, I)$, $p \not\preceq p'$ and $p' \not\preceq p$.

Note that $\mathcal{P}(w, C) = \mathcal{P}(w)$ due to Lines 12 and 13 of Algorithm 1.
We want to prove the following properties:

**Property 2.** Let $w = (u, t, I \uplus J, S) \in S(\mathcal{I})$, with $|I| \ge 2$, and if $u$ is the origin of a client in $I$, then $|P(w, I)| \le n^{(\text{capa}-1) \cdot (|I|-2)} \cdot \text{TW}^{|I|-2}$.

**Property 3.** Let $w = (u, t, I \uplus J, S) \in S(\mathcal{I})$, with $|I| \ge 1$, and if $u$ is not the origin of any client in $I$ then $|P(w, I)| \le n^{(\text{capa}-1) \cdot (|I|-1)} \cdot \text{TW}^{|I|-1}$.

<footnote n="1">¹By polynomially bounded, we mean that TW is a unary encoded number or, equivalently, that there exists a polynomial $p$ such that, for each instance $(G, (V_c, V'_c, B_c, E_c), \tau, \omega, \text{capa}, \alpha)$, TW is no more than $p(\text{size})$ where size is the maximum of the size of $G$, the number of clients, and the logarithm of every other numerical value such as $\tau(a), \omega(a), \text{capa}$ and $\alpha$.</footnote>
We prove the two properties by induction on the size of $|I|$. Each property alternatively proves the other one. The following lemmas proves that Property 3 is true when $|I| = 1$, that if Property 3 is true when $|I| \le c$ for some constant $c$, then Property 2 is true when $|I| = c + 1$, and, finally, when Property 2 is true when $|I| \le c$ for some constant $c$, then Property 3 is true when $|I| = c$.

**Lemma 3.8.** *Property 3 is true when $|I| = 1$.*

*Proof.* Let $I = \{i\}$. In that case, every mapping of $|P(w, I)|$ maps some positive real to the client $i$. There can be only one non-dominated mapping: the one associating the smallest real to $i$. $\square$

**Lemma 3.9.** *If, for some constant $c \le \text{capa}$, Property 3 is true when $1 \le |I| \le c$, then Property 2 is true when $|I| = c + 1$.*

*Proof.* Let $w = w(u, t, I \uplus J, S)$, we assume $I = \{i_1, i_2, \dots, i_{c+1}\}$. In order to prove Property 2, we assume that $u$ is the origin of some client in $I$. Without loss of generality, we also assume that, in any topological ordering of $G$, $v_{i_j}$ is before $v_{i_k}$ if and only if $j \le k$. Then $u = v_{i_{c+1}}$. Otherwise, $u$ is some other origin $v_{i_j}$ and, when the taxi reaches $u$, as the client $i_{c+1}$ is in $I$, it was already picked up by the taxi. This contradicts the fact that the taxi cannot have already reached $v_{i_{c+1}}$ because $v_{i_j}$ is before that node in any topological ordering.

As a consequence, for any mapping $p$ of $\mathcal{P}(w)$, $p(i_{c+1}) = 0$. If we consider two mappings $p$ and $p'$ of $\mathcal{P}(w)$, $p_{|I \setminus i_{c+1}} \preceq p'_{|I \setminus i_{c+1}}$ if and only if $p_{|I} \preceq p'_{|I}$. Thus, $|\mathcal{P}(w, I)| = |\mathcal{P}(w, I \setminus i_{c+1})|$. By the hypothesis, $|P(w, I \setminus i_{c+1})| \le n^{(\text{capa}-1) \cdot (c-1)}$. $TW^{c-1} = n^{(\text{capa}-1) \cdot (|I|-2)} \cdot TW^{|I|-2}$. Thus Property 2 is proved for $I$. $\square$

In order to prove the last lemma, we first prove an intermediate result.

**Definition 6.** Using the pred array, we can define a precedence tree of mappings in which $p^-$ is linked to $p$ if $pred(p) = (w^-, p^-)$ for some state $w^-$. Let $w_1 = w(u_1, t_1, I \uplus J_1, S_1)$ and $w_2 = w(u_2, t_2, I \uplus J_2, S_2)$ such that there is a path from $w_1$ to $w_2$ in $S(I)$. We say that a mapping $p_1$ of $\mathcal{P}(w_1)$ generates $p_2$ of $\mathcal{P}(w_2)$ if there is a path of mappings from $(w_1, p_1)$ to $(w_2, p_2)$ in the precedence tree.

**Lemma 3.10.** Let $w_1 = w(u_1, t_1, I \uplus J_1, S_1)$ and $w_2 = w(u_2, t_2, I \uplus J_2, S_2)$ such that there is a path from $w_1$ to $w_2$ in $S(I)$. Let $q_1$ be a mapping of $\mathcal{P}(w_1, I)$ and $p_1$ and $p'_1$ be two mappings of $\mathcal{P}(w_1)$ such that $p_{1|I} = q_1$ and $p'_{1|I} = q_1$. Let $p_2$ and $p'_2$ be two mappings of $\mathcal{P}(w_2)$ such that $p_1$ generates $p_2$ and $p'_1$ generates $p'_2$. Let finally $q_2$ and $q'_2$ be $p_{2|I}$ and $p'_{2|I}$. Then $q_2 \preceq q'_2$ or $q'_2 \preceq q_2$.

*Proof.* We first assume that $w_1$ is a predecessor of $w_2$. Note that, due to Algorithm 2 at Line 7, $p_2(i) - p_1(i) = p'_2(i) - p'_1(i)$ equals $\frac{\omega(u_1, u_2)}{|I \uplus J_1|}$ for every clients $i \in I$. Since $p_{1|I} = p'_{1|I} = q_1$, $p_1(i) = p'_1(i) = q_1(i)$ and then $q_2(i) = p_2(i) = p'_2(i) = q'_2(i)$.

We can similarly show the same property if $w_1$ is an ancestor of $w_2$ instead of just a predecessor. In that case, there are intermediate mappings between $p_1$ and $p_2$, and between $p'_1$ and $p'_2$. There is a path $(w_1 = x_1, x_2, \dots, w_2 =$
$x_i$) such that $p_1$ generates a mapping $p_{x_2}$ of $x_2$ which generates a mapping $p_{x_3}$ of $x_3$, ... There is also a path ($w_1 = x'_1, x'_2, \dots, w_2 = x'_k$) such that $p'_1$ generates a mapping $p'_{x_2}$ of $x'_2$ which generates a mapping $p'_{x_3}$ of $x'_3$, ... Let $x_i = w(u_i^x, t_i^x, C_i^x, S_i^x)$ and $x'_i = w(u_{i'}^x, t_{i'}^x, C_{i'}^x, S_{i'}^x)$. Due to Algorithm 2 at Line 7, $p_2(i) - p_1(i) = \sum_{i=1}^{l-1} \frac{\omega(u_{i+1}^x - u_i^x)}{|C_i^x|}$ and $p'_2(i) - p'_1(i) = \sum_{i=1}^{k-1} \frac{\omega(u_{i+1}^x - u_i^x)}{|C_i^x|}$. Since $p_{1|I} = p'_{1|I} = q_1$, for all $i \in I$, $p_1(i) = p'_1(i) = q_1(i)$ and then depending whether $\sum_{i=1}^{l-1} \frac{\omega(u_{i+1}^x - u_i^x)}{|C_i^x|} \ge \sum_{i=1}^{l-1} \frac{\omega(u_{i+1}^x - u_i^x)}{|C_i^x|}$ or not, either for all $i \in I$ $q_2(i) \ge q'_2(i)$ or for all $i \in I$ $q_2(i) < q'_2(i)$. $\square$

**Lemma 3.11.** If, for some constant $c \le \text{capa}$, Property 2 is true when $2 \le |I| < c$, then Property 3 is true when $|I| = c$.

*Proof.* Let $w = w(u, t, I \uplus J, S)$, we assume $I = \{i_1, i_2, \dots, i_c\}$ and $u$ is not the origin of any client in $I$.

Let

$$A = \bigcup_{\substack{t' \in [e_{i_c}, b_{i_c}] \\ J' \subset [\llbracket 1; n \rrbracket] \setminus I \\ |J'| \le \text{capa} - |I| \\ S' \in [\llbracket 1; n \rrbracket]} \mathcal{P}(w(v_{i_c}, t', I \uplus J', S'), I)$$

We want to prove that $|\mathcal{P}(w, I)| \le |A|$.

We define a function *anc* associating to each mapping of $\mathcal{P}(w, I)$ an ancestor mapping of $A$. Let $q$ be a mapping of $\mathcal{P}(w, I)$. There exists a mapping $p$ of $\mathcal{P}(w)$ such that $q = p|_I$. Thus there exists an ancestor $w_c = w(v_{i_c}, t', I \uplus J', S')$ of $w$ in $S(\mathcal{I})$ and a mapping $p_c$ of $\mathcal{P}(w_c)$ such that $p_c$ generates $p$. Let *anc*($q$) = $p_c|_I$.

If $|\mathcal{P}(w, I)| > |A|$, there exist two mappings $q_1$ and $q_2$ in $\mathcal{P}(w, I)$ such that $anc(q_1) = anc(q_2)$. By Lemma 3.10, $q_1 \prec q_2$ or $q_2 \prec q_1$. There is a contradiction because every mapping of $\mathcal{P}(w, I)$ is non-dominated. Consequently $|\mathcal{P}(w, I)| \le |A|$.

$$ \begin{aligned} |\mathcal{P}(w, I)| \le |A| &\le \sum_{\substack{t' \in [e_{i_c}, b_{i_c}] \\ J' \subset [\llbracket 1; n \rrbracket] \setminus I \\ |J'| \le \text{capa} - |I| \\ S' \in [\llbracket 1; n \rrbracket]} |\mathcal{P}(w(v_{i_c}, t', I \uplus J', S'), I)| \\ &\le (TW \cdot n^{\text{capa}-2} \cdot n) \cdot (n^{(\text{capa}-1) \cdot (|I|-2)} \cdot TW^{|I|-2}) \\ &\le n^{(\text{capa}-1) \cdot (|I|-1)} \cdot TW^{|I|-1} \end{aligned} $$

Thus Property 3 is proved for $I$. $\square$

**Lemma 3.12.** *Algorithm 1 is pseudo XP with respect to capa.*

*Proof.* We assume capa is fixed and want to prove that the algorithm is polynomial in $|I|$ and TW. Note firstly that $S(\mathcal{I})$ has $|S(\mathcal{I})| = O(n \cdot TW \cdot n^{\text{capa}} \cdot n)$ nodes, thus Line 1 is done in time at most $O(|S(\mathcal{I})|^2) = O(TW^2 \cdot n^{2 \cdot \text{capa}+4})$.
The loop at Line 2 does $O(n \cdot TW)$ constant time iterations.

The topological sorting at Line 6 can be done in time $O(|S(I)|^2)$ with the
Kahn algorithm [12].

The For loops at Lines 7 and 9 do each at most one iteration per node in $S(I)$. The time complexities of those loops depend on the number of mappings associated with a node of the auxiliary graph. Lemmas 3.8, 3.9 and 3.11 prove by induction that Properties 2 and 3 are true. Thus, for each node $w \in S(I)$, the size of $\mathcal{P}(w)$ is never more than $TW^{capa} \cdot n^{capa \cdot capa}$.

Line 10 calls the SUBMAP function. This function has two For loops, at Lines 3 and 5, doing respectively $|\mathcal{P}(w_1)|$ and $O(\text{capa})$ iterations. Each iteration of the inner loop and the other operations of the iterations of the outer loop have a constant time complexity. Thus the SUBMAP function is done in time $O(TW^{capa} \cdot n^{capa \cdot capa} \cdot \text{capa})$. It returns a set of size at most $|\mathcal{P}(w_1)|$.

The For loop at Line 11 does one iteration per mapping returned by the SUBMAP function. The If condition at Line 12 and the remove operation at the next line need $O(|\mathcal{P}(w)|)$ comparisons of mappings. Each comparison is done in time $O(\text{capa})$. The other operations of the For Loop are done in constant time. Consequently, the loop complexity is $O((TW^{capa} \cdot n^{capa \cdot capa})^2 \cdot \text{capa})$ and the complexity of the loop at Line 7 is $O(|S(I)|^2 \cdot (TW^{capa} \cdot n^{capa \cdot capa})^2 \cdot \text{capa})$.

The set $T$ at Line 16 contains at most one $O(n^2)$ state nodes. The three next operations are done either in constant time or in $O(n^2)$ time.

Finally, the last line calls the BUILD function which is done in time $O(|G|)$. We recall that $O(|G|) = O(n^2)$ because we removed the intermediate nodes that are neither an origin nor a destination of a client.

Thus, the complexity of the algorithm is $O(TW^{2 \cdot capa + 2} \cdot n^{2 \cdot capa^2 + 2 \cdot capa + 4} \cdot \text{capa})$. This complexity is polynomial if $TW$ is polynomially bounded and if $\text{capa}$ is fixed. □

By Lemma 3.4 and 3.12, we prove the following theorem.

**Theorem 3.5.** If $G$ is a DAG, $\max\{-DARP-M$ is pseudo $XP$ in $\text{capa}$.$\}$

### 3.2.2. A parameterized approximation for max-DARP-M

**Corollary 3.2.** If $G$ is a DAG, there is a $\frac{1}{\sqrt{n}}$-approximation for $\max$-$DARP$-$M$ in time pseudo $XP$ with respect to $\text{capa}$.

*Proof.* We use Algorithm 4.

If $G$ is a DAG and as $\text{capa}$ is a fixed parameter, we can compute the taxi $P$ at Line 4 in pseudopolynomial time by Theorem 3.5. Consequently, Algorithm 4 is pseudopolynomial.

We define $s(P)$ as the number of clients that are driven by the taxi $P$. Let $\mathcal{P}^* = (P_1^*, P_2^*, \dots, P_q^*)$ be an optimal solution for $I$ and let $\mathcal{P} = (P_1, P_2, \dots, P_r)$ be the solution returned by Algorithm 4. We now show the following property :

**Property 4.** Either $\mathcal{P}^*$ and $\mathcal{P}$ are empty or
$$ \frac{\sum_{i=1}^{q} s(P_i^*)}{\sum_{i=1}^{r} s(P_i)} \le \sqrt{\sum_{i=1}^{q} s(P_i^*)}. $$
**Algorithm 4**

**Require:** An instance $\mathcal{I} = (G, (V_c, V'_c, B_c, E_c), \tau, \omega, capa, \alpha)$ of max-DARP-M

**Ensure:** A feasible solution for $\mathcal{I}$

1: $\mathcal{P} \leftarrow \emptyset$

2: loop

3: $\mathcal{I}_1 \leftarrow$ the instance of max-1-DARP-M with the same parameters as $\mathcal{I}$

4: $P \leftarrow$ an optimal solution for the instance $\mathcal{I}_1$ of max-1-DARP-M

5: **If** $P = \emptyset$ **Then** Return $\mathcal{P}$

6: **Else**

7: Insert $P$ into $\mathcal{P}$

8: Remove every client satisfied by $P$ from $\mathcal{I}$.

Note that $\mathcal{P}$ is empty if and only if $\mathcal{P}^*$ is empty. We just have to assume that $\mathcal{P} \neq \emptyset$ and prove the second part of the property. Finally, note that Property 4 implies that Algorithm 4 is a $\frac{1}{\sqrt{n}}$-approximation algorithm as $\sum_{i=1}^{q} s(P_i^*) \leq n$.

We prove Property 4 by induction on $n$, the number of clients.

**Basis:** if there are 2 clients, then, there cannot be more than one taxi in a feasible solution for $\mathcal{I}: q = r = 1$. Consequently, the optimal solutions for $\mathcal{I}$ and for $\mathcal{I}_1$ are the same. Thus, $\frac{s(P_1^*)}{s(P_1)} = 1 \leq \sqrt{2} = \sqrt{s(P_1^*)}$. Consequently, Property 4 is proved in that case.

**Inductive Step:** We now assume that the property is true for every instance with $n$ clients or less. Let $\mathcal{I}$ be an instance with $n+1$ clients. Let $l$ be the number of taxis in $\mathcal{P}^*$ with a non empty intersection with $P_1$. Without loss of generality, we renumber those taxis $(P_1^*, P_2^*, \dots, P_l^*)$. Note that $l \leq s(P_1)$ because a client cannot be satisfied by two taxis in $\mathcal{P}^*$, thus, there cannot be more than $s(P_1)$ taxis intersecting $P_1$. In addition, note that $l \leq q$.

As $P_1$ is an optimal solution of $\mathcal{I}_1$ and as every taxi in $\mathcal{P}^*$ is a feasible solution of $\mathcal{I}_1$,

$$ \frac{\sum_{i=1}^{l} s(P_i^*)}{s(P_1)} \leq \frac{l \cdot s(P_1)}{s(P_1)} \\ \leq l \\ \leq s(P_1) $$

Consequently,

$$ \sqrt{\sum_{i=1}^{l} s(P_i^*)} \leq s(P_1) \qquad (8) $$

$$ \frac{\sum_{i=1}^{l} s(P_i^*)}{s(P_1)} \leq \sqrt{\sum_{i=1}^{l} s(P_i^*)} $$
If $l = q$, then the property is proved.

Otherwise, let $\mathcal{J}$ be the instance $\mathcal{I}$ where every client satisfied by $P_1$ is removed. Note that, this instance is exactly the instance Algorithm 4 is working on at the beginning of the second of iteration. Consequently, if we directly run Algorithm 4 on instance $\mathcal{J}$, it returns $(P_2, P_3, \dots, P_r)$.

Let $Q^*$ be an optimal solution of $\mathcal{J}$. Note that, as $l \neq q$, $(P_{l+1}^*, P_{l+2}^*, \dots, P_q^*)$ is not empty, and as it is a feasible solution for $\mathcal{J}$, $Q^*$ is not empty. In addition, $r \ge 2$. By the inductive hypothesis,

$$ \frac{\sum_{Q^* \in \mathcal{Q}^*} s(Q^*)}{\sum_{i=2}^{r} s(P_i)} \le \sqrt{\sum_{Q^* \in \mathcal{Q}^*} s(Q^*)} \\ \sqrt{\sum_{Q^* \in \mathcal{Q}^*} s(Q^*)} \le \sum_{i=2}^{r} s(P_i) $$

As $(P_{l+1}^*, P_{l+2}^*, \dots, P_q^*)$ is a feasible solution for $\mathcal{J}$,

$$ \sqrt{\sum_{i=l+1}^{q} s(P_i^*)} \le \sum_{i=2}^{r} s(P_i) $$

By equation (8),

$$ \sqrt{\sum_{i=1}^{l} s(P_i^*)} + \sqrt{\sum_{i=l+1}^{q} s(P_i^*)} \le \sum_{i=1}^{r} s(P_i) $$

Finally, note that if $A > 0$ and $B > 0$, then $\sqrt{A+B} \le \sqrt{A} + \sqrt{B}$,

$$ \sqrt{\sum_{i=1}^{q} s(P_i^*)} \le \sum_{i=1}^{r} s(P_i) $$

The inductive step is proved. Consequently, Property 4 is proved too and this concludes the proof of the corollary. $\square$

**Remark 6.** The proof of Corollary 3.2 proves also that the smaller the optimal solution is, the better the approximation ratio is.

## 4. Conclusion

We have studied a taxi sharing problem in which the price of a trip is evenly shared between the passengers of the trip. The bill of the passengers must be
reduced by a given factor $\alpha$. In addition, the taxi must satisfy a capacity con-
straint and a time window constraint. We defined two optimization problems,
max-DARP-M and max-1-DARP-M, and a decision problem 1-DARP-M and
studied the parameterized complexity and approximability of those problems.
It seems that the cost constraint affects the complexity of the problem more
than the time constraint. The latter makes the problems weakly hard whereas
the problems are strongly hard to solve even if the time constraint is removed
and if all the natural parameters are fixed.

We showed that there exists a pseudopolynomial algorithm for max-1-DARP-M and 1-DARP-M if the capacity *capa* of the taxis is fixed and if the road network is acyclic. This algorithm makes it possible to build a $\frac{1}{\sqrt{n}}$-approximation for max-DARP-M. However, considering its time complexity, this algorithm seems unpractical without any implementation improvement.

Some questions remain open: what is the parameterized complexity and approximability of the three problems with respect to $\alpha$ or to $\alpha$ and TW?, and is there a constant factor parameterized approximation for max-DARP-M in *capa*?

To conclude, max-1-DARP-M seems too hard to be solved in practice and it
looks like the cost constraint is the main cause of that. We think this constraint
is hard because it is independently defined for each client. A way to simplify it
could be to define a unique constraint for all the clients or for all the clients of a
same taxi. In the current model, every client cannot pay more than $\alpha$ multiplied
by the cost of a private ride. Instead of that constraint, we could ask all the
clients of a same taxi to not pay more than the sum of all their private rides
multiplied by $\alpha$. If we then fairly divide the cost of the ride, no client would
pay more than $\alpha$ multiplied by the cost of a private ride. Note that some of the
clients would not pay exactly the cost of their own ride but also a part of the
rides of the other clients.

[1] ATTANASIO, A., CORDEAU, J., GHIANI, G., AND LAPORTE, G. Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. *Parallel Computing* 30, 3 (2004), 377-387.

[2] CHAN, S. *Metaheuristics for solving the dial-a-ride problem*. PhD thesis, North Carolina State University, 2004.

[3] CORDEAU, J. A branch-and-cut algorithm for the dial-a-ride problem. *Operations Research* 54, 3 (2006), 573-586.

[4] CORDEAU, J., AND LAPORTE, G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. *Transportation Research Part B: Methodological* 37, 6 (2003), 579-594.

[5] CORDEAU, J., AND LAPORTE, G. The dial-a-ride problem: models and algorithms. *Annals of Operations Research* 153, 1 (may 2007), 29-46.
[6] COSLOVICH, L., PESENTI, R., AND UKOVICH, W. A two-phase inser-
tion technique of unexpected customers for a dynamic dial-a-ride problem.
*European Journal of Operational Research* 175, 3 (2006), 1605–1615.

[7] CRAINIC, T., AND MALUCELLI, F. Meta-heuristics for a class of demand-
responsive transit systems. *INFORMS Journal on Computing* 17, 1 (2005),
10–24.

[8] DUMAS, Y., DESROSIERS, J., AND SOUMIS, F. The pickup and delivery problem with time windows. *European Journal of Operational Research* 54, 1 (1991), 7–22.

[9] GAREY, M., AND JOHNSON, D. *Computers and intractability: a guide to the theory of NP-completeness*. W. H. Freeman & Co., New York, NY, USA, 1979.

[10] HU, T., AND CHANG, C. Exact Algorithm for Dial-A-Ride Problems with Time-Dependent Travel Cost. *Journal of the Eastern Asia Society for Transportation Studies* 10 (2013), 916–933.

[11] JUNG, J., JAYAKRISHNAN, R., AND PARK, J. Dynamic Shared-Taxi Dis-
patch Algorithm with Hybrid-Simulated Annealing. *Computer-Aided Civil and Infrastructure Engineering* (jun 2015).

[12] KAHN, A. B. Topological sorting of large networks. *Commun. ACM* 5, 11 (Nov. 1962), 558–562.

[13] KANN, V. Maximum bounded 3-dimensional matching is MAX SNP-complete. *Information Processing Letters* 37, 1 (1991), 27–35.

[14] MA, S., ZHENG, Y., AND WOLFSON, O. Real-time city-scale taxi ridesharing. *Knowledge and Data Engineering, IEEE Transactions on* 27, 7 (2015), 1782–1795.

[15] NEDREGÅRD, I. *The Integrated Dial-a-Ride Problem-Balancing Costs and Convenience*. PhD thesis, Norges teknisk-naturvitenskapelige universitet, Trondheim, 2015.

[16] PARRAGH, S., DOERNER, K., AND HARTL, R. Variable neighborhood search for the dial-a-ride problem. *Computers & Operations Research* 37, 6 (2010), 1129–1138.

[17] PIETRZAK, K. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. *Journal of Computer and System Sciences* 67, 4 (2003), 757–771.

[18] POWELL, W. B., AND CHEN, Z.-L. A generalized threshold algorithm for the shortest path problem with time windows. In *Network Design: Connectivity and Facilities Location, Proceedings of a DIMACS Workshop, Princetin, New Jersey, USA, April 28-30, 1997* (1997), pp. 303–318.
[19] ROPKE, S., AND CORDEAU, J. Branch and cut and price for the pickup and delivery problem with time windows. *Transportation Science* 43, 3 (2009), 267–286.

[20] SANTOS, D., AND XAVIER, E. Dynamic taxi and ridesharing: A framework and heuristics for the optimization problem. In *Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence* (2013), IJCAI 13', AAAI Press, pp. 2885–2891.

[21] SANTOS, D., AND XAVIER, E. Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an Incentive. *Expert Systems with Applications* 42, 19 (2015), 6728–6737.

[22] SAVELSBERGH, M., AND SOL, M. The General Pickup and Delivery Problem. *Transportation Science* 29, 1 (feb 1995), 17–29.

[23] WANG, X., DESSOUKY, M., AND ORDONEZ, F. A Pickup and Delivery Problem for Ridesharing Considering Congestion. *Transportation letters* (2015).