A Hybrid Heuristic Algorithm for the Dial-a-Ride Problem

Abstract

In this paper, we propose a simple heuristic algorithm based on the Variable Neighborhood Search (VNS), which combines with the Set Covering strategy in order to solve the Dial-a-Ride Problem (DARP). In this problem, customers must be served by a heterogeneous fleet of vehicles. Each customer has a pickup and a delivery location, where each one of them has time windows that must be obeyed. All vehicles have a duration time and have to start and end their routes in a single depot, and each customer has a maximum time ride. We have tested our algorithm on the benchmark instances of literature. Experiments showed that although the algorithm is simple, it can obtain the optimal solutions for some instances and achieve solutions near the optima for the others.

Supported by CAPES.

1 Introduction

Lutz et al. [14] have reported the fact of the combinations of declining fertility, and increasing life expectancies resulted in the aging of the population. They also presented a likely increase in the speed of the aging population in the next decades and continuous aging of the world’s population throughout the century. Due to this aging of the population, a lot of services need to be improved. Among them are transportation services. The problems involving the transportation can be classified as Vehicle Routing Problems (VRP). The VRP consists of determining a set of routes executed by a fleet of vehicles to satisfy the necessities of a set of users [22]. Many VRPs with different characteristics have been studied over the years, and one of them is the Dial-a-Ride Problem - DARP [4].

The DARP arises in the context of users transportation, a service for the people with reduced locomotion, or disabled people. Different from other VRPs, in the DARP, the customer’s inconvenience has to take into account. The customer’s nuisance can be defined as waiting time and travel time. The DARP consists of planning routes and schedules to meet a set of customers from a fleet of vehicles. Each customer has a pickup and a delivery location, where it must be collected and delivered, respectively. A maximum ride time has to be respected for each customer and duration time for each vehicle. A time window must be respected for every pickup and delivery point. The aim is to design a routing plan, i.e., a set of routes, capable of attending as many users as possible, under a set of constraints. Not different from other VRP variants, the DARP can be classified as static and dynamic. In the static case, all information about transportation request is known beforehand and used to calculate an a priori routing plan. In the dynamic case, the routing plan is designed in a real-time manner when a new request is revealed [6].

The DARP can be classified as the combination of two classical optimization problems: Vehicle Routing Problem with Pickup and Delivery (VRPPD) and Vehicle Routing Problem with Time Windows (VRPTW). The DARP differs from them as far as the human perspective is concerned, in DARP the comfort and convenience of users should be taken into account [6].

Besides, DARP is classified as an $\mathcal {NP}$-Hard problem due to its high complexity. Thus, optimal solutions cannot be obtained in a reasonable computational time. Therefore, DARP has been mainly addressed by heuristic and metaheuristic algorithms [6, 10].

In this paper, we propose a VNS-based algorithm to solve the DARP. Our algorithm was combined with a Set Covering Problem (SCP) formulation, which is applied throughout the VNS algorithm in order to improve its current solution. This approach has been able to find high-quality solutions in short computational time.

The remainder of this paper is organized as follows. In Sect. 2, we present a brief literary review, contextualizing and exemplifying the DARP and its variants, as well as different ways for solving them. The formal definition is shown in Sect. 3. The proposed algorithm is detailed in Sect. 4. Section 5 presents the computational experiments and results. Conclusions are given in Sect. 6.

2 Literature Review

Several DARP variants have been studied in the past few years. We can classify them into two main branches: static and dynamic versions.

In the static version, all the information about the customer requests and vehicles is known beforehand. Cordeau and Laporte [4] considered the problem with a homogeneous fleet of vehicles and single depot. To solve it, they used a Tabu Search (TS) algorithm combined with three heuristic methods. Cordeau [5] approached the DARP by an exact branch-and-cut algorithm, which was tested on a set of instances randomly generated with a maximum of 48 requests. Jorgensen et al. [12] addressed the variant of DARP with a Genetic Algorithm (GA), which considers a heterogeneous fleet of vehicles and multiple depots they made the algorithm basing on the classical cluster-first and route-second approach. Mauri et al. [17], using the data provided by the city of Vitória–ES in Brazil, approached a static variant with a heterogeneous fleet of vehicles and multiple depots. The authors used a Simulated Annealing (SA) algorithm to solve the problem. Their results show that SA produced good quality solutions for all the instances.

