# An Enhanced Approach for the Dial a ride problem with drivers preferences

Sana Ouasaid
Department of Computer Science
Hassan II University
LIM@II-FSTM, B.P. 146, Mohammedia, Morocco
<EMAIL_ADDRESS>
&Mohammed Saddoune
Department of Computer Science
Hassan II University
LIM@II-FSTM, B.P. 146, Mohammedia, Morocco

###### Abstract

The paper addresses a variant of the Dial-A-Ride problem with additional
features. It is referred to as the DARP with driver preferences, which
attempts to determine a solution more driver-oriented by designing a short
trip in a specific direction that has to be finished at a destination of
interest within a restricted time window. For this purpose, two solutions are
considered. The first involves solving the new MILP exactly using the CPLEX
software. The second is a new approach that employs an iterated local search
as a general framework and exploits many heuristics. Numerical experiments
indicate that the approach can efficiently solve the generated DARPDP
instances in a reasonable time.

_Keywords_ Dial-A-Ride Problem $\cdot$ Driver preferences $\cdot$
Metaheuristic Approach $\cdot$ Multi-objective optimization

## Introduction

With the ever-growing demand for mobility, several shared services have merged
with the purpose of solving specific problems. As an example, the Dial-A-Ride
problem (DARP) is considered an NP-Hard problem concerning on-demand
transportation. The DARP consists of planning vehicle routes to efficiently
serve transport requests in different locations. Each request specifies the
number of passengers and the locations for the start and the end of the trip.
As well as the time windows associated with those locations. This problem
arises in several contexts, such as commercial taxi services, which are
defined through some key choices: fleet, passengers, route, schedule, and
fares. In this paper, we propose an extension of DARP from the point of view
of taxi drivers.

The purpose behind this is that the drivers prefer short- and medium-distance
trips on more profitable lines. The lines can be considered as connecting two
target designated areas known for high demand in a specific period, such as
guys, streetcar stations, etc. Indeed, starting from his current position, the
taxi driver aims to pick up and drop off as many as possible requests in a
flexible manner and ends his trip at a destination of interest at a specific
time. Our proposal is to assist drivers by providing a solution that can be
truly designed around their preferences. It will adapt routes and schedules to
pick up passengers in a more profitable way for drivers while maintaining the
preferences of the onboard passengers.

The remainder of this work can be summarized as follows. Section 1 presents
some literature reviews on the DARP variants and solution methods. Afterward,
a description with related assumptions to the problem studied is given in
Section 2. In Section 3, the general solution approach is explained in detail.
Section 4 describes how new instances based on real-world data are generated
and presents the computational results and analysis of the performance of the
CPLEX solver and the proposed method. Section 5 concludes the paper and
presents some possible future directions.

##  1 Literature Review

Depending on the real-world applications, a DARP was extended to different
variants defined with different constraints and objectives. To solve these
variants several solution methods are designed. In the following, we emphasize
more recent contributions, significant problem extensions, and methods
applied.

There are many variants of DARP, obtained either by adding constraints. Like
the DARP with time windows (DARPTW for Dial a ride problem with time windows)
in which the visit of each customer must be completed in a given time
interval. Or through modification, for example, the Multi-depot DARP where a
depot is specified for each vehicle rather than a single depot serving as the
departure and destination of all the vehicles. For a detailed presentation of
the different variants of DARP, as well as the existing solution methods. One
can refer to Cordeau and Laporte Cordeau (2006).

Parragh et al.Parragh et al. (2015) tackled the DARP with split requests and
profits (DARPSRP). They consider that each request concerns several persons
and can be split and assigned to different vehicles. In fact, multiple
requests can be handled at the same time. The problem concept is the design of
routes aiming for the maximization of the total profit under a set of
constraints vehicle capacity, customer time windows, maximum ride time,
precedence, and pairing.

Masmoudi et al.Masmoudi et al. (2018) presented a Dial-a-Ride Problem with
Electric Vehicles and battery swapping stations (DARP-EV). They consider
multiple types of EVs such that each EV can provide several types of resources
(each with a specific capacity). The problem consists of generating vehicle
routes to serve a set of prespecified requests while minimizing the total
routing cost during a certain planning horizon.

D. Brevet et al Brevet et al. (2019) dealt with the problem of on-demand
transport with private vehicles and alternative locations (DARP-PV-AN), an
extension that allows customers to manage their own trips using private
vehicles. They add several alternative points for the origin/destination of
transport requests to address privacy issues. A compact MILP model and an
evolutionary local search algorithm (ELS) are proposed to solve the problem.

Masson et al Masson et al. (2014) investigate the incorporation of transfers
into DARP (DARPT). The objective is to minimise total routing cost under a set
of additional transfer point-related constraints. They designed a formulation
for the general case where the number of transfer locations is limited to one
of each demand.

Fleet homogeneity is a classic DARP assumption. It can be extended to
heterogeneous fleets when customers have specific service requirements and
expectations. The multi-depot variant with heterogeneous vehicles (MDHDARP)
was presented by Detti et al. Detti et al. (2017), the studied problem derives
from a real-world healthcare application. Among the constraints, we can list
vehicle capacity, pickup and delivery time windows, precedence constraints,
and quality of service provided. They extended the problem by introducing
vehicle-patient compatibility to ensure that the assigned vehicle is
compatible with the patient’s needs. In addition to heterogeneous fleet
management, Parragh et al. Parragh (2012) consider heterogeneous users and
constraints related to the drivers, such as drivers’ work duration limits and
lunch breaks. To tackle this problem, they implemented a hybrid algorithm
combining column generation with a VNS heuristic algorithm.

DARPs belong to the family of complex combinatorial problems whereas
concerning most often many requests. To address those problems, exact methods
find difficulties that drive several contributions to the use of
metaheuristics. Combining more than one metaheuristic results in hybrid
metaheuristics that have been proven to perform better than the classic ones.
In the following, we concentrate on the meta-heuristics used in the design of
our approach. For each metaheuristic, we concentrate on important
contributions.

The Large Neighborhood Search (LNS), Masson et al. Masson et al. (2014) used
an adaptive strategy into LNS (ALNS) with destroy and repair operators to deal
with (DARPT). The adaptiveness of the heuristic is ensured by a mechanism that
calls each operator depending on its performance in previous iterations.
Molenbruch et al. Molenbruch et al. (2017) designed a large neighborhood
search metaheuristic to solve the collaborative DARP.

Simulated Annealing (SA), Braekers et al. Braekers et al. (2014) presented a
version of Simulated Annealing to solve large instances for the MD-H-DARP
(noted as Deterministic Annealing). They proved that the algorithm able to
produce good results, both in terms of solution quality and computation time.
Reinhardt et al.Reinhardt et al. (2013) proposed a simulated annealing-based
heuristic to deal with a DARP for disabled passengers at airports with
complicating synchronization constraints.

The Iterated Local Search (ILS), unlike the above-mentioned metaheuristic, the
iterated local search is not widely used to solve the DARP. The only work that
we found was that of Malheiros et al.Malheiros et al. (2021). The algorithm
proposed combines the iterated local search algorithm with a set partitioning
approach (ILS-SP) and obtains high-quality solutions of multi-depot
heterogeneous DARP within a short time.

Path-relinking (PR) is a common ingredient of hybrid optimization methods.
Parragh et al. Parragh et al. (2009) used it as a post-optimization within an
iterated variable neighborhood search algorithm to tackle a bi-objective DARP.
In Molenbruch et al. Molenbruch et al. (2017) a path relinking phase was
applied after a multi-directional local search algorithm to deal with a DARP
with real-life characteristics concerning the medical needs of patients.

Table 1: Literature review summary Reference | Objectif Function | Constraints | Solution Methods
---|---|---|---
Parragh et al.Parragh et al. (2015) |  | Min Routing cost
---
| Standard DARP constraints
---
| Variable neighborhood search (VNS)
---
+
Path relinking (PR)
Parragh et al.Parragh (2012) |  | Min Routing cost
---
| Standard DARP constraints
---
+
Heterogeneous clients/vehicles
+
Max route duration
+
Lunch breaks
| Variable neighborhood search (VNS)
---
+
Column generation algorithm (CG)
Reinhardt et al.Reinhardt et al. (2013) |  | Min Routing cost
---
+
Max Number of met requests
| Standard DARP constraints
---
+
Transfers
| Simulated Annealing (SA)
---
Masson et al.Masson et al. (2014) |  | Min Routing cost
---
| Standard DARP constraints
---
+
Transfers
| Adaptive Large Neighborhood Search (ALNS)
---
Braekers et al.Braekers et al. (2014) |  | Min Routing cost
---
| Standard DARP constraints
---
+
Multi-depot
| Branch and Cut
---
+
Deterministic Annealing (DA)
Molenbruch et al.Molenbruch et al. (2017) |  | Min Routing cost
---
+
Min Mean user ride times
| Standard DARP constraints
---
+
Restrictions user–user/user–driver
| Path Relinking (PR)
---
+
Multi-directional local search algorithm
Malheiros et al.Malheiros et al. (2021) |  | Min Routing cost
---
| Standard DARP constraints
---
+
Multi-depot
+
Heterogeneous vehicles
| Iterated Local Search (ILS)
---
+
Set partitioning (SP)
Parragh et al.Parragh et al. (2009) |  | Max Total profit
---
| Standard DARP constraints
---
+
Split loads constraints
| Branch and Price (B&P)
---
Masmoudi et al.Masmoudi et al. (2018) |  | Min Routing cost
---
+
Min BSS costs
| Standard DARP constraints
---
+
G-VRP constraints
| Evolutionary Variable Neighborhood Search (EVO-VNS)
---
Brevet et al.Brevet et al. (2019) |  | Min Routing cost
---
| Standard DARP constraints
---
+
Private vehicles
+
Alternative nodes
| Evolutionary Local Search (ELS)
---
Detti et al.Detti et al. (2017) |  | Min Total distance traveled
---
+
Min Total travel time
+
Min vehicles waiting times
| Standard DARP constraints
---
+
Multi-depot
+
Heterogeneous vehicles
+
Compatibility constraints
| Variable Neighborhood Search (VNS)
---
+
Tabu Search (TS)

