Improving the non-urgent sanitary transportation

1st Timothée Chane-Hai

DISP, UR4570

Univ Lyon, INSA Lyon, Univ Lyon 1, Univ Lyon 2

Lyon, France

timothee.chane-hai@insa-lyon.fr

3rd Céline Robardet

LIRIS UMR 5205, F-69621

Univ Lyon, INSA Lyon, CNRS

Lyon, France

celine.robardet@insa-lyon.fr

2nd Samuel Vercraene

DISP, UR4570

Univ Lyon, INSA Lyon, Univ Lyon 1, Univ Lyon 2

Lyon, France

samuel.vercraene@insa-lyon.fr

4th Thibaud Monteiro

DISP, UR4570

Univ Lyon, INSA Lyon, Univ Lyon 1, Univ Lyon 2

Lyon, France

thibaud.monteiro@insa-lyon.fr

*Abstract*—This article introduces the round-trip dial-a-ride problem (RT-DARP). In this variant of the dial-a-ride problem (DARP), each user has a round-trip demand with one morning request and one afternoon request. The novelty of this approach is that a user's maximum ride time is shared between the two requests, creating a dependency between the morning routes and the afternoon routes.

The RT-DARP is solved using the small and large neighbourhood search (SLNS) metaheuristic and further speed up by an improved feasibility testing procedure. Results from this new formulation are compared with results from solving separately the morning and afternoon DARP. The experiments are performed on a new benchmark generated for the RT-DARP. The results from the RT-DARP always outperform the results from the separated formulation. From a managerial perspective, the RT-DARP makes it possible to improve the quality of service without changing the transportation cost.

*Index Terms*—sanitary transportation, healthcare management, small and large neighborhood search, dial-a-ride problem, round-trip

# I. INTRODUCTION

Dial-a-ride transportation plays an important role in medical systems. Indeed, non-urgent door-to-door transportation benefits many patients such as disabled, elderly, rural patients, etc. With the ageing of the population, the demand is increasing. In addition, the sharing of transportation resources can play a role in the ecological transition. This dial-a-ride system is illustrated by Fig. 1.

However, these systems are difficult to implement as they correspond to dial-a-ride problems (DARP) which are NP-hard. To solve a DARP, one must build a set of routes that minimizes the transportation cost and satisfies all the door-to-door transportation requests of the users. This routing must respect the time windows constraints at pickup and drop-off locations, maximum ride times and the capacity of the vehicles. In order to incorporate more real life characteristics, many variants have been developed. We refer the reader to [1] for a recent literature review.

In this work, we introduce a new variant: the round-trip dial-a-ride problem (RT-DARP). In this multi-trip problem,

<figure><img src="image_1.png" /><figcaption>Fig. 1. Example of dial-a-ride transportation in a medical context.</figcaption></figure>

each user has one morning and one afternoon request. The multi-trip component has been well studied in vehicle routing problems (VRP) but less in DARPs. We refer the reader to [2] for a literature review on the multi-trip VRP. Concerning the DARP, the multi-trip component has been used to integrate the characteristics of sanitary transportation. On the one hand, it can be used to integrate constraints related to medical context. For example in [3], the vehicle must return to the hospital to be disinfected between two trips to avoid the spread of diseases. In [4], the vehicle staff can be changed between two trips depending on the needs of the next patients. In [5], [6], it is used to take into account lunch and coffee breaks for the drivers. On the other hand, the multi-trip component can be used to improve aspect related to the quality of service. By considering multiple requests over a planning horizon, the
drivers, service times and groups consistency are respectively improved in [7]–[9]. The novelty of our approach is to consider a maximum daily ride time encompassing each pair of morning and afternoon requests. Thus, a dependence is created between the morning and the afternoon planning.

This feature is inspired by the real sanitary transportation of disabled children in the Auvergne-Rhône-Alpes region, in France. The GIHP company is in charge of the non-urgent sanitary transportation of disabled children. In the morning, the children go from their home to socio-medical-institutions (MSI) and in the afternoon, they return from the MSIs to their respective home. Approximately 1800 children and their families benefit from this transportation system everyday. Currently, the GIHP manages independently the morning and the afternoon routes. Unfortunately, this procedure can result in unfair situations. For example, one child can have two short trips (i.e., close to the child's direct rides) while another one can have two long trips (i.e., close to the child's maximum rides). With the RT-DARP, we bind the morning and afternoon rides by introducing a daily maximum ride time for each user. This daily maximum ride time ensures that any long morning trip is followed by a short afternoon trip and vice versa.