Parragh [19] combined other constraints to the classic DARP and proposed a branch-and-cut algorithm to solve the problem. She added real characteristics to the problem as heterogeneity to the vehicles and users. In her tests, for the instances up to 40 requests, she found the optimal solution. Again, Parragh et al. [20] proposed a hybrid column generation and large neighborhood search algorithm to solve the problem. They improved nine of the 20 instances used in their tests in 1.1%. Currently, the best-known solutions of eight of these instances are the solutions founded by Parraagh et al. [20].

Braekers et al. [3] approached the DARP using the branch-and-cut algorithm combined with a metaheuristic named determinist annealing based in the simulated annealing metaheuristic. They formulated the problem as a single depot and multi-depot for heterogeneous DARP. They tested their approach in benchmarks created by Cordeau [5], Parragh 2011 [19], and Cordeau et al. [4]. They also extended the sets of instances creating 36 larger new instances in the same way of Parragh  [19]. They match or exceed most of the best-known results found for these instances. Most of the solutions founded by the authors remain as the best-known solution for the instances. Masmoudi et al. [16] solved the same heterogeneous version of the DARP using a hybrid Genetic Algorithm. They used a constructive heuristic and efficient crossovers to guided the algorithm. They tested their approach in the instances of [5, 19], and [3]. The results demonstrate the algorithm is efficient in terms of best and average solution quality.

In the dynamic version of DARP, new customer requests are added during the route. Madsen et al. [15] solve the DARP adapting an insertion algorithm called REBUS originally developed by Jaw et al. [11]. The version of the problem solved used the multiple capacities and multiple objectives. Using data given by Copenhagen Fire-Fighting Service, they tested their approach on real-life cases. In a flexible way, the algorithm permits a weighing of multiple goals such that the solution reflects the customer’s preferences. Attanasio et al. [1] approached the dynamic DARP with the objective to accept as many requests as possible while satisfying the constraints of the problem. To solve the problem, they used a parallel strategy of a Tabu Search heuristic previously used by Cordeau and Laporte [4] in the static case of the problem.

In Germany, Beaudry et al. [2] proposed a two-phase heuristic to solve a dynamic DARP. The first phase is a simple insertion scheme, and the second phase is a Tabu Search algorithm that considers infeasible solutions during the search process. The problem was structured with data given by several large hospitals. They proposed additional constraints on the standard problem. For example, a different degree of urgency in the requests, the patient of the request cannot share the vehicle with another patient, among others. Experiments provided high-quality solutions, and the algorithm show capable of handling the dynamic aspect of the problem. Schilde et al. [21] proposed a dynamic DARP to solve the problem of the organization performing patient transportation in Austria. They approached the dynamic case of the DARP with a homogeneous fleet of vehicles and a single depot. To solve the problem, the authors proposed four different metaheuristics, a Variable Neighborhood Search (VNS), a Stochastic Variable Neighborhood Search (S-VNS), both dynamics, a Multiple Plan Approach (MPA), and a Multiple Scenario Approach (MSA). They tested their algorithms on a set of 12 instances based on a real road network. Results show that dynamic S-VNS strongly outperforms the others. Again in Germany, Hanne et al. [8] solve a dynamic DARP with hospital-specific constraints. They designed a computer-based planning system, Opti-TRANS, to support several concerns related to patient transport. They illustrated the system work in the daily performance of a large German hospital, and the system presents many benefits, including streamlined transportation processes and workflow.

Thus, the large number of DARP variants, here, we study the Heterogeneous DARP with single depot proposed by Parragh et al [20]. The heterogeneity is considered in the user and vehicles [20].

3 Formal Definition

The DARP can be defined as follows. Let $G = (V, E)$ be a complete graph, where V is the set of vertices and E the set of arcs. The set of vertice V is partitioned into $\{\{0, 2n + 1\}, P, D\}$, where 0 and $2n + 1$ are two copies of the depot, $P = \{1,...,n\}$ is the set of pickup vertices and $D = \{n + 1,..., 2n\}$ is the set of delivery vertices. For each arc $\left( i,j\right) \in E$ is associated a routing cost $c_{ij}$ and a travel time $t_{ij}$.

Each customer request i consists of a pickup and delivery vertex pair $\{i, n+i\}$, where $i \in P$ and $n+i \in D$. The maximum travel time of each customer cannot exceed L. To each vertex $i \in V$ is associated a load $q_i$, with $q_{0} = q_{2n+1} = 0$, $q_{i} \ge 0\;\forall i \in P$ and $q_{i} = -q_{i+n}\;\forall i \in D$, and a non-negative service time $\tau _{i}$. Moreover, each $i \in V$ has a time window $\left[ e_i, l_i\right]$, where $e_i$ and $l_i$ are integers non-negative.

