# Models and algorithms for reliability-oriented Dial-a-Ride with autonomous electric vehicles

Victor Pimenta, Alain Quilliot, Hélène Toussaint, Daniele Vigo

► To cite this version:

Victor Pimenta, Alain Quilliot, Hélène Toussaint, Daniele Vigo. Models and algorithms for reliability-oriented Dial-a-Ride with autonomous electric vehicles. European Journal of Operational Research, 2017, 257 (2), pp.601 - 613. 10.1016/j.ejor.2016.07.037. hal-01708139

HAL Id: hal-01708139

https://hal.science/hal-01708139v1

Submitted on 8 Jan 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Models and Algorithms for Reliability-Oriented Dial-a-Ride with Autonomous Electric Vehicles

Victor PIMENTA¹, Alain QUILLIOT¹, Hélène TOUSSAINT¹

Daniele VIGO²*

¹LIMOS CNRS 6158, Labex IMOBS3, Blaise Pascal University, 63000 Clermont-Ferrand, France

²DEI “Guglielmo Marconi” – University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy

**Abstract** — We consider a static decision model related to the management of a Dial-a-Ride (DAR) system involving small autonomous electrical vehicles in a closed industrial site. Because of the specific features of the system, in this paper we concentrate on its reliability and propose a model that aims at assigning requests to vehicles by minimizing the number of loading/unloading operations. We propose an integer linear programming formulation of such Stop Number Minimization Problem and examine the behavior of some of its variants. Next, we consider and analyze a set covering oriented reformulation of the model. Finally, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) based heuristic approach that implements insertion mechanisms and is well fitted to realistic dynamic contexts. All proposed methods are tested on benchmark instances involving some tens of requests.

**Keywords:** Dial-a-Ride Problem, ILP models, Resource Constrained Scheduling

## 1. INTRODUCTION

The current trends in mobility management involve the use of flexible reactive systems, which meet mobility demands in a dynamic way by implementing some vehicle-sharing and by interacting with alternative transportation modes. Such systems strive to find their room between fully individual mobility and traditional collective transportation systems. They also aim at bridging the gap between goods and people mobility, and require the use of advanced technologies (see [16]) such as Internet, web services, mobile communications, and remote tracking and monitoring. Depending on the context, they may work either as *closed systems*, whose access is restricted to users who accept rules related to mobility tracking, pricing and responsibility, or *open systems*, which work on the basis of a free access/free market principle. Among such systems one may mention *Dial-a-Ride*, *Car-Sharing*, *Car-Pooling* (e.g., AUTOLIB), and *Ride Sharing* systems (see, e.g., [1], [2], and [3]).

Recent advances in artificial perception and remote control make now possible new generations of autonomous (i.e., without any driver) individual or collective electrical vehicles, such as Cycab and VIPA (the *Individual Autonomous Vehicles* of Ligier S.A., see http://www.ligier.fr/ligier-vipa and
Figure 1), which lead to the design of new mobility services. In the case of VIPA electric cars, experiments are currently undertaken in Clermont-Ferrand, France to assist internal mobility of both people and objects (internal mail, small packages...) inside the industrial site of Michelin. Other

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

applications are considered for the future, involving hospitals and some pedestrian downtown areas.

<caption>**Figure 1.** An image of a VIPA car from Ligier S.A.</caption>

Such an experimental service works as a specific *Dial-a-Ride* (DAR) system (see [2], [5], [6], and [7]). Users call from smartphones or from *ad-hoc* communication devices and wait for the vehicles that serve them. But, since related movements are performed inside a closed and restricted area (smaller than a few square kilometers), users' demands must be handled in a very reactive way. In addition, since autonomous vehicles are involved there are very few routing options and vehicles move along predetermined routes with fixed lengths. Thus, routing as well as minimizing individual and total travel times are not a key issue in this system. Instead, what matters is system *reliability*, that concerns the steady flow of the vehicles traffic and which can be improved through a lean scheduling. In other words, scheduling has to smooth as much as possible the trajectories of the vehicles and has to minimize sequences that require complex interactions between the vehicles.

The model that we consider here is typical of this new kind of problems, and may be viewed as an extension of interval graph coloring models (see, e.g., [13]). As previously mentioned, our problem derives from a case study about the management of a specific DAR system, which involves VIPA autonomous vehicles working in real-time as *"horizontal elevators"*, moving people or goods in a district or an industrial site. A set of autonomous vehicles travel between several stations located along a circuit serving requests, each having a specific origin and destination station: the main constraints of the problem are those of a classical DAR problem. However, our main focus is on travel time reliability, which is mainly correlated with the number of *stops* performed during the service. Hence, we aim at serving the requests in such a way that the vehicles minimize the number of stops they perform, thus enabling them to stay as much as possible on the main track without deviating to the *loading/unloading* areas. In practical settings, such decision problem has to be solved *on line* and the performance of the solution methods, inevitably of a heuristic nature, has to be evaluated through discrete-event simulation. However, both to better understand the structure of the problem and to get benchmarks for heuristic solutions we study here a static (*off-line*) version of the problem.
The paper is organized as follows. In Section 2, we define the *Stop Number Minimization Problem* (SNMP) in a formal way and introduce an integer linear programming (ILP) formulation. We also discuss variants and extensions of the SNMP, and propose a *set covering* reformulation that avoids considering the number of vehicles as a parameter of the model. Next, in Section 3 we discuss some theoretical properties of our model and perform an experimental analysis of the behavior of its different ILP formulations. Finally, in Section 4, we propose and test a greedy randomized adaptive search procedure (GRASP) heuristic based on an insertion mechanism, which is well-fitted to *on-line* contexts. Finally in Section 5 we draw some conclusions and outline possible future research directions.

## 2. PROBLEM DEFINITION AND MODELING.

In our problem we consider a set of autonomous VIPA vehicles traveling along a closed network that has the shape of a circuit $\Gamma$ with $n$ nodes, while serving a set of DAR demands. In practical settings also other network topologies can be considered, such as tree or star ones, but in all such cases the common feature is that there is only one elementary path connecting each origin $o$ to a destination $d$ of a transportation *request*. As a consequence, routing decisions are not part of our problem The nodes of the circuit $\Gamma$ are denoted by 0, ..., $n-1$, where node 0 represents the *Depot*, that is the base of the vehicles. The remaining nodes correspond to parking slots that may be either the origin or the destination of a request. The vehicles travel the circuit always in the same direction. Hence, when a request calls for the transportation of a load from an origin $o$ to a destination $d$, the trajectory of the vehicle is {$o, (o+1) \ Mod \ n, (o+2) \ Mod \ n, ..., d$}, where Mod is the modulo division operator. Circuit $\Gamma$ is made up of a *common track* and of *loading/unloading areas*, associated with nodes {0, ..., $n-1$} as illustrated by Figure 2. Note that in our application vehicles have a lateral loading and unloading access. Hence, the circuit has to be traveled counterclockwise to allow loading and unloading be performed at the stops through platforms that are located outside the circuit itself.

<figure><img src="image_3.png" /><figcaption>Figure 2. An illustration of the VIPA circuit</figcaption></figure>

The speed of the vehicles on the common track is considered constant, and in our application it is equal to about 15 km/h. Overtaking is forbidden on the main track and when a vehicle leaves a *loading/unloading* area it has no precedence on the vehicles which travel on the main track. The time required by a vehicle to move between two stops clearly takes into account the decelerations and accelerations required before and after the stop. The time a vehicle spends in a *loading/unloading* area is a random variable, increasing in a weak (sub-linear) way with the number of *loading/unloading* operations that are performed on this area.
Traveling along the whole circuit without stopping only takes a few minutes. Therefore, a vehicle is allowed to travel several times along $\Gamma$ (i.e., performing so-called *waiting laps*) before actually serving an user. However, the load of a request may not stay on the vehicle for a full tour, i.e., once loaded it has to be unloaded as soon as the vehicle reaches its destination. A solution is therefore defined by assigning to each request $j$ the vehicle that serves it and the number $h$ of waiting laps, i.e., the number of times the vehicle is going to travel the whole circuit $\Gamma$ before it starts the service of that request.

We are given a fixed number $K$ of identical vehicles, all located initially (i.e., at time 0) at the *Depot* node. All the vehicles have the same capacity $Q$, which represents either a maximum weight or a number of passengers that can be transported. We denote by $H$ the largest number of *waiting laps* for the vehicles, which is the maximum number of tours a vehicle is allowed to perform before starting the service of a request. Note that because the numbers of vehicles and of waiting laps are fixed it may happen that some request remains not serviced (i.e., is rejected). However, as our main focus is on travel time reliability we avoid considering the management of rejected requests. As a consequence, we assume that the vehicle number $K$ is large enough to enable the system to meet all requests while respecting the maximum waiting lap restriction.

We adopt a *static* point of view, where all the user requests are known in advance (i.e., at time 0). A *request* (or *demand*) $j$ is defined by a triple $(o(j), d(j), L(j))$ including an *origin node* $o(j)$ and a *destination node* $d(j)$, both in the set $\{0, ..., n-1\}$, together with a *load* $L(j)$. This defines the SNMP (*Stop Number Minimization Problem*) problem. In case all loads $L(j), j = 1, ..., m$, are equal to 1, the problem is called *Unit SNMP*. Furthermore, we suppose here that users ask for the system only when they are ready to move, therefore a request does not involve any kind of temporal requirement such as time windows.

Since we forbid that the load of a request stays on board of a vehicle during a full tour, we make here the assumption that individual *travel times* of the requests are always constant and need not be optimized as is, instead, done in classical DAR problems. We note here that the number of times a vehicle stops while moving from origin $o(j)$ to destination $d(j)$ to serve other requests has clearly an impact on the duration of the individual *travel time* of $j$. We will address this issue later, in Section 2.2 where we discuss SNMP variants and *Quality of Service*. However, we also note that, because of the accelerations and decelerations required to stop at a loading/unloading area, minimizing the number of stops will also help minimizing the *global travel time* of the fleet.

## 2.1 An ILP formulation of the Stop Number Minimization Problem

To simplify the model description let us unfold the circuit $\Gamma$ into a linear ordered set $I(\Gamma) = \{0, ..., (H+2) \cdot n\}$ of nodes, each representing the visit of a node of the circuit during one of the $H$ waiting laps, as depicted in Figure 3. The set $I(\Gamma) = \{0, ..., (H+2) \cdot n\}$, where both 0 and $(H+2) \cdot n$ correspond to the depot, is called the *Stop Node Set*. Let us also define $p = (H+2) \cdot n - 1$ as the index of the last stop in $I(\Gamma)$.

<figure><img src="image_4.png" /><figcaption>**Figure 3.** The Stop Node Set obtained by unfolding a circuit with two waiting laps.</figcaption></figure>
Let D be the set of all requests $j = (o(j), d(j), L(j))$, $j = 1, ..., m$, where if $d(j) < o(j)$, we replace the destination with $d(j) + n$. In this way, we may associate with each request $j = 1, ..., m$, a collection of $H+1$ discrete intervals $I_{j,h} = \{o(j) + h \cdot n, ..., d(j) + h \cdot n\}, h = 0, ..., H$, of the Stop Node Set, where the service of the request must take place. Without loss of generality, we suppose that each node $i = 1, ..., n-1$ is active for our problem, i.e., that there exists at least one index value $j$ such that either $i = o(j)$ or $i = d(j)$. If this is not the case, we may remove all non-active nodes from the set $\{1, ..., n-1\}$, reduce $n$ and renumber the active nodes accordingly.

Furthermore, for each node $i$ in the set $I(\Gamma)$, $i \neq (H+2) \cdot n$, we define the following two sets:

- $Cross(i) = \{(j,h), j = 1, ..., m, h = 0, ..., H, (j,h) \in Cross(i)\}$ means that a vehicle leaving node $i$ must carry the load $L(j)$ of request $j$ served with waiting lap equal to $h$;

- $Stop(i) = \{(j,h), j = 1, ..., m, h = 0, ..., H, (j,h) \in Stop(i)\}$ means that the origin or the destination node of request $j$ served with time lap $h$.

Then, we get the following ILP model for SNMP, where the number $K$ of available vehicles is fixed to a suitably large number. The model uses the following binary decision variables. Variable $Z_{j,k,h}$ takes value 1 if vehicle $k = 1, ..., K$ serves request $j = 1, ..., m$ with waiting lap $h = 0, ..., H$, and 0 otherwise. Variable $T_{k,i}$ takes value 1 if $i = 1, ..., p$ is a stop node for vehicle $k = 1, ..., K$, and 0 otherwise. The model is then:

$$ \text{SNMP}(K) \quad \min \sum_{k=1}^{K} \sum_{i=0}^{p} T_{ki} \qquad (1) $$

subject to:

$$ \sum_{k=1}^{K} \sum_{h=1}^{H} Z_{jkh} = 1, \qquad \forall j = 1, ..., m \qquad (2) $$

$$ \sum_{(j,h) \in Cross(i)} L(j) \cdot Z_{jkh} \le Q, \qquad \forall k = 1, ..., K; \forall i = 0, ..., p \qquad (3) $$

$$ Z_{jkh} \le T_{ki}, \qquad \forall k = 1, ..., K; \forall i = 0, ..., p; \forall (j, h) \in Stop(i) \qquad (4) $$

$$ Z_{jkh} \in \{0,1\}, \qquad \forall j = 1, ..., m; \forall k = 1, ..., K; \forall h = 0, ..., H; \qquad (5) $$

$$ T_{ki} \in \{0,1\}, \qquad \forall k = 1, ..., K; \forall i = 0, ..., p; \qquad (6) $$

where the objective function (1) minimizes the number of stops, constraints (2) impose that each request is assigned exactly once. Constraints (3) are the capacity constraints and (4) are the coupling constraints for the decision variables. Finally constraints (5) and (6) define the decision variables. Note that the optimal solution of SNMP(K) uses at most K vehicles, i.e., if convenient it may leave some vehicle unused. Further discussion on the available number of vehicles will be provided in the following sections.
## 2.2 Extensions and Variants of the SNMP

The problem we defined in the previous section can be easily extended and modified to consider further characteristics of real-world problems. In the following we present some of such variants.

First of all, the SNMP model can be easily extended to consider time windows for the service. These are modeled by imposing lower and upper bounds $Min(j)$, $Max(j)$, $j = 1, ..., m$ on the values of the waiting laps associated with each request. Hence, service time window is imposed by adding to SNMP the following set of constraints:

$$Z_{jkh} = 0 \qquad \forall h \in \{Min(j),..., Max(j)\}; \forall k = 1,..., K. \qquad (7)$$

Let us now denote by Load-Vehicle(K), LV(K) for short, the feasibility problem which derives from restricting the SNMP with K vehicles to only consider decision variables Z. The resulting problem has no objective function and includes the constraints (2), (3), (5) and (6) of SNMP above. Then by computing the smallest value K = $K_{min}$ such that LV(K) has a feasible solution, we model the variant in which the objective is that of minimizing the number of used vehicles.

Another variant of SNMP, called Global Travel Time Minimization Problem (GTTMP), calls for the minimization of the total number of tours performed by the K vehicles to serve all the requests. To this end, let us define a continuous decision variable $r_k$, $k=1, ..., K$, which is defined as the largest value of waiting laps associated with a request served by vehicle k. Thus, $r_k + 1$ is equal to the total number of complete circuits traveled by vehicle k. Given the value K, the model of GTTMP is

$$\text{GTTMP} \qquad \min \sum_{k=1}^{K} r_k \qquad (8)$$

subject to:

$$\sum_{k=1}^{K} \sum_{h=1}^{H} Z_{jkh} = 1, \qquad \forall j = 1, ..., m \qquad (9)$$

$$\sum_{(j,h) \in \text{Cross}(i)} L(j) \cdot Z_{jkh} \le Q, \qquad \forall k = 1, ..., K; \forall i = 0, ..., p \qquad (10)$$

$$h \cdot Z_{jkh} \le r_k \qquad \forall k = 1, ..., K; \forall j = 1, ..., m; \forall h = 1, ..., H; \qquad (11)$$

$$Z_{jkh} \in \{0,1\}, \qquad \forall j = 1, ..., m; \forall k = 1, ..., K; \forall h = 0, ..., H; \qquad (12)$$

$$r_k \ge 0, \qquad \forall k = 1, ..., K; \qquad (13)$$

where the objective function (8) minimizes the total number of circuits. Constraints (9) impose that each request is assigned exactly once. Constraints (10) are the capacity constraints and (11) are the coupling constraints for the variables. Finally, constraints (12) and (13) define the decision variables.

### 2.2.1 Quality of Service

Both SNMP and GTTMP reflect the common viewpoint of the fleet managers in the VIPA context, i.e., in the context of vehicles performing services inside an industrial area, where managers pursue a specific industrial purpose and are seeking to minimize the total service time for all requests. Clearly such solutions may be sub-optimal if we consider the viewpoint of users for which the number of stops
performed between origin and destinations has certainly an impact on users' individual travel time. A first possibility of considering individual travel times consists in setting the individual waiting time of user j to the value h(j) of the waiting lap associated with j. Then SNMP can be easily extended by including into the objective function the sum of h(j) for j=1, ..., n. In such a case, the experiments we conducted with this extended objective function show that minimizing the Stop Number and minimizing the Waiting Lap Number are not convergent criteria. Indeed, minimizing the Waiting Lap Number tends to use as many vehicles as possible, while instead, minimizing the Stop Number tends to let a given vehicle perform as many laps as possible. In addition, a more precise modeling of individual travel times should explicitly take into account the number of stops performed between origin and destination of the request. It is, however, clear that the corresponding model would be more complex and its consideration goes beyond the scope of the present paper. In the analysis of computational tests performed in Section 3.2 we will briefly discuss the distribution of stops between origin and destinations of requests.

## 2.3 A Set Covering Reformulation of SNMP

As it also happens for the graph coloring problem (see, e.g., [8], [13], and [16]) the linear relaxation of model (1)-(6) can be weak, particularly when the number of available vehicles is large with respect to $K_{min}$. This behavior is confirmed in our computational testing, discussed in Section 3.3, which shows that by using such formulation it is possible to solve only small-size instances. Therefore, following what is done for similar problems, such as graph coloring (see, e.g., [8]), we introduce a different model based on a set-covering reformulation of SNMP. To this end, let us define the notion of feasible service as a pair $s = (J, h)$, where J is a subset of requests, and $h(\cdot)$ a function from $J$ to $\{0, ..., H\}$, that associates a waiting lap to each $j \in J$ and such that

$$ \sum_{j \in J: (j, h(j)) \in \text{Cross}(i)} L(j) \le Q, \quad \forall i = 0, ..., p. \qquad (14) $$

Clearly, a feasible service identifies a set J of requests which can be served by a vehicle together with, for each such request $j \in J$, its related waiting lap $h(j)$. According to this, we use the notation $j \in s$ to say that request j is served by service s.

We denote by $S$ the set of all feasible services, and for each $s \in S$ we define $N_s$ as the number of stops performed by the vehicle executing $s$. The set-covering reformulation of SNMP, called SC-SNMP uses binary decision variables $X_s$, which take value 1 if the feasible service $s$ is selected and executed by a vehicle.

$$ \text{SC-SNMP} \quad \min \sum_{s} N_{s} \cdot X_{s} \qquad (15) $$

subject to:

$$ \sum_{s | j \in s} X_s = 1, \quad \forall j = 1, ..., m \qquad (16) $$

$$ X_s \in \{0,1\}, \quad \forall s \in S \qquad (17) $$

where the objective function (15) minimizes the number of stops. Constraints (16) impose that each request is assigned exactly once and constraints (17) define the decision variables.
We notice that this Set Covering oriented reformulation does not involve the parameter K. Also, it is
very generic because variants, such as GTTMP, may be cast into the same framework in a very natural
way.

3. PRELIMINARY THEORETICAL AND EXPERIMENTAL ANALYSIS

In this section we analyze in detail the SNMP and provide some insights with respect to its complexity
and the possibility of solving it to optimality by analyzing the results we obtained on benchmark
instances. The heuristic solution of SNMP, which is more appropriate in the on-line contexts, will be
addressed in Section 4. We also compare experimentally with SNMP some of the variants that were
introduced in the previous section.

**3.1 Discussion on Problem Complexity**

The problem we introduced in the previous section has clear relations with other important families of
optimization problems, such as the interval graph coloring. It is, therefore, important to address the
worst-case computational complexity of the problem. To this end, we recall that an instance of the 2-
Partition Problem (2PP) is defined by a collection $a_1, \dots, a_m$ of positive integer numbers, such that $S =$
$\Sigma_{i=1}^m a_i$ is even, and that solving it means computing a subset $A$ of $\{1, \dots, m\}$ such that $\Sigma_{i \in A} a_i =$
$S/2$. Such a problem is known to be NP-Hard according to [12]. We then introduce the following:

**Theorem 1:** In the case where $H = 0$, and no hypothesis is done about the capacity $Q$ and the loads $L(j)$, $j = 1, \dots, m$, the SNMP is NP-Hard.

**Proof:** Let us check that the 2PP problem may be viewed as a specific case of our *Stop Minimization* problem. To this end, we consider a collection of requests $j = 1, \dots, m$ such that:

* $o(j) = 1$ and $d(j) = n-1$ for each $j = 1, \dots, m$;

* $Q = \frac{1}{2} \sum_{j=1}^{m} L(j)$.

In such a case, the optimal value of the related instance of *Stop Minimization* is equal to 4 if and only if the instance of the 2PP which is defined by *Q* and the loads *L*(*j*) has a solution. ☐

In the remaining part of this section, we are going to perform a brief analysis of different restrictions
of SNMP, to better understand which features make the problem difficult, and which ones make it
close to be polynomial in time. The complexity proof above mainly relies on an argument involving
the loads of the requests. So, from the complexity point of view, an interesting special case of SNMP
is clearly that with unit load request, i.e., with $L(j)=1, j = 1, \dots, m$, and denoted as Unit SNMP
(USNMP), Unfortunately, we were not able to derive a tight bound on the complexity of such variant,
but we have the following:

**Conjecture:** USNMP is NP-Hard, even when $H=0$.

However, some remarks may be raised showing that, in the case with $H=0$, the USNMP is close to
being polynomial in time. First of all, we may notice that, if $H=0$, then the constraint matrix associated
with the LV(K) feasibility model (see Section 2.2) is totally unimodular: this may be obtained, through
a straightforward calculus about determinants, as a consequence of the fact that, for every $k = 1, \dots, K$,
the matrices $M_k$ defined by the capacity constraints are all interval matrices and are all equal. As a consequence, if $Q=1$, we see that the feasible solutions of our problem are exactly the feasible solutions of the vertex coloring problem defined by the color number $K$ and by the interval graph induced in a natural way by the request set $D$ on the discrete linearly ordered set $0, \dots, 2n$. Furthermore, if $H=0$, the vertices of the polyhedron defined by the LV($K$) feasibility model are all integral, and, solving the problem of minimizing the number of used vehicles in SNMP can be performed in polynomial time. Moreover, if $H=0$, the unit-load variant of such vehicle-number minimization problem can be solved through a min-cost flow algorithm (see, e.g., [13]).

Another interesting case arises when both $K$ and $Q$ are fixed and $H=0$: here SNMP is polynomial in time even with unrestricted load values $L(j), j = 1, \dots, m$.

**Theorem 2:** If $H=0$ and if $Q$, $K$ are fixed, then the SNMP can be solved in polynomial time.

**Proof:** We prove that, if $H=0$ and $Q$ is fixed, then our problem can be viewed as a shortest path problem defined on an acyclic network with polynomial size, which is solvable in polynomial time through dynamic programming.

To this end, let us describe how the network $G = (N, A)$ is constructed. We define a state vector as any vector $F = F_{k,c}, k = 1, \dots, K, c = 1, \dots, Q$, with values in $[0, n-1]$, and such that, for any $k, F_{k,Q} \le \dots \le F_{k,l}$. Let $\mathcal{F}$ denote the set of all state vectors. As we will see later, we will replicate such state vectors for each node $i$. Vector $F$ tells us, for any node $i$, and any vehicle $k$, that the load of vehicle $k$ is going to be at least equal to $c$ while $k$ is moving from $i$ until $i + F_{k,c}$.