Solving realistic problems involves dealing with complex and large instances. Despite having many effective solution methods developed for the VRP, it is not possible to use them for the DARP. In particular, this is due to the maximum ride time over a request with a pickup and a delivery. To our knowledge, exact methods such as branch-and-cut ([10], [11]) and branch-and-price-and-cut ([12]–[14]) can only solve classic DARPs up to 96 users. Thus, we focused our attention on metaheuristics. Among metaheuristics, the large neighbourhood search (LNS) has consistently showed great results on routing problems. This method, based on a ruin and repair principle, has been introduced in [15] and many variants use the framework from [16] as a basis. One of these variants is the small and large neighbourhood search (SLNS), introduced in [17]. In the SLNS, the algorithm performs small moves most of the time and performs a large move once in a while. During a small iteration, the algorithm removes a small portion of the users and insert them back in the solution. Because of the small size, those small moves are really fast. At the opposite, the large moves are slower but allow to escape local optimums. This algorithm has demonstrated competitive results on multiple VRP variants. To our knowledge, this method has never been used on DARP. In this work, we adapt the SLNS to the RT-DARP.

The rest of the article is organized as follows: Section II describes the RT-DARP, Section III details the solution method. Then, the numerical results and managerial insights are presented in Section IV. Finally, the conclusion and perspectives are provided in Section V.

## II. PROBLEM DESCRIPTION

### A. Problem setting

In the RT-DARP, a user $u \in \mathcal{U}$ has one morning and one afternoon request $r_u^m, r_u^a \in \mathcal{R}$. A request $r \in \mathcal{R}$ has a pickup

location $P_r \in \mathcal{P}$, a drop-off location $D_r \in \mathcal{D}$ and a maximum ride time $\bar{L}_r$. On top of the requests' maximum ride time, a user $u$ has a daily maximum ride time $\bar{L}_u$.

A vehicle $k \in \mathcal{K}$ has a capacity $\bar{Q}_k$, a fixed cost $C_k^f$, a distance-related cost $C_k^d$ and a cost related to the ride time $C_k^t$. A vehicle $k$ can do a morning or an afternoon route or both. Thus, it has a morning starting depot $o_k^{m+} \in \mathcal{O}^{m+}$, a morning ending depot $o_k^{m-} \in \mathcal{O}^{m-}$, an afternoon starting depot $o_k^{a+} \in \mathcal{O}^{a+}$, an afternoon ending depot $o_k^{a-} \in \mathcal{O}^{a-}$.

A node $n \in \mathcal{N}$ has a time window $[A_n, B_n]$, a service duration $S_n$ and a load variation $Q_n$. The load variation is equal to 0 at depot nodes, 1 at pickup nodes and -1 at drop-off nodes.

An arc $(i, j) \in \mathcal{A}$ has a duration $T_{ij}$ and a distance $D_{ij}$.

### B. Mathematical model

The following variables are used to solve the RT-DARP:

* $x_{ij}^k$ is a binary variable equal to 1 if the vehicle $k \in \mathcal{K}$ users the arc $(i, j) \in \mathcal{A}$;

* $w_i^k$ is a positive continuous variable equal to the time of service of the vehicle $k \in \mathcal{K}$ at node $i \in \mathcal{N}$;

* $w_i$ is a positive continuous variable equal to the time of service at node $i \in \mathcal{N}$;

* $l_i^k$ is a positive integer variable equal to the number of users in the vehicle $k \in \mathcal{K}$ after departing from node $i \in \mathcal{N}$;

* $y^k$ is a binary variable equal to 1 if the vehicle $k \in \mathcal{K}$ is used.

We formulate the RT-DARP as a mixed integer program:

* the objective is to minimize the transportation cost:

$$ \min \sum_{k \in \mathcal{K}} C_k^f y^k + \sum_{k \in \mathcal{K}} C_k^t ((w_{o_k^{m-}} - w_{o_k^{m+}}) + (w_{o_k^{a-}} - w_{o_k^{a+}})) + \sum_{k \in \mathcal{K}} \sum_{(i,j) \in \mathcal{A}} C_k^d D_{ij} x_{ij}^k; $$

* the flow is conserved:

$$ \sum_{(j,i) \in \mathcal{A}} x_{ji}^k - \sum_{(i,j) \in \mathcal{A}} x_{ij}^k = 0, \quad \forall i \in \mathcal{P} \cup \mathcal{D}, k \in \mathcal{K}; $$

* every request is served exactly once:

$$ \sum_{k \in \mathcal{K}} \sum_{(i, P_r) \in \mathcal{A}} x_{iP_r}^k = 1, \quad \forall r \in \mathcal{R}; $$

* a request pickup and drop-off node is served by the same vehicle:

$$ \sum_{(P_r, j) \in \mathcal{A}} x_{P_r, j}^k - \sum_{(i, D_r) \in \mathcal{A}} x_{iD_r}^k = 0, \quad \forall r \in \mathcal{R}, k \in \mathcal{K}; $$
• the service time at a node is set according to the vehicle service time at the same node:

$$w_i = \sum_{k \in \mathcal{K}} w_i^k, \quad \forall i \in \mathcal{N};$$

• the arrival time at a node is set according to the incoming arc duration and the service duration at the previous node:

$$\begin{aligned}
w_j^k &\ge w_i^k + S_i + T_{ij} - M_{ij}(1 - x_{ij}^k), \\
M_{ij} &= B_i + S_i + T_{ij}, \\
\forall (i, j) \in \mathcal{A}, k \in \mathcal{K};
\end{aligned}$$

• a pickup is served before its drop-off:

$$\begin{aligned}
w_{P_r} + S_{P_r} + T_{P_r D_r} \le w_{D_r} + M_r \left( 1 - \sum_{k \in \mathcal{K}} \sum_{i \in \mathcal{N}} x_{ik}^k \right), \\
M_r = B_{P_r} + S_{P_r} + T_{P_r D_r}, \\
\forall r \in \mathcal{R};
\end{aligned}$$

• time windows are respected:

$$\begin{aligned}
A_j \le w_j + M_j \left( 1 - \sum_{k \in \mathcal{K}} \sum_{i \in \mathcal{N}} x_{ij}^k \right) &\le B_j, \\
M_j &= A_j, \\
\forall j \in \mathcal{N};
\end{aligned}$$

• a vehicle that leaves in the morning (respectively afternoon), returns in the morning (respectively afternoon):

$$\begin{aligned}
\sum_{j \in \mathcal{P}} x_{o_k^{m+j}}^k - \sum_{i \in \mathcal{D}} x_{i o_k^{m-}}^k &= 0, \\
\sum_{j \in \mathcal{P}} x_{o_k^{a+j}}^k - \sum_{i \in \mathcal{D}} x_{i o_k^{a-}}^k &= 0, \\
\forall k \in \mathcal{K};
\end{aligned}$$

• a vehicle is used if it leaves the depot at least once:

$$\begin{aligned}
M y^k &\ge \sum_{i \in \mathcal{P}} \left( x_{o_k^{m+i}}^k + x_{o_k^{a+i}}^k \right), \\
M &= 2, \\
\forall k \in \mathcal{K};
\end{aligned}$$

• the cumulative load at a node is set according to the load variation at the visited node and the previous cumulative load:

$$\begin{aligned}
l_j^k &\ge l_i^k + Q_j - M_j^k (1 - x_{ij}^k), \\
M_j^k &= \overline{Q}_k + Q_j, \\
\forall (i, j) \in \mathcal{A}, k \in \mathcal{K};
\end{aligned}$$

• the capacity of the vehicle is not exceeded:

$$l_i^k \le \overline{Q}_k \sum_{j \in \mathcal{N}} x_{ij}^k, \quad \forall i \in \mathcal{P}, k \in \mathcal{K};$$

• the request maximum ride time is respected:

$$w_{D_r} - (w_{P_r} + s_{P_r}) \le \overline{L}_r, \quad \forall r \in \mathcal{R};$$

• the user maximum ride time is respected:

$$\begin{aligned}
\overline{L}_u &\ge (w_{D_u^m} - w_{P_u^m} - S_{P_u^m}) \\
&\quad + (w_{D_u^a} - w_{P_u^a} - S_{P_u^a}), \\
&\forall u \in \mathcal{U};
\end{aligned}$$

• each decision variable is defined on its respective ensemble:

$$\begin{aligned}
x_{ij}^k &\in \{0, 1\}, & \forall i \in \mathcal{N}, j \in \mathcal{N}, k \in \mathcal{K}; \\
w_i^k &\in \mathbb{R}^+, & \forall i \in \mathcal{N}, k \in \mathcal{K}; \\
w_i &\in \mathbb{R}^+, & \forall i \in \mathcal{N}; \\
l_i^k &\in \mathbb{Z}^+, & \forall i \in \mathcal{N}, k \in \mathcal{K}; \\
y^k &\in \{0, 1\}, & \forall k \in \mathcal{K}.
\end{aligned}$$

The objective of this formulation is to minimize the transportation costs, which includes the fixed cost of vehicles, the distance related costs, and the duration related costs. Having multiple aspects of the transportation costs allows to improve the quality of service (duration), the environmental impact (distance), and the fleet size (fixed cost).

### III. SOLUTION METHOD

In this section, we present the framework used to solve the RT-DARP. This metaheuristic is based on a Small and Large Neighborhood Search (SLNS) framework coupled with an improved feasibility testing procedure.

#### A. Small and Large Neighborhood Search (SLNS) framework

The SLNS is a variant of the classic LNS framework, introduced in [17]. The principle of the LNS is very simple: at each iteration, a removal operator removes a part of the inserted users, then an insertion operator inserts each of them back in a different position. As a consequence, a new solution is generated at each iteration and thousands of solutions are generated during the search.

The main specificity of the SLNS is that the metaheuristic performs many small iterations (i.e., small sized removal) and once in a while a large iteration (i.e., large sized removal). At the opposite, the removal size is selected randomly for each iteration in the LNS. More precisely, the SLNS performs small and fast iterations most of the time. A large iteration is performed only if the number of consecutive small iterations that did not improved the best solution reaches a certain threshold. During a large iteration, the new solution is generated from the best solution. This new solution is then used for the next small iterations. In this search strategy, small iterations allow for fast intensification while large iterations allow for diversification.

To perform removals and insertions, we used the following operators: random removal, history removal, greedy insertion, K-regret insertion (K = 2, 3, 4). For more details on the operators implementation, we refer the reader to [16]
## B. Improved feasibility tests

For each candidate insertion, a lot of feasibility tests must be done. In other words, we must check that the insertion will result in a solution that respects all the constraints of the problem. Due to the large number of candidate insertions, the implementation of the feasibility tests has a significant impact on the performance of the metaheuristic. In our solution method, the feasibility tests are performed in increasing order of complexity. If an insertion does not pass a simple test, then the more complex tests can be skipped. This procedure allows to speed up the insertions evaluation.

The first set of feasibility tests has a $O(1)$ complexity. These tests concern the capacity constraint and some necessary but not sufficient time-windows constraints. We refer the reader to [7] for the detailed implementation of these tests. Then, the precedences between nodes are tested. When inserting a node in a route, we must make sure that each previous (respectively following) node can be a predecessor (respectively successor) of the inserted node. This precedence filter has a $O(n)$ complexity, with $n$ being the size of the route (i.e., the number of visited nodes). The final and longest test is the complete scheduling of the route. With the insertion of a new user in the route, we must recompute the route schedule and ensure that the new schedule respects the time windows and the maximum ride time of each user. We used the procedure described in [18] which has a $O(n^2)$ complexity with $n$ the size of the route.

Finally, to further improve the speed of the precedence test, we developed a pre-processing procedure specific to the RT-DARP problem. For each pair of nodes, we compute the ride time threshold that creates a precedence constraint. Indeed, when the afternoon request $r_u^a$ of a user $u$ is inserted, a portion of its maximum ride time $\bar{L}_u$ is consumed. Thus, less ride time remains for serving its morning request $r_u^m$. As a consequence, some detours are no longer possible while serving the morning request $r_u^m$. Nodes in the newly infeasible detours become predecessors of the morning request $r_u^m$. We anticipate those situations in a pre-processing step. This makes it possible to retrieve the precedences relations in constant time, even if they change dynamically during the search.

# IV. COMPUTATIONAL EXPERIMENTS