The set of vehicles is represented by K. Each vehicle $k \in K$ starts and ends its route in the depot. The capacity of vehicle k is $Q_{k}$ and the maximal duration of route k is denoted by $T_k$.

Given the vertex $v_i$ we denoted by $A_i$ the arrival time of the vehicle in the vertex; and $B_i$ the beginning of the service, where $B_i \ge \max \{A_i, e_i\}$, cannot start before $e_i$. The departure time $D_i = B_i + \tau _i$ is the time the vehicle leaves the vertex. The vehicle waiting time is defined by $W_i = B_i - A_i$. The ride time of the client is determined by $L_i = B_{n+i} - D_i$ and the total duration of the route is calculated as $B^k_{n+1} - B^k_0$, where $B^k_{n+1}$ and $B^k_0$ represents the beginning of service on the depot by vehicle k, when it finishes and starts the ride, respectively.

The objective of the DARP is to find a set of routes that serve all customers such that minimizes the total routing cost.

4 Heuristic Approach

To solve the problem we based our heuristic on a VNS and a set covering procedure. Sections 4.1–4.4 define the heuristic components, while Sect. 4.5 presents the set covering model.

4.1 Solution Representation

We represent a DARP solution through a matrix of |K| rows, where each row informs the route assigned to a vehicle (the k-th row refers to the route of the k-th vehicle). Each route begins and ends at the depot. The pickup and delivery customers are inserted in the route, satisfying the problem constraints.

Figure 1 shows a solution representation for an instance with five vehicles ($A, B, \cdots , E$) and 13 customer requests. The numbers with positive sign $(1+~\cdots ~13+)$ represent the pickup locations and the ones with negative sign $(1-~\cdots ~13-)$ are the delivery points. The depot is represented by node 0.

Fig. 1.

Example of a solution representation.

4.2 Solution Evaluation

The solution evaluation was done based on an approach used by Cordeau and Laporte [4] and Parragh et al. [18]. Following them, we penalized the violations of load q(s), duration d(s), time windows tw, and user ride time t(s). The load and duration are computed and penalized in the route, based on the constraints $Q_k$ and $T_k$. The time windows penalization is computed as

$$\begin{aligned} \displaystyle tw = \sum _{i=0}^{2n} (B_i - l_i)^{+} \end{aligned}$$

where $x^{+} = \max {\{x, 0\}}$. In turn, the ride time is calculated as

$$\begin{aligned} \displaystyle t = \sum _{i=1}^{n} (L_i - L)^{+} \end{aligned}$$

Thus, the solution evaluation was calculated as follows:

$$\begin{aligned} f(s) = c(s) + \alpha tw(s) + \beta t(s) + \delta d(s) + \gamma q(s) \end{aligned}$$

The penalization variables for load ($\gamma$), duration ($\delta$), time window ($\alpha$), and ride time ($\beta$) violations were set to $\alpha = \beta = \delta = \gamma = 1$.

4.3 Neighborhood Structures

To explore the solution space of the DARP, six neighborhoods was implemented. These neighborhoods consist in the relocation of requests among the solution routes. For all neighborhoods, two routes, $r_1$ (blue line) and $r_2$ (black line) are randomly selected.

• Relocation – A request (pickup and delivery points) are removed from $r_1$ and inserted in $r_2$. Figure 2 shows the relocation of request ($1^+, 1^-$) from $r_1$ to $r_2$.

• Swap – Two requests are selected, one from $r_1$ and another and $r_2$, and exchanged them. Figure 3 shows the exchange of one request ($6^+, 6^-$) in route $r_1$ with other request ($4^+, 4^-$) in route $r_2$.

• Crossover – Two points are selected, one in $r_1$ and other in $r_2$. All pickup customers before the selected point in $r_1$ (and their respective deliveries) are connected to all pickup customers (and their respective deliveries) that come after the selected point in $r_2$. The same way to the customers before $r_2$ point and after the $r_1$ point. Figure 4 shows the crossover of routes, the red line shows the selected points for each route and the relocation of requests.