We define the Time Space $\mathcal{TS}$ as the set of all pairs $t = (i, j), i = 0, \dots, n-1, j = 1, \dots, m$, such that $o(j) = i$. The space $\mathcal{TS}$ is linearly ordered in a natural way by the lexicographic order: $(i, j) < (i', j')$ if and only if $i < i'$ OR $((i = i') \text{ AND } (j < j'))$. For any $t \in \mathcal{TS}$, we denote by $\sigma(t)$ its successor in $\mathcal{TS}$ according to the linear ordering. In case $t$ is the last element of $\mathcal{TS}$ with respect to such ordering, we set $\sigma(t) = \text{Nil}$. Then we set $N = \mathcal{F} \times \mathcal{TS} \cup \{\text{End}\}$, where $\text{End}$ is a fictitious node, and $\mathcal{F} \times \mathcal{TS}$ denotes the Cartesian product of the State Space $\mathcal{F}$ and the Time Space $\mathcal{TS}$. The meaning of a node $(F, (i, j))$ of $N$ is that, while we are scanning the set $0, \dots, n-1$, we assign a vehicle to every request $j'$ such that $(o(j), j') < (i, j)$ and we have to decide which vehicle we assign to $j$. Then, the coefficient $F_{k,c}$ indicates that vehicle $k$ will carry a load at least equal to $c$ when moving from $i$ to $i + F_{k,c}$.

In addition, $\text{arc } e = ((F, t), (F', t'))$ is in $A$, if $t' = \sigma(t)$ and $F'$ derives from $F$ by assigning the demand $j$ to some unique vehicle $k$. Arc $e$ is associated with a cost $W_e$, which is defined as the number of additional stops required to assign vehicle $k$ to request $j$. Whenever $\sigma(t) = \text{Nil}$, we define an arc from $(F, t)$ to $\text{End}$, with cost equal to 0.

Solving SNMP amounts to computing a shortest path in the network $G$, from the source node $(0, (0, 0))$ to node $\text{End}$. This is true in any case when $H=0$. If $Q$ is bounded or fixed, then the size of the State Space $\mathcal{F}$ is polynomially bounded in $n$ and $m$. $\square$

**Remark 1 (Difficult features of SNMP).**

If $H > 0$, then Theorem 2 does not hold since the state set $\mathcal{TS}$ should contain, for any time $(i_0, j_0)$ of the time space $\mathcal{TS}$, a list of those requests $j$ such that $o(j) = i_0$ modulo $n$, and which have already been scheduled. So, it follows from Theorems 1 and 2 that, because of the interval structure which is underlying the SNMP, the case when $H=0$ and loads $L(j), j = 1, \dots, m$, are all equal to 1, is close to be polynomial in time. From a practical viewpoint, the difficulty will mainly arise from the existence of waiting laps and from the load distribution.
## 3.2 Solving SNMP through the basic ILP model

To examine the practical difficulty of SNMP, we first solved the ILP model described in Section 2.1, under different hypotheses on *H* and on the loads *L*(*j*). More precisely, we analyze the variation of running times and the gap of the solution with respect to the linear relaxation of the model as a function of the main problem parameters, namely *n*, *m* and *K*.

Since no test-bed exists for SNMP, we randomly generate a set of benchmark instances with different sizes. Each instance is denoted by a code *X*_n-*m*-*H*-*L*-*Q* that summarizes its main characteristics, where *X* is equal to either *N* or *U* for unrestricted and unit load instances, respectively, *n* is the number of nodes, *m* the number of requests, *H* is the maximum number of waiting laps, *L* is the maximum load of a request and *Q* is the vehicle capacity. Tests are run using ILOG-CPLEX 12.5 solver on a Linux CentOS release 6.6 server with 4 processors Intel(R) Xeon(R) CPU X5687 @ 3.60GHz.

Table 1 reports the results we obtained with instances with *n* = {10, 15} and *m* = {28, 33, 38} with loads randomly generated in the interval [1,10] and vehicle capacity *Q* equal to 20. For each instance we report the corresponding number of *n*, *m*, and *H*. Furthermore, we include:

- *K*<sub>min</sub>: minimum number of vehicles;

- *K*\*: number of vehicles used in the optimal solution

- *z*\*: optimal solution value of SNMP

- *LB*: value of the linear relaxation of the model at the root node

- *GAP*: percentage gap of the linear relaxation with respect to the optimal solution, computed as $(z^* - LB)/z^*$;

- *CPU*: running time in seconds.

Table 2 reports instead the results for unit loads. In such case, to guarantee that for the smaller values of *H* the number of required vehicles is greater than 1, we reduced the vehicle capacity *Q* to 5. The difficulty of the problem seems relatively non sensitive to the number of nodes *n* while it strongly depends on the number of requests *m* as shown by Figure 4 that reports the average solution time for various *m* values in the test set. Another quite evident issue is that the difficulty increases when the value of *H* increases: the instances with *H* = 0 are easier than those with *H* > 0. As shown by Figure 5 the computing time growth with *H* is considerably steep even if the average percentage gap only moderately worsen between *H*=0 and 4. Finally, we should observe that in some cases the optimal solution value is obtained with a number of vehicles larger than the minimum possible: this happened in about one third of the 30 instances in the benchmark.

By observing Table 1 we note that model SNMP is not solvable within reasonable computing time as soon as *m* becomes close to 40, whereas it is relatively less sensible to the value of *n*. This is not surprising since the quality of the linear relaxation of the ILP model is quite poor showing gaps as large as 50%. An immediate explanation of such poor quality of the bound is related to the coupling constraints (4): by relaxing the integrality constraint on *Z* it is possible to split requests *j* = 1, ..., *m* into several small fractional pieces, and distribute them among the vehicles *k* = 1, ..., *K* and the waiting laps 0, ..., *H*. It follows that the related values of *T*<sub>*i*,k*</sub> may turn out to be very close to 0.
<table><caption>Table 1: Solution of the ILP model of Section 2.1 for instances with unrestricted loads.</caption><thead><tr><th>Instance</th><th>n</th><th>m</th><th>H</th><th>K<sub>min</sub></th><th>K*</th><th>z*</th><th>LB</th><th>%GAP</th><th>CPU</th></tr></thead><tbody><tr><td>N_10-28-0-10-20</td><td>10</td><td>28</td><td>0</td><td>5</td><td>6</td><td>24</td><td>16</td><td>33.3%</td><td>0.91</td></tr><tr><td>N_10-28-1-10-20</td><td>10</td><td>28</td><td>1</td><td>3</td><td>3</td><td>21</td><td>13</td><td>38.1%</td><td>24.02</td></tr><tr><td>N_10-28-2-10-20</td><td>10</td><td>28</td><td>2</td><td>2</td><td>2</td><td>20</td><td>12</td><td>40.0%</td><td>73.36</td></tr><tr><td>N_10-28-3-10-20</td><td>10</td><td>28</td><td>3</td><td>2</td><td>2</td><td>20</td><td>12</td><td>40.0%</td><td>411.53</td></tr><tr><td>N_10-28-4-10-20</td><td>10</td><td>28</td><td>4</td><td>1</td><td>2</td><td>20</td><td>12</td><td>40.0%</td><td>469.59</td></tr><tr><td>N_10-33-0-10-20</td><td>10</td><td>33</td><td>0</td><td>5</td><td>5</td><td>25</td><td>15</td><td>40.0%</td><td>3.26</td></tr><tr><td>N_10-33-1-10-20</td><td>10</td><td>33</td><td>1</td><td>3</td><td>3</td><td>22</td><td>13</td><td>40.9%</td><td>58.94</td></tr><tr><td>N_10-33-2-10-20</td><td>10</td><td>33</td><td>2</td><td>2</td><td>2</td><td>21</td><td>12</td><td>42.9%</td><td>91.03</td></tr><tr><td>N_10-33-3-10-20</td><td>10</td><td>33</td><td>3</td><td>2</td><td>2</td><td>21</td><td>12</td><td>42.9%</td><td>2057.87</td></tr><tr><td>N_10-33-4-10-20</td><td>10</td><td>33</td><td>4</td><td>1</td><td>1</td><td>21</td><td>11</td><td>47.6%</td><td>76.54</td></tr><tr><td>N_10-38-0-10-20</td><td>10</td><td>38</td><td>0</td><td>5</td><td>6</td><td>28</td><td>16</td><td>42.9%</td><td>176.52</td></tr><tr><td>N_10-38-1-10-20</td><td>10</td><td>38</td><td>1</td><td>3</td><td>3</td><td>24</td><td>13</td><td>45.8%</td><td>320.27</td></tr><tr><td>N_10-38-2-10-20</td><td>10</td><td>38</td><td>2</td><td>2</td><td>3</td><td>23</td><td>12</td><td>47.8%</td><td>5663.64</td></tr><tr><td>N_10-38-3-10-20</td><td>10</td><td>38</td><td>3</td><td>2</td><td>2</td><td>23</td><td>12</td><td>47.8%</td><td>13042.29</td></tr><tr><td>N_10-38-4-10-20</td><td>10</td><td>38</td><td>4</td><td>1</td><td>2</td><td>23</td><td>12</td><td>47.8%</td><td>70946.74</td></tr><tr><td>N_15-28-0-10-20</td><td>15</td><td>28</td><td>0</td><td>4</td><td>4</td><td>24</td><td>18</td><td>25.0%</td><td>0.31</td></tr><tr><td>N_15-28-1-10-20</td><td>15</td><td>28</td><td>1</td><td>2</td><td>3</td><td>22</td><td>17</td><td>22.7%</td><td>1.89</td></tr><tr><td>N_15-28-2-10-20</td><td>15</td><td>28</td><td>2</td><td>2</td><td>2</td><td>22</td><td>16</td><td>27.3%</td><td>2.86</td></tr><tr><td>N_15-28-3-10-20</td><td>15</td><td>28</td><td>3</td><td>1</td><td>2</td><td>22</td><td>16</td><td>27.3%</td><td>24.26</td></tr><tr><td>N_15-28-4-10-20</td><td>15</td><td>28</td><td>4</td><td>1</td><td>1</td><td>22</td><td>16</td><td>27.3%</td><td>9.51</td></tr><tr><td>N_15-33-0-10-20</td><td>15</td><td>33</td><td>0</td><td>4</td><td>4</td><td>31</td><td>24</td><td>22.6%</td><td>0.78</td></tr><tr><td>N_15-33-1-10-20</td><td>15</td><td>33</td><td>1</td><td>2</td><td>3</td><td>28</td><td>20</td><td>28.6%</td><td>26.66</td></tr><tr><td>N_15-33-2-10-20</td><td>15</td><td>33</td><td>2</td><td>2</td><td>2</td><td>26</td><td>18</td><td>30.8%</td><td>44.89</td></tr><tr><td>N_15-33-3-10-20</td><td>15</td><td>33</td><td>3</td><td>2</td><td>2</td><td>25</td><td>17</td><td>32.0%</td><td>123.18</td></tr><tr><td>N_15-33-4-10-20</td><td>15</td><td>33</td><td>4</td><td>1</td><td>2</td><td>25</td><td>17</td><td>32.0%</td><td>538.9</td></tr><tr><td>N_15-38-0-10-20</td><td>15</td><td>38</td><td>0</td><td>6</td><td>7</td><td>34</td><td>23</td><td>32.4%</td><td>42.43</td></tr><tr><td>N_15-38-1-10-20</td><td>15</td><td>38</td><td>1</td><td>3</td><td>4</td><td>29</td><td>19</td><td>34.5%</td><td>567.92</td></tr><tr><td>N_15-38-2-10-20</td><td>15</td><td>38</td><td>2</td><td>2</td><td>3</td><td>28</td><td>18</td><td>35.7%</td><td>2637.6</td></tr><tr><td>N_15-38-3-10-20</td><td>15</td><td>38</td><td>3</td><td>2</td><td>2</td><td>28</td><td>17</td><td>39.3%</td><td>7562.48</td></tr><tr><td>N_15-38-4-10-20</td><td>15</td><td>38</td><td>4</td><td>2</td><td>2</td><td>28</td><td>17</td><td>39.3%</td><td>48911.54</td></tr></tbody></table>

As it could be expected from the results of Section 3.1, the instances with unit load are easier to solve and the gap at the root node is substantially smaller. Moreover, for unit load instances the optimal number of vehicles $K^*$ is always equal to $K_{min}$.
<table><caption>Table 2: Solution of the ILP model of Section 2.1 for instances with unit loads.</caption><thead><tr><th>Instance</th><th>n</th><th>m</th><th>H</th><th>K<sub>min</sub></th><th>K*</th><th>z*</th><th>LB</th><th>%GAP</th><th>CPU</th></tr></thead><tbody><tr><td>U_10-28-0-1-5</td><td>10</td><td>28</td><td>0</td><td>4</td><td>4</td><td>23</td><td>15</td><td>34.8%</td><td>0.85</td></tr><tr><td>U_10-28-1-1-5</td><td>10</td><td>28</td><td>1</td><td>2</td><td>2</td><td>20</td><td>13</td><td>35.0%</td><td>2.26</td></tr><tr><td>U_10-28-2-1-5</td><td>10</td><td>28</td><td>2</td><td>2</td><td>2</td><td>19</td><td>12</td><td>36.8%</td><td>12.84</td></tr><tr><td>U_10-28-3-1-5</td><td>10</td><td>28</td><td>3</td><td>1</td><td>1</td><td>18</td><td>12</td><td>33.3%</td><td>2.01</td></tr><tr><td>U_10-28-4-1-5</td><td>10</td><td>28</td><td>4</td><td>1</td><td>1</td><td>18</td><td>11</td><td>38.9%</td><td>4.76</td></tr><tr><td>U_10-33-0-1-5</td><td>10</td><td>33</td><td>0</td><td>4</td><td>4</td><td>26</td><td>18</td><td>30.8%</td><td>1.81</td></tr><tr><td>U_10-33-1-1-5</td><td>10</td><td>33</td><td>1</td><td>2</td><td>2</td><td>22</td><td>14</td><td>36.4%</td><td>6.33</td></tr><tr><td>U_10-33-2-1-5</td><td>10</td><td>33</td><td>2</td><td>2</td><td>2</td><td>21</td><td>13</td><td>38.1%</td><td>55.35</td></tr><tr><td>U_10-33-3-1-5</td><td>10</td><td>33</td><td>3</td><td>1</td><td>1</td><td>20</td><td>12</td><td>40.0%</td><td>20.1</td></tr><tr><td>U_10-33-4-1-5</td><td>10</td><td>33</td><td>4</td><td>1</td><td>1</td><td>20</td><td>12</td><td>40.0%</td><td>32.54</td></tr><tr><td>U_10-38-0-1-5</td><td>10</td><td>38</td><td>0</td><td>5</td><td>5</td><td>25</td><td>16</td><td>36.0%</td><td>10.28</td></tr><tr><td>U_10-38-1-1-5</td><td>10</td><td>38</td><td>1</td><td>3</td><td>3</td><td>22</td><td>13</td><td>40.9%</td><td>86.58</td></tr><tr><td>U_10-38-2-1-5</td><td>10</td><td>38</td><td>2</td><td>2</td><td>2</td><td>21</td><td>12</td><td>42.9%</td><td>189.21</td></tr><tr><td>U_10-38-3-1-5</td><td>10</td><td>38</td><td>3</td><td>2</td><td>2</td><td>21</td><td>12</td><td>42.9%</td><td>1525.3</td></tr><tr><td>U_10-38-4-1-5</td><td>10</td><td>38</td><td>4</td><td>1</td><td>1</td><td>21</td><td>12</td><td>42.9%</td><td>90.18</td></tr><tr><td>U_15-28-0-1-5</td><td>15</td><td>28</td><td>0</td><td>4</td><td>4</td><td>23</td><td>20</td><td>13.0%</td><td>0.31</td></tr><tr><td>U_15-28-1-1-5</td><td>15</td><td>28</td><td>1</td><td>2</td><td>2</td><td>22</td><td>18</td><td>18.2%</td><td>0.42</td></tr><tr><td>U_15-28-2-1-5</td><td>15</td><td>28</td><td>2</td><td>2</td><td>2</td><td>21</td><td>17</td><td>19.0%</td><td>2.59</td></tr><tr><td>U_15-28-3-1-5</td><td>15</td><td>28</td><td>3</td><td>1</td><td>1</td><td>21</td><td>17</td><td>19.0%</td><td>0.87</td></tr><tr><td>U_15-28-4-1-5</td><td>15</td><td>28</td><td>4</td><td>1</td><td>1</td><td>21</td><td>16</td><td>23.8%</td><td>1.93</td></tr><tr><td>U_15-33-0-1-5</td><td>15</td><td>33</td><td>0</td><td>4</td><td>4</td><td>29</td><td>21</td><td>27.6%</td><td>1.02</td></tr><tr><td>U_15-33-1-1-5</td><td>15</td><td>33</td><td>1</td><td>2</td><td>2</td><td>25</td><td>18</td><td>28.0%</td><td>2.14</td></tr><tr><td>U_15-33-2-1-5</td><td>15</td><td>33</td><td>2</td><td>2</td><td>2</td><td>25</td><td>17</td><td>32.0%</td><td>41.18</td></tr><tr><td>U_15-33-3-1-5</td><td>15</td><td>33</td><td>3</td><td>1</td><td>1</td><td>24</td><td>17</td><td>29.2%</td><td>5.8</td></tr><tr><td>U_15-33-4-1-5</td><td>15</td><td>33</td><td>4</td><td>1</td><td>1</td><td>24</td><td>17</td><td>29.2%</td><td>23.29</td></tr><tr><td>U_15-38-0-1-5</td><td>15</td><td>38</td><td>0</td><td>5</td><td>5</td><td>30</td><td>21</td><td>30.0%</td><td>4.25</td></tr><tr><td>U_15-38-1-1-5</td><td>15</td><td>38</td><td>1</td><td>3</td><td>3</td><td>26</td><td>18</td><td>30.8%</td><td>28.87</td></tr><tr><td>U_15-38-2-1-5</td><td>15</td><td>38</td><td>2</td><td>2</td><td>2</td><td>25</td><td>17</td><td>32.0%</td><td>73.32</td></tr><tr><td>U_15-38-3-1-5</td><td>15</td><td>38</td><td>3</td><td>2</td><td>2</td><td>25</td><td>17</td><td>32.0%</td><td>247.1</td></tr><tr><td>U_15-38-4-1-5</td><td>15</td><td>38</td><td>4</td><td>1</td><td>1</td><td>25</td><td>17</td><td>32.0%</td><td>36.51</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>Figure 4. Average CPU time for the solution of instances with various numbers of requests.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 5. Average CPU time for the solution of instances with various number of waiting laps.</figcaption></figure>

Because of the disappointing behavior of the continuous relaxation in producing tight lower bounds for the SNMP model we also tried to apply Lagrangean Relaxation. Unfortunately, such relaxation did not yield any significant improvement. Some details on the behavior of the Lagrangean Relaxation scheme are given in an Appendix.

### 3.2.1 Evaluating Stop Numbers for a Specific User.

We conducted some specific testing on the number of stops for specific users. The tests show that, if $H = 0$, the average number of times a vehicle $k$ stops while servicing a given user $j$ does not depend on $k$ and only depends on $j$. More precisely, it is proportional to the ratio $(d(j) - o(j) - 1)/n$ if $d(j) - o(j) > 0$ and to $(n + d(j) - o(j) - 1)/n$ otherwise. However, when $H > 0$ it is interesting to observe how the number of times a vehicle $k$ stops during lap $h$ depends on the value $h$ itself. Such correlation may be summarized in the following Table 3, which considers the instances with unit loads $U_{10-x-y-1-5}$, with $x \in \{28, 33\}$, and $y \in \{2, 4\}$. In the table *Stop(h)*, which we call the *Local Stop Number* associated with lap $h$, denotes the number of times an active vehicle stops during lap $h$.

<table><caption>Table 3: Dependence of the Local Stop Number Stop(h) on the lap index h.</caption><thead><tr><th>Instance</th><th>n</th><th>m</th><th>H</th><th>K*</th><th>z*</th><th>z*</th><th>Stop(1)</th><th>Stop(2)</th><th>Stop(3)</th><th>Stop(4)</th><th>Stop(5)</th></tr></thead><tbody><tr><td>U_10-28-2-1-5</td><td>10</td><td>28</td><td>2</td><td>2</td><td>4</td><td>19</td><td>10</td><td>7</td><td>2</td><td>-</td><td>-</td></tr><tr><td>U_10-28-4-1-5</td><td>10</td><td>28</td><td>4</td><td>1</td><td>2</td><td>18</td><td>9</td><td>5</td><td>3</td><td>1</td><td>-</td></tr><tr><td>U_10-33-2-1-5</td><td>10</td><td>33</td><td>2</td><td>2</td><td>2</td><td>21</td><td>11</td><td>8</td><td>2</td><td>-</td><td>-</td></tr><tr><td>U_10-33-4-1-5</td><td>10</td><td>33</td><td>4</td><td>1</td><td>1</td><td>20</td><td>9</td><td>6</td><td>4</td><td>1</td><td>-</td></tr></tbody></table>

From the table we can observe that in general, for a given user $j$, the largest its actual *waiting time* the smallest will be its *travel time*, in terms of additional stops between its origin and destination.
### 3.3 Solving the Set-Covering Based Formulation.

A better lower bound to SNMP is given by the continuous relaxation of the set-covering based model SC-SNMP described in Section 2.3, which can be solved through column generation.

Let us suppose that we are given an active subset $S_0$ of the feasible service set $S$, and that we solved the restriction to $S_0$ of the SC-SNMP. Then, let $\lambda = (\lambda_j, j = 1, ..., m)$ be the dual solution associated with the optimal solution of such restricted problem. Generating a new service $s = (J, h)$ requires solving the following ILP model:

$$ \max \sum_{j=1}^{m} \sum_{h=0}^{H} \lambda_j \cdot Z_{jh} - \sum_{i=0}^{p} T_i \qquad (18) $$

subject to:

$$ \sum_{h=0}^{H} Z_{jh} \le 1, \qquad \forall j = 1, ..., m \qquad (19) $$

$$ \sum_{(j,h) \in \text{Cross}(i)} L(j) \cdot Z_{jh} \le Q, \qquad \forall i = 0, ..., p \qquad (20) $$

$$ Z_{jh} \le T_i, \qquad \forall i = 0, ..., p; \forall (j, h) \in \text{Stop}(i) \qquad (21) $$

$$ Z_{jh} \in \{0,1\}, \qquad \forall j = 1, ..., m; \forall h = 0, ..., H \qquad (22) $$

$$ T_i \in \{0,1\}, \qquad \forall i = 0, ..., p \qquad (23) $$

where the objective function (18) maximizes the cost of the new service, constraints (19) impose that each request is assigned at most once. Constraints (20) are the capacity constraints and (21) are the coupling constraints for the decision variables. Finally, constraints (22) and (23) define the decision variables. Note that the service generated by this ILP model is an improving column for the master problem if and only if its cost (18) is strictly positive.

Whenever the above Pricing problem returns a solution that is strictly positive we may add the corresponding feasible service to $S_0$ and iterate, otherwise the current restricted problem provides the optimal solution to SC-SNMP. The exact solution of SC-SNMP can be obtained through a complete Branch and Price algorithm based on such lower bound. However, since our aim is mainly to investigate the quality of the lower bound obtained with such formulation we do not implemented a full Branch and Price algorithm and we restrict our analysis to the root node of the branch-decision-tree.

Because the solution of the pricing problem is extremely time-consuming we adopt an hybrid approach that first tries to construct heuristically services with positive reduced cost computed as in (18) that may be added to the current SC-SNMP and resorts to the exact solution only when heuristics are unsuccessful. For the heuristic step we use several heuristics based on the Greedy Randomized Adaptive Search Procedure (GRASP, see [11] and [23]), approach followed by a local search step. More precisely, the GRASP is a construction algorithm in which at each iteration the next request to be added to the current service is randomly selected among the $R$ best ones, i.e., those maximizing the associated insertion cost. This, for request $j$, is computed as the difference between $\lambda_j$ and the minimum number of additional stops created by the insertion in one of the existing vehicle tours. We also consider a variant in which the insertion is divided by the load of the request so as to favor insertions with largest unit cost. We consider $R \in \{1, 2, 3\}$, where clearly $R = 1$ corresponds to a deterministic greedy. The six resulting GRASP algorithms are followed by a local search procedure
that considers two-exchanges between requests. As shown in the following, the GRASP pricing works quite well and provides most of the columns that are used in the calculation of the bound by using a negligible computing time.

According to our experimental testing, by relaxing the integrality constraint of SC-SNMP we obtain very good lower bound values, as shown by the following Table 4 that reports the experiments performed on the same benchmark instances and relative to the root node of a Branch and Price algorithm. For the solution of the pricing problem we use the hybrid approach described above, and we impose an overall time limit of 3 hours of computing time. In Table 5 we instead report the results for unit load instances. The columns of the Tables have the same meaning as in the previous tables, while $COL_H$ and $COL_E$ is the total number of generated columns by the heuristic and by the exact pricing algorithms. Note that almost all the CPU time is spent in the exact pricing step of the algorithm as generally happens in similar approaches. The optimal solution values reported in column $z^*$ are those computed with the initial ILP model described in Section 2.1.

<table><caption>Table 4 Results of the column generation algorithm for instances with unrestricted loads</caption><thead><tr><th>.</th><th>n</th><th>m</th><th>H</th><th>z*</th><th>LB</th><th>GAP</th><th>COL<sub>H</sub></th><th>COL<sub>E</sub></th><th>CPU</th></tr></thead><tbody><tr><td>N_10-28-0-10-20</td><td>10</td><td>28</td><td>0</td><td>24</td><td>24</td><td>0,0</td><td>98</td><td>7</td><td>0.6</td></tr><tr><td>N_10-28-1-10-20</td><td>10</td><td>28</td><td>1</td><td>21</td><td>21</td><td>0,0</td><td>188</td><td>23</td><td>9.7</td></tr><tr><td>N_10-28-2-10-20</td><td>10</td><td>28</td><td>2</td><td>20</td><td>20</td><td>0.0</td><td>241</td><td>68</td><td>95.6</td></tr><tr><td>N_10-28-3-10-20</td><td>10</td><td>28</td><td>3</td><td>20</td><td>20</td><td>0.0</td><td>271</td><td>92</td><td>1014.9</td></tr><tr><td>N_10-28-4-10-20</td><td>10</td><td>28</td><td>4</td><td>20</td><td>20</td><td>0.0</td><td>273</td><td>96</td><td>4229.0</td></tr><tr><td>N_10-33-0-10-20</td><td>10</td><td>33</td><td>0</td><td>25</td><td>25</td><td>0.0</td><td>163</td><td>13</td><td>1.3</td></tr><tr><td>N_10-33-1-10-20</td><td>10</td><td>33</td><td>1</td><td>22</td><td>21</td><td>4.5</td><td>299</td><td>119</td><td>31.8</td></tr><tr><td>N_10-33-2-10-20</td><td>10</td><td>33</td><td>2</td><td>21</td><td>20</td><td>4.8</td><td>318</td><td>186</td><td>505.0</td></tr><tr><td>N_10-33-3-10-20</td><td>10</td><td>33</td><td>3</td><td>21</td><td>20</td><td>4.8</td><td>412</td><td>182</td><td>3015.0</td></tr><tr><td>N_10-33-4-10-20</td><td>10</td><td>33</td><td>4</td><td>21</td><td>--</td><td>--</td><td>352</td><td>204</td><td>T.L.</td></tr><tr><td>N_10-38-0-10-20</td><td>10</td><td>38</td><td>0</td><td>28</td><td>27</td><td>3.6</td><td>219</td><td>69</td><td>9.0</td></tr><tr><td>N_10-38-1-10-20</td><td>10</td><td>38</td><td>1</td><td>24</td><td>23</td><td>4.2</td><td>361</td><td>124</td><td>81.3</td></tr><tr><td>N_10-38-2-10-20</td><td>10</td><td>38</td><td>2</td><td>23</td><td>23</td><td>0.0</td><td>431</td><td>154</td><td>1585.2</td></tr><tr><td>N_10-38-3-10-20</td><td>10</td><td>38</td><td>3</td><td>23</td><td>--</td><td>--</td><td>445</td><td>179</td><td>T.L.</td></tr><tr><td>N_10-38-4-10-20</td><td>10</td><td>38</td><td>4</td><td>23</td><td>--</td><td>--</td><td>426</td><td>183</td><td>T.L.</td></tr><tr><td>N_15-28-0-10-20</td><td>15</td><td>28</td><td>0</td><td>24</td><td>24</td><td>0.0</td><td>100</td><td>4</td><td>0.3</td></tr><tr><td>N_15-28-1-10-20</td><td>15</td><td>28</td><td>1</td><td>22</td><td>22</td><td>0.0</td><td>170</td><td>45</td><td>7.1</td></tr><tr><td>N_15-28-2-10-20</td><td>15</td><td>28</td><td>2</td><td>22</td><td>22</td><td>0.0</td><td>209</td><td>65</td><td>17.3</td></tr><tr><td>N_15-28-3-10-20</td><td>15</td><td>28</td><td>3</td><td>22</td><td>22</td><td>0.0</td><td>241</td><td>78</td><td>61.7</td></tr><tr><td>N_15-28-4-10-20</td><td>15</td><td>28</td><td>4</td><td>22</td><td>22</td><td>0.0</td><td>201</td><td>51</td><td>75.9</td></tr><tr><td>N_15-33-0-10-20</td><td>15</td><td>33</td><td>0</td><td>31</td><td>31</td><td>0.0</td><td>159</td><td>10</td><td>1.1</td></tr><tr><td>N_15-33-1-10-20</td><td>15</td><td>33</td><td>1</td><td>28</td><td>27</td><td>3.6</td><td>292</td><td>45</td><td>15.3</td></tr><tr><td>N_15-33-2-10-20</td><td>15</td><td>33</td><td>2</td><td>26</td><td>25</td><td>3.8</td><td>363</td><td>166</td><td>150.3</td></tr><tr><td>N_15-33-3-10-20</td><td>15</td><td>33</td><td>3</td><td>25</td><td>25</td><td>0.0</td><td>452</td><td>216</td><td>1001.0</td></tr><tr><td>N_15-33-4-10-20</td><td>15</td><td>33</td><td>4</td><td>25</td><td>25</td><td>0.0</td><td>469</td><td>258</td><td>2960.7</td></tr><tr><td>N_15-38-0-10-20</td><td>15</td><td>38</td><td>0</td><td>34</td><td>33</td><td>2.9</td><td>196</td><td>49</td><td>2.6</td></tr><tr><td>N_15-38-1-10-20</td><td>15</td><td>38</td><td>1</td><td>29</td><td>29</td><td>0.0</td><td>398</td><td>145</td><td>41.2</td></tr><tr><td>N_15-38-2-10-20</td><td>15</td><td>38</td><td>2</td><td>28</td><td>28</td><td>0.0</td><td>417</td><td>214</td><td>561.2</td></tr><tr><td>N_15-38-3-10-20</td><td>15</td><td>38</td><td>3</td><td>28</td><td>28</td><td>0.0</td><td>448</td><td>249</td><td>5558.1</td></tr><tr><td>N_15-38-4-10-20</td><td>15</td><td>38</td><td>4</td><td>28</td><td>--</td><td>--</td><td>477</td><td>292</td><td>T.L.</td></tr></tbody></table>
<table><caption>Table 5: Results of the column generation algorithm for instances with unit loads.</caption><thead><tr><th>Instance</th><th>n</th><th>m</th><th>H</th><th>z*</th><th>LB</th><th>GAP</th><th>COL<sub>H</sub></th><th>COL<sub>E</sub></th><th>CPU</th></tr></thead><tbody><tr><td>U 10-28-0-1-5</td><td>10</td><td>28</td><td>0</td><td>23</td><td>22</td><td>4.3</td><td>174</td><td>12</td><td>1.3</td></tr><tr><td>U 10-28-1-1-5</td><td>10</td><td>28</td><td>1</td><td>20</td><td>19</td><td>5.0</td><td>314</td><td>61</td><td>10.1</td></tr><tr><td>U 10-28-2-1-5</td><td>10</td><td>28</td><td>2</td><td>19</td><td>18</td><td>5.3</td><td>354</td><td>141</td><td>41.7</td></tr><tr><td>U 10-28-3-1-5</td><td>10</td><td>28</td><td>3</td><td>18</td><td>18</td><td>0.0</td><td>393</td><td>172</td><td>181.0</td></tr><tr><td>U 10-28-4-1-5</td><td>10</td><td>28</td><td>4</td><td>18</td><td>18</td><td>0.0</td><td>391</td><td>189</td><td>834.1</td></tr><tr><td>U 10-33-0-1-5</td><td>10</td><td>33</td><td>0</td><td>26</td><td>26</td><td>0.0</td><td>207</td><td>15</td><td>1.6</td></tr><tr><td>U 10-33-1-1-5</td><td>10</td><td>33</td><td>1</td><td>22</td><td>21</td><td>4.5</td><td>332</td><td>111</td><td>27.2</td></tr><tr><td>U 10-33-2-1-5</td><td>10</td><td>33</td><td>2</td><td>21</td><td>20</td><td>4.8</td><td>451</td><td>177</td><td>249.9</td></tr><tr><td>U 10-33-3-1-5</td><td>10</td><td>33</td><td>3</td><td>20</td><td>20</td><td>0.0</td><td>531</td><td>259</td><td>980.4</td></tr><tr><td>U 10-33-4-1-5</td><td>10</td><td>33</td><td>4</td><td>20</td><td>20</td><td>0.0</td><td>486</td><td>256</td><td>3796.5</td></tr><tr><td>U 10-38-0-1-5</td><td>10</td><td>38</td><td>0</td><td>25</td><td>25</td><td>0.0</td><td>243</td><td>34</td><td>1.9</td></tr><tr><td>U 10-38-1-1-5</td><td>10</td><td>38</td><td>1</td><td>22</td><td>21</td><td>4.5</td><td>450</td><td>130</td><td>24.3</td></tr><tr><td>U 10-38-2-1-5</td><td>10</td><td>38</td><td>2</td><td>21</td><td>20</td><td>4.8</td><td>529</td><td>279</td><td>562.4</td></tr><tr><td>U 10-38-3-1-5</td><td>10</td><td>38</td><td>3</td><td>21</td><td>20</td><td>4.8</td><td>533</td><td>269</td><td>4041.0</td></tr><tr><td>U 10-38-4-1-5</td><td>10</td><td>38</td><td>4</td><td>21</td><td>--</td><td>--</td><td>490</td><td>271</td><td>T.L.</td></tr><tr><td>U 15-28-0-1-5</td><td>15</td><td>28</td><td>0</td><td>23</td><td>23</td><td>0.0</td><td>202</td><td>18</td><td>0.5</td></tr><tr><td>U 15-28-1-1-5</td><td>15</td><td>28</td><td>1</td><td>22</td><td>21</td><td>4.5</td><td>224</td><td>55</td><td>10.3</td></tr><tr><td>U 15-28-2-1-5</td><td>15</td><td>28</td><td>2</td><td>21</td><td>21</td><td>0.0</td><td>289</td><td>113</td><td>42.0</td></tr><tr><td>U 15-28-3-1-5</td><td>15</td><td>28</td><td>3</td><td>21</td><td>21</td><td>0.0</td><td>269</td><td>157</td><td>97.1</td></tr><tr><td>U 15-28-4-1-5</td><td>15</td><td>28</td><td>4</td><td>21</td><td>21</td><td>0.0</td><td>275</td><td>116</td><td>146.8</td></tr><tr><td>U 15-33-0-1-5</td><td>15</td><td>33</td><td>0</td><td>29</td><td>29</td><td>0.0</td><td>198</td><td>27</td><td>2.5</td></tr><tr><td>U 15-33-1-1-5</td><td>15</td><td>33</td><td>1</td><td>25</td><td>25</td><td>0.0</td><td>366</td><td>115</td><td>22.1</td></tr><tr><td>U 15-33-2-1-5</td><td>15</td><td>33</td><td>2</td><td>25</td><td>24</td><td>4.0</td><td>420</td><td>191</td><td>204.7</td></tr><tr><td>U 15-33-3-1-5</td><td>15</td><td>33</td><td>3</td><td>24</td><td>24</td><td>0.0</td><td>472</td><td>278</td><td>820.9</td></tr><tr><td>U 15-33-4-1-5</td><td>15</td><td>33</td><td>4</td><td>24</td><td>24</td><td>0.0</td><td>572</td><td>280</td><td>2873.2</td></tr><tr><td>U 15-38-0-1-5</td><td>15</td><td>38</td><td>0</td><td>30</td><td>30</td><td>0.0</td><td>241</td><td>26</td><td>3.9</td></tr><tr><td>U 15-38-1-1-5</td><td>15</td><td>38</td><td>1</td><td>26</td><td>25</td><td>3.8</td><td>476</td><td>176</td><td>30.7</td></tr><tr><td>U 15-38-2-1-5</td><td>15</td><td>38</td><td>2</td><td>25</td><td>25</td><td>0.0</td><td>474</td><td>283</td><td>244.2</td></tr><tr><td>U 15-38-3-1-5</td><td>15</td><td>38</td><td>3</td><td>25</td><td>24</td><td>4.0</td><td>602</td><td>347</td><td>1311.6</td></tr><tr><td>U 15-38-4-1-5</td><td>15</td><td>38</td><td>4</td><td>25</td><td>24</td><td>4.0</td><td>558</td><td>385</td><td>5273.3</td></tr></tbody></table>

While Tables 1 and 2 show a considerable difference between the general and the unit case, this is not the case with the set-covering-based model.

However, the pricing problem turns out to be extremely time consuming, when it is solved as an integer program through CPLEX, making it impossible to incorporate it into an overall complete Branch and Price approach. Furthermore, our experimental analysis shows that relaxing the integrality constraint in the pricing problem provides a very poor lower bound as may be expected due to the very specific nature of the objective function of the pricing problem that is the difference of two terms. Moreover, we may observe that:
**Theorem 3:** The pricing problem is NP-Hard, even in the case where $H = 0$, we have unit loads, and $Q = +\infty$.

**Proof:** We just need to prove that if $W$ is equal to an integer in $\{1, ..., n-1\}$, then solving the pricing problem while imposing that $\sum_i T_i = W$ is NP-Hard. Let us consider any non-oriented graph $G$ whose node set is the set $\{1, ..., n-1\}$. With every edge $(x, y)$, $x < y$, in this graph we may associate some request $j$ such that $o(j) = x$ and $d(j) = y$, and set $\lambda_j = 1$. Then, computing a solution $(Z, T)$ of the pricing problem such that $\sum_i T_i = W$ and $\sum_j \lambda_j Z_{j,h} \ge W.(W-1)/2$ requires finding a complete sub-graph of $G$ with exactly $W$ nodes, which is known to be NP-Hard (see, e.g., [12]). $\square$

On the other hand, if $H = 0$, and $Q$ is fixed, our problem happens to be polynomial in time:

**Theorem 4:** In case $Q$ is fixed and $H = 0$, then the pricing problem can be solved in polynomial time.

**Proof.** The pricing problem can be solved through dynamic programming as a shortest path problem defined on an acyclic directed graph $F$ with a number of vertices which depends polynomially by $n$ and $m$. We define a state as being any integer-valued vector $V = (V_1, ..., V_Q)$, such that $n \ge V_1 \ge V_2 \ge ..., \ge V_Q \ge -1$. Such state corresponds to the possible load profile functions of a vehicle when it arrives at node $i$, while being loaded according to decisions which have been taken at preceding nodes $i'$, i.e. such that $i' \le i$. The vehicle carries a load not smaller than $c$ when arriving at any node $i_1$ such that $i_1 \le i + V_c$ and such load is going to be less than $c$ when the vehicle leaves node $i + V_c$. The fact that $V_1 = -1$ means that the vehicle is empty when it arrives at $i$. Clearly, vector $V$ tells us whether the vehicle is supposed to unload at node $i$, and, whether $i$ is currently scheduled as a stop node for the vehicle. We denote by $\mathcal{V}$ the set of all possible states. Then the nodes in the directed graph $F$ are all triples $(i, j, V)$, $i = 0, ..., n-1, j = 1, ..., m$, such that $o(j) = i, V \in \mathcal{V}$, augmented with 2 fictitious nodes, called *Start* and *End*. An arc $((i_0, j_0, V_0), (i_1, j_1, V_1))$ exists in $F$ if one of the following cases occurs:

1) $i_1 = i_0 + 1, j_1 = \{\min j: o(j) = i_1\}, V_1 = V_0 - 1$. In this case, the vehicle moves from $i_0$ to $i_0 + 1$ without loading $L(j_0)$;

2) $i_1 = i_0 + 1, j_1 = \{\min j: o(j) = i_1\}, V_1$ derives from $V_0$ by taking into account the additional load $L(j_0)$ between $o(j_0) = i_0$ and $d(j_0)$ and the fact the vehicle has been moving from $i_0$ to $i_0 + 1$ after loading $L(j_0)$. In this case, the vehicle moves from $i_0$ to $i_0 + 1$ after loading $L(j_0)$;