In the following section, we compare the RT-DARP with its corresponding 2-DARP. Each 2-DARP corresponds to a RT-DARP where the users' maximum ride time are equally distributed between their morning and afternoon requests. As a consequence, the morning and afternoon DARPs are independent. The SLNS has been coded in C++ and compiled into a 64 bits single-thread code using g++ 11.3.0. The experiments are performed on a 2.0 GHz AMD EPYC 7702 CPU under a Linux Ubuntu 22.04.1 LTS operating system. For each instance, 5 runs are performed with a different random seed. We use the same parameters setting as in [17] for the SLNS and the same parameters setting as in [18] for the removal and insertion operators.

## A. RT-DARP instances

To our knowledge, no instances exist for the RT-DARP. As a consequence, we generated a new benchmark.

Each user has a morning and an afternoon request. All the morning (respectively afternoon) requests happen during the morning (respectively afternoon) time period. The pickup and drop-off locations are randomly distributed on a (-10, 10) grid. For each user, the morning pickup (respectively morning drop-off) and the afternoon drop-off (respectively afternoon pickup) correspond to the same location. The maximum ride time for a user is equal to his or her direct ride time multiplied by a maximum ride time coefficient (mrt). This coefficient has been set to 1.2, 1.3., 1.4 and 1.5. In the RT-DARP formulation, the maximum ride time for the morning (respectively afternoon) request is set to the user maximum ride time minus the afternoon (respectively morning) request direct ride time. In the 2-DARP formulation, the maximum ride time for a request is set to half of its user maximum ride time to ensure independence between the morning and afternoon DARP. To mimic real situations, the morning drop-off (respectively afternoon pickup) time windows are randomly distributed around 8am (respectively 4pm) according to a normal distribution with a variance of 90 minutes. Time windows stay open for 10 minutes. The remaining time windows are computed using the time windows tightening procedure described in [11]. Service time takes 3 minutes at pickup and drop-off nodes. The load is equal to 1 at pickup nodes and -1 at drop-off nodes.

Our model presented in Section II allows for each vehicle to be unique with its own capacity, own costs and own depots. However, in this communication and as a demonstration of our method's effectiveness, we used an infinite fleet of homogeneous vehicles that leave from the depot located at the center of the map. Both the load and the service duration are equal to 0 at depot nodes. The vehicles' cost corresponds to the real transportation cost of sanitary transportation in France (0.25€ per kilometer, 0.5€ per minute, fixed cost of 50€). Each vehicle has a capacity of 6 passengers.

Because our work is motivated by real problems, our instances are fairly large compared to the literature. In total, we generated 24 instances: 8 instances with 100 users, 8 instances with 200 users and 8 instances with 400 users. The computation time is set to 5 minutes for instances with 100 users, 20 minutes for instances with 200 users and 60 minutes for instances with 400 users. This time limit includes pre-computed operations and the optimization part.

## B. Managerial insights

Instances from the benchmark are solved using the RT-DARP formulation and the 2-DARP formulation. The comparative results are presented in table I. The column gap (respectively cost) corresponds to the average gap (respectively cost) over the 5 runs of the 8 instances. The gap is computed based on the best known solution (bks) found for each instance as follows: $gap = \frac{cost-bks}{bks}$.

First of all, the RT-DARP formulation gives better results than the RT-DARP formulation. In average, the gap is reduced
<table><caption>TABLE I
COMPARISON BETWEEN THE RT-DARP AND THE 2-DARP.</caption><thead><tr><th rowspan="2">nb users</th><th rowspan="2">mrt</th><th colspan="2">2-DARP</th><th colspan="2">RT-DARP</th></tr><tr><th>gap</th><th>cost</th><th>gap</th><th>cost</th></tr></thead><tbody><tr><td rowspan="5">100</td><td>1.1</td><td>2.24</td><td>7 219</td><td>0.39</td><td>7 088</td></tr><tr><td>1.2</td><td>6.37</td><td>7 052</td><td>0.52</td><td>6 664</td></tr><tr><td>1.3</td><td>5.58</td><td>6 692</td><td>0.65</td><td>6 380</td></tr><tr><td>1.4</td><td>5.31</td><td>6 428</td><td>1.01</td><td>6 166</td></tr><tr><td>1.5</td><td>3.97</td><td>6 217</td><td>0.53</td><td>6 011</td></tr><tr><td rowspan="5">200</td><td>1.1</td><td>3.58</td><td>13 505</td><td>0.61</td><td>13 118</td></tr><tr><td>1.2</td><td>6.76</td><td>12 983</td><td>0.49</td><td>12 220</td></tr><tr><td>1.3</td><td>5.10</td><td>12 195</td><td>0.68</td><td>11 683</td></tr><tr><td>1.4</td><td>3.31</td><td>11 564</td><td>0.64</td><td>11 265</td></tr><tr><td>1.5</td><td>3.19</td><td>11 210</td><td>0.65</td><td>10 935</td></tr><tr><td rowspan="5">400</td><td>1.1</td><td>4.78</td><td>25 724</td><td>0.39</td><td>24 646</td></tr><tr><td>1.2</td><td>6.50</td><td>24 081</td><td>0.41</td><td>22 705</td></tr><tr><td>1.3</td><td>3.26</td><td>22 239</td><td>0.46</td><td>21 636</td></tr><tr><td>1.4</td><td>1.92</td><td>21 152</td><td>0.49</td><td>20 855</td></tr><tr><td>1.5</td><td>1.82</td><td>20 458</td><td>0.58</td><td>20 209</td></tr><tr><td>All</td><td></td><td>4.24</td><td>13 915</td><td>0.57</td><td>13 439</td></tr></tbody></table>