• Swap(2) – Four requests are selected, two adjacent requests from $r_1$ and two adjacent requests in $r_2$, and they are exchanged. All the four possible combination orders of exchanging the request arcs are considered. Figure 5 shows the exchange of two requests ($6^+, 6^-$) and ($8^+, 8^-$) in route $r_1$ with two requests ($4^+, 4^-$) and ($3^+, 3^-$) in route $r_2$.

• Swap(2-1) – Three requests are selected, two adjacent requests from $r_1$ and one in $r_2$, and they are exchanged. The move examines the two possible visiting orders of transferring the $r_1$ requests. Figure 6 illustrates the exchange of two requests ($6^+, 6^-$) and ($8^+, 8^-$) in route $r_1$ with the request ($4^+, 4^-$) in route $r_2$.

• Relocation(2) – Two adjacent requests are removed from $r_1$ and inserted in $r_2$. Figure 7 shows the relocation of requests ($6^+, 6^-$) and ($8^+, 8^-$) from $r_1$ to $r_2$.

Fig. 2.

Relocation. (Color figure online)

Fig. 3.

Swap. (Color figure online)

Fig. 4.

Crossover. (Color figure online)

Fig. 5.

Swap2. (Color figure online)

Fig. 6.

Swap2. (Color figure online)

Fig. 7.

Relocation. (Color figure online)

4.4 Variable Neighborhood Search

To tackle the DARP, a VNS-based algorithm [9] was proposed. For its use, three components have to be specified:

• Generate initial solution Procedure: A function that greedily selects each request taking into account the time window allocating to each chosen car with the shortest time traveled.

• Local Search Procedure: The method used as local search was the Randomized Variable Neighborhood Descent (RVND), that has its behavior like a classic Variable Neighborhood Descent, but the neighborhoods are randomly selected.

• Shaking Procedure: Let $\varOmega$ be a set of neighborhood structures. The shaking procedure consists of selecting a random neighborhood belonging to $\varOmega$ and then choosing a random neighbor of the current solution in this neighborhood.

All steps of our VNS algorithm applied to solve the DARP are presented in Algorithm 1. The algorithm receives as parameters an initial solution $s_0$ and the maximum number of iterations (iterMax). In the line 4 is applied a shaking in the current solution. The local search is applied in line 5, where all different feasible routes are stored in a set R. This set is used in the set covering model. When the number of iterations exceeds half of iterMax, the set covering procedure is applied (line 13).

4.5 Set Covering

Let R be a set of different feasible routes found by VNS algorithm, V the set of customers and |K| the maximum number of vehicles available. A cover of V is a combination J of routes $j \in R$, where each customer $i \in V$ is covered by at least one route $j \in R$. Let $c_j$ be the cost of each route j and the binary constant $\rho _{ij}$ that informs if customer i is served by route j. The Set Covering problem (SCP) consists in finding a set $J \subseteq R$ such that the total cost is minimized.

In order to present the mathematical model for the SCP, let $y_j$ be a binary variable associated with a route $j \in J$. Follow the model used in our algorithm.

$$\begin{aligned} \min {\sum _{j \in R} c_j y_j} \end{aligned}$$

Subject to:

$$\begin{aligned}&\sum _{j \in R} \rho _{ij}y_j \ge 1,&\forall i \in V \end{aligned}$$

(1)

$$\begin{aligned}&\sum _{j \in R} y_j \le |K|,\end{aligned}$$

(2)

$$\begin{aligned}&y_j \in \{0,1\} \end{aligned}$$

(3)

5 Computational Experiments

The developed heuristic was coded in C/C++ using the mathematical solver Gurobi 8.0.0, with all its default settings. All experiments were performed on an Intel Core i7-7700K processor with 3.60 GHz and 16 GB RAM running Ubuntu 16.04 LTS 64 bits.

5.1 Instances Description

In order to validate our approaches, the computational experiments were performed using three groups of instances (E, I, U) proposed by Parragh [19]. These instances have heterogeneity based on data given by the Austrian Red Cross. The instances were randomly generated in the square $[-10,10]^2$ using the uniform distribution. The depot was located in the center of the plan. Each edge $\left( v_i, v_j\right) \in A$ has the cost $c_{ij}$ and travel time $t_{ij}$ were calculated using Euclidean distance. Each vertex i was defined a time window $[e_i, l_i]$. The pickup vertices $e_i$ were established in a range of $[0, T-60]$, where T is the time of planning horizon and $l_i$ was set as $e_i + 15$. The delivery vertices $l_i$ were defined in the interval [60, T] and $e_i$ was set as $l_i - 15$. Each instance is represented by the name ak-n, where k is the number of vehicles used and n is the total number of requests.