3) $i_1 = i_0, j_1 = \{\min j: o(j) = i_1\}, V_1 = V_0$. Here, the vehicle remains at $i_0$ and does not load $L(j_0)$;

4) $i_1 = i_0, j_1 = \{\min j > j_0: o(j) = i_1\}, V_1$ derives from $V_0$ by taking into account the additional load $L(j_0)$ between $o(j_0) = i_0$ and $d(j_0)$. In this case, the vehicle remains at $i_0$ and loads $L(j_0)$;

In Cases 1 and 3, the arc $((i_0, j_0, V_0), (i_1, j_1, V_1))$ is associated with a null length. In Cases 2 and 4, the arc is associated with a length that expresses the impact on the *Stop Number* of the insertion of request $j_0$ into of the vehicle, taking into account the current state $V_0$. One easily checks that solving our *Stop Minimization-Price* problem means computing a shortest path in this acyclic digraph $F$. $\square$

**Remark 2** (*Theorem 4 and an efficient pricing algorithm*)

In many cases, it happens that a dynamic programming algorithm such as that used to prove Theorem 4, may be adapted to obtain an efficient algorithm, even when time-polynomiality does not apply. Unfortunately, this is not the case here. Clearly, if $H$ is not 0, the main assumption of our algorithmic scheme is not relevant any more. However, even when $H = 0$, the number of non-dominated states in $\mathcal{V}$
tends to become large very fast. Indeed, we implement the above algorithmic scheme by linearly ordering the request set $D = \{1..m\}$ in a way which is consistent with the natural ordering on the *origin set* $\{o(j), j = 1..m\}$, and by considering that, once some request $j$ has been inserted into the service $J$, the decision is about the next request $j'$ in $D$ which is going to be in $J$. Then the state space $\mathcal{V}$ is as in the proof of Theorem 4, and corresponds to all possible *load profile functions* which may characterize the state of the vehicle after $j$ has been loaded. State set $\mathcal{V}$ may be filtered by a *dominance relation*, but, because of the complex structure of the elements of $\mathcal{V}$, such relation lacks the strength to filter $\mathcal{V}$ in an efficient way. As a consequence, the computing time quickly explode as illustrated in the following Table 6. The table reports the time, in seconds, required to solve the pricing problem with either CPLEX 12 or with the dynamic program (DP) for some instances with unrestricted and unit loads and various values of $n$, $m$ and $Q$.