by 3.67% (= 4.24 - 0.57). At best, this reduction amounts for 6.27% (= 6.76 - 0.49) for instances with 200 users and a maximum ride time coefficient of 1.2.

Second, it is possible to increase the quality of service without a significant increase in the transportation costs just by using the RT-DARP formulation instead of solving separately the morning and afternoon DARP. This is illustrated in Fig. 2. The graphic shows, for the RT-DARP and the 2-DARP, the average cost relative to the maximum ride time coefficient for the instances with 200 users. Indeed, the cost for the RT-DARP with a maximum ride time coefficient of 1.4 (1.3, 1.2) is fairly close to the cost for the RT-DARP with a maximum ride time of 1.5 (1.4, 1.3). The same tendency can be observed in the table I for the other instances.

To summarize, just by using the RT-DARP formulation instead of the 2-DARP formulation, it is possible to either improve the cost for a similar quality of service or improve the quality of service for a similar cost.

V. CONCLUSION

In this article, we propose a new approach to improve the non-urgent sanitary transportation. For that, we introduced the round-trip dial-a-ride problem (RT-DARP). In this variant of the DARP, each user has one morning and one afternoon request and a maximum daily ride time that must be shared between the morning and afternoon service. This maximum daily ride time creates a dependence between the morning and afternoon DARP. This feature is extracted from the sanitary transportation system in France. To solve generated instances

<figure><img src="image_2.png" /><figcaption>Fig. 2. Average cost relative to the maximum ride time coefficient for instances with 200 users.</figcaption></figure>

with 100, 200 and 400 users, we adapted the small and large neighbourhood search metaheuristic to the RT-DARP. Compared to the formulation with two independent DARPs (one for the morning problem and one for the afternoon problem), the RT-DARP shows a cost reduction of 3.67% in average and up to 6.27% at best. In addition, the RT-DARP formulation allows to improve the quality of service (i.e., reduction of the allowed maximum ride times) without a significant increase in the transportation cost.

The next step of this work is to incorporate more characteristics such as heterogeneous users or reconfigurable vehicles to test the RT-DARP on real instances.

REFERENCES

[1] S. C. Ho, W. Y. Szeto, Y.-H. Kuo, J. M. Y. Leung, M. Petering, and T. W. H. Tou, "A survey of dial-a-ride problems: Literature review and recent developments," *Transportation Research Part B: Methodological*, vol. 111, pp. 395-421, May 1, 2018.

[2] D. Cattaruzza, N. Absi, and D. Feillet, "Vehicle routing problems with multiple trips," *Annals of Operations Research*, vol. 271, no. 1, pp. 127-159, Dec. 1, 2018.

[3] Z. Zhang, M. Liu, and A. Lim, "A memetic algorithm for the patient transportation problem," *Omega*, vol. 54, pp. 60-71, Jul. 1, 2015.

[4] A. Lim, Z. Zhang, and H. Qin, "Pickup and delivery service with manpower planning in hong kong public hospitals," *Transportation Science*, vol. 51, no. 2, pp. 688-705, May 2017, Publisher: INFORMS.

[5] S. N. Parragh, J.-F. Cordeau, K. F. Doerner, and R. F. Hartl, "Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints," *OR Spectrum*, vol. 34, no. 3, pp. 593-633, Jul. 1, 2012.