Despite the large variety of DARP variants arising from real-life scenarios,
to the best of our knowledge, there is still some gap in driver requirements
when designing schedules. In fact, there is a lack of papers that address
constraints related to drivers, which are typically defined in terms of work
duration limits and lunch breaks. With respect to the literature on DARP
variants, we propose to take driver availability and preferences into account
while scheduling requests. Thus, as distinguish from the standard DARP
formulation, we incorporate a threshold constraint and a lateness penalty
within the objective function to ensure the accurate modeling of the driver’s
arrival time to a specific area of interest. In terms of solution methods,
there have been successful hybrid approaches proposed for different DARP
variants. However, most of these methods involves only two methods, which
motivated us to design a hybrid algorithm that thoroughly explores the
benefits of several approaches.

The table 1 provides an overview of the literature review with the column
Objectif Function presenting the criteria incorporated in the model’s Objectif
Function. The column Constraints displays the constraints considered in the
model (the standard constraints refer to the common constraints used in the
model presented by Cordeau and Laporte (2003)). The column Algorithms
describes the articles’ methodologies.

##  2 DARPDP: Description and Formulation

We propose an extension of the Dial-A-Ride problem that takes advantage of
shared taxis and carpooling. Typically, we consider a set of clients who want
to share a taxi and geographically dispersed taxis. Given that each driver’s
taxi has preferences, we assume that starting from a location representing his
current position, he seeks to achieve a profitable route in an area close to
his final destination. This destination is considered as known high demand at
a specific time, such as (bus stops, streetcar stations, electric buses, and
train stations). From the driver’s perspective, we try to model the problem so
that he can benefit from every time saving while achieving his objectives and
without ignoring the clients’ preferences. A solution for the problem is
represented by a set of routes. We base the assumptions of the model on three
main components: client, driver, and route:

Client (request) we associate each request with two vertices a vertex of
origin and a vertex of destination, and time windows associated with these two
points. Additionally, a demand representing the number of passengers to
transport as well as a service time, and a maximum ride time constrains the
duration of his trip.

Driver (taxi) To each taxi, we associate two vertices, an origin vertex and a
destination vertex with a time window.

Route Each route respects many constraints: the capacity of the taxi, a
restricted duration, the order of passage on the vertices of each request, and
the time windows associated with this later (hard constraints). For the taxi
destination time window, we assume it is hard with a small epsilon tolerance.
For example, as commonly found in train stations, even if the taxi driver
misses the arrival of a train, the crowd leaving the station does not disperse
on the spot, and a small tolerance has no repercussions.

Figure 1: Illustrative example of the DARPDP network

Since this problem is an extension of the DARP, we adopt a model previously
defined in the literature (Cordeau’s formulation Cordeau (2006)), where we
adjust the objective function and the constraints to improve driver
satisfaction. To describe the mathematical model we use the notations listed
in Table 2.

Table 2: List of notations Notation | Description
---|---
Sets |
$\mathcal{G}=(\mathcal{V},\mathcal{A})$ | An oriented and weighted graph illustrates the given network.
$\mathcal{A}$ | Set of arcs.
$\mathcal{V}$ | Set of all vertices $\mathcal{V}=\\{s_{k}/k\in\mathcal{K}\\}\cup\mathcal{P}\cup\mathcal{D}\cup\\{t_{k}/k\in\mathcal{K}\\}$.
$\mathcal{N}$ | Set of all requests’ vertices $\mathcal{N}=\mathcal{P}\cup\mathcal{D}$.
$\mathcal{K}$ | Set of all taxis $\mathcal{K}:=\\{1,...,m\\}$.
$\\{s_{k}/k\in\mathcal{K}\\}$ | Set of taxis’ origins $\\{s_{k}/k\in\mathcal{K}\\}:=\\{1,...,m\\}$.
$\\{t_{k}/k\in\mathcal{K}\\}$ | Set of taxis’ destinations $\\{t_{k}/k\in\mathcal{K}\\}:=\\{n+m,...,2m+n\\}$.
$\mathcal{P}$ | Set of pickups’ vertices $\mathcal{P}:=\\{m,...,m+n\\}$
$\mathcal{D}$ | Set of deliveries’ vertices $\mathcal{D}:=\\{2m+n,...,2(n+m)\\}$
Parameters |
$n,m$ | The total number of requests, taxis respectively.
$s_{i}$ | A service time of vertex i $(s_{i}=0\quad,\forall i\in\\{s_{k}/k\in\mathcal{K}\\}\cup\\{t_{k}/k\in\mathcal{K}\\})$.
$[e_{i},l_{i}]$ | Represent the earliest and the last time at which the service can begin
| at vertex i.
$q_{i}$ | A demand of client i (number of passengers to be picked up or delivered)
|  $(q_{i}=0,\forall
i\in\\{s_{k}/k\in\mathcal{K}\\}\cup\\{t_{k}/k\in\mathcal{K}\\}$ and
$q_{i}=-q_{i+m},\forall i\in\mathcal{P})$
$d_{i,j}$ | The distance required to cross the arc $(i,j)$.
$t_{i,j}$ | The time required to cross the arc $(i,j)$.
$T_{r}$ | The maximum duration of the routes of any taxi.
$T_{M}$ | The maximum ride time of each request.
Decision variables |
$x_{i,j}^{k}$ | Binary variable equal to 1 if vertex j is served immediately after vertex i
| by a taxi k, and to 0 otherwise;
$T_{i}^{k}$ | Continuous variable corresponding to the time at which taxi k starts
| its service at vertex i;
$Q_{i}^{k}$ | Continuous variable corresponding to the number of passengers in the taxi k
| after servicing location i of $\mathrm{V}$;
$y_{i}^{k}$ | Binary variable, equal to 1 if client i is served by a vehicle k (each client
| is represented by his pickup point i);

Therefore, we base the objective function on the following three criteria:

  1. 1.

Maximise the number of served requests, which is equivalent to minimizing the
total number of rejected requests; we intend to satisfy as many requests as
possible during the duration of the route.

  2. 2.

Minimise the total distance traveled (expressed in miles).

  3. 3.

Set a tolerance value of $\epsilon_{k}$ for the driver’s destination time
window and minimise any deviation from this latter (expressed in minutes).