<table><caption>Table 6: Using CPLEX and Dynamic Programming (DP) to perform the column generation step.</caption><thead><tr><td>Request-Type</td><td>n</td><td>m</td><td>Q</td><td>CPLEX(s)</td><td>DP (s)</td></tr></thead><tbody><tr><td>unrestricted</td><td>10</td><td>28</td><td>5</td><td>8</td><td>35</td></tr><tr><td>unrestricted</td><td>15</td><td>28</td><td>5</td><td>6</td><td>52</td></tr><tr><td>unit</td><td>10</td><td>28</td><td>5</td><td>8</td><td>699</td></tr><tr><td>unit</td><td>10</td><td>33</td><td>5</td><td>15</td><td>&gt;3600</td></tr></tbody></table>

Table 6 clearly shows that, unfortunately, the DP approach lacks the efficiency that would be necessary to obtain tight lower bounds for large instances.

## 4. A HYBRID GRASP-R&R HEURISTIC FOR SNMP

In practical applications the *Stop Number Minimization Problem* must be solved quickly to be used in the real-time management of autonomous vehicles. Clearly the exact methods proposed in the previous sections are not suitable in such a context due to the very long time they require to determine the solutions. Therefore, in this section we propose a fast heuristic approach for SNMP. Although we present a complete method that works on the static problem, so that we can compare its results with those of the exact methods, the approach is designed to be used also in the *on-line* context, so as to define the routing of the vehicles as soon as new requests are revealed. This possibility is guaranteed by the structure of the algorithm that is based on a simple insertion mechanism. At a given time instant of the planning horizon some vehicles are already partially loaded with requests that were revealed before and the currently arriving one is inserted in the best position of the current tours.