In group E of instances, half of the patients are normal ones, 25% are wheelchair ones and 25% stretcher ones. 10% of the patients have one companion. The fleet of vehicles for this group is homogeneous with vehicles of type V1. Each vehicle V1 has two places to companions, one for a wheelchair patient, one for the stretcher patient and one for a normal patient. In group I of instances, 83% of requests are from normal patients, 11% are wheelchair ones, and 6% are stretcher ones. Half of the patients have one companion. The fleet of vehicles is heterogeneous with vehicles of types V1 and V2. Each vehicle V2 has one place to companions, one for a wheelchair patient, one for stretcher patient and six for the normal patients. In group U of instances, are just considered the normal patients and there are no companions. The fleet of vehicles is homogeneous with vehicles of type V3. Each vehicle V3 just has places for normal patients. Table 2 shows the heterogeneity of patients and vehicles by instance groups (Table 1).

Table 1. Patients occupation

Table 2. Instances information

5.2 Experimental Results

For each instance, the algorithm was executed 10 times using as stop criteria $iterMax = 100$, which represents the maximum number of the iterations without improving the best solution found. For running the set covering problem was used half of the iterMax iterations. The parameters used in the algorithm were calibrated using the IRACE package [13]. Table 3 shows the tested configurations for the parameters. The best configurations returned by IRACE are boldfaced. The neighborhoods are represented as follow and the selected neighborhoods are presented in Sect. 4.3:

• 1 - Relocation - Relocation of one request of one vehicle to another.

• 2 - Swap - Exchange of one request of one vehicle to another.

• 3 - Crossover - Crossover between two vehicles.

• 4 - Swap(2) - Exchange of two requests of one vehicle to another.

• 5 - Swap(2-1) - Exchange of two requests of one vehicle with one request from another.

• 6 - Relocation(2) - Relocation of two requests of one vehicle to another.

Table 3. IRACE Calibration

Table 4. Results for instances U, E and I

Table 4 presents the results on the instances group U, E and I. In group U, the customers and vehicle fleet were considered as homogeneous. In group E the customers were considered heterogeneous and the vehicle fleet was homogeneous. In the group I the customers and vehicle fleet are heterogeneous. In this table, the column Instance represents the name for each instance, this name is composed by the number of vehicles used and the number of requests. The columns Parragh [19] and Braekers et al. [3] show the results obtained by these authors in their experiments. The column Best VNS presents the best solution found by our algorithm and the column AVG VNS shows the average values in 10 executions of the VNS algorithm. For each column of the table, sol reports the objective function value, gap the difference between the solution value found and the best-known solution (BKS) value, while the column time shows the time spend by the algorithm in seconds. The times in this work are from different computers, the computer used by Parragh [19] was an Intel Pentium D with 3.20 GHz and 4 GB RAM and the computer used by Braekers et al. [3] was an Intel Core with 2.6 GHz and 4 GB RAM, and the computer used in this work is an Intel Core I7-7700 CPU @ 3.60 GHz with 16 GB RAM. Some methods have been developed for a fair comparison, methods that measure the performance of computers in general, and can be found in work of Dongarra [7].

According to Table 4, we can see that our algorithm was able to find the BKS solution for 10 of 36 instances, where they are four in group U and E and two in group I. The VNS found solutions with gap up to 1% for 12 of 36 cases, where they are four in group U, five in group E and three in group I. In the last 14 cases our algorithm obtained solutions with gap up to 2.95%.

Regarding computation time, our algorithm on average is faster in 26 out of 32 instances compared to Parragh [19] and find the better solution just for one case (a4−40 of group U). Compared to Braekers et al. [3], the VNS algorithm on average is faster just for half of 32 instances.

6 Conclusions

In this paper, we propose a simple heuristic algorithm based on the Variable Neighborhood Search for the Dial-a-Ride Problem. This problem is a variation of the Vehicle Routing Problem, where the customer’s convenience is taken into account. We considered a heterogeneous demand for customers and vehicles. Our algorithm was tested in the instances described in the literature. In three groups with a total of 36 instances. The VNS algorithm showed able to find 10 of 36 best-known solutions, and for 12 of 36 solutions, we find a solution with a gap less than 1%. For the other 14 instances, in the worst case, we find a solution with a gap of 2.95%.