There are several algorithms for solving multi-objective optimization
problems. We consider the hierarchical and the weighted sum methods. We use
the first one to express the priority of maximizing the number of served
requests so that the solution doesn’t sacrifice more than $20\%$ of its
optimal value to optimize the other objectives (which means a solution to the
problem must satisfy at least $80\%$ of the total requests). To tackle the
remaining objectives, we use a weighted sum approach. Indeed, it is necessary
to make sure that all terms in the objective function are comparable and have
the same unit of measurement. One suggestion is to express the objective
function in terms of time. In the first stage, we convert the distance from
miles to kilometers and then to minutes by multiplying it by the speed (One
note is that while the distance is now expressed in minutes, it doesn’t
accurately reflect the total duration of the route because it doesn’t take
into consideration the waiting times at different stops.
The mathematical model is represented as follows:
_The Objective-Function_

$Min(w_{1}\times\sum_{k\in K}\sum_{i\in V}\sum_{j\in
V}c_{i,j}^{k}x_{i,j}^{k}+w_{2}\times\sum_{k\in
K}max\\{0,T_{t_{k}}^{k}-l_{t_{k}}\\})$ (1)

subject to the constraints:

$\displaystyle\sum_{i\in\mathcal{P}}(1-\sum_{k\in\mathcal{K}}y_{i}^{k})\leq\epsilon$
(2) $\displaystyle\sum_{k\in\mathcal{K}}y_{i}^{k}\leq 1$ $\displaystyle\forall
i\in\mathcal{P}$ (3)
$\displaystyle\sum_{k\in\mathcal{K}}\sum_{j\in\mathcal{V}}x_{i,j}^{k}=\sum_{k\in\mathcal{K}}y_{i}^{k}$
$\displaystyle\forall i\in\mathcal{P}$ (4)
$\displaystyle\sum_{j\in\mathcal{V}\backslash{t_{k}}}x_{j,i}^{k}-\sum_{j\in\mathcal{V}\backslash{t_{k}}}x_{j,i+m}^{k}=0$
$\displaystyle\forall i\in\mathcal{P},\forall k\in\mathcal{K}$ (5)
$\displaystyle\sum_{j\in\mathcal{V}\backslash{\mathcal{D}}}x_{s_{k},j}^{k}=1$
$\displaystyle\forall k\in\mathcal{K}$ (6)
$\displaystyle\sum_{j\in\mathcal{V}\backslash{t_{k}}}x_{ji}^{k}=\sum_{j\in\mathcal{V}\backslash{s_{k}}}x_{ij}^{k}$
$\displaystyle\forall i\in\mathcal{N},k\in\mathcal{K}$ (7)
$\displaystyle\sum_{i\in\mathcal{V}\backslash{\mathcal{P}}}x_{i,t_{k}}^{k}=1$
$\displaystyle\forall k\in\mathcal{K}$ (8) $\displaystyle
T_{i}^{k}+s_{i}+t_{i,j}\leq T_{j}^{k}+M\left(1-x_{ij}^{k}\right)$
$\displaystyle\forall i\in\mathcal{V},j\in\mathcal{V},k\in\mathcal{K}$ (9)
$\displaystyle t_{t,i+m}\leq T_{i+m}^{k}-\left(T_{i}^{k}+s_{i}\right)\leq
T_{M}$ $\displaystyle\forall i\in\mathcal{P},\forall k\in\mathcal{K}$ (10)
$\displaystyle e_{i}\leq T_{i}^{k}\leq l_{i}$ $\displaystyle\forall
i\in\mathcal{N},k\in\mathcal{K}$ (11) $\displaystyle T_{t_{k}}^{k}\leq
l_{t_{k}}+\epsilon_{k}$ $\displaystyle\forall k\in\mathcal{K}$ (13)
$\displaystyle Q_{i}^{k}+q_{j}\leq Q_{j}^{k}+M\left(1-x_{ij}^{k}\right)$
$\displaystyle\forall i\in\mathcal{V},j\in\mathcal{V},k\in\mathcal{K}$ (14)
$\displaystyle max\\{0,q_{i}\\}\leq Q_{i}^{k}\leq min\\{Q_{k},Q_{k}+q_{i}\\}$
$\displaystyle\forall i\in\mathcal{V},k\in\mathcal{K}$ (15) $\displaystyle
Q_{sk}^{k}=Q_{t_{k}}^{k}=0$ $\displaystyle\forall k\in\mathcal{K}$ (16)
$\displaystyle x_{ij}^{k}\in\\{0,1\\}$ $\displaystyle\forall
i\in\mathcal{V},j\in\mathcal{V},k\in\mathcal{K}$ (17)

#####

The objective function (1) aims to minimize the total sum of the distances
traveled and the violation of the driver’s desired destination time.
Constraint (2) is the $\epsilon-constraint$ that bound the total number of
unserved requests. Constraints (3) ensure that each request is served at most
once by a unique taxi. Constraints (4) ensure consistency between the
variables $x_{i,j}^{k}$ and $y_{i}^{k}$. Constraints(5) guarantee that the
request’s pickup and delivery vertices are served by the same vehicle.
Constraints (6_8) guarantee that each taxi starts its trip at its current
position, leaves each vertex it arrives at, and ends at the destination point
that corresponds to it. The consistency of the time is ensured through
constraints (9). Constraint (10) ensures that the ride time for each request
must not exceed the maximum ride time allowed. Constraints (11) guarantee that
all requests are handled within their time windows. Constraint (12) ensures
the driver’s preferences since the time window of the destination is assumed
to be soft but controlled. We enable an increase by an epsilon that represents
the minimum value by which we can exceed the driver’s desired time. Otherwise,
it will be penalized in the objective function. At each vertex, constraints
(13_15) were designed to make sure that the sum of passengers in the taxi is
smaller than its capacity. Constraint (16) states the binary domain.

##  3 The proposed Method

The proposed method to solve the DARPDP is a metaheuristic method based on an
Iterated Local Search ILS scheme which was introduced for the first time by
Lourenço et al. (2003) Lourenco et al. (2003). ILS has significant success in
solving vehicle routing problems in the literature. For a complete description
of this method, we refer to (Lourenço. Martin and Stützle (2010) Lourenço et
al. (2010)). The following key points constitute the basis of the proposed
approach strategy :

  * •

A two phases heuristic to generate initial solutions;

  * •

A local search to improve the current solution;

  * •

A post-optimization method to efficiently traverse the solution space;

  * •

An acceptance Criterion to define whether a new solution should be accepted;

  * •

A perturbation to diversify the search space.

We give the general framework’s pseudo-code in Algorithm 1 and further details
on each component in the following sections.

Algorithm 1 gives the general structure of the proposed method, which starts
with the initialization of different parameters and the construction of the
initial solution. The main loop in lines (6-26) performs until reaching a
maximum run time. At each iteration, a learning-based local search phase
improves the current solution. The path relinking then enhances the solution.
If the resulting solution $s"$ is better than the current one $s$, $s"$
replaces $s$, and if it is better than the best, $s"$ replaces $s^{*}$.
Otherwise, the number of iterations without improvement increments, and a call
to simulated annealing is required to determine whether to accept $s"$ as a
new solution. When an even number of iterations without improvement is met,
the algorithm executes a Perturbation phase. Finally, The temperature
parameter T decreases and restarts after reaching a minimum temperature.

Algorithm 1 The proposed approach E-ILS

1:

2:Input Data : Contains information about vertices, requests and vehicles

3:$CPU_{max}$: The maximum running time

4:$T_{min},T_{max}$:The minimum and the maximum temperature, respectively

5:$sizeN$ : The size of the neighborhoods

6:$sizeE$: The maximum size of the set E, the set of elite solutions

7:$s^{*}$

8:$s_{0}\leftarrow TwoPhasesHeuristic(InputData)$

9:$s,s^{*}\leftarrow s_{0}$

10:$T\leftarrow T_{max}$

11:$NoImprov\leftarrow 0$

12:$Update\\_setE(s,sizeE)$

13:while $CPU<CPU_{max}$ do

14: $s^{\prime}\leftarrow LearningBasedLocalSearch(s,s^{*},sizeN)$

15: $s^{\prime\prime}\leftarrow PathRelinking(s^{\prime},E)$

16: if $F(s^{\prime\prime})<F(s)$ then

17: $s\leftarrow s^{\prime\prime}$

18: if $F(s^{\prime\prime})<F(s^{*})$ then

19: $s^{*}\leftarrow s^{\prime\prime}$

20: end if

21: else

22: $NoImprov\leftarrow NoImprov+1$

23: $s\leftarrow SimulatedAnnealing(s,s^{\prime\prime},T)$

24: end if

25: $Update\\_setE(s,sizeE)$

26: if $NoImprov\bmod 2$ then

27: $s\leftarrow Perturbation(s,sizeN)$

28: end if

29: $T\leftarrow T*\alpha_{T}$

30: if $T<=T_{min}$ then

31: $T\leftarrow T_{max}$;

32: end if

33:end while

###  3.1 The initial solution

In our proposed approach, we generate the initial solution by a new two-phase
heuristic based on a cluster-first route second principle. First, we perform a
"clustering" phase, after which the requests are decomposed based on spatial
characteristics. The idea is that requests will be assigned to the taxi if
they are located in a specific area (assumed around the direction in which the
driver wants to drive). To this end, we approximate the route taken by the
taxi by an imaginary line connecting its origin and destination points. After
assigning requests to routes, we perform sequential and parallel insertions to
insert requests into routes. We explain the method in detail in the following.

Algorithm 2 TwoPhasesHeuristic

1:Input Data: V(vertices), R(requests), K(taxis)

2:An initial solution s

3:for $(v,k)\hskip 3.0pt\in(V,K)$ do

4: Compute $d_{v,k}$

5:end for

6:for $k\in K$ do

7: Compute $\bar{d_{k}}=\frac{\sum_{v\in V}d_{v,k}}{|V|}$

8: $L_{k}=\\{r\in R/d_{r+,k}<\bar{d_{k}},d_{r-,k}<\bar{d_{k}}\\}$

9:end for

10:for $r\in R$ do

11: if $r\in\bigcap_{i\geq 2}L_{k_{i}}$ then

12: $I_{r}=\\{i/r\in\bigcap_{i}L_{k_{i}}\\}$

13: $\\{L_{k_{i}}/k_{i}\in K,i\in I_{r}\\}=\\{L_{k_{i}}/\\{r\\}/k_{i}\in
K,i\in I_{r}\\}$

14: $L_{MC}\leftarrow L_{MC}\cup\\{(r,L_{rk})/rk\in K\\}$

15: end if

16:end for

17:$s_{0}\leftarrow Anemptysolution$

18:_Sequential insertion_

19:for $route\in s_{0}$ do

20: Sort $L_{k}$ by the upper bound for the start of service of each request

21: ($min\\{l_{p},l_{d}-T_{p,d}-s_{d}\\}$)

22: for request r in $L_{k}$ do

23: $route_{k}\leftarrow insert\\_best(r,route_{k})$.

24: end for

25:end for

26:_Parallel insertion_

27:for request rc in $L_{MC}$ do

28: Choose the most profitable route.

29: $best\\_route_{rc}\leftarrow insert(rc,best\\_route_{rc})$

30:end for

31:For the step 6 and 7 if an insertion is failed the request will be
rejected.

The algorithm 2 starts by calculating the distances between the vertices and
different imaginary lines (lines 1-3). We use the minimum distance from a
point to the line segment as a distance measure and the euclidean metric. The
average distances to each taxi’s line are then used to create a candidate list
of the requests that can be assigned to this taxi (lines 5-6). A request will
be assigned to a taxi if its origin and destination are within a certain
radius around the taxi direction. One note is that a request can be part of
multiple clusters (we associate each cluster with a list). For this, we
differentiate between a list specific to a taxi and one containing the
requests belonging to multiple clusters (we note the list $L_{MC}$). In the
latter case (lines 8-14), we save the index of these clusters in a list noted
as $I_{r}$ specific to each request. The request will then be removed from its
original list (cluster) and inserted into the list $L_{MC}$ that contains
pairs of (request, potential route assignment). In lines (16-26), the routes’
construction phase is carried out, starting with the initialization of an
empty solution (each route starts at the driver’s origin location and ends at
his destination location). We proceed to insert sequentially, in each route,
its specific candidate requests list in the best position. Therefore, we
insert in parallel the remaining requests in $L_{MC}$ in different potential
routes and choose the best route. Note that the best possible insertion is the
one that satisfies all the constraints and minimizes the distance the most.

###  3.2 Learning local Search

The purpose behind this local search technique is to enhance a given initial
solution by focusing the search on promising areas. This method was inspired
by the heuristic adopted in the work of Bo Peng et al. Peng B (2020), which
uses a learning process to determine which operators contribute most to the
improvement of the solution. To do this, this mechanism applies a reward and
penalty strategy to manage the movements dynamically. Thus, the operators that
provide better results are chosen more often in the following iterations.

Learning mechanism At the beginning of the search phase, All moves are
assigned the same score $(sc_{0}=1)$ and thus the same probability of being
chosen. After each iteration, the operator receives either a reward or a
penalty in the form of scores, depending on the current solution and the best
solution found so far. Then the new score is recorded, and the probability of
choosing this operator is recalculated at the next iteration using the scores
collected at the previous iterations. The probability is calculated by the
formula:

$\lambda_{k}=\frac{sc_{k}}{\sum_{i=1}^{n}sc_{i}},\quad k=1,2,\ldots,n.$ (18)

With n the total number of moves.
The operators used were selected after some experiments considering the impact
on the final solution. They are briefly described as follows.

The Relocate consists of moving a request from one route to another (Braekers
et al.Braekers et al. (2014)).

The _Exchange_ consists in exchanging two requests from different routes. The
best exchange is found by trying to insert the origin and destination of each
request into the best position in the other route (Braekers et al.Braekers et
al. (2014)).

The _Exchange Natural_ consists of choosing two routes and performing all
possible exchanges of a natural sequence in one route with any other natural
sequence in another route. A natural sequence is a sequence of requests before
and after which the vehicle is empty (Parragh et al.Parragh S N (2010),
Molenbruch et al. Molenbruch et al. (2017)).

The _R-4-opt_ consists in selecting a route, then selecting four consecutive
arcs in this route. These arcs are deleted, then the segments are reconnected
by other arcs in a different order (Chassaing et al.Chassaing (2016)).

The _Shift_ consists in choosing a route randomly. For all the combinations of
two stops, and performs the exchanges that respect the precedence constraints.

At each call to an operator, the process behind it is repeated at most n
times, where n is the size of the neighborhood. However, inserting all
possible solutions would be very time-consuming. Thus, the algorithm stops the
search after obtaining the first improving solution.

Algorithm 3 Learning Local Search

1:

2:MaxIter: The maximum number of iterations without improvement

3:s: A solution to be improved

4:sizeN

5:$s^{*}$

6:$I_{NoImprove}\leftarrow 0$

7:$\mathcal{N}\leftarrow$ The set of neighborhood structures to be used.

8:$Scores\leftarrow\\{score_{N}=1/N\in\mathcal{N}\\}$

9:while $I_{NoImprove}<MaxIter$ do

10: $P\leftarrow\\{P_{N}=\frac{score_{N}}{\sum score_{N}}/N\in\mathcal{N}\\}$

11: $L\leftarrow\\{N\in\mathcal{N}/P_{N}>rand\\}$

12: $L_{0}\leftarrow L$

13: while $L\neq\emptyset$ do

14: $M\leftarrow rand(L)$

15: $s^{\prime}\leftarrow M(s)$

16: if $f(s^{\prime})<f(s)$ then

17: $s\leftarrow s^{\prime}$

18: $L\leftarrow L_{0}$

19: $I_{NoImprove}\leftarrow 0$

20: if $f(s^{\prime})<f(s^{*})$ then

21: $score_{M}\leftarrow score_{M}+\alpha*\beta_{1}$

22: $s^{*}\leftarrow s^{\prime}$

23: else

24: $score_{M}\leftarrow score_{M}+\alpha*\beta_{2}$

25: end if

26: else

27: $score_{M}\leftarrow score_{M}*\gamma$

28: $L\leftarrow L\backslash M$

29: $I_{NoImprove}\leftarrow I_{NoImprove}+1$

30: end if

31: end while

32:end while

The algorithm 3 starts with the initialization of the number of iterations
without improvement and the list of moves. Then, assigns the value 1 to each
operator to start the search. The main loop is performed until the number of
iterations without improvement is reached. In the first entry in the loop, all
the moves have the same probability of being called. As the execution
progresses, this probability changes according to the performance of each
neighborhood. In line 7, to build the list of candidate neighborhoods, a
probability is chosen between 0 and 1, and another loop starts as long as this
last list is not empty. Then, the procedure executes move by move randomly,
and the resulting neighboring solution is noted as $s^{\prime}$.Depending on
the quality of this latter, the score will change; if this solution improves
the current solution, the current solution will be modified. The search will
be restarted by restoring the list of candidates and the number of iterations
without improvement. Otherwise, the movement will be removed from the list and
the number of iterations without improvement will be incremented by 1.

We can summarize the changes in the score as follow:

  * •

New best solution: whenever the use of an operator results in a new best
solution, its score is increased by $(\alpha*\beta_{1})$: $score\leftarrow
score+\alpha*\beta_{1}$

  * •

New improving solution: each time the use of an operator results in a new
solution that improves the current one, its score is increased by
$(\alpha*\beta_{2})$: $score\leftarrow score+\alpha*\beta_{2}$

  * •

Each time the use of an operator results in a new solution whose cost is worse
than the current solution, its score is multiplied by $\gamma$.
$score\leftarrow score*\gamma$

###  3.3 Path-relinking

After conducting tests on small instances solved optimally, we noticed that
some solutions differ from one request in the wrong position from the optimal
one. One thought is that a new iteration of learning local search can deviate
from the global optimal solution. To address this, we further enhance the
approach with a path relinking (PR) procedure. This permits fast
intensification and leads to the desired solution in less time than a call to
Learning Local Search.

The (PR) was first proposed by Glover Glover (1997) and applied as a post-
optimization based on the exploration of paths connecting the current solution
and the best elite solutions previously produced during the search. The
reasoning behind this idea is that a path from the current solution to a
guiding one will result in new solutions that combine the best features of the
two solutions. We have implemented a back-and-forward strategy which is
explained in algorithm 4.

Algorithm 4 Path-Relinking

1:procedure Path-Relinking($s^{i},s^{j}$)

2: $\Delta\leftarrow\\{j=1,...,n:s_{j}^{i}\neq s_{j}^{g}\\}$

3: $s^{*}\leftarrow argmin\\{f(s^{i}),f(s^{g})\\}$

4: $f^{*}\leftarrow min\\{f(s^{i}),f(s^{g})\\}$

5: $s\leftarrow s^{i}$

6: while $|\Delta|>1$ do

7: $l^{*}\leftarrow argmin\\{f(s\oplus l):l\in\Delta\\}$

8: $s\leftarrow s\oplus l^{*}$

9: $\Delta\leftarrow\Delta\backslash\\{l^{*}\\}$

10: if $f(s)<f^{*}$ then

11: $s^{*}\leftarrow s$

12: $f^{*}\leftarrow f(s)$

13: end if

14: $s^{i}\leftarrow s^{g}$

15: $s^{g}\leftarrow s^{i}$

16: end while

17:end procedure

In each call to (PR) 4, the current solution is considered as initial
solution, and a guiding solution is randomly selected from the elite set E.
The procedure starts with computing the set $\Delta$ (which represents the
symmetrical difference between the two solutions and the set of movements
required) (line 2). In lines (3-4), the algorithm states the best solution
between the two solutions (the starting one) and (the guiding one) as $s^{*}$
and its cost value as $f^{*}$. And the current solution receives $s^{i}$ (the
initial solution). The search then enters a while loop, which constitutes the
main body of the algorithm. At each iteration, it carries out the following
operations: generates a solution path connecting $s^{i}$ and $s^{g}$; deletes
the move from $\Delta$ and returns the best solution along this path as the
current solution. If this solution has an objective value lower than the best
one, the best solution and its cost are updated. Next, the algorithm
alternates between the initial solution $s^{i}$ and the guiding solution
$s^{g}$, and a new iteration starts. The while loop continues until $\Delta$
becomes empty.

Then a set $\Delta$ composed of requests in the initial solution that are
considered as being in the wrong route with respect to the guiding solution.
The set $\Delta$ is computed based on these three key moves as in Santos and
Xavier Santos and Xavier (2015):

$\left\\{\begin{array}[]{l}\text{1. }r\notin s_{i}\text{ and }r\in s_{g}\\\
\text{2. }r\in s_{i}\text{ and }r\notin s_{g}\\\ \text{3. }r\in s_{i}\text{
and }r\in s_{g}\text{ but }id_{R_{s_{i}}^{r}}\neq
id_{R_{s_{g}}^{r}}\end{array}\Rightarrow\left\\{\begin{array}[]{l}\text{1.
Insert r in }s_{i}/id_{R_{s_{i}}^{r}}=id_{R_{s_{g}}^{r}}\\\ \text{2. Remove r
from }s_{i}\\\ \text{3. Remove r from }R_{s_{i}}^{r}\text{and insert}\\\
\text{it in }R_{s_{i}}^{\prime r}/id_{R_{s_{i}}^{\prime
r}}=id_{R_{s_{g}}^{r}}\\\ \end{array}\right.\right.$

Where $r$ a request, $s_{i}$ the initial solution , $s_{g}$ the guiding
solution, $id_{R_{s_{i}}^{r}}$ represents the id of the route $R$ associated
with a request $r$ in the solution $s_{i}$.

###  3.4 Perturbation

During the process of generating the initial solution, we did not focus on
reducing the number of rejected requests, and it turns out that the principle
behind the local search algorithm results in an improved solution that
maintains the same number of requests as the initial solution. More
specifically, the operators can improve the current solution by making changes
that affect only the requests that are part of the solution. However, when a
request is removed from the current solution, we consider the possibility of
inserting others. One approach could be to take advantage of the perturbation
phase to delete less profitable requests and insert others.

Therefore, the perturbation can be seen as a Large Neighborhood Search (LNS)
based approach. The principle of this approach is to remove a number of
requests from their current routes and rearrange them at an optimal cost. We
opt for this method in order to attempt to insert requests that were rejected
in prior iterations. To do this, we begin by removing a certain number of
requests from the current solution. Next, we reconstruct the solution by
iteratively inserting as many of the previously rejected requests as possible,
using repair operators.
We have implemented four removal operators (Route Removal, Greedy Removal,
Random Removal, and Related Removal) and three repair operators (Compatibility
Insertion, Best Insertion, and Random Insertion).

#### Destruction operators

The objective of these operators is to delete a number of requests. We use
four destruction operators: Route Removal, Greedy Removal, Random Removal, and
Related Removal.

_Route removal_ The operator selects the route with the minimum number of
requests and thus deletes all the requests figured in it (Nagata and Bräysy
Nagata and Brysy (2009).

_Random removal_ The operator randomly selects n requests from the solution
and then deletes them. All the routes modified will be optimized by the
"Shift" operator (Pisinger and Ropke Pisinger (2007)).

_Greedy removal_ For each request, the algorithm simulates its removal from
its current route. The overall cost saving is calculated using a defined
metric given in the following equation.

$sav(r)=\begin{cases}(t_{p-1,p}+t_{p,d}+t_{d,d+1})-t_{p-1,d+1}\quad if\quad
d=p+1\\\
(t_{p-1,p}+t_{p,p+1}-t_{p-1,p+1})+(t_{d-1,d}+t_{d,d+1}-t_{d-1,d+1})\quad
Otherwise\\\ \end{cases}$ (19)

Where p and d are the request’s pickup and delivery positions, respectively.
The $t_{i,j}$ represents the time spent in the solution to traverse the arc
(i,j). The request whose deletion produces the largest saving is chosen. The
operator repeats the same steps until n requests are deleted.

_Related removal_ This operator removes a number of related requests (similar
requests) from the solution. The measure of similarity is borrowed from data
mining. We consider that each request is defined by four attributes
(features); We note A as the set of these attributes. A = {position of pickup
point, the position of the delivery point, ready time of pickup point, due
time of the delivery point}. The value of a request $r_{i}$ for an attribute
$a_{k}$ is represented by the similarity function $f(r_{i},a_{k})$. The
similarity between two requests $r_{i}$ and $r_{j}$ is denoted
$Sim(r_{i},r_{j})$ and is represented by the aggregation of the similarity of
all attributes divided by the number of attributes.

The similarity value between requests $r_{i}$ and $r_{j}$ with respect to an
attribute $a_{k}\in A$ is defined as:

$sim_{a_{k}}(r_{i},r_{j})=1-\frac{|f(r_{i},a_{k})-f(r_{j},a_{k})|}{\max_{r\in
R}f(r,a_{k})-\min_{r\in R}f(r,a_{k})}$ (20)

(In order to normalize the values, we set them within the range 0-1 by
dividing by the largest value (1 – value/largest value)).
Two requests $r_{i}$ and $r_{j}$ are related if the sum of the attribute
values divided by the number of attributes is small. The first removed request
$r_{i}$ is selected randomly. Then, the r-1 most related requests to $r_{i}$
are removed and added to the list of rejected requests.

#### Insertion operators

To repair the solution after the destruction phase, we adapted three insertion
methods to insert the rejected requests, namely, Best Insertion, Random
Insertion, and Compatibility Insertion.

A simple insertion technique for the dial-a-ride problem involves inserting a
request per iteration in parallel on different routes and examining all
feasible insertions of both the pickup and delivery points. Therefore, two
options are possible; choosing the best feasible insertion _Best Insertion_ or
a random one _Random Insertion_.

_Compatibility Insertion_ The Compatibility Insertion aims to insert the
rejected requests in the most compatible route based on a compatibility
matrix. To construct the matrix, we first calculate the distance between each
pair of requests. The distance measure used is defined as follows:

$\begin{split}CompMeasure(r_{1},r_{2})&=max(\lvert
l_{r_{1}^{+}}-e_{r_{2}^{+}}-t_{r_{1}^{+},r_{2}^{+}}\rvert,\lvert
l_{r_{2}^{+}}-e_{r_{1}^{+}}-t_{r_{1}^{+},r_{2}^{+}}\rvert)\\\ &+max(\lvert
l_{r_{1}^{+}}-e_{r_{2}^{-}}-t_{r_{1}^{+},r_{2}^{-}}\rvert,\lvert
l_{r_{2}^{-}}-e_{r_{1}^{+}}-t_{r_{1}^{+},r_{2}^{-}}\rvert)\\\ &+max(\lvert
l_{r_{1}^{-}}-e_{r_{2}^{+}}-t_{r_{1}^{-},r_{2}^{+}}\rvert,\lvert
l_{r_{2}^{+}}-e_{r_{1}^{-}}-t_{r_{1}^{-},r_{2}^{+}}\rvert)\\\ &+max(\lvert
l_{r_{1}^{-}}-e_{r_{2}^{-}}-t_{r_{1}^{-},r_{2}^{-}}\rvert,\lvert
l_{r_{2}^{-}}-e_{r_{1}^{-}}-t_{r_{1}^{-},r_{2}^{-}}\rvert)\end{split}$ (21)

To determine the most compatible route for each request, we compute the sum of
the distances between this request and all route requests, divided by the
number of requests.

Algorithm 5 Perturbation

1:procedure Perturbation($s$)

2: Choose random r from the list of rejected requests.

3: $O^{-},O^{+}:=$ A set of destruction (repair) operators

4: $d\in O^{-}$ and $r\in O^{+}$

5: $s^{{}^{\prime}}\leftarrow Destroy(s^{{}^{\prime}},d)$

6: $s^{{}^{\prime}}\leftarrow
Repair(s^{{}^{\prime}},r,R^{r}_{s^{{}^{\prime}}})$

7: return s’

8:end procedure

The Perturbation is described in Algorithm 5. Given "s" a current solution
obtained by the local search. The algorithm chooses a number r of requests to
remove from s (line 2). And two operators destroy and repair are selected from
the list of operators. Then it degrades the current solution by removing r
requests from s and putting them in the list of rejected requests. Then, the
reinsertion operator completes the partial solution obtained by inserting as
many requests as possible.

### Acceptance Criterion

The last part of the heuristic is devoted to taking control of the acceptance
of new solutions (i.e., determining whether the solution produced is accepted
as the new current solution for the next iteration). Along the lines of many
researches, we employed an acceptance criterion borrowed from simulated
annealing. The basic idea is that, initially, we only accept solutions whose
cost is lower than the cost of the current solution. And during the solution
process, to better avoid getting trapped in a local minimum, deteriorating
solutions are accepted with a given probability.

Algorithm 6 Based SA Acceptance Criterion

1:procedure SA($s,s^{\prime},T$)

2: if $f(s)<f(s^{\prime})$ then

3: return s

4: else

5: $r\leftarrow rand(0,1)$

6: if $r<\exp{\frac{f(s)-f(s^{\prime})}{T}}$ then

7: return s

8: else

9: return s’

10: end if

11: end if

12:end procedure

The integration of simulated annealing: At the beginning of the search,
algorithm 1 sets the temperature to its upper bound $T_{max}$. Once a new
solution is returned, the procedure SA was called (algorithm 6) to decide with
which solution the approach will continue the search. Besides the current
temperature, the procedure takes as input the current solution $s^{\prime}$
and the new solution $s$ to compare them. If $s$ is better than $s^{\prime}$,
it will return $s$. Otherwise, a random number r between 0 and 1 is chosen,
and if $r<exp(-f(s)-f(s^{\prime}))$ then returns $s$ otherwise returns
$s^{\prime}$. After this iteration, the current temperature is reduced by
multiplying it with a given cooling rate $\alpha$. If the current temperature
reaches its lower bound $T_{min}$ (close to 0) then is reset to the initial
value $T_{max}$.

##  4 Computational Results

To validate our work, we first present the generation process of new test
instances from real-world data of taxis in New York City. We next carry out a
set of experiments using both algorithms proposed; an exact algorithm that
results in solving the mixed integer mathematical programming and the approach
proposed in section 3.

The results were performed on an Intel(R) Core i7, with 2.60 GHz and 32 GB
RAM, and the Windows operating system. The algorithms were coded in Python
3.8, where the model is solved using IBM ILOG CPLEX Optimization Studio 20.

###  4.1 Test instances

NYC Open Data is one of the largest and most widely used open data platforms
in the world. We used the green and yellow taxi trip data from the year 2021.
For a quick overview of the data set, the dataset has 22793 rows and 18
columns. A more detailed description can be found on the NYC open data website
https://opendata.cityofnewyork.us.

The new benchmark problems for the DARPDP are generated from the yellow taxi
trip data for January 2021. We only extracted the columns “PULocationID”,
“DOLocationID”, “tpep_pickup_datetime”, “tpep_dropoff_datetime”, and the
“trip_distance”.We have considered a time horizon of 2 hours, and therefore we
have restricted the “data_times” columns so that only the “date_time” between
“08h10” and “10h10” are kept (this period was chosen because of an extremely
interesting demand).

We constructed 28 instances (where the number of requests in {10, 15, 20, 30,
50, 100, 200} according to 4 scenarios. The scenarios are generated according
to the following characteristics: the width of the time windows of the
customers (either small of 5 minutes (type-a) or medium of 10 minutes
(type-b)); the number of taxis to be used, calculated as nbr/9 (with "nbr" the
number of requests, and we assume that each vehicle will serve an average of 9
passengers in its trip); we took either the lower or upper bound.

In the following, we describe the process for generating each instance from
the original reference dataset:

Choice of the locations of the client vertices (Pickups/ Deliveries) and the
vehicle vertices (Origins/ Destinations) We joined the Lat/Long geographic
coordinates on the "PULocationID" and "DOLocationID" columns by merging the
dataset with the shape files for the taxi zones file.

Choice of the clients’ time windows For setting the time windows for the
different vertices, we used the column “tpep_pickup_datetime” and
“tpep_dropoff_datetime” as the center of the time windows associated with the
pickup and drop-off points with the consideration of the width (either small
or medium).

Choice of the drivers’ time windows Whereas for the time windows of the taxis,
for origins are flexible $[490,610]$, and for destinations, we generated the
time windows by first choosing a uniform random number $e_{i}$ in the interval
$[550,595]$ in, then choosing $(l_{i}=e_{i}+w)$ (with w the width of the time
windows associated to the drivers’ destination, w = 15 minutes).

Additional data To make instances as realistic as possible, we consider that
the maximum duration of each trip is 90 minutes and that the maximum time a
passenger can stay in a taxi is 30 minutes. The service time is set at 30
seconds and represents the upper limit of time required for a passenger to get
on and out of the taxi. And to simplify the problem, the demand is assumed to
be 1, and the maximum capacity of all taxis is set to 3 passengers. All times
are in minutes. The time between any two vertices of the network is determined
using the Euclidean distance.

We refer to the instances as "inst_an_m" ("inst_bn_m"), representing type-a
(type-b) instances with up to n requests and m vehicles. Regarding the number
of requests, we divide the instances into three groups. Set small contains
instances with (10 and 15 requests), the set medium has instances with (20,
30, and 50 requests), and set large contains instances with (100 and 200
requests). All test instances can be accessed from
https://github.com/SanaaOsd/TestInstancesDARPDP.

Table 3 summarizes the main characteristics of the newly generated instances.
The first column represents the instance name (either of type a or type b),
the second column represents the number of requests to be served, and the
third column the number of available taxis.

Table 3: Instances and their characteristics Instance | Nb of requests | Nb of taxis
---|---|---
inst_10_1 | 10 | 1
inst_10_2 | 10 | 2
inst_15_1 | 15 | 1
inst_15_2 | 15 | 2
inst_20_2 | 20 | 2
inst_20_3 | 20 | 3
inst_30_3 | 30 | 3
inst_a30_4 | 30 | 4
inst_a50_5 | 50 | 5
inst_50_6 | 50 | 6
inst_100_11 | 100 | 11
inst_100_12 | 100 | 12
inst_200_22 | 200 | 22
inst_200_23 | 200 | 23

###  4.2 Parameter settings

The proposed method has several parameters to tune. We choose the parameter
setting while developing the algorithm. Once the parameters related to a
component(Method) are fixed to their best setting, we proceed to the next
component.
Starting with the learning local search, we choose to re-use the value of the
size of the neighbourhoods ($sizeN$) used in the work of Parragh et al.Parragh
S N (2010), and the values reported in Bo. Peng et al. Peng B (2020) for the
learning mechanism parameters, where ($\alpha$) is the reaction factor
controls how quickly the score function reacts to changes according to the
performance of the operators, ($\beta_{1}$) the reward parameter if an
operator results in a new best solution, ($\beta_{2}$) the reward parameter if
an operator improves the current solution, ($\gamma$) the penalty parameter if
an operator results in a solution worse than the current one. Still the number
of iterations ($Iter_{max}$), we investigated three settings where
$Iter_{max}$ is chosen from (5, 10, 20).
For parameters related to the SA method, we choose a commonly used value for
the cooling rate ($\alpha_{T}$), and for the minimum and maximum temperature
($T_{min}$, $T_{max}$) we set candidate values depending on the number of
requests and the number of vehicles n and m respectively,
$\\{(m/2,n/2),(m/2,n),(m,n)\\}$.
Concerning the Path-Relinking method, it only requires a single parameter, the
maximum size of the elite solutions, which is investigated with three settings
(1, 5, 10). In order to obtain a perfect trade-off between the solution
quality and the computation time, the maximum running time ($CPU_{max}$), is
fixed regarding the number of requests in each instance, for the small type
300s, the medium instances (900s), and 1200s for the large ones. After some
preliminary testing, the weights in the objective function are set to
$w_{1}=40$ and $w_{2}=60$.
Table 4, shows the results of 10 runs for each instance within a time limit of
300 seconds per run. For the $Iter_{max}$ parameter, we perform the learning
local search only, for the SA parameter, we run the E-ILS without Path
Relinking, and for the sizeE parameter, we run the E-ILS. The rows denoted
"Best" and "Avg" represent the best and average solution values obtained with
the algorithm, while the column "CPU" represents the average run time in
seconds.
One can observe in the table 4 that setting the $Iter_{max}$ to 5 appear to
require less CPU time, but with an increase in the solution value. In
contrast, applying 20 may eventually lead to a slight improvement but at the
expensive of more processing time, we decided to set $Iter_{max}$ to 10 since
it offered a good balance between solution quality and CPU time. Setting the
($T_{min}$, $T_{max}$) to $(m/2,n/2)$ produces better solutions, in terms of
both best and average results as well as computational time. For the $sizeE$
we conclude that 1 performs better than other values. Table 5 shows the
retained values of the different parameters.

Table 4: Settings of some important parameters for the E-ILS $Iter_{max}$ | 5 | 10 | 20
---|---|---|---
Best | 2757.6086 | 2727.1267 | 2725.0864
Avg | 2839.62 | 2811.8222 | 2802.4756
CPU[s] | 49.64567 | 51.70144 | 85.27037
$\left(T_{min},T_{max}\right)$ | (m/2, n/2) | $(m/2,n)$ | $(m,n)$
Best | 1832.583 | 1848.905 | 1869.189
Avg | 1951.851 | 1956.866 | 1964.608
CPU[s] | 124.24 | 117.58 | 155.31
$sizeE$ | 1 | 5 | 10
Best | 1334.75 | 1388.041 | 1360.246
Avg | 1433.261 | 1493.89 | 1445.335
CPU[s] | 161.4597 | 175.5342 | 178.9134
Table 5: Parameters setting adopted in the E-ILS Parameter | Final Value
---|---
$\alpha$ | 0.1
$\beta_{1}$ | 5
$\beta_{2}$ | 1
$\gamma$ | 0.9
$sizeN$ | 3
$sizeE$ | 1
$\alpha_{T}$ | 0.99
$T_{min}$ | $m/2$
$T_{max}$ | $n/2$
$CPU_{max}$ | Small(300s)
| Medium(900s)
| Large(1200s)
$Iter_{max}$ | 10

###  4.3 Test Results

In this section, we describe the numerical experiments to evaluate the
performance of the proposed method (noted as E-ILS) in solving DARPDP
instances. We compare the proposed E-ILS algorithm to CPLEX for small
instances and with three alternate versions of the method for the medium and
the large instances. Besides comparing the objective function values and
computational times of the obtained solutions, we evaluate the performance of
the algorithms through three key performance indicators listed below:

  * •

The coverage rate represents the percentage of served clients.

$KPI_{1}=\frac{\sum_{k\in K}\sum_{i\in P}y_{i}^{k}}{\lvert P\rvert}\times
100\%$ (22)

  * •

The percentage of empty mileage refers to the distance traveled by vehicles
without passengers onboard.

$KPI_{2}=\sum_{k\in K}\frac{\sum_{(i,j)\in
V}T_{j}^{k}-T_{i}^{k}}{T_{t_{k}}^{k}-T_{s_{k}}^{k}}\times 100\%$ (23)

Where i and j are two stops on which the vehicle drives empty $Q_{i}^{k}=0$.

  * •

The excess ride time represents the average of the differences between the
direct travel time between the pick-up location and the delivery location and
the actual transport time of the client in the solution (in minutes).

$KPI_{3}=\frac{\sum_{k\in K}\sum_{i\in
P}T_{i+p}^{k}-(T_{i}^{k}+s_{i})-t_{i,i+p}}{\lvert P\rvert}$ (24)

For each method, we solve each instance ten times and then compare the best
objective function values and the computational times.

#### Comparison of CPLEX and the proposed E-ILS algorithm on small instances

Table 6 illustrates the comparison between CPLEX and the proposed E-ILS
algorithm for small DARPDP instances. The columns “Best” report the objective
function value of the best solution obtained in 10 runs, "CPU[s]" refers to
the computational time in seconds, and "gap[%]" indicates the default gap as
defined in CPLEX.

Table 6: Results of E-ILS and CPLEX on DARPDP instances | CPLEX | E-ILS
---|---|---
Instance | Best | CPU [s] | Best | CPU [s] | gap [%]
inst_a10_1 | 331.893 | 0.094 | 331.893 | 1.191 | 0
inst_a10_2 | 137.1 | 0.204 | 137.1 | 16.145 | 0
inst_a15_1 | 272.922 | 3.719 | 272.922 | 27.969 | 0
inst_a15_2 | 318.586 | 0.281 | 318.586 | 17.807 | 0.003
inst_a20_2 | 410.026 | 0.531 | 410.026 | 93.501 | 0.01
inst_a20_3 | 353.498 | 2.734 | 353.498 | 136.26 | 0.01
inst_b10_1 | 172.758 | 3.719 | 172.758 | 4.47 | 0
inst_b10_2 | 197.29 | 10.687 | 197.29 | 28.14 | 0
inst_b15_1 | 271.757 | 167.61 | 271.757 | 29.50 | 0.005
inst_b15_2 | 333.858 | 72.75 | 333.858 | 120.82 | 0
inst_b20_2 | 253.495 | 584.141 | 253.495 | 349.72 | 0.01
inst_b20_3 | 403.057 | 1471.17 | 403.057 | 671.90 | 0.01

As shown in Table 6, only instances of up to 20 requests are solved using
CPLEX. For the rest, none were solved within the limit of 2 hours. One can
notice that for these instances, the objective function value of E-ILS is
equivalent to that of CPLEX. However, the proposed method requires more
computational time.

Table 7: Comparison between E-ILS and CPLEX for DARPDP instances based on the three KPIs | CPLEX | E-ILS
---|---|---
Instance | $KPI_{1}[\%]$ | $KPI_{2}[\%]$ | $KPI_{3}[min]$ | $KPI_{1}[\%]$ | $KPI_{2}[\%]$ | $KPI_{3}[min]$
inst_a10_1 | 80 | 50.25 | 6.935 | 80 | 53.69 | 5.992
inst_a10_2 | 80 | 61.87 | 7.960 | 80 | 46.43 | 7.651
inst_a15_1 | 80 | 39.63 | 4.509 | 80 | 29.29 | 4.410
inst_a15_2 | 80 | 66.88 | 5.594 | 80 | 67.50 | 4.511
inst_a20_2 | 80 | 36.25 | 7.325 | 80 | 31.25 | 7.295
inst_a20_3 | 80 | 66.12 | 6.416 | 80 | 62.12 | 5.409
inst_b10_1 | 80 | 30.89 | 6.382 | 80 | 13.95 | 2.489
inst_b10_2 | 80 | 50.70 | 11.081 | 80 | 2.10 | 10.181
inst_b15_1 | 80 | 23.36 | 7.640 | 80 | 31.87 | 5.759
inst_b15_2 | 80 | 25.07 | 7.452 | 80 | 32.99 | 7.293
inst_b20_2 | 80 | 23.61 | 10.768 | 80 | 31.47 | 10.028
inst_b20_3 | 80 | 47.54 | 9.949 | 80 | 1.81 | 8.093

From table 7, it can be seen that the coverage rate is almost equivalent.
Actually, the number of served requests is the strict minimum that verifies
the $\epsilon-constraint$. For the columns, empty mileage, and ride time, the
performance of the E-ILS method is better than CPLEX. Indeed, the empty
mileage is about $34\%$ on average for the E-ILS method versus $44\%$ on
average for CPLEX. The excess ride time is about 6.59 minutes per client for
the E-ILS versus 7.67 minutes per client for the CPLEX. It should be noted
that these KPIs were calculated based on the resulting solutions. Their
incorporation within the objective function implies more complexity, requiring
dedicated investigation in a further work.

###  4.4 Impact of method design components

In our hybrid approach, several components are applied in order to measure
their impact; four combinations are selected and tested as follows:

  * •

M0: the classical ILS uses as a local search phase a simple local search that
consists in applying three moves (Relocate, Exchange, R-4-opt) one after the
other. The perturbation is based on the same simple local search with the size
of the moves increasing by one. And a simple acceptance criterion considering
that only the best solutions will be accepted.

  * •

M1: Same as above, but use the proposed perturbation.

  * •

M2: Same as above, but add a PR phase to intensify the search.

  * •

E-ILS: Represents our hybrid approach following the general structure of
Algorithm 1.

In order to compare our method to existing algorithms, another combination of
the ILS algorithm with a set partitioning problem is tested which is the ILS-
SP method by Malheiros et al.Malheiros et al. (2021). It is important to
mention that the algorithm was designed to solve the multi-depot heterogeneous
variant of DARP (MDHDARP). An adjusted reimplementation in Python was required
to fit our model and data. Results of initial tests show unreasonably long
execution times. Thus an additional stopping criterion to the ILS-SP was
added; i.e., the same time limits as used in our approach.

Table 8: Comparison of E-ILS with the three alternate versions on a-type
instances

| M0 | M1 | M2 | E-ILS | ILS-SP
---|---|---|---|---|---
Instance | Best | CPU [s] | Best | CPU [s] | gap [%] | Best | CPU [s] | gap [%] | Best | CPU [s] | gap [%] | Best | CPU [s] | gap [%]
inst_a10_1 | 411.31 | 4.43 | 331.893 | 9.37 | -19 | 331.893 | 6.97 | -19 | 331.893 | 1.19 | -19 | 331.893 | 3.85 | -19
inst_a10_2 | 222.298 | 3.21 | 151.044 | 19.84 | -32 | 148.323 | 25.24 | -33 | 137.1 | 16.15 | -38 | 137.1 | 21.59 | -38
inst_a15_1 | 409.707 | 41.26 | 392.552 | 56.04 | -4 | 395.814 | 36.64 | -3 | 272.922 | 27.97 | -33 | 421.999 | 35.33 | 3
inst_a15_2 | 339.154 | 28.31 | 335.874 | 23.04 | -1 | 318.586 | 45.73 | -6 | 318.586 | 17.81 | -6 | 318.586 | 19.25 | -6
inst_a20_2 | 567.005 | 126.04 | 509.99 | 124.67 | -10 | 501.013 | 165.10 | -12 | 410.026 | 93.50 | -28 | 449.678 | 97.45 | -21
inst_a20_3 | 383.589 | 79.31 | 377.407 | 309.23 | -2 | 346.548 | 280.42 | -5 | 353.498 | 136.26 | -8 | 358.531 | 143.00 | -7
inst_a30_3 | 996.256 | 84.69 | 989.557 | 272.76 | -1 | 913.185 | 277.15 | -8 | 909.882 | 446.44 | -9 | 867.282 | 455.09 | -13
inst_a30_4 | 983.364 | 548.20 | 947.188 | 731.71 | -4 | 899.68 | 556.93 | -9 | 812.369 | 612.28 | -17 | 906.635 | 615.02 | -8
inst_a50_5 | 1273.956 | 670.96 | 1248.764 | 797.20 | -2 | 1232.311 | 444.98 | -3 | 1147.149 | 848.16 | -10 | 1163.03 | 853.41 | -9
inst_a50_6 | 1396.797 | 398.45 | 1372.294 | 611.63 | -2 | 1346.459 | 486.74 | -4 | 1271.975 | 534.43 | -9 | 1276.124 | 542.46 | -9
inst_a100_11 | 2725.092 | 966.81 | 2451.173 | 1027.44 | -10 | 2329.29 | 786.72 | -15 | 2209.674 | 989.43 | -19 | 2101.015 | 999.37 | -23
inst_a100_12 | 2367.649 | 881.12 | 2190.862 | 1036.31 | -7 | 2045.925 | 710.86 | -14 | 1860.426 | 961.07 | -21 | 1765.178 | 965.10 | -25
inst_a200_22 | 4433.232 | 1084.73 | 4234.225 | 1073.47 | -4 | 4227.707 | 1102.64 | -5 | 4128.984 | 1007.03 | -7 | 4112.832 | 1013.57 | -7
inst_a200_22 | 5261.09 | 1026.43 | 4741.591 | 1105.94 | -10 | 4643.92 | 1124.31 | -12 | 4600.176 | 1061.63 | -13 | 4557.271 | 1070.96 | -13
Average |  | 424.57 |  | 514.19 |  |  | 432.17 |  |  | 482.38 |  |  | 488.25 |
CPU[s] |  |  |  |  |  |  |  |  |  |  |  |  |  |
Average |  |  |  |  | -8 |  |  | -10 |  |  | -17 |  |  | -14
Gap[%] |  |  |  |  |  |  |  |  |  |  |  |  |  |

Table 9: Comparison of E-ILS with the three alternate versions on b-type
instances

| M0 | M1 | M2 | E-ILS | ILS-SP
---|---|---|---|---|---
Instance | Best | CPU [s] | Best | CPU [s] | gap [%] | Best | CPU [s] | gap [%] | Best | CPU [s] | gap [%] | Best | CPU [s] | gap [%]
inst_b10_1 | 220.093 | 5.38 | 172.758 | 19.57 | -22 | 172.758 | 17.43 | -22 | 172.758 | 4.47 | -22 | 184.904 | 14.30 | -16
inst_b10_2 | 306.107 | 5.09 | 267.847 | 49.11 | -12 | 197.29 | 37.34 | -36 | 197.29 | 28.14 | -36 | 239.929 | 50.87 | -22
inst_b15_1 | 345.145 | 24.45 | 328.937 | 27.57 | -5 | 271.757 | 50.72 | -21 | 271.757 | 29.50 | -21 | 286.355 | 49.41 | -17
inst_b15_2 | 465.27 | 42.61 | 419.624 | 130.54 | -10 | 398.337 | 137.35 | -14 | 333.858 | 120.82 | -28 | 366.005 | 126.76 | -21
inst_b20_2 | 444.35 | 271.41 | 387.863 | 420.69 | -13 | 357.538 | 277.99 | -20 | 253.495 | 349.72 | -43 | 348.395 | 393.47 | -22
inst_b20_3 | 639.132 | 455.20 | 582.421 | 265.56 | -9 | 566.4 | 329.77 | -11 | 403.057 | 671.90 | -37 | 471.102 | 678.64 | -26
inst_b30_3 | 1029.23 | 349.15 | 876.739 | 896.57 | -15 | 862.052 | 835.43 | -16 | 784.352 | 871.79 | -24 | 856.572 | 878.90 | -17
inst_b30_4 | 844.618 | 724.06 | 780.735 | 625.66 | -8 | 823.726 | 599.48 | -2 | 732.154 | 629.29 | -13 | 816.175 | 690.89 | -3
inst_b50_5 | 1318.057 | 636.38 | 1371.513 | 859.22 | 4 | 1296.419 | 855.67 | -2 | 1210.899 | 605.95 | -8 | 1216.253 | 664.10 | -8
inst_b50_6 | 869.341 | 655.65 | 918.229 | 871.46 | 6 | 862.72 | 739.01 | -1 | 767.605 | 671.15 | -12 | 807.239 | 702.29 | -7
inst_b100_11 | 2625.673 | 919.27 | 2786.48 | 1099.71 | 6 | 2623.454 | 930.37 | 0 | 2580.933 | 1114.62 | -2 | 2569.959 | 1043.03 | -2
inst_b100_12 | 2292.097 | 784.30 | 2143.297 | 935.25 | -6 | 2110.755 | 861.50 | -8 | 1993.452 | 1021.65 | -13 | 1910.7 | 1065.75 | -17
inst_b200_22 | 4591.072 | 1041.14 | 4676.657 | 1107.45 | 2 | 4696.947 | 1041.07 | 2 | 4423.672 | 1104.43 | -4 | 4321.651 | 1090.97 | -6
inst_b200_23 | 4073.375 | 1131.56 | 4008.19 | 1141.60 | -2 | 4077.901 | 1049.11 | 0 | 3733.878 | 1089.74 | -8 | 3381.286 | 1076.08 | -17
Average |  | 503.26 |  | 603.57 |  |  | 554.45 |  |  | 593.79 |  |  | 608.96 |
CPU[s] |  |  |  |  |  |  |  |  |  |  |  |  |  |
Average |  |  |  |  | -6 |  |  | -11 |  |  | -19 |  |  | -14
Gap[%] |  |  |  |  |  |  |  |  |  |  |  |  |  |

Table 10: Comparison between E-ILS and the three alternate versions for a-type
DARPDP instances based on the three KPIs

| M0 | M1 | M2 | E-ILS | ILS-SP
---|---|---|---|---|---
Instance | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$
inst_a10_1 | 90 | 44 | 5.32 | 80 | 54 | 5.74 | 80 | 54 | 5.92 | 80 | 54 | 5.99 | 80 | 54 | 5.99
inst_a10_2 | 80 | 53 | 6.9 | 80 | 62 | 7.78 | 80 | 48 | 7.08 | 80 | 46 | 7.56 | 80 | 46 | 7.56
inst_a15_1 | 93 | 32 | 5.17 | 87 | 39 | 5.23 | 87 | 43 | 4.59 | 80 | 29 | 4.41 | 93 | 32 | 5.47
inst_a15_2 | 80 | 67 | 4.73 | 80 | 52 | 4.27 | 80 | 68 | 4.39 | 80 | 68 | 4.51 | 80 | 68 | 4.39
inst_a20_2 | 80 | 48 | 7.51 | 80 | 47 | 7.93 | 80 | 43 | 7.40 | 80 | 31 | 7.30 | 80 | 24 | 8.85
inst_a20_3 | 80 | 56 | 5.30 | 80 | 51 | 6.23 | 80 | 58 | 5.07 | 80 | 62 | 5.41 | 80 | 62 | 5.39
inst_a30_3 | 80 | 55 | 4.69 | 80 | 49 | 5.17 | 80 | 51 | 5.02 | 80 | 47 | 5.39 | 80 | 48 | 5.19
inst_a30_4 | 80 | 55 | 6.63 | 80 | 38 | 8.64 | 93 | 30 | 8.85 | 93 | 28 | 8.11 | 83 | 42 | 7.72
inst_a50_5 | 100 | 21 | 8.10 | 98 | 19 | 7.70 | 98 | 20 | 7.78 | 86 | 28 | 8.52 | 90 | 30 | 9.05
inst_a50_6 | 94 | 21 | 6.61 | 96 | 28 | 7.12 | 94 | 43 | 6.59 | 94 | 44 | 7.25 | 80 | 43 | 7.14
inst_a100_11 | 80 | 45 | 6.33 | 80 | 43 | 6.49 | 82 | 45 | 5.77 | 80 | 42 | 6.61 | 82 | 42 | 6.37
inst_a100_12 | 88 | 50 | 6.15 | 80 | 46 | 6.82 | 81 | 39 | 7.24 | 80 | 46 | 7.19 | 80 | 47 | 6.96
inst_a200_22 | 89 | 43 | 6.75 | 89 | 42 | 7.09 | 89 | 41 | 7.04 | 89 | 46 | 6.48 | 89 | 44 | 6.81
inst_a200_23 | 89 | 40 | 7.97 | 89 | 44 | 7.03 | 89 | 42 | 7.39 | 89 | 41 | 7.71 | 89 | 42 | 7.26
Average $KPI_{1}[\%]$ | 86 |  |  | 84 |  |  | 85 |  |  | 84 |  |  | 83 |  |
Average $KPI_{2}[\%]$ |  | 45 |  |  | 44 |  |  | 45 |  |  | 44 |  |  | 45 |
Average $KPI_{3}[min]$ |  |  | 6.30 |  |  | 6.66 |  |  | 6.44 |  |  | 6.60 |  |  | 6.73

Table 11: Comparison between E-ILS and the three alternate versions for b-type
DARPDP instances based on the three KPIs

| M0 | M1 | M2 | E-ILS | ILS-SP
---|---|---|---|---|---
Instance | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$ | $KPI_{1}$ | $KPI_{2}$ | $KPI_{3}$
inst_b10_1 | 90 | 61 | 2.40 | 80 | 14 | 2.49 | 80 | 14 | 2.49 | 80 | 14 | 2.49 | 80 | 14 | 5.61
inst_b10_2 | 80 | 21 | 8.36 | 80 | 40 | 7.46 | 80 | 2 | 10.18 | 80 | 2 | 10.18 | 80 | 12 | 9.91
inst_b15_1 | 87 | 31 | 6.23 | 80 | 31 | 5.35 | 80 | 32 | 5.76 | 80 | 32 | 5.76 | 80 | 32 | 5.71
inst_b15_2 | 80 | 42 | 6.65 | 87 | 20 | 7.19 | 87 | 34 | 7.32 | 80 | 33 | 7.29 | 80 | 32 | 7.82
inst_b20_2 | 95 | 18 | 9.98 | 80 | 10 | 8.76 | 80 | 33 | 8.59 | 80 | 31 | 10.03 | 80 | 34 | 9.15
inst_b20_3 | 85 | 14 | 7.46 | 85 | 14 | 9.17 | 90 | 2 | 8.96 | 80 | 2 | 8.09 | 80 | 29 | 6.39
inst_b30_3 | 90 | 29 | 4.52 | 83 | 55 | 3.92 | 83 | 52 | 4.39 | 83 | 62 | 3.11 | 93 | 51 | 4.12
inst_b30_4 | 90 | 36 | 6.75 | 93 | 50 | 5.74 | 83 | 27 | 7.67 | 93 | 21 | 6.16 | 93 | 33 | 5.79
inst_b50_5 | 88 | 34 | 5.94 | 82 | 49 | 5.56 | 84 | 35 | 6.65 | 82 | 37 | 6.16 | 80 | 33 | 6.32
inst_b50_6 | 84 | 41 | 5.42 | 88 | 57 | 5.00 | 82 | 54 | 5.00 | 80 | 49 | 5.45 | 86 | 41 | 6.18
inst_b100_11 | 89 | 42 | 6.29 | 89 | 40 | 6.79 | 89 | 46 | 5.88 | 89 | 47 | 6.22 | 89 | 40 | 6.60
inst_b100_12 | 88 | 47 | 6.12 | 88 | 45 | 5.95 | 88 | 46 | 6.07 | 82 | 44 | 6.65 | 81 | 43 | 5.87
inst_b200_22 | 89 | 48 | 5.88 | 89 | 37 | 6.72 | 89 | 40 | 6.57 | 89 | 40 | 6.63 | 89 | 37 | 7.03
inst_b200_23 | 88.5 | 51 | 5.50 | 80 | 50 | 5.66 | 88.5 | 51 | 5.22 | 80 | 48 | 5.31 | 80 | 48 | 5.11
Average $KPI_{1}[\%]$ | 87 |  |  | 85 |  |  | 85 |  |  | 83 |  |  | 84 |  |
Average $KPI_{2}[\%]$ |  | 37 |  |  | 37 |  |  | 33 |  |  | 33 |  |  | 34 |
Average $KPI_{3}[min]$ |  |  | 6.25 |  |  | 6.13 |  |  | 6.48 |  |  | 6.40 |  |  | 6.54

Tables 9 and 9 show the results achieved by the five heuristics for the a-type
(b-type) instances, respectively. The percentage gaps between the basic ILS
(M0) and the other methods (E-ILS, M1, M2, ILS-SP) are calculated as
$100(Best_{Method}-Best_{M0})/Best_{M0}$.

It is worth emphasizing that E-ILS and ILS-SP significantly outperforms the
basic ILS (M0) with an average of 17%(19%) and 14%(14%) respectively increase
in solution quality for all a-type (b-type) DARPDP instances, respectively.
However, this comes at the expense of more computational time but is still
reasonable, as indicated in tables 9 and 9. Besides, the solutions obtained by
$M1$ with LNS-based perturbation are 8% (6%) on average better than $M0$,
which is already, an important improvement, and hence this approach
effectively diversify the search space. As one might expect, adding a PR phase
intensify deeply the search and gives an improvement of 10% (11%) compared to
M0. It is worth mentioning that the considerable improvement achieved by the
E-ILS is related to exchanging the Simple Local Search for a Learning Local
Search. One can notice that on large instances, the ILS-SP performs slightly
better. However, for the small instances our proposed approach is much more
effective.

In the comparative tables 11 and 11, one can notice that there is no assertion
that one method is the most efficient on the three key performance indicators
simultaneously. Although we can draw the following conclusions.

According to figure 2, it can be seen that the computation time obviously
increases with increasing the number of requests. Comparing the scenarios,
a-type, and b-type instances. As one might expect, the complexity of the
problem increases with b-type instances, which is consistent with the reported
increase in resolution time.

Figure 2: Running time per instance type The figure illustrates The variation
of execution time depending on the types of instances

Through the analysis of the figure 3, one can notice that the percentage of
empty mileage decreases with the increase in the excess ride time. Therefore,
as one might expect, an extra ride time is related to an indirect trip.
Interestingly, this decrease in direct trips also comes with a general
reduction of the scenario with one request onboard the vehicle.

Figure 3: Correlation between key performance indicators The two figures
illustrate the average percentage of Empty Mileage and the average Excess Ride
Time on the solutions for a-type test instances and b-type test instances

##  5 Conclusion

In this research, the dial-a-ride problem was adapted to handle a more
practical application. The new problem considers driver preferences in terms
of working during times and in areas that suit their personal preferences. To
ensure this, we have added for each driver individual origin, destination and
time window to reach his destination. The driver’s preferences modeled by
additional threshold constraint which define the maximum allowable tolerance
time for reaching the driver’s destination, and this deviation is minimised
further in the objective function. We proposed a new efficient E-ILS algorithm
where the advantages of multiple heuristics are fully investigated and
combined into a unified ILS framework, including learning local search, path-
relinking, and large neighborhood search. The computational results, using
generated instances based on real-world data and analyzing three key indicator
performances, confirm that the metaheuristic approach is more efficient than
CPLEX at producing high-quality solutions in a reasonable time for the small
DARPDP instances and outperforms the basic ILS for the large ones.
Our future work will focus on three aspects: (1) Addressing the online version
of the proposed problem is an interesting research direction. (2) The problem
is challenging to resolve because of the multiplicity and complexity of the
constraints. The performance of the proposed model can be improved either by
adding cuts to relax hard constraints or by decomposing the problem into sub-
problems. (3) We paid considerable attention to designing the algorithm; it
seems to be a very promising approach. However, the results of preliminary
experiments show that we still need more tests on the parameters besides the
calibration of probabilities to call different method components. Hence,
additional verification could result in better solution performance and
convergence.

## References

  * Cordeau [2006] J F Cordeau.  A branch-and-cut algorithm for the dial-a-ride problem.  _Operations Research_ , 54:573–586, 2006.
  * Parragh et al. [2015] S N Parragh, J Pinho de Sousa, and B Almada-Lobo.  The dial-a-ride problem with split requests and profits.  _Transportation Science_ , 49:311–334, 2015.
  * Masmoudi et al. [2018] M A Masmoudi, M Hosny, E Demir, K N Genikomsakis, and N Cheikhrouhou.  The dial-a-ride problem with electric vehicles and battery swapping stations.  _Transportation Research Part E: Logistics and Transportation Review_ , 118:392–420, 2018.
  * Brevet et al. [2019] D Brevet, C Duhamel, and M et al. Iori.  A dial-a-ride problem using private vehicles and alternative nodes.  _Journal on Vehicle Routing Algorithms_ , 2:89–107, 2019\.
  * Masson et al. [2014] R Masson, F Lehuédé, and O Péton.  The dial-a-ride problem with transfers.  _Operations Research_ , 13:12–23, 2014.
  * Detti et al. [2017] P Detti, F Papalini, and G Zabalo Manrique de Lara.  A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare.  _OMEGA_ , 70:1–14, 2017.
  * Parragh [2012] Cordeau JF Doerner K F Hartl R F Parragh, S N.  Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints.  _OR Spectrum_ , 34:593–633, 2012.
  * Molenbruch et al. [2017] Y Molenbruch, K Braekers, A Caris, and G Vanden Berghe.  Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation.  _Computers & Operations Research_, 77:58–71, 2017.
  * Braekers et al. [2014] K Braekers, A Caris, and G K Janssens.  Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots.  _Transportation Research Part B: Methodological_ , 67:166–186, 2014.
  * Reinhardt et al. [2013] L B Reinhardt, T Clausen, and D Pisinger.  Synchronized dial-a-ride transportation of disabled passengers at airports.  _European Journal of Operational Research_ , 225:106–117, 2013.
  * Malheiros et al. [2021] I Malheiros, R Ramalho, B Passeti, T Bulhões, and A Subramanian.  A hybrid algorithm for the multi-depot heterogeneous dial-a-ride problem.  _Computers & Operations Research_, 129(105196), 2021.
  * Parragh et al. [2009] S N Parragh, K F Doerner, X Gandibleux, and R F Hartl.  A heuristic two-phase solution method for the multi-objective dial-a-ride problem.  _Networks_ , 54:227–242, 2009.
  * Lourenco et al. [2003] H R Lourenco, O C Martin, and T Stutzle.  Iterated local search.  In F Glover and G A Kochenberger, editors, _Handbook of Metaheuristics_ , volume 57, page 320–353. Springer, Boston, MA, 2003.
  * Lourenço et al. [2010] H R Lourenço, O C Martin, and T Stützle.  Iterated local search: Framework and applications.  In M Gendreau and J Y Potvin, editors, _Handbook of Metaheuristics_ , volume 146, page 363–397. Springer, Boston, MA, 2nd edition, 2010.
  * Peng B [2020] Lv Z Cheng T C E Glover F Peng B, Zhang Y.  A learning-based memetic algorithm for the multiple vehicle pickup and delivery problem with lifo loading.  _Computers & Industrial Engineering_, 142(106241), 2020\.
  * Parragh S N [2010] Hartl R F Parragh S N, Doerner K F.  Variable neighborhood search for the dial-a-ride problem.  _Computers & Operations Research_, 37:1129–1138, 2010\.
  * Chassaing [2016] Duhamel C Lacomme P Chassaing, M.  An els-based approach with dynamic probabilities management in local search for the dial-a-ride problem.  _Engineering Applications of Artificial Intelligence_ , 48:119–133, 2016.
  * Glover [1997] F Glover.  Tabu search and adaptive memory programming — advances, applications and challenges.  In R S Barr, R V Helgason, and J L Kennington, editors, _Interfaces in Computer Science and Operations Research_ , volume 7, page 1–75. Springer, Boston, MA, 1997.
  * Santos and Xavier [2015] D O Santos and E C Xavier.  Taxi and ride sharing: A dynamic dial-a-ride problem with money as an incentive.  _Expert Systems with Applications_ , 42:6728–6737, 2015\.
  * Nagata and Brysy [2009] Y Nagata and O Brysy.  A powerful route minimization heuristic for the vehicle routing problem with time windows.  _Operations Research Letters_ , 37:333–338, 2009.
  * Pisinger [2007] Ropke S Pisinger, D.  A general heuristic for vehicle routing problems.  _Computers & Operations Research_, 34:2403–2435, 2007\.