The overall algorithm we propose is a hybrid one, which combines sequentially a GRASP (see [11] and [23]), to quickly construct an initial solution, followed by a fast refining procedure based on the *Ruin-and-Recreate* (R&R, see [25]) paradigm. The two phases are repeated for a prefixed number $\rho$ of replications and the best solution found over all replications is returned. In the following we describe in detail the various components of the algorithm.
## 4.1 The GRASP step

Since finding a feasible solution using exactly *K* vehicles is not guaranteed for a heuristic method, the algorithm accepts in the initialization phase to construct solutions having more than *K* vehicles. The number of used vehicles is possibly reduced in the R&R step.

The GRASP-based algorithm starts from an empty solution, and then iteratively selects the next not yet serviced request according to a *priority rule* that takes into account the current loading status of the vehicles in the interval between the origin and destination of the request. More precisely, for each not yet serviced request *j* we compute a priority score *P*<sub>j</sub>, defined as the number of feasible insertion points in the active vehicles which have sufficient residual capacity to carry its load *L*(*j*) between the origin node *o*(*j*) and the destination node *d*(*j*) for some waiting lap *h* ≤ *H*. Whenever the request has at least one feasible insertion in a vehicle that share the stop with an already inserted one, with probability 0.5 the priority score is further reduced by 1. If no feasible insertion exists for request *j* in the active vehicles we conventionally set *P*<sub>j</sub> =-1.

At the current iteration, the next request *j'* is randomly selected among those minimizing the value *P*<sub>j</sub> over all not yet serviced ones. Note that, if *P*<sub>j</sub> = -1, i.e., no feasible insertion point exists for request *j'* in one of the active vehicles, then a new vehicle is initialized with request *j'* and a new iteration is started.

Once the next request *j'* (with $P_j \ge 0$) is selected, it is inserted in the solution as follows. We first examine all feasible insertion points in the active vehicles and, for each such point, we consider the number of additional stops resulting from the insertion. Let $\sigma$ be the smallest number of additional stops found and let $T(j',\sigma)$ be the set of feasible insertion points for *j'* associated with value $\sigma$. More precisely, $T(j',\sigma) = \{(k,h): \text{j'} \text{ can be inserted in vehicle } k \text{ with } h \text{ waiting laps and introducing } \sigma \text{ additional stops}\}$. We randomly select the insertion point among those in set $T(j',\sigma)$.

During our extensive preliminary computational testing, we examined different strategies to implement both the selection and the insertion criteria in the above algorithm. For example, we consider in the insertion step also the residual capacity of the vehicle around the insertion point to favor insertions in less filled areas. However, the algorithm we just described here is the one that experimentally provides the best compromise between solutions quality and required running times. Furthermore, the testing shows that performing an increasing number of replications is beneficial on the algorithm performance given that the computing time needed for a given iteration is very small for the instances of our benchmark. The marginal benefit of incrementing the number of iterations is reported in Figure 6. Such figure shows the evolution of the average gap of the GRASP solution with respect to the optimal one, when $\rho$ is increased from 1 to 100,000. The figure also shows the considerable benefit obtained by combining the simple and fast GRASP algorithm with the R&R step. In our computational testing we used 10,000 iterations that represent a good compromise between computing time and quality.
<figure><img src="image_7.png" /><figcaption>**Figure 6.** Evolution of the percentage gap of the solution of the GRASP and GRASP+R&R as a function of the number of iterations.</figcaption></figure>

## 4.2 The Ruin and Recreate step

Following the *Ruin and Recreate* idea, the refinement step possibly improves the solution obtained by the GRASP by alternating two phases. In the *Ruin* phase the current solution is partially destroyed by removing from it some of the requests. Then the solution is reconstructed in the *Recreate* step by reinserting the removed requests using again the GRASP algorithm.

The key factor of the R&R algorithm is clearly the *Ruin* mechanism, for which several possible strategies were proposed in the literature (see, e.g. [25]). Those strategies are often combined together by introducing a random sorting decision mechanism that allows switching from a strategy to another one as in the *Adaptive Large Neighborhood Search* (see Pisinger and Ropke [24]). In our implementation we want to keep a high speed and considerable simplicity, hence we adopt two simple *Ruin* mechanisms, thus getting two different implementations of the whole R&R algorithm.

Let us call *unpaired requests* all requests that do not share both stops at origin or destination with other requests. The first *Ruin* mechanism, R1, is a deterministic one that concentrates on the *unpaired requests* and removes all of them from the current solution. The second mechanism is instead a mixed one that combines R1, chosen with probability $\pi$, with a probabilistic one, called R2 and chosen with probability $1-\pi$, where each request $j = 1, ..., m$ may be removed with probability $\pi'$. During our extensive preliminary testing we attempt several other *Ruin* rules but the two which we just described represent the best performing ones. In particular, rule R1 is particularly well suited for a fast execution
in which just a few iterations are performed, whereas the probabilistic rule R2 works best when more
time is available for the iterations.

The R&R algorithm has been implemented in two versions. The first one, called *R&R-Fast* is a simple descent algorithm that uses *Ruin* mechanism R1 described above. As soon as a non-improving solution is found the algorithm is stopped and the current best solution is returned. Clearly such a method is suited to quickly polish the solutions obtained with the GRASP and is sufficiently well performing to be used within *on-line* contexts. A better version, simply called *R&R* hereafter, is a more traditional implementation where the search is continued even in case a non-improving solution is found. More precisely, *Ruin* mechanism R2 is used, combined with a probabilistic acceptance rule (see also [24]) where the current non-improving solution is accepted with probability max{0,(0.9 – Δ/10)} where Δ is the number of additional stops with respect to the current best solution. The process is iterated until no improvement is found for γ consecutive R&R iterations.

4.3 *Testing of the Hybrid Algorithm.*

To have a clear assessment on the performance of the proposed algorithm we test it on the instances
with unrestricted load that we previously solved with the ILP exact approach. An intensive
preliminary testing allows us to define the parameters set that offers the best compromise between
quality and computing time, which is: ρ =10,000, π = 0.75, π' = 5 and γ = 10.

As in the case of the experiments which we performed on the ILP formulation, we ran the tests while
using a Linux CentOS release 6.6 server with 4 processors Intel(R) Xeon(R) CPU X5687 @
3.60GHz, together with a C++ gcc version 4.4.7 compiler.

The results are summarized in Table 7 and Table 8. For each instance Table 7 reports the optimal solution value z*. Then, we give the results of the simple GRASP, i.e., without the R&R step, for the GRASP followed by the simple descent *R&R-Fast* and the GRASP followed by the complete *R&R*. For each algorithm we give the value of the solution, the percentage gap with respect to the optimal one and the computing time in seconds. In Table 8, we test the sensitivity of the results produced by our GRASP algorithms to their random control components, by providing, for the same instances and a number of runs equal to 10, the average, best and worse value produced by both simple GRASP and GRASP+R&R.

Table 7 shows that the proposed algorithm is very effective. In fact the complete GRASP+$R\&R$ finds,
in a few seconds of computing time, 26 out of 30 optimal solutions and in the remaining cases uses at
most one additional stop. The computing times are also growing slowly with the value of $m$, making
our algorithm suitable also for larger instances involving several tens of stops. Moreover, in cases
where faster running times are needed (e.g. in the on-line context) the more aggressive GRASP+$R\&R$-
$Fast$ is still able to find 50% of optimal solutions in about one second. Finally, we should observe that
the R&R step is really worth being used since it greatly improves the GRASP solutions with a modest
computing time requirement.

Table 8 shows that two distinct runs may produce results with very different quality levels when we
restrict ourselves to the use of the simple greedy GRASP scheme, and that this strong dependence to
random sorting is drastically reduced in the case of GRASP+$R\&R$.
<table><caption>Table 7: Results of the heuristic approaches on instances with unrestricted loads.</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">n</th><th rowspan="2">m</th><th rowspan="2">H</th><th rowspan="2">z*</th><th colspan="3">GRASP</th><th colspan="3">GRASP+R&R-Fast</th><th colspan="3">GRASP+R&R</th></tr><tr><th>UB</th><th>GAP</th><th>CPU</th><th>UB</th><th>GAP</th><th>CPU</th><th>UB</th><th>GAP</th><th>CPU</th></tr></thead><tbody><tr><td>N_10-28-0-10-20</td><td>10</td><td>28</td><td>0</td><td>24</td><td>26</td><td>8.3</td><td>0.3</td><td>24</td><td>0.0</td><td>0.8</td><td>24</td><td>0.0</td><td>7.5</td></tr><tr><td>N_10-28-1-10-20</td><td>10</td><td>28</td><td>1</td><td>21</td><td>23</td><td>9.5</td><td>0.4</td><td>21</td><td>0.0</td><td>0.7</td><td>21</td><td>0.0</td><td>4.0</td></tr><tr><td>N_10-28-2-10-20</td><td>10</td><td>28</td><td>2</td><td>20</td><td>21</td><td>5.0</td><td>0.4</td><td>21</td><td>5.0</td><td>0.7</td><td>20</td><td>0.0</td><td>3.6</td></tr><tr><td>N_10-28-3-10-20</td><td>10</td><td>28</td><td>3</td><td>20</td><td>22</td><td>10.0</td><td>0.5</td><td>20</td><td>0.0</td><td>0.8</td><td>20</td><td>0.0</td><td>4.1</td></tr><tr><td>N_10-28-4-10-20</td><td>10</td><td>28</td><td>4</td><td>20</td><td>21</td><td>5.0</td><td>0.5</td><td>21</td><td>5.0</td><td>0.9</td><td>20</td><td>0.0</td><td>4.6</td></tr><tr><td>N_10-33-0-10-20</td><td>10</td><td>33</td><td>0</td><td>25</td><td>26</td><td>4.0</td><td>0.4</td><td>25</td><td>0.0</td><td>0.6</td><td>25</td><td>0.0</td><td>3.4</td></tr><tr><td>N_10-33-1-10-20</td><td>10</td><td>33</td><td>1</td><td>22</td><td>24</td><td>9.1</td><td>0.5</td><td>23</td><td>4.5</td><td>0.7</td><td>22</td><td>0.0</td><td>3.2</td></tr><tr><td>N_10-33-2-10-20</td><td>10</td><td>33</td><td>2</td><td>21</td><td>24</td><td>14.3</td><td>0.6</td><td>22</td><td>4.8</td><td>0.7</td><td>21</td><td>0.0</td><td>3.0</td></tr><tr><td>N_10-33-3-10-20</td><td>10</td><td>33</td><td>3</td><td>21</td><td>23</td><td>9.5</td><td>0.6</td><td>22</td><td>4.8</td><td>0.8</td><td>21</td><td>0.0</td><td>3.6</td></tr><tr><td>N_10-33-4-10-20</td><td>10</td><td>33</td><td>4</td><td>21</td><td>22</td><td>4.8</td><td>0.6</td><td>22</td><td>4.8</td><td>0.7</td><td>21</td><td>0.0</td><td>3.0</td></tr><tr><td>N_10-38-0-10-20</td><td>10</td><td>38</td><td>0</td><td>28</td><td>30</td><td>7.1</td><td>0.5</td><td>28</td><td>0.0</td><td>0.8</td><td>28</td><td>0.0</td><td>9.5</td></tr><tr><td>N_10-38-1-10-20</td><td>10</td><td>38</td><td>1</td><td>24</td><td>28</td><td>16.7</td><td>0.6</td><td>26</td><td>8.3</td><td>0.9</td><td>24</td><td>0.0</td><td>4.6</td></tr><tr><td>N_10-38-2-10-20</td><td>10</td><td>38</td><td>2</td><td>23</td><td>26</td><td>13.0</td><td>0.7</td><td>24</td><td>4.3</td><td>0.9</td><td>24</td><td>4.3</td><td>4.5</td></tr><tr><td>N_10-38-3-10-20</td><td>10</td><td>38</td><td>3</td><td>23</td><td>27</td><td>17.4</td><td>0.8</td><td>25</td><td>8.7</td><td>1.1</td><td>24</td><td>4.3</td><td>5.0</td></tr><tr><td>N_10-38-4-10-20</td><td>10</td><td>38</td><td>4</td><td>23</td><td>26</td><td>13.0</td><td>0.8</td><td>25</td><td>8.7</td><td>1.1</td><td>24</td><td>4.3</td><td>5.6</td></tr><tr><td>N_15-28-0-10-20</td><td>15</td><td>28</td><td>0</td><td>24</td><td>24</td><td>0.0</td><td>0.3</td><td>24</td><td>0.0</td><td>0.6</td><td>24</td><td>0.0</td><td>4.0</td></tr><tr><td>N_15-28-1-10-20</td><td>15</td><td>28</td><td>1</td><td>22</td><td>24</td><td>9.1</td><td>0.4</td><td>22</td><td>0.0</td><td>0.7</td><td>22</td><td>0.0</td><td>3.9</td></tr><tr><td>N_15-28-2-10-20</td><td>15</td><td>28</td><td>2</td><td>22</td><td>24</td><td>9.1</td><td>0.5</td><td>22</td><td>0.0</td><td>0.8</td><td>22</td><td>0.0</td><td>4.0</td></tr><tr><td>N_15-28-3-10-20</td><td>15</td><td>28</td><td>3</td><td>22</td><td>24</td><td>9.1</td><td>0.5</td><td>22</td><td>0.0</td><td>0.7</td><td>22</td><td>0.0</td><td>4.2</td></tr><tr><td>N_15-28-4-10-20</td><td>15</td><td>28</td><td>4</td><td>22</td><td>23</td><td>4.5</td><td>0.5</td><td>22</td><td>0.0</td><td>0.8</td><td>22</td><td>0.0</td><td>3.7</td></tr><tr><td>N_15-33-0-10-20</td><td>15</td><td>33</td><td>0</td><td>31</td><td>33</td><td>6.5</td><td>0.4</td><td>31</td><td>0.0</td><td>0.9</td><td>31</td><td>0.0</td><td>16.1</td></tr><tr><td>N_15-33-1-10-20</td><td>15</td><td>33</td><td>1</td><td>28</td><td>31</td><td>10.7</td><td>0.5</td><td>28</td><td>0.0</td><td>1.1</td><td>28</td><td>0.0</td><td>8.9</td></tr><tr><td>N_15-33-2-10-20</td><td>15</td><td>33</td><td>2</td><td>26</td><td>29</td><td>11.5</td><td>0.6</td><td>26</td><td>0.0</td><td>1.1</td><td>26</td><td>0.0</td><td>7.7</td></tr><tr><td>N_15-33-3-10-20</td><td>15</td><td>33</td><td>3</td><td>25</td><td>27</td><td>8.0</td><td>0.7</td><td>26</td><td>4.0</td><td>1.3</td><td>25</td><td>0.0</td><td>8.1</td></tr><tr><td>N_15-33-4-10-20</td><td>15</td><td>33</td><td>4</td><td>25</td><td>28</td><td>12.0</td><td>0.7</td><td>26</td><td>4.0</td><td>1.2</td><td>25</td><td>0.0</td><td>8.9</td></tr><tr><td>N_15-38-0-10-20</td><td>15</td><td>38</td><td>0</td><td>34</td><td>38</td><td>11.8</td><td>0.6</td><td>34</td><td>0.0</td><td>1.4</td><td>34</td><td>0.0</td><td>14.6</td></tr><tr><td>N_15-38-1-10-20</td><td>15</td><td>38</td><td>1</td><td>29</td><td>36</td><td>24.1</td><td>0.8</td><td>31</td><td>6.9</td><td>1.5</td><td>30</td><td>3.4</td><td>10.2</td></tr><tr><td>N_15-38-2-10-20</td><td>15</td><td>38</td><td>2</td><td>28</td><td>35</td><td>25.0</td><td>0.8</td><td>30</td><td>7.1</td><td>1.6</td><td>28</td><td>0.0</td><td>10.1</td></tr><tr><td>N_15-38-3-10-20</td><td>15</td><td>38</td><td>3</td><td>28</td><td>32</td><td>14.3</td><td>1.0</td><td>30</td><td>7.1</td><td>1.7</td><td>28</td><td>0.0</td><td>9.3</td></tr><tr><td>N_15-38-4-10-20</td><td>15</td><td>38</td><td>4</td><td>28</td><td>34</td><td>21.4</td><td>1.1</td><td>29</td><td>3.6</td><td>1.9</td><td>28</td><td>0.0</td><td>10.5</td></tr></tbody><tfoot><tr><td>Average</td><td></td><td></td><td></td><td></td><td>24.3</td><td>27.0</td><td>10.8</td><td>0.6</td><td>25.1</td><td>3.1</td><td>1.0</td><td>24.5</td><td>0.5</td><td>6.4</td></tr></tfoot></table>
<table><caption>Table 8: Sensitivity Analysis of the heuristic performance out of 10 runs.</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">n</th><th rowspan="2">m</th><th rowspan="2">H</th><th rowspan="2">z*</th><th colspan="3">GRASP (10 runs)</th><th colspan="3">GRASP+R&R (10 runs)</th></tr><tr><th>best</th><th>worst</th><th>average</th><th>best</th><th>worst</th><th>average</th></tr></thead><tbody><tr><td>N 10-28-0-10-20</td><td>10</td><td>28</td><td>0</td><td>24</td><td>31</td><td>36</td><td>33.4</td><td>24</td><td>26</td><td>24.9</td></tr><tr><td>N 10-28-1-10-20</td><td>10</td><td>28</td><td>1</td><td>21</td><td>25</td><td>35</td><td>30.6</td><td>22</td><td>24</td><td>23.2</td></tr><tr><td>N 10-28-2-10-20</td><td>10</td><td>28</td><td>2</td><td>20</td><td>25</td><td>33</td><td>29</td><td>22</td><td>27</td><td>23.5</td></tr><tr><td>N 10-28-3-10-20</td><td>10</td><td>28</td><td>3</td><td>20</td><td>25</td><td>33</td><td>29.9</td><td>22</td><td>27</td><td>23.3</td></tr><tr><td>N 10-28-4-10-20</td><td>10</td><td>28</td><td>4</td><td>20</td><td>23</td><td>34</td><td>28</td><td>21</td><td>25</td><td>22.6</td></tr><tr><td>N 10-33-0-10-20</td><td>10</td><td>33</td><td>0</td><td>25</td><td>29</td><td>33</td><td>30.8</td><td>26</td><td>28</td><td>27.2</td></tr><tr><td>N 10-33-1-10-20</td><td>10</td><td>33</td><td>1</td><td>22</td><td>28</td><td>33</td><td>30.3</td><td>23</td><td>27</td><td>24.9</td></tr><tr><td>N 10-33-2-10-20</td><td>10</td><td>33</td><td>2</td><td>21</td><td>28</td><td>33</td><td>30.7</td><td>22</td><td>28</td><td>25.1</td></tr><tr><td>N 10-33-3-10-20</td><td>10</td><td>33</td><td>3</td><td>21</td><td>26</td><td>34</td><td>29.8</td><td>24</td><td>26</td><td>24.8</td></tr><tr><td>N 10-33-4-10-20</td><td>10</td><td>33</td><td>4</td><td>21</td><td>24</td><td>31</td><td>27.8</td><td>23</td><td>26</td><td>24.6</td></tr><tr><td>N 10-38-0-10-20</td><td>10</td><td>38</td><td>0</td><td>28</td><td>36</td><td>41</td><td>38.2</td><td>28</td><td>32</td><td>30</td></tr><tr><td>N 10-38-1-10-20</td><td>10</td><td>38</td><td>1</td><td>24</td><td>32</td><td>35</td><td>33.7</td><td>28</td><td>33</td><td>29.1</td></tr><tr><td>N 10-38-2-10-20</td><td>10</td><td>38</td><td>2</td><td>23</td><td>31</td><td>37</td><td>34.1</td><td>25</td><td>30</td><td>27.6</td></tr><tr><td>N 10-38-3-10-20</td><td>10</td><td>38</td><td>3</td><td>23</td><td>31</td><td>37</td><td>33.2</td><td>25</td><td>28</td><td>26.9</td></tr><tr><td>N 10-38-4-10-20</td><td>10</td><td>38</td><td>4</td><td>23</td><td>31</td><td>36</td><td>33.7</td><td>26</td><td>29</td><td>27.5</td></tr><tr><td>N 15-28-0-10-20</td><td>15</td><td>28</td><td>0</td><td>24</td><td>28</td><td>34</td><td>30.1</td><td>24</td><td>26</td><td>24.8</td></tr><tr><td>N 15-28-1-10-20</td><td>15</td><td>28</td><td>1</td><td>22</td><td>28</td><td>35</td><td>30.4</td><td>23</td><td>28</td><td>24.5</td></tr><tr><td>N 15-28-2-10-20</td><td>15</td><td>28</td><td>2</td><td>22</td><td>28</td><td>32</td><td>29.5</td><td>22</td><td>28</td><td>23.8</td></tr><tr><td>N 15-28-3-10-20</td><td>15</td><td>28</td><td>3</td><td>22</td><td>26</td><td>33</td><td>30.1</td><td>23</td><td>26</td><td>24.2</td></tr><tr><td>N 15-28-4-10-20</td><td>15</td><td>28</td><td>4</td><td>22</td><td>26</td><td>33</td><td>29</td><td>23</td><td>26</td><td>24</td></tr><tr><td>N 15-33-0-10-20</td><td>15</td><td>33</td><td>0</td><td>31</td><td>37</td><td>44</td><td>39.9</td><td>31</td><td>35</td><td>32.3</td></tr><tr><td>N 15-33-1-10-20</td><td>15</td><td>33</td><td>1</td><td>28</td><td>35</td><td>43</td><td>39.9</td><td>28</td><td>31</td><td>29.3</td></tr><tr><td>N 15-33-2-10-20</td><td>15</td><td>33</td><td>2</td><td>26</td><td>35</td><td>43</td><td>37.8</td><td>27</td><td>30</td><td>28.3</td></tr><tr><td>N 15-33-3-10-20</td><td>15</td><td>33</td><td>3</td><td>25</td><td>34</td><td>40</td><td>37.6</td><td>28</td><td>31</td><td>29.5</td></tr><tr><td>N 15-33-4-10-20</td><td>15</td><td>33</td><td>4</td><td>25</td><td>32</td><td>40</td><td>36.1</td><td>26</td><td>32</td><td>28.7</td></tr><tr><td>N 15-38-0-10-20</td><td>15</td><td>38</td><td>0</td><td>34</td><td>40</td><td>50</td><td>46</td><td>34</td><td>36</td><td>35.1</td></tr><tr><td>N 15-38-1-10-20</td><td>15</td><td>38</td><td>1</td><td>29</td><td>41</td><td>50</td><td>45.4</td><td>31</td><td>36</td><td>32.6</td></tr><tr><td>N 15-38-2-10-20</td><td>15</td><td>38</td><td>2</td><td>28</td><td>40</td><td>47</td><td>42.9</td><td>30</td><td>36</td><td>32.9</td></tr><tr><td>N 15-38-3-10-20</td><td>15</td><td>38</td><td>3</td><td>28</td><td>41</td><td>46</td><td>43</td><td>30</td><td>33</td><td>31.7</td></tr><tr><td>N 15-38-4-10-20</td><td>15</td><td>38</td><td>4</td><td>28</td><td>38</td><td>46</td><td>42.8</td><td>31</td><td>36</td><td>32.8</td></tr></tbody><tfoot><tr><td>Average</td><td></td><td></td><td></td><td></td><td>24.3</td><td>31.1</td><td>37.9</td><td>34.5</td><td>25.7</td><td>29.5</td><td>27.3</td></tr></tfoot></table>

## 5. CONCLUSIONS

In this paper we considered a problem arising in the monitoring of a fleet of autonomous electric vehicles for which we defined the scheduling that minimizes the overall number of stops performed to serve a set of pickup and delivery requests. The problem turned out to be particularly difficult to solve exactly: we proposed two different models and used them to derive bounds and determine the optimal
solution for instances with up to 38 requests. We also developed a fast and effective hybrid heuristic that is also suitable for the solution of on-line or semi-online versions of the problem.

To the best of our knowledge this problem was never studied before in the literature, therefore our work represent a starting point for further research, particularly with respect to exact methods. Clearly more sophisticated optimization approaches based on the Branch-and-Price scheme can attempt the solution of larger instances providing also tighter bounds.

Another direction for further research lies on the possibility of considering different network topologies such as trees or more complex and connected ones that may introduce the need of explicitly considering routing as part of the problem. Also additional problem characteristics, such as time windows, or the battery charging times, may add interesting components to the problem that are relevant in practical applications.

Finally, the actual inclusion of algorithms in the *on-line* context may require the evaluation of algorithms with better or guaranteed performance in real time.

## REFERENCES

[1] H. Bast, D. Delling, A. Goldberg, M. Muller-Hannemann, T. Pajor, P. Sanders, D. Wagner, R. Werneck (2014). Route planning in transportation network. Technical Report MSR-TR 2014-4-8, Microsoft Research

[2] R. Boerndorfer, M. Groetschel, F. Klostermeiner, C. Kuttner (1999). Telebus Berlin: Vehicle routing scheduling in a dial a ride system. In N. Wilson, editor, *Computer-Aided Transit Scheduling*, vol. 471 Lecture Notes in Economics and Mathematical Systems, 391-422, Springer Berlin Heidelberg.

[3] B. Boyaci, K. Zografos (2015). An optimization framework for the development of efficient one way car-sharing systems. *Europ. J. Oper. Res.* 2, 718-733.

[4] P. Coll, J. Marenco, I. Diaz, I., P. Zabala (2002). Facets of the graph coloring polytope. *Ann. Oper. Res.* 116, 79-90.

[5] J-F. Cordeau, G. Laporte (2007). Dial-a-Ride: models and algorithms. *Ann. Oper. Res.* 153, 29-46.

[6] J-F. Cordeau (2006). A branch and cut algorithm for the Dial-a-Ride. *Oper. Res.* 54, 573-586.

[7] J-F. Cordeau, M. Gendreau, G. Laporte, J.Y. Potvin, F. Semet (2002). A guide to vehicle routing heuristics. *J. Op. Res. Soc.* 53, 512-522.

[8] D. Cornaz, V. Jost (2008). A one to one correspondence between coloring and stable sets. *Oper. Res. Letters* 36, 673-676.

[9] W.E. de Paepe, J.K. Lenstra, J. Sgall, R.A. Sitters, L. Stougie (2004). Computer aided complexity classification of Dial-a-Ride Problems. *INFORMS J. Comp.* 22, 1130-1152.

[10] K.F. Doerner J-J. Salazar-González (2014). Pickup-and-Delivery Problems for People Transportation. In P. Toth and D. Vigo, editors, *Vehicle Routing: Problems, Methods and Applications*, Ch. 6, 193-212. SIAM Philadelphia, MD.

[11] T.A. Feo, M.G.C. Resende (1989). A probabilistic heuristic for a computationally difficult set covering problem. *Op. Res. Lett.* 8, 67-71.

[12] M.R. Garey, D.S. Johnson (1979). *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman & Co. New York, NY.
[13] M.C. Golumbic (2004). *Algorithmic Graph Theory and Perfect Graphs*. 2nd edition, Elsevier, Amsterdam.

[14] P. Hansen, M. Labbe, D. Schindl (2009). Set covering and packing formulations of graph coloring: algorithms and first polyhedral results. *Discr. Opt.* 6, 135-147.

[15] L. Higgins, J.B. Laughlin, K. Turnbull (2000). Automatic vehicle location and advanced paratransit at Houston METROLift. in *Proc of the 2000 Transport. Research Board Conf.*, Washington DC.

[16] Y. Luo, P. Schonfeld (2007). Reinsertion heuristic for static Dial-a-Ride. *Trans. Res. B* 41, 736-755.

[17] E. Malaguti, M. Monaci, P. Toth (2011). An exact approach for the vertex coloring problem. *Discr. Opt.* 8, 174 - 190.

[18] A. Mehrotra, M.J. Trick (1996). A column generation approach for graph coloring. *INFORMS J. Comp.* 8, 344-354.

[19] I. Mendez-Diaz, P. Zabala (2006). A cutting plane algorithm for graph coloring. *Discr. Appl. Math.* 154, 826-847.

[20] K. Palmer, M. Dessouky, T. Abelmaguid (2004). Impact of management practices and advanced technologies on demand responsive transit systems. *Trans. Res. A* 38, 495-509.

[21] C.H. Papadimitriou, M. Yannanakis (1979). Scheduling interval ordered tasks. *SIAM J. Comp.* 8, 405-409.

[22] A. Quilliot, S. Deleplanque (2015). Constraint propagation for the Dial-a-Ride problem with split loads, in S. Fidanovka, editor, *Recent Advances in Computational Optimization*, series Studies in Computational Intelligence 470, 31-50, Springer International Publishing, Switzerland.

[23] M.G.C. Resende, C.C. Ribeiro (2003). *Greedy randomized adaptive search procedures*. In F. Glover and G. Kochenberger, editors, *Handbook of Metaheuristics*, 219-249, Kluwer Academic Publishers, Norwell, MA.

[24] D. Pisinger, S. Ropke (2007). A general heuristic for vehicle routing problems. *Comp. & O.R.* 34, 2403-2435.

[25] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, G. Dueck (2000). Record breaking optimization results-using the ruin & recreate principle, *Journal of Computational Physics* 159 139-171.
# APPENDIX: A LAGRANGEAN LOWER BOUND FOR THE SNMP MODEL

A possible way of obtaining better bounds for the SNMP ILP model with respect to the continuous relaxation is represented by defining a Lagrangean relaxation of the coupling constraints (4), which relates vectors Z and T. The resulting Lagrangean function Lag(Z, T, λ) is:

$$ 
\begin{aligned}
Lag(Z, T, \lambda) &= \sum_{k=1}^{K} \sum_{i=0}^{n} T_{k,i} - \sum_{k=1}^{K} \sum_{i=0}^{n} \sum_{h=0}^{H} \lambda_{i,k,h} (T_{k,i} - Z_{i,k,h}) = \\
&= \sum_{k=1}^{K} \sum_{i=0}^{n} T_{k,i} \left( 1 - \sum_{h=0}^{H} \lambda_{i,k,h} \right) + \sum_{k=1}^{K} \sum_{i=0}^{n} \sum_{h=0}^{H} \lambda_{i,k,h} Z_{i,k,h}.
\end{aligned}
$$

The minimization of Lag(Z, T, λ) can be easily obtained through separation. The restriction of the sub-problem to vector T is trivial. The restriction of the sub-problem to vector Z instead requires to compute Z = (Z_{j,k,h}, j = 1, ..., m, k = 1, ..., K, h = 0, ..., H) with {0, 1} values, which is a feasible solution of LV(K), and which minimizes the quantity $\sum_{k=1}^{K} \sum_{i=0}^{n} \sum_{h=0}^{H} \lambda_{i,k,h} Z_{i,k,h}$. As discussed in Section 3.1, such a problem can be handled rather efficiently by CPLEX, especially in the case when H = 0, that means when it appears as an extension of the interval graph coloring problem.

However the lower bound which results from such Lagrangean relaxation proved experimentally to be not satisfactory, and hardly improves the lower bound which derives from the continuous relaxation. This may be explained by the fact that the integrality constraint has no impact on the optimal value of the above sub-problem on T; as for the sub-problem on Z, the error induced by relaxing the integrality constraint on Z is not very high (usually not larger than 15% or 20%). As a consequence, the gap between Inf_{Z, T integral} Lag(Z, T, λ) and Inf_{Z, T rational} Lag(Z, T, λ) usually does not exceed 10%. But Sup_λ Inf_{Z, T rational} Lag(Z, T, λ) is exactly equal (by Duality Theory) to the optimal value of the continuous relaxation of SNMP. It follows that, in most cases, the value Sup_λ Inf_{Z, T integral} Lag(Z, T, λ) does not improve this value by more than 5% to 10%, and so does not provides us with a significantly better lower bound than the standard one.