# Enhanced Iterated local search for the technician routing and scheduling
problem

Ala-Eddine Yahiaoui  Sohaib Afifi  Hamid Allaoui  Univ. Artois, UR 3926,
Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A),
Béthune, F-62400, France, e-mail:
<EMAIL_ADDRESS>Université
Laval, Faculté des sciences et de génie, 1065 Avenue de la Médecine, QC G1V
0A6, e-mail<EMAIL_ADDRESS>
###### Abstract

Most public facilities in the European countries, including France, Germany,
and the UK, were built during the reconstruction projects between 1950 and
1980. Owing to the deteriorating state of such vital infrastructure has become
relatively expensive in the recent decades. A significant part of the
maintenance operation costs is spent on the technical staff. Therefore, the
optimal use of the available workforce is essential to optimize the operation
costs. This includes planning technical interventions, workload balancing,
productivity improvement, etc. In this paper, we focus on the routing of
technicians and scheduling of their tasks. We address for this purpose a
variant of the workforce scheduling problem called the technician routing and
scheduling problem (TRSP). This problem has applications in different fields,
such as transportation infrastructure (rail and road networks),
telecommunications, and sewage facilities. To solve the TRSP, we propose an
enhanced iterated local search (eILS) approach. The enhancement of the ILS
firstly includes an intensification procedure that incorporates a set of local
search operators and removal-repair heuristics crafted for the TRSP. Next,
four different mechanisms are used in the perturbation phase. Finally, an
elite set of solutions is used to extensively explore the neighborhood of
local optima as well as to enhance diversification during search space
exploration. To measure the performance of the proposed method, experiments
were conducted based on benchmark instances from the literature, and the
results obtained were compared with those of an existing method. Our method
achieved very good results, since it reached the best overall gap, which is
three times lower than that of the literature. Furthermore, eILS improved the
best-known solution for $34$ instances among a total of $56$ while maintaining
reasonable computational times.

###### keywords:

Maintenance, technician routing and scheduling, iterated local search, elite
solutions, diversification, intensification.

††journal: Computers & Operations Research

##  1 Introduction

Workforce scheduling is a relevant research topic in transportation and
logistics, since it can be applied in many fields [6], such as technician
routing and scheduling, manpower allocation, security personnel routing and
rostering and home care services. Interest in this research area is also
driven by the importance of ensuring an efficient and satisfying client
service policy after a product delivery, which substantially contributes to
the maintain of the market share [15]. The workforce scheduling problem
focuses on the elaboration of models and solution methods for planning in-
field personnel activities, including their mobilization between different
locations. Moreover, the problem consists in the elaboration of workload
allocation and routing of technician crews, as well as the scheduling of their
operations at the level of task locations, which include industrial
facilities, patient homes, telecommunication infrastructure, etc. In addition,
many objectives and challenges may be considered, such as increasing
productivity, reducing transportation costs, increasing the number of
fulfilled tasks, reducing outsourcing costs, reducing overtime, balancing
technician workloads, etc. Furthermore, to have a reliable and satisfactory
organization of the workforce in the field, several requirements and
constraints have to be met : in addition to the vehicle routing problem
classical constraints (capacity and time windows) and work regulations (breaks
and workload). Other aspects could be taken into consideration such as skill
types and competency levels required by each task, precedence constraints
between several tasks for the same customer, priorities, limited crews of
technicians, and sometimes the use of specific tools and spare parts.

In this paper, we address a variant of the technician routing and scheduling
problem (TRSP) presented by Pillac et al.[24]. Given a crew of technicians and
a set of tasks to fulfill at their respective locations, the goal is to assign
subsets of tasks to individual technicians and construct the routes for each
technician in such a way that the total duration of the routes is minimized.
Several types of constraints must be respected by each route. First, given the
multi-depot structure of the TRSP, where each technician is associated with
their home depot where they should start and finish the allocated route. A
second type of constraints is the compatibility between technicians and tasks,
where each task requires proficiency in a specific type of skill by the
assigned technician, whereas a given technician may not have necessary the
proficiency in all those skills. Both previous conjugated constraints give
rise to the site-dependent constraint. Another type of constraints is resource
requirement, where each task requires a certain amount of resources of
different types. Two general resource classes are considered: tools and spare
parts. While the former is renewable, the latter is non-renewable. Moreover,
each technician starts the journey from his home depot with a set of tools and
an initial inventory of spare parts. However, in the cases where a technician
does not have enough tools or spare parts to continue the journey, the
inventory can be replenished by visiting a central depot once at some point in
the route, where an infinite stock of tools and spare parts is available.
Finally, as the TRSP is an extension of the VRPTW, a time window is associated
with each task. In addition, each home depot has opening and closing times.

The main contribution of this paper is the proposal of an enhanced iterated
local search (eILS) for the TRSP. It incorporates several procedures that are
used during the intensification and perturbation phases. First, the
intensification phase combines a set of removal-repair heuristics and local
search operators. Second, several perturbation procedures are incorporated
into the eILS. They differ in whether they are based on remove-repair
operators or local search-based deterioration. In both cases, the criteria
used may also differ, whether based on travel costs or duration. Hence, four
perturbation mechanisms are introduced. On the other hand, an Elite set of
solutions is used to enhance the intensification and diversity management of
the eILS. The extensive intensification approach is inspired by the proximate-
optimality principle, and is achieved by allowing each solution to be the
starting point of several ILS phases. Whereas diversity management is achieved
by maintaining a relatively diverse population of solutions and discarding
duplicates solutions that are too close. At the lower level, we propose a new
local search operator called SwapSequence operator. It interchanges two
sequences of $k$ and $k^{\prime}$ visits between two different routes. A new
removal operator is also proposed. It is derived from the related removal
operator introduced in [27], where instead of removing a set of individual
tasks, it removes sequences of tasks. A key feature of the eILS is the
implementation of a time-constant moves evaluation and feasibility tests. This
includes time window feasibility checks, renewable and nonrenewable resource
availability tests, technician skills compatibility tests and duration
evaluation. Moreover, several speed-up techniques have been introduced in the
eILS to achieve computational efficiency.

The remainder to this paper is organized as follows. A brief state-of-the-art
for the general workforce scheduling problem is proposed in Section 2. In
Section 3 we describe TRSP by introducing the necessary notation as well as an
illustrative example. Our metaheuristic approach proposed for TRSP is
presented in Section 4. The computational tests and detailed results, are
presented and discussed in Section 5. Finally, we present some conclusions
drawn from this study and discuss relevant perspectives and extensions for
TRSP.

##  2 Related work

In this paper, we study a variant of the workforce scheduling problem where a
set of technicians need to fulfill tasks at different locations. This general
class of problems is called the workforce scheduling and routing problem
(WSRP) [6]. A key characteristic of this class of problems is that moving from
one location to another takes a significant amount of time, therefore,
minimizing travel time will substantially contribute to cost reduction and
improved productivity. Applications of these problems in real life can be
found in several sectors, such as home health-care services and infrastructure
maintenance operations.

Most WSRP variants found in the literature are extensions for the VRP with
time windows (VRPTW). In this class of problems, each point of interest or
customer is associated with a time window that specifies when the vehicle
should start the service [10]. The main objective function of VRPTW is cost
minimization. Other variants minimize first the number of vehicles before
optimizing travel costs. Another objective function that is less frequently
used in the literature is the minimization of the duration [11]. In addition
to the basic VRPTw, WSRP problems may also consider additional characteristics
and constraints, such as multiple depots, multi-trips, site-dependent
considerations, etc. In home health care for example, Li et al. presented in
[19] a variant of the technician routing and scheduling problem with workload
balance and outpatient service performed by doctors. Bredstrom & Ronnqvist.
(2007) [4] introduced a new variant of the VRPTW, with additional
synchronization constraints between pairs of caregivers on a selected subset
of patients. Another variant of the VRPTW with profits and synchronization
constraints has also been studied in [36], with an application in the context
of fire-fighting. Several studies in recent years have focused on the
integration of uncertainties into the workforce scheduling problem. Chen et
al. (2016) [7] considered uncertain service times, and proposed a branch-and-
cut approach to solve the problem. Shi et al. (2019) [28] proposed a robust
optimization model with uncertain service and travel times and proposed a
metaheuristic and Monte Carlo simulation to solve the problem.

One of the first applications of VRP in the field of workforce scheduling was
reported by Weigel and Cao. (1999) [33]. The authors proposed the use of VRPTW
to model technician dispatching and home delivery problems faced by a well-
known retailer. To solve this problem, they proposed a tabu search algorithm
that combines intra and inter-route improvement procedures after the initial
assignment of requests to technicians. Xu and Chiu (2001) [35] addressed the
field technician scheduling problem inspired by the telecommunication
industry. In the studied problem, the objective is to maximize the preferences
when assigning tasks to technicians, as well as the minimization of the work
duration. The authors proposed several approaches to solve the problem,
namely, a greedy randomized adaptive search procedure (GRASP), upper bounds,
relaxation schemes and an extended mathematical model. Tang et al. (2007) [30]
modeled a maintenance-scheduling problem on a horizon of several days as
several multiple-tour maximum collection problems with time-dependent rewards.
The rewards decrease overtime to favor faster scheduling tasks. The authors
proposed solving the problem using a tabu search heuristic. Bostel et al.
(2008) [1] addressed a field force planning and routing problem solved on a
multi-period time horizon and uses a rolling horizon approach, with an
application in the field of water treatment and distribution. A memetic
algorithm and a column generation-based heuristic is proposed to deal with the
static version. An adapted procedure is proposed to address the dynamic
version of the problem. An exact method based on the column generation
approach was proposed for the same problem in Tricoire et al. 2013 [31].

The TRSP gained more attention after the French Operations Research Society
(ROADEF) dedicated the yearly challenge to addressing the technician and
intervention scheduling problem proposed by a well-known telecommunication
company [12]. In this problem, each task is associated with a priority level
and requires a certain level of proficiency in a set of skills such that it
can be performed by a technician. Technicians are grouped into teams and
dispatched to fulfill tasks without the consideration of travel times. The
objective of the problem is to execute tasks as early as possible depending on
their priority levels. Cordeau et al. (2010) [9] developed an ALNS method
whereas Hashimoto et al. (2011) [14] proposed a GRASP method. Although the
problem does not consider any routing decisions, it has been the origin of
several variants of WSRP. Kovacs et al. (2012) [17] proposed the service
technician routing and scheduling problem (STRSP) which is a generalization of
the variant proposed in [12], because it takes into consideration the
optimization of travel times. Moreover, in the case where it is not possible
to execute all the tasks, an outsourcing cost is associated with each
unfulfilled task. Two variants are investigated: the first is with team
building and the other is without team building. The authors proposed a
generic ALNS approach for both variants, which were validated on new benchmark
instances derived from the one proposed in [12]. Later, Xie et al. (2017) [34]
tackled the variant without team building in [17] and proposed an iterated
local search algorithm that succeeded in finding several new best-known
solutions for the problem. Mathlouthi et al. (2018) [22] introduced a new
variant of the TRSP. The main features are the consideration of multiple time
windows per task, possibility for technicians to break during the day and
possibility of picking up some special types of spare parts that are available
only at a subset of central depots. The authors proposed a mathematical
formulation that was tested on small-size instances. To tackle large-size
instances, the same authors proposed in Mathlouthi et al. (2018) [21] a tabu
search heuristic enhanced by an adaptive memory mechanism.

Zamorano and Stolletz (2017) [37] proposed a new variant of the TRSP that
combines team building and multi-period features. This variant was inspired by
real-life problems faced by an external maintenance provider specializing in
forklifts. The authors proposed a mixed-integer program and branch-and-price
algorithm while considering different sub-problem formulations during the
column generation phase. Tests are carried out on a set of artificial
instances and real-world data. Pekel. (2020) [23] addressed the same problem
presented in [37]. The author proposed an improved particle swarm optimization
(IPSO) algorithm and compared its results with those of a branch-and-cut
algorithm. Guastaroba et al. (2020) [13] presented another variant of the WSRP
with multiple periods and team building. To solve this problem, they proposed
a mixed-integer program and two meta-heuristic methods. The first method is a
math-heuristic approach based on ALNS whereas the second is a three-phase
decomposition algorithm.

##  3 Problem description

We consider a set of technicians/vehicles $\mathcal{K}=\\{0,\ldots,K-1\\}$,
where $|\mathcal{K}|=K$, and a set of tasks $\mathcal{R}=\\{0,\ldots,N-1\\}$,
where $|\mathcal{R}|=N$. In the following, the two words, technician and
vehicle are used interchangeably. Each technician $k\in\mathcal{K}$ starts
from its home depot $o_{k}\in O=\\{1+k|k\in K\\}$ and ends at the same depot.
A central depot ”$0$” is open to technicians to replenish their inventory of
spare parts and necessary tools. We define $\delta_{0}$ as the replenishment
time at the central depot. Each task $i$ is associated with a location
$u_{i}\in U=\\{K+1+i|i\in\mathcal{R}\\}$, a service time duration $\delta_{i}$
and a time window $[e_{i},l_{i}]$, defining earliest and latest service
starting times. In addition, for each arc $(i,j)|i,j\in V=O\cup U\cup\\{0\\}$,
we associate travel time $t_{ij}$, which is the same for all vehicles. We also
consider several types of spare parts $T=\\{1,\ldots,|T|\\}$, tools
$P=\\{1,\dots,|P|\\}$ and skills $Q=\\{1,\dots,|Q|\\}$. Each task
$i\in\mathcal{R}$ requires $d_{ip}$ units of spare parts of type $p\in P$, and
the tool $t\in T$ if the Boolean $b_{it}$ is true. We also set the constant
$a_{iq}$ to 1 if task $i$ requires skill $q\in Q$. For each vehicle
$k\in\mathcal{K}$, we denote the initial inventory of spare parts of type
$p\in P$ by $v^{k}_{p}$, whereas a Boolean $w^{k}_{t}$ is set to 1 if a tool
$t\in T$ is in the vehicle starting from the depot. We also set a constant
$y^{k}_{q}$ to 1 if the technician possesses a skill $q\in Q$. Because skills
are intrinsic to each technician, we can define a compatibility list of
technicians for each task. Hence, we denote for each task $i\in\mathcal{R}$,
the set of compatible technicians by $K_{i}$. Finally, we associate for each
home depot $o_{k}|k\in\mathcal{K}$ an opening and a closing time window
$[e_{k},l_{k}]$.

##  4 Enhanced iterated local search

We provide in this section a detailed description of the eILS.

###  4.1 Low-level heuristics

In this section, we propose a detailed description of the low-level
heuristics/operators used to describe the different components of the eILS.

####  4.1.1 Remove-Repair based perturbation

Given an input solution and a perturbation parameter $D_{max}$, this procedure
removes a random number of tasks between $1$ and $D_{max}$, and then applies
the best insertion algorithm to repair the solution.

##### Best insertion algorithm

This heuristic iteratively inserts tasks in the solution at their best
positions according to one of the two evaluation criteria : the duration or
the travel costs. At each iteration, the unscheduled list of tasks is
computed, and all feasible insertions in compatible vehicles are computed for
each task. If no feasible insertion for a given task is found in a compatible
vehicle, then the best insertion algorithm looks for feasible insertions while
considering a pass by the central depot for replenishment. The task with the
best insertion is selected and scheduled at its respective position. This
process is iterated until all tasks are scheduled or no feasible insertions
are found.

##### Removal operators

Given a solution, removal operators remove a random number of tasks between
$1$ and $D_{max}$.

  * 1.

Random Removal : randomly selects the tasks and removes them from their
respective routes.

  * 2.

Worst Removal : iteratively selects the task yielding the maximum cost
reduction. Two versions are available depending on the move evaluation : based
on duration or on travel costs.

  * 3.

Sequence related removal : This removal heuristic is inspired by the related
removal operator introduced in Shaw et al. [27] as well as the SISR operator
in [8]. The basic idea of this operator is to remove sub-sequences of visits
from distinct routes so that the best insertion algorithm re-inserts them, and
hopefully, constructs promising sub-sequences that improve the objective value
of the solution. This approach proved to be efficient, especially on problems
where tasks have tight time windows.

In the first step, a set of tasks are selected from different routes using the
related removal operator of Shaw et al. [27]. This operator takes into
consideration the spatial and temporal relatedness of those tasks. We call
these tasks seeds. In the second step, a sub-sequence of visits occurring
after the seeds are removed together with the seeds. Fig. 1 simulates the
impact of the sequence-related removal operator. The number of removed tasks
is initialized by 3, and varies according to the perturbation parameter (See
Section 4.2).

Figure 1: Sequence-related removal process

It is noteworthy to mention that, after every task is removed from a given
route, a test is systematically performed to verify whether the visit to the
central depot is still relevant, or the initial inventory of tools and spare
parts satisfies the requirements of the remaining tasks in the route.

Based on these operators, Algorithm 1 presents the skeleton of a remove-repair
based perturbation procedure.

input : Solution $S$, perturbation parameter $D_{max}$

1 $unscheduled\leftarrow getUnscheduledTasks(S)$

2 $r\leftarrow\mathcal{U}(1,3)$

3 if  _$(r=1)$_ then $tmpUnscheduled\leftarrow RandomRemoval(S,D_{max})$

4 else if  _$(r=2)$_ then $tmpUnscheduled\leftarrow WorstRemoval(S,D_{max})$

5 else $tmpUnscheduled\leftarrow SeqRelatedRemoval(S,D_{max})$

6 $(S,unscheduled)\leftarrow BestInsertion(S,unscheduled)$

7 $(S,tmpUnscheduled)\leftarrow BestInsertion(S,tmpUnscheduled)$

8 $unscheduled\leftarrow unscheduled\cup tmpUnscheduled$

return $S$

Algorithm 1 Removal/repair perturbation procedure

####  4.1.2 Local search operators

The local search procedure is implemented as a variable neighbourhood descent
search (VNDS) procedure. This component is composed of two sets of local
search operators, inter-route search operators and intra-route search
operators.

The inter-route search operators set $\mathcal{N}^{e}$ comprises three (03)
operators.

  * 1.

2-Opt* : this operator explores the possibilities of exchanging two arcs
$(i,j)$ and $(k,l)$ located in two distinct routes by arcs $(i,l)$ and
$(k,j)$. Because in the TRSP each vehicle should start and end at the same
depot, exchanging arcs between the last visits and the depots should be taken
into consideration during moves evaluation.

  * 2.

Swap-relocate : this operator explores the relocation of a task or an arc to
another route, either by placing it between two consecutive visits or by
interchanging it with a task in the second route. Moreover, we consider the
possibility of reversing the arc before being relocated. This gives raise to
six (06) different movements. $Swap-relocate(1,0)$ is a simple relocation of a
task from one route to another. $Swap-relocate(1,1)$ is a swap of two tasks
visited in two distinct routes. $Swap-relocate(2,0)$ is a relocation of an arc
whereas $Swap-relocate(2,1)$ is an interchange of an arc with a task from
another route. Finally, $Swap-relocate(2,0)^{r}$ and $Swap-relocate(2,1)^{r}$
perform a reverse of the arc before performing the relocation or the
interchange.

  * 3.

Swap-sequence : this operator is similar to Swap-relocate, except that it does
not consider the reversal of sub-sequences. Several combinations are possible
: Swap-sequence(2,2), Swap-sequence(3,k) and Swap-sequence(4,k), where the
length of second subsequence $k$ is less than or equal to the first
subsequence.

Regarding the intra-route search operators set $\mathcal{N}^{a}$, four (04)
operators are considered :

  * 1.

Exchange1 : this operator explores the possibilities of exchanging the
position of two tasks $i$ and $j$ located in the same route.

  * 2.

Shift1 : this operator tries to move a given task $i$ forward and backward to
another position in the same route.

  * 3.

R-Opt : this operator tries to move a sequence of two or three visits forward
and backward in the same route.

  * 4.

2-Opt : this operator explores the possibility to improve a given route by
replacing the two arcs $(i,j)$ and $(k,l)$ by the arcs $(i,k)$ and $(j,l)$;
this implies the reversal of a sub-sequence between visits $j$ and $k$, $j$
and $k$ included.

###  4.2 Iterative remove-repair heuristic

We also propose in this paper a fast heuristic called iterative removal/repair
procedure (IRRP). This fast heuristic is used in several parts of the eILS.
Algorithm 2 outlines the general heuristic structure. The main difference
between IRRP and classic ILS is that it does not contain an intensification
phase. The algorithm starts from an arbitrary solution (empty, partial or a
complete one) and iteratively performs a removal/repair perturbation phase
(See Section 4.1.1). Once a new solution is constructed, it undergoes first an
acceptance process to verify whether the incumbent solution is going to be
updated. Subsequently, if an improvement in the objective function is
achieved, $S_{best}$ is updated. Also, the value of $D_{max}$ is updated at
the end of each iteration.

input : Solution $S$.

1 $S_{Best}\leftarrow S$

2 $S_{Incumb}\leftarrow S$

3 $init(D_{max})$

4 while  _$(!StopCondition)$_ do

5 $S_{Tmp}\leftarrow removalRepairPerturbation(S_{Incumb},D_{max})$ (See
Section 4.1.1)

6

7 if  _$(AcceptSolution(S_{Tmp}))$_ then $S_{Incumb}\leftarrow S_{Tmp}$

8

9 if  _$(f(S_{Incumb}) <f(S_{Best}))$_ then $S_{Best}\leftarrow S_{Incumb}$

10 $Update(D_{max})$

11

12 end while

return $S_{Best}$

Algorithm 2 Iterative removal/repair procedure

###  4.3 Iterated local search

The ILS is a metaheuristic scheme introduced by Lourenço et al. (2003) [20].
This approach is known by its high potential, ease of implementation and few
number of parameters to tune [18]. A typical ILS algorithm is generally
composed of three components: generation of an initial solution, perturbation
phase, and local search procedure. The perturbation and local search
procedures are iteratively applied to construct a new solution at each
iteration. Instead of starting each time from scratch or the same base
solution, they use the solution of the previous iteration as a starting point.
The role of the perturbation phase is to prevent the metaheuristic from being
trapped in local optima, whereas the local search aims at finding new local
optimal solutions. The series of local optima produced by this process can be
considered as a single chain of solutions followed by the ILS. Algorithm 5
depicts the general scheme of the ILS. $D_{max}$ is called the perturbation
degree and it is provided as a parameter to the perturbation procedure. It is
initialized with a small value, and then incremented after each iteration
without improvement. It is then reset to its initial value after each
improvement. The stopping condition used in the ILS is $N$ iterations without
improvement. The best solution is updated after each improvement of the total
duration (line 7). It is noteworthy to mention that the fitness of partial
solutions is computed as the sum of its total duration and the number of
unscheduled tasks multiplied by a penalty. In our case, we set the penalty to
$10^{3}$.

input : Initial solution $S$.

1 $S\leftarrow Intensification(S)$ (See Section 4.3.1)

2 $S_{ILS}\leftarrow S$

3 $D_{max}\leftarrow D_{0}$

4 while  _$(!StopCondition)$_ do

5 $S\leftarrow Perturbation(S,D_{max})$ (See Section 4.3.2)

6 $S\leftarrow Intensification(S)$ (See Section 4.3.1)

7 if  _$(f(S) <f(S_{ILS}))$_ then

8 $S_{ILS}\leftarrow S$

9

10 end if

11 $Update(D_{max})$

12 end while

return $S_{ILS}$

Algorithm 3 Iterated local search algorithm

An important issue with the ILS, is that by moving from one local optimum to
another after each iteration, the exploration of the surrounding neighborhood
of each solution is limited, which may cause the ILS to miss some good
improving solutions. This aspect is pointed out by the proximate-optimality
principle (POP) [2] which suggests that good solutions are close to each
other. To address this drawback, we further enhance the ILS by storing a set
of elite solutions that are supplied by local optima found so far, and used
later as a base solution for the ILS (See Section 4.4).

####  4.3.1 Intensification phase

A key feature of our approach is its reliance on an intensification phase that
combines IRRP with a set of local search operators.

The procedure is a version of IRRP (see Section 4.2) that starts from a
complete or a partial solution. Intensification is achieved by fixing
$D_{max}$ to a relatively small value (see Section 5.2), and performing no
more than $N$ iterations. In this version of the IRRP, the solution provided
int the input is maintained as the incumbent solution during all the process
(Algorithm 2, line 6), and it is only updated if the objective value is
improved. A small and fixed value of $D_{max}$ (Algorithm 2, line 8) allows
the $IRRP$ to extensively explore the neighborhood of the current solution.
During the removal repair perturbation phase, the aim is to improve the total
duration of the incumbent solution. It is noteworthy to mention that we
consider one removal operator rather than three (see Section 4.1.1) in the
IRRP used during intensification, which is the random removal operator.

Algorithm 4 shows a pseudo code for the intensification procedure. The
algorithm sequentially executes the operators one after another and iterates
as long as there is at least one of the operators that succeeds in improving
the current solution. After preliminary experimentation, $applySwap-
sequence(S)$ only calls Swap-sequence(3,k), whereas $applySwap-relocate(S)$
explores all the combinations described earlier (see Section 4.1.2).

Input: Solution $S$

1 $Imprv\leftarrow True$

2 while  _$(Imprv=True)$_ do

3 $Imprv\leftarrow False$

4 if  _$(applyIRRP(S))$_ then $Imprv\leftarrow True$

5 if  _$(applyShift^{1}(S))$_ then $Imprv\leftarrow True$

6 if  _$(applyExchange^{1}(S))$_ then $Imprv\leftarrow True$

7 if  _$(apply2OptStar(S))$_ then $Imprv\leftarrow True$

8 if  _$(apply2Opt(S))$_ then $Imprv\leftarrow True$

9 if  _$(applyROpt(S))$_ then $Imprv\leftarrow True$

10 if  _$(applySwap-relocate(S))$_ then $Imprv\leftarrow True$

11 if  _$(applySwap-sequence(S))$_ then $Imprv\leftarrow True$

12

13 end while

return $S$

Algorithm 4 Intensification procedure

####  4.3.2 Perturbation phase

Two perturbation approaches have been commonly used in the literature. The
first approach is based on removal/repair procedures (see Section 4.1.1),
whereas the second one is based on local search operators. Hereafter, we
discuss the implementation of these perturbation mechanisms in our method.

This perturbation procedure is based on the Swap-sequence operator described
earlier (see Section 4.1.2). A similar approach can be found in [34]. It
applies a series of feasible but non-improving moves that deteriorate the
fitness of the solution given as an input. Moreover, this procedure is
designed such that the order in which the perturbation moves are performed is
different from that used during the intensification phase. This is achieved in
a similar way as in Brandao (2020) [3]. First, a data structure (an array) is
used to store the number of times each task is involved in local search moves
performed during the intensification phase so far. Then, at the beginning of
the perturbation phase, the array of counters is sorted in non-increasing
order. For each task in this data structure, non-improving moves involving the
sub-sequence that starts from this task are computed, and a random move is
selected and performed. This process iterates over the list of tasks in a
cyclic fashion, until the maximum number of moves is reached. The maximum
number of moves is determined as a function of the perturbation degree
parameter (see Section 4).

###  4.4 Elite solutions

As explained in the previous sections, the ILS moves systematically from a
local optimum to another after each iteration, without necessarily exploring
all the neighborhood of each local optimum. To tackle this issue, we propose
to store in a list of a maximum size of $N_{Pop}$ a set of good and relatively
diversified solutions called elite set. The basic idea of this approach is
that instead of starting ILS from an empty solution, we rather use the ILS to
continuously improve the solutions in the elite set. Basically, the elite set
of solutions undergoes a series of updates that add new solutions of good
quality and sufficiently diversified, and simultaneously discard unpromising
ones. This approach shares several characteristics with evolutionary
algorithms ([25], [32]), where a population of solutions evolves over several
generations.

The evaluation of the solutions present in the elite set is of crucial
importance, because it allows the systematic discarding of unpromising
solutions and maintains a high level of diversity. To achieve this purpose, we
consider a so-called biased fitness, which takes into consideration, in
addition to the fitness of the solution, its contribution to the diversity of
the elite set [25]. The contribution of each solution to the diversity of the
elite set is computed as the average distance between the current solution and
the $n_{Close}$ closest solutions in the elite set. This parameter is fixed to
a value of $20\%$ of the size of the population. Solutions are then ordered
according to a weighted sum of their fitness and diversity contributions; and
the best $N_{Pop}$ solutions are maintained, and the others are discarded.

###  4.5 Generation of Initial Solutions

This procedure is a version of IRRP that starts from an empty solution. The
incumbent solution is always updated using the newly constructed solution in
the previous iteration (Algorithm 2, line 6). $D_{max}$ is set to its initial
value which is equal to $D_{0}=3$. The value of $D_{max}$ is incremented by 1
after each iteration without improvement (Algorithm 2, line 8), and reset to
its initial value once a new best solution is found. The stopping condition of
IRRP is $2N+K$, where $N$ is the number of tasks and $K$ is the number of
vehicles. The evaluation criterion used in IRRP is the total duration (see
Section 4.7).

###  4.6 General flow

The algorithm starts with the initialization of the elite set. $K$ solutions
are constructed from scratch using IRRP heuristic (lines 2-6) (see Section
4.5). After computing the biased fitness of each solution (see Section 4.4),
$N_{Pop}$ solutions are stored whereas the others are discarded (line 7).

As described in Section 4.3.2, a set $\mathcal{P}$ of four different versions
of ILS is considered.

  * 1.

$ILS_{1}$ : the perturbation is performed in a remove-repair fashion while
using duration as moves evaluation criteria.

  * 2.

$ILS_{2}$ : the perturbation is performed in a remove-repair fashion while
using travel cost as moves evaluation criteria.

  * 3.

$ILS_{3}$ : the perturbation is performed based on a local search procedure
and moves evaluations is based on duration.

  * 4.

$ILS_{4}$ : the perturbation is performed based on a local search procedure
and moves evaluations is based on travel cost.

Two phases are considered in the algorithm of the eILS. During phase one, only
$ILS_{1}$ is used to generate new solutions. After $CV_{1}$ iterations without
improving the best solution, eILS passes to phase 2 where $ILS_{2},ILS_{3}$,
and $ILS_{4}$ are sequentially called in this order, and each one is executed
during $CV_{2}$ iterations. Once a new improving solution is found, eILS
switches systematically to phase 1. This logic is presented by the procedure
$selectILS(i,lstImpr,CV_{1},CV_{2})$ (line 12) in Algorithm 5. After the
experimentation, the values of $CV_{1}$ and $CV_{2}$ are set respectively to
values $45$ and $30$. Regarding the general flow, the algorithm fetches at the
beginning of each iteration a solution $S$ from the elite set using binary
tournament, then applies on it a major perturbation operation with a
perturbation degree equal to $N/2$ (line 10), and provides it to a variant of
$ILS$, which is chosen (line 12) based on the current iteration $i$, the
iteration of the last improvement $lstImpr$, as well as $CV_{1}$ and $CV_{2}$.
The best solution found by the ILS is then added to the elite set and triggers
an update operation, during which at most $N_{Pop}$ solutions are retained in
the elite set, whereas duplicates and unpromising solutions are removed (line
12). This process is iterated $N_{Ils}$ times. At the end of the eILS, the
best solution in terms of objective value present in the elite set is returned
(line 14).

input : ILS versions $\mathcal{P}$, number of task $N$, convergence speed
$CS_{1}$ and $CS_{2}$

output : Best solution found so far $S_{Best}$.

1 $\mathcal{S}\leftarrow$ $Pop\leftarrow\emptyset$

2 for  _$i=1$ to $K$_ do

3 $S\leftarrow\emptyset$

4 $S_{IRRP}\leftarrow IRRP(S)\quad$ (see Section 4.2)

5 $Pop\leftarrow Pop\cup\\{S_{IRRP}\\}$

6 end for

7$Pop\leftarrow initPopulation(Pop)\quad$ (see Section 4.4)

8 $lstImpr\leftarrow 0$

9 for  _$(i=1$ to $N_{Ils})$_ do

10 $S\leftarrow BinaryTournement(Pop)$

11 $S\leftarrow removalRepairPerturbation(S,N/2)$ (see Section 4.1.1)

12 $ILS\leftarrow selectILS(i,lstImpr,\mathcal{P},CS_{1},CS_{2})$

13 $S_{ILS}\leftarrow ILS(S)\quad$ (see Section 4.3)

14 $Pop\leftarrow updatePopulation(Pop,S_{ILS})\quad$ (see Section 4.4)

15 if  _$(fitness(S_{ILS}) <fitness(S_{Best}))$_ then

16 $S_{Best}\leftarrow S_{ILS}$

17 $lstImpr\leftarrow i$

18

19 end if

20

21 end for

22$S_{Best}\leftarrow Top(Pop)$

return $S_{Best}$

Algorithm 5 Resolution algorithm

###  4.7 Move evaluation and feasibility check

The TRSP is a rich vehicle routing problem [5], with several characteristics
and constraints, such as time windows, renewable and non-renewable resources,
multi-depot, and site-dependent considerations. The difficulty of the problem
is further increased when dealing with duration minimization rather than
travel costs minimization. Hence, the need for a constant-time cost evaluation
and feasibility checks, for both, repair and local search moves, is crucial
for the overall performance of our method.

Before proceeding further, let us consider $\sigma$ as a sequence of arbitrary
visits of nodes, which can be task locations, home depots, or the central
depot. We denote the node at the $i^{th}$ position of $\sigma$ by
$\sigma^{i}$.

We also define the concatenation operator of two or more sub-sequences
$\sigma_{1}$ and $\sigma_{2}$ as :

$\sigma=\sigma_{1}\oplus\sigma_{2}$ (1)

Let $\Delta(\sigma)$, $\Lambda^{r}(\sigma)$, $\Lambda^{n}(\sigma)$ and
$\Psi(\sigma)$ be duration of sequence $\sigma$, accumulated renewable
resources of sequence $\sigma$, accumulated non-renewable resources of
sequence $\sigma$ and the accumulated skills needed by tasks in sequence
$\sigma$, respectively. We propose in the following the formulas used to
perform feasibility checks and moves evaluation in a constant time.

##### Renewable resources

For each task at position $i$ in the sequence $\sigma$, we record the number
of times a given type of tool $t\in T$ is required by the tasks from the start
of $\sigma$ to position $i$, or until the central depot in the case where it
is visited before position $i$.

The following equations hold.

$\Lambda^{r}_{t}(\sigma^{i})=\left\\{\begin{array}[]{l}\Lambda^{r}_{t}(\sigma^{i-1})+b_{\sigma^{i},t}\quad
if\;\sigma^{k}\neq 0\;\forall k\leq i-1\\\ \Lambda^{r}_{t}(\sigma^{i-1})\quad
otherwise\end{array}\right.$

$\Lambda^{r}_{t}(\sigma)$ = $\Lambda^{r}_{t}(\sigma^{|\sigma|})$.

$\Lambda^{r}_{t}(\sigma)=\left\\{\begin{array}[]{l}\Lambda^{r}_{t}(\sigma_{1})+\Lambda^{r}_{t}(\sigma_{2})\quad
if\;0\notin\sigma_{1}\\\ \Lambda^{r}_{t}(\sigma_{1})\quad
otherwise\end{array}\right.$

Let $k\in\mathcal{K}$ be the vehicle performing sequence $\sigma$. $\sigma$ is
unfeasible if $\exists t\in\\{1,\ldots,|T|\\}$ where $w^{k}_{t}=0$ and
$\Lambda^{r}_{t}(\sigma)>0$.

##### Non-renewable resources

For each task at position $i$ in the sequence $\sigma$, we record the number
of times a given type of spare part $p\in P$ is required by the tasks from the
start of $\sigma$ to position $i$, or until the central depot in the case
where it is visited before position $i$.

The following equations hold.

$\Lambda^{n}_{p}(\sigma^{i})=\left\\{\begin{array}[]{l}\Lambda^{n}_{p}(\sigma^{i-1})+d_{\sigma^{i},p}\quad
if\;\sigma^{k}\neq 0\;\forall k\leq i-1\\\ \Lambda^{n}_{p}(\sigma^{i-1})\quad
otherwise\end{array}\right.$

$\Lambda^{n}_{p}(\sigma)$ = $\Lambda^{n}_{p}(\sigma^{|\sigma|})$.

$\Lambda^{n}_{p}(\sigma)=\left\\{\begin{array}[]{l}\Lambda^{n}_{p}(\sigma_{1})+\Lambda^{n}_{p}(\sigma_{2})\quad
if\;0\notin\sigma_{1}\\\ \Lambda^{n}_{p}(\sigma_{1})\quad
otherwise\end{array}\right.$

Let $k\in\mathcal{K}$ be the vehicle performing sequence $\sigma$. $\sigma$ is
unfeasible if $\exists p\in\\{1,\ldots,|P|\\}$ where
$v^{k}_{p}>\Lambda^{n}_{p}(\sigma)$.

##### Skills

For each task in a sequence $\sigma$, we record the number of times a given
skill is required by the tasks since the start of the sequence. For each type
of skill $q\in Q$, the following equations hold. $\Psi_{q}(\sigma^{i})$ =
$\Psi_{q}(\sigma^{i-1})$ \+ $a_{\sigma^{i},q}$. $\Psi_{q}(\sigma)$ =
$\Psi_{q}(\sigma^{|\sigma|})$. $\Psi_{q}(\sigma)$ = $\Psi_{q}(\sigma_{1})$ \+
$\Psi_{q}(\sigma_{2})$. Let $k\in\mathcal{K}$ be the technician performing
sequence $\sigma$. $\sigma$ is unfeasible if $\exists q\in\\{1,\ldots,|Q|\\}$
where $y^{k}_{q}=0$ and $\Psi_{q}(\sigma)>0$.

##### Time window feasibility

To perform time window feasibility checks in a constant time, we adopted the
approach proposed by Kindervarter and Savelsbergh (2018) [16], where the
authors proposed to compute the Forward Time Slack $FTS_{i}$ at the $i^{th}$
position of $\sigma$, indicating how much time delay is possible at this
position while maintaining time windows feasibility of the subsequent visits.
Let $WT_{i}$ and $h^{\sigma}_{i}$ be the waiting time and the service starting
time at the $i^{th}$ position of $\sigma$, respectively. We define the total
waiting time $TWT_{ij}$ between $\sigma_{i}$ and $\sigma_{j}$, $i\leq j$ as
follows: $TWT^{\sigma}_{ij}=\sum_{k=i+1}^{j}WT_{k}$.

The forward time slack at the $i^{th}$ position of $\sigma$ is defined as :
$FTS^{\sigma}_{i}=\min\limits_{i\leq
k\leq|\sigma|}\\{TWT^{\sigma}_{ik}+l_{\sigma_{k}}-h^{\sigma}_{k}\\}$, where
$h^{\sigma}_{k}$ is the service starting time of the visit at position $k$ of
$\sigma$. For convenience, we denote the FTS at the starting position as
$FTS^{\sigma}$. The insertion of a task $r\in R$ in the $i^{th}$ position of
$\sigma$ is feasible if : $s_{r}<l_{r}\quad and\quad
Shift_{i}<FTS^{\sigma}_{i}$, where $s_{r}$ is calculated as follows:
$s_{r}=max\\{h^{\sigma}_{i-1}+\delta_{\sigma_{i-1}}+t_{\sigma_{i-1},r},e_{r}\\}$
and $Shift_{i}=\tilde{h}^{\sigma}_{i}-h^{\sigma}_{i}$, where
$\tilde{h}^{\sigma}_{i}=max\\{s_{r}+\delta_{r}+t_{r,\sigma_{i}},e_{\sigma_{i}}\\}$.

##### Movement evaluation

The objective function of the TRSP is to minimize the total duration of the
routes. This also includes the possibility of delaying the departure of
vehicles from the depots to minimize the total waiting time. We proceed in a
similar manner as in Savelsbergh. (1992) [26]. Let us first define the maximum
delay of the service starting time at the $i^{th}$ position of $\sigma$
without violating time windows at subsequent visits or causing any delays at
the arrival depot as the Passive Time Slack (PTS) of $\sigma$, and it is
denoted by $PTS_{i}^{\sigma}$. This is calculated as follows :
$PTS_{i}^{\sigma}=\\{FTS^{\sigma}_{i},TWT^{\sigma}_{i|\sigma|}\\}$. For
convenience, we denote the PTS at the starting position as $PTS^{\sigma}$.

The duration of sequence $\sigma$ is computed as

$\Delta(\sigma)=h^{\sigma}_{|\sigma|}+\delta_{\sigma_{|\sigma|}}-h^{\sigma}_{1}-PTS^{\sigma}$.

To compute the duration of the concatenated sequences, we compute the new PTS
and the earliest arrival at the final position of the new sequence. For this
purpose, we first define the allowed backward shift of a given sequence
$\sigma$, at a given position $i$, as the maximum gain in duration at the
final depot yielded by the backward shift of the service starting time at
position $i$ of $\sigma$, assuming of course that the service can start in an
earlier date. The allowed backward shift is denoted by $BS_{i}^{\sigma}$ and
it is computed as follows:
$BS^{\sigma}_{i}=min\\{h^{\sigma}_{i}-e_{\sigma_{i}},BS^{\sigma_{i+1}}\\}$.
For convenience, we note the BS at the first position of $\sigma$ by
$BS^{\sigma}$.

Without loss of generality, we consider the concatenation of three sub-
sequences into a single sequence:
$\sigma=\sigma_{1}\oplus\sigma_{2}\oplus\sigma_{3}$. Let $Shift^{\sigma_{2}}$
and $Shift^{\sigma_{3}}$ be, respectively, the shifts at the first elements of
$\sigma_{2}$ and $\sigma_{3}$ after concatenation. We also denote by
$WT^{\sigma_{2}}$ and $WT^{\sigma_{3}}$ the new waiting times at the first
elements of $\sigma_{2}$ and $\sigma_{3}$ after concatenation.

Depending on the value of $Shift^{\sigma_{3}}$, either positive or negative,
we propose the following formulas to compute the duration of $\sigma$.

If $Shift^{\sigma_{3}}\geq 0$ :

  * 1.

$h^{\sigma}_{|\sigma|}=h^{\sigma_{3}}_{|\sigma_{3}|}+max(0,Shift^{\sigma_{3}}-PTS^{\sigma_{3}})$

  * 2.

$PTS^{\sigma}=min\\{FTS^{\sigma_{1}},min\\{TWT^{\sigma_{1}}+WT^{\sigma_{2}}+max\\{0,FTS^{\sigma_{2}}-Shift^{\sigma_{2}}\\},TWT^{\sigma_{1}}+WT^{\sigma_{2}}+max\\{0,TWT^{\sigma_{2}}-Shift^{\sigma_{2}}\\}+WT^{\sigma_{3}}+max(0,PTS^{\sigma_{3}}-Shift^{\sigma_{3}})\\}\\}$

If $Shift^{\sigma_{3}}<0$ :

  * 1.

$h^{\sigma}_{|\sigma|}=h^{\sigma_{3}}_{|\sigma_{3}|}-min(-Shift^{\sigma_{3}},BS^{\sigma_{3}})$

  * 2.

$PTS^{\sigma}=min\\{FTS^{\sigma_{1}},min\\{TWT^{\sigma_{1}}+WT^{\sigma_{2}}+max\\{0,FTS^{\sigma_{2}}-Shift^{\sigma_{2}}\\},TWT^{\sigma_{1}}+WT^{\sigma_{2}}+max\\{0,TWT^{\sigma_{2}}-Shift^{\sigma_{2}}\\}+WT^{\sigma_{3}}+max(0,PTS^{\sigma_{3}}-Shift^{\sigma_{3}}-BS^{\sigma_{3}})\\}\\}$

###  4.8 Speed-up techniques

Local search operators and the best insertion algorithm are the most time-
consuming components of the proposed scheme. We propose in the following two
speed-up techniques used to reduce the computational burden.

####  4.8.1 Parallel best insertion algorithm

An efficient method to implement the best insertion algorithm is to consider
each route separately. The basic idea is to compute the best feasible
insertion of the unscheduled tasks for each route. Then, those feasible
insertions of all routes are stored in a heap structure that we call a HEAP.
The insertion process is performed as follows. It starts by selecting the best
move (if any) from HEAP. If the task has not yet been inserted, the insertion
is performed and the task is marked as fulfilled and removed from the list of
unscheduled tasks. The algorithm systematically computes feasible insertions
of the remaining unscheduled tasks while considering only the last modified
route. If feasible moves are found, then the best move is selected and pushed
to HEAP. This process is iterated until HEAP becomes empty, i.e. no route has
feasible insertions in HEAP.

####  4.8.2 Nearest predecessors

Many irrelevant movement evaluations are performed during local search calls.
Experimentation showed that most improvements are achieved by local search
movements involving the nearest neighbors. To take advantage of this
observation, we propose to compute a list of the nearest predecessors for each
task. Given an arbitrary task $i$, and for each predecessor $j$, and assuming
that arc $(j,i)$ is feasible, the distance is computed as follows :

$dist(j,i)=max\\{max(0,e_{i}-l_{j}),t_{ji}\\}.$ (2)

The predecessors of $i$ are sorted in non-decreasing order according to
distance and only the first $\chi$ predecessors are considered during local
search movements. The value of $\chi$ was fixed to a value equal to $30$ after
experimentation.

The nearest predecessors lists are mainly used by inter-route local search
operators. The $2-opt*$ operator, for example, where arcs $(i,j)$ and $(k,l)$
are interchanged, it starts by selecting a task $j$, and then picks a task $l$
among the $\chi$ nearest predecessors. $l$ should be scheduled on a route
different from that of task $j$. Move evaluation in $Swap-Relocate$ and $Swap-
Sequence$ are carried out in the same fashion.

##  5 Computational results

We present in this section the computational tests carried out to assess the
performance of the proposed eILS. Our algorithm is coded in C++ and runs on a
PC with an Intel Core i7 2.6GHz processor and 16 GB RAM. The results of the
eILS are compared with those of parallel ALNS (pALNS) algorithm found in [24].

###  5.1 Benchmark instances

Benchmark instances for TRSP are derived from 56 instances of Solomon
benchmark for VRPTW [29]. All instances have 100 tasks, that are either
randomly distributed (R), in clusters (C) or a mix patterns (RC). Each class
can be grouped into two sub-classes: (1) instances with short time windows or
(2) large time windows (i.e. C1, C2, R1, R2, RC1, RC2). For each instance, 25
home depots are added, each associated with a technician and initial inventory
of tools and spare parts. Each technician is associated with a set of skills
(five types of skills are considered) and each task is associated with
requirements in terms of skills, tools, and spare parts. The depot present in
the original instances of VRPTW is considered the central depot used for
replenishment. As indicated in the problem definition, the central depot has
unlimited inventory, and each technician can carry as many tools and spare
parts as needed for their journey without any capacity limitations.

###  5.2 Parameter settings

In this section, we investigate the impact of several parameters of the eILS
on the overall performance. Three parameters were determined: number of tasks
to remove $D_{max}$ at each iteration in the $IRRP$ during the intensification
phase, size of the Elite set $N_{pop}$, and number of iterations $N_{ils}$ of
eILS. The values for each parameter are listed in Table (1).

Table 1: Parameter settings Parameter | Description | Range
---|---|---
$d_{max}$ |  Perturbation parameter in $IRRP$ | $[5,10,15]$
$N_{ils}$ | Number of Iterations | $[450,500,550,600]$
$N_{pop}$ | Size of elite set | $[10,15,20]$

Twelve instances were arbitrarily selected for this purpose, and each instance
was executed 10 times for each combination of parameter values, that is,
$144*10$ runs for each instance. Figures 3,3 and 4 show the aggregated overall
gaps for each combination of the three parameters, whereas figures 5,7 and 7
show the overall computational times variations according to the values of the
same parameters.

Figure 2: Impact of $D_{max}$ in IRRP on overall gap

Figure 3: Impact of the number of iterations on overall gap

Figure 4: Impact of the population size on overall gap Figure 5: Impact of the
number of iterations on overall computational time

Figure 6: Impact of the number of iterations on overall computational time

Figure 7: Impact of the population size on overall computational time

Based on this experiment, the selected value of each parameter are listed in
Table 2.

Table 2: Parameter settings for the eILS Parameters | $d_{max}$ | $N_{ils}$ | $N_{pop}$
---|---|---|---
Value | $10$ | $600$ | $10$

###  5.3 Sensitivity analysis

In this section, we present a study of the sensitivity analysis of several
components of the eILS. We start by investigating the contribution of each
perturbation mechanism, then, we focus on two components of the eILS, which
are the related-removal operator and Swap-Sepquence local search operator.

####  5.3.1 Perturbation mechanisms

We focus in this section on the contribution of each of the four perturbation
mechanisms (see Section 4.6). We ran our algorithm 10 times while considering
several configurations of the eILS. These configurations are the following:

  * 1.

$Conf_{1}$ = $ILS1$

  * 2.

$Conf_{2}$ = $ILS1+ILS2$

  * 3.

$Conf_{3}$ = $ILS1+ILS2+ILS3$

  * 4.

$Conf_{4}$ = $ILS1+ILS2+ILS3+ILS4$ = eILS

We provide the following performance indicators for the methods:

  * 1.

$CPU$ : the average computational times of the 10 runs per sub-class. In this
section, we take as a reference the computational times of $Conf_{1}$.

  * 2.

$GAP$ : the gap between the best objective value of a given method and the
best-know solution per sub-class, and it is calculated as follows:

$GAP=\frac{C_{best}-C^{M}_{best}}{C_{best}}\times 100$ (3)

where $C_{best}$ is the best-known solution and $C^{M}_{best}$ is the best
objective value of the 10 runs of either pALNS or eILS.

  * 3.

$DEV$ : the deviation of the average best results from the best objective
values per sub-class.

$DEV=\frac{C^{M}_{best}-AVG^{M}}{C^{M}_{best}}\times 100$ (4)

where $AVG^{M}$ is the average objective value of the ten runs given by the
eILS or pALNS.

Table 3: Sensitivity analysis of perturbation mechanisms Parameters | $Conf_{1}$ | $Conf_{2}$ | $Conf_{3}$ | $Conf_{4}$
---|---|---|---|---
$GAP(\%)$ | $0.243$ | $0.21$ | $0.198$ | $0.19$
$DEV(\%)$ | $0.707$ | $0.673$ | $0.7$ | $0.684$
$CPU$ | $1$ | $1$ | $1.14$ | $1.02$

Table 3 provides performance measures for the configurations presented in this
section. This clearly shows the contribution of each ILS version (perturbation
mechanism) to the global performance of eILS. Adding $ILS2$ to $ILS1$
($Conf_{2}$) has clearly improved the overall gap (row 2) from $0.243\%$ to
$0.21\%$, the deviation from $0.707\%$ to $0.673\%$, Interestingly, these
substantial improvements have been achieved while maintaining similar
computational times. Adding $ILS3$ in $Conf_{3}$ has also improved the the
overall gap from $0.21\%$ to $0.198\%$, although a slight deterioration has
been observed on the deviation from the objective value (row 3) and a
substantial increase in computational times by a factor of $1.14$.Finally, the
full scheme of eILS has achieved the best global performance in terms of the
overall gap with an associated value of $0.19\%$. The overall deviation has
slightly deteriorated from $0.673\%$ to $0.684\%$. The computational times
have slightly increased by a factor of $1.02$ compared to $Conf_{1}$.

####  5.3.2 Components sensitivity analysis

In this section, we suggest to investigate the contribution of some of eILS
components to the overall performance. We focus our attention on two
components, namely, related-sequence removal, referred to by $SeqRem$, and
swap-sequence local search operator, referred to by $SwapSeq$. A similar
approach of related-sequence removal operator but more complex can be found in
[8].

Table 4: Sensitivity analysis for some components of the eILS Parameters | no $SwapSeq$ | no $SeqRem$ | eILS
---|---|---|---
$GAP(\%)$ | $0.210$ | $0.192$ | $0.179$
$DEV$ $(\%)$ | $0.810$ | $0.607$ | $0.629$
$CPU$ | $0.84$ | $0.88$ | $1$

Table 4 shows a comparison of the three versions of eILS. The first version
does not include the related sequence removal operator (column 1), whereas the
second version does not include the swap sequence operator (column 2). The
last column of Table 4 shows the results of eILS, including both components.
The results clearly show the contribution of both components to the overall
results of the eILS. The absence of related-sequence removal (column 2)
substantially deteriorates the quality of solutions obtained by the eILS. More
precisely, the percentage gap ($GAP$) evolves from $0.179\%$ to $0.192\%$.
However, the computational times have substantially decreased by a factor of
$0.88$ compared to eILS.

The same behavior has been observed when the swap-sequence local search
operator is discard. The percentage gap goes from $0.179\%$ to $0.210\%$
whereas the percentage deviation has achieved $0.810\%$ compared to $0.629\%$
of the eILS. However, the computational times have substantially decreased by
a factor of $0.84$ compared to the whole scheme of eILS.

###  5.4 Computational results

We conduct experiments to assess the performance of our method. We compare our
method with the pALNS presented in [24]. The pALNS was implemented using Java
7 and Gurobi 4.60 on an Ubuntu 11.10 64-bit machine, with an Intel i7 860
processor (4×2.8GHz) and 6GB of RAM, using K = 8 subprocesses. To guarantee a
fair comparison between the two methods, we adopt the same protocol used in
[24], that is, we perform ten random runs of the eILS on each instance tested,
and we report the best objective value, the average objective value, and the
average computational times.

Table 5 shows a comparison between the two methods.

We recorded the deviation from the average ($DEV$) computed using Eq. (4), the
computational times ($CPU$) and the gap to the best solution ($GAP$) computed
using Eq. (3). The computational times and deviation from the average of the
pALNS can be found in [24]. Because pALNS is a parallel approach, the authors
in [24] reported two computational times: the computational times of the
parallel ALNS $cpu_{1}$ and the computational times of post-optimization phase
(route recombination) $cpu_{2}$. Hence, we estimate the computational times of
a sequential version of pALNS as $CPU_{pALNS}=8\times cpu_{1}+cpu_{2}$.

Table 5: Summary of results of eILS and pALNS Class | pALNS | eILS
---|---|---
$CPU$ $(s)$ |  $GAP$ $(\%)$ |  $DEV$ $(\%)$ |  $CPU$ $(s)$ |  $GAP$ $(\%)$ |  $DEV$ $(\%)$
$C1$ | $580.9$ | $0.060$ | $0.23$ | $329.97$ | $0.054$ | $0.291$
$C2$ | $246$ | $0.474$ | $0.42$ | $414.88$ | $0$ | $0.112$
$R1$ | $731.4$ | $0.094$ | $0.82$ | $343.87$ | $0.351$ | $0.886$
$R2$ | $290.1$ | $1.5$ | $1.46$ | $382.03$ | $0.065$ | $0.818$
$RC1$ | $409$ | $0.104$ | $0.68$ | $327.41$ | $0.609$ | $0.985$
$RC2$ | $238.8$ | $1.466$ | $1.43$ | $369.17$ | $0$ | $1.111$
$Mean$ | $434.9$ | $0.617$ | $0.86$ | $360.54$ | $0.184$ | $0.713$

The results in Table 5 show no clear dominance between the two methods.
However, we notice that for sub-classes with tight windows (R1, and RC1),
pALNS succeeds in outperforming eILS, since it achieves a percentage gap of
$0.094\%$ and $0.104\%$ respectively, against $0.351\%$, and $0.609\%$. This
is mainly justified by the use of a powerful post-optimization approach based
on a set covering formulation used in [24]. Nevertheless, eILS improves the
best know solutions of several instances of these classes. In contrast, for
subclasses C1, C2, R2, and RC2, which are characterized by relatively large
time windows, eILS outperforms pALNS in terms of percentage gaps and deviation
from the average. More precisely, eILS reaches percentage gaps of $0.54\%$,
$0\%$, $0.013\%$, and $0.062\%$ on these subclasses, against the percentage
gaps of $0.060\%$, $0.522\%$, $1.512\%$, and $1.527\%$ achieved by the pALNS.

It is noteworthy to mention that the computational times of the eILS are much
higher on subclasses with large time windows. This is mainly owing to the
extensive use of local search operators, especially because these type of
instances have room for improving solution costs, whereas for instances with
tight time windows, the contribution of local search operators is limited to
inter-route operators. As a consequence, eILS succeeds in improving almost all
the instances of C2, RC2 and RC2, achieving a total number of 34 new best-
known solutions (see A).

Globally, although the eILS fails to improve the best-know solution for a
number of instances in classes C1, R1 and RC1, it achieves a better overall
gap to best, which is equal to $0.184\%$, which is more that three times lower
than that of pALNS $(0.617\%)$. Regarding computational times, eILS has an
overall CPU time equal to $360.54s$, against $434.9s$ for pALNS.

##  6 Conclusion and perspective

In this paper, we addressed a variant of the workforce scheduling problem
called TRSP. This variant incorporates several state-of-the-art constraints
such as time windows, multi-depot, site-dependent, capacity constraints, etc.
We proposed in this paper an enhanced version of the ILS metaheuristic. The
eILS combines a stack of local search operators, removal heuristics, a best
insertion algorithm, and an intensification/diversification mechanism based on
an elite set of solutions. The performance of the proposed method was compared
with that of a math-heuristic approach from the literature. The eILS achieved
excellent results by improving the best-known solution for many benchmark
instances.

Several promising research perspectives was determined after the study of the
TRSP. This study highlights the need to design exact approaches for TRSP.
Mathematical models, either linear or non-linear, seem to be not suitable and
often fail to solve small instances. This is mainly because of the nature of
the objective function, where instead of minimizing travel costs, the duration
is minimized. The most suitable approach for finding optimal solutions for the
TRSP is the branch-and-price method [11]. Another promising direction is the
integration of the synchronization constraints into the TRSP. This allows the
problem to cover relevant cases where a given task requires the intervention
of multiple technicians, either simultaneously or with precedence relations,
to perform the maintenance operation. Finally, because the objective function
aims at the minimization of the total duration, a promising research direction
consists in the elaboration of methods that consider workload balancing.

## Acknowledgment

This work was carried out within the framework of the ELSAT220 project. The
ELSAT2020 project is co-financed by the Hauts-de-France Region and European
Economic and Regional Development Fund (ERDF) of the EU.

## CRediT authorship contribution statement

Ala-Eddine Yahiaoui: Conceptualization, Methodology, Software, Validation,
Writing – original draft, Writing – review & editing. Sohaib Afifi and Hamid
Allaoui: Review & editing.

## References

  * [1] Nathalie Bostel, Pierre Dejax, Pierre Guez, and Fabien Tricoire.  Multiperiod planning and routing on a rolling horizon for field force optimization logistics.  In The vehicle routing problem: latest advances and new challenges, pages 503–525. Springer, 2008.
  * [2] José Brandão.  Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows.  Computers & Industrial Engineering, 120:146–159, 2018.
  * [3] José Brandão.  A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem.  European Journal of Operational Research, 284(2):559–571, 2020\.
  * [4] David Bredstrom and Mikael Rönnqvist.  A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints.  NHH Dept. of Finance & Management Science Discussion Paper, (2007/7), 2007.
  * [5] Jose Caceres-Cruz, Pol Arias, Daniel Guimarans, Daniel Riera, and Angel A Juan.  Rich vehicle routing problem: Survey.  ACM Computing Surveys (CSUR), 47(2):1–28, 2014.
  * [6] J Arturo Castillo-Salazar, Dario Landa-Silva, and Rong Qu.  Workforce scheduling and routing problems: literature survey and computational study.  Annals of Operations Research, 239(1):39–67, 2016.
  * [7] Lu Chen, Michel Gendreau, Minh Hoàng Hà, and André Langevin.  A robust optimization approach for the road network daily maintenance routing problem with uncertain service time.  Transportation research part E: logistics and transportation review, 85:40–51, 2016.
  * [8] Jan Christiaens and Greet Vanden Berghe.  Slack induction by string removals for vehicle routing problems.  Transportation Science, 54(2):417–433, 2020.
  * [9] Jean-François Cordeau, Gilbert Laporte, Federico Pasin, and Stefan Ropke.  Scheduling technicians and tasks in a telecommunications company.  Journal of Scheduling, 13(4):393–409, 2010.
  * [10] Martin Desrochers, Jacques Desrosiers, and Marius Solomon.  A new optimization algorithm for the vehicle routing problem with time windows.  Operations research, 40(2):342–354, 1992.
  * [11] Martin Desrochers and François Soumis.  A generalized permanent labelling algorithm for the shortest path problem with time windows.  INFOR: Information Systems and Operational Research, 26(3):191–212, 1988.
  * [12] Pierre-François Dutot, Alexandre Laugier, and Anne-Marie Bustos.  Technicians and interventions scheduling for telecommunications.  France Telecom R&D, 2006.
  * [13] Gianfranco Guastaroba, J-F Côté, and Leandro C Coelho.  The multi-period workforce scheduling and routing problem.  Omega, page 102302, 2020.
  * [14] Hideki Hashimoto, Sylvain Boussier, Michel Vasquez, and Christophe Wilbaut.  A grasp-based approach for technicians and interventions scheduling for telecommunications.  Annals of Operations Research, 183(1):143–161, 2011.
  * [15] Amy Khalfay, Alan Crispin, and Keeley Crockett.  A review of technician and task scheduling problems, datasets and solution approaches.  In 2017 Intelligent Systems Conference (IntelliSys), pages 288–296. IEEE, 2017.
  * [16] Gerard AP Kindervater and Martin WP Savelsbergh.  10\. vehicle routing: handling edge exchanges.  In Local search in combinatorial optimization, pages 337–360. Princeton University Press, 2018.
  * [17] Attila A Kovacs, Sophie N Parragh, Karl F Doerner, and Richard F Hartl.  Adaptive large neighborhood search for service technician routing and scheduling problems.  Journal of scheduling, 15(5):579–600, 2012.
  * [18] Raphael Kramer, Jean-François Cordeau, and Manuel Iori.  Rich vehicle routing with auxiliary depots and anticipated deliveries: An application to pharmaceutical distribution.  Transportation Research Part E: Logistics and Transportation Review, 129:162–174, 2019.
  * [19] Yanfeng Li, Ting Xiang, and Wai Yuen Szeto.  Home health care routing and scheduling problem with the consideration of outpatient services.  Transportation Research Part E: Logistics and Transportation Review, 152:102420, 2021.
  * [20] Helena R Lourenço, Olivier C Martin, and Thomas Stützle.  Iterated local search.  In Handbook of metaheuristics, pages 320–353. Springer, 2003.
  * [21] Ines Mathlouthi, Michel Gendreau, and Jean-Yves Potvin.  A metaheuristic based on tabu search for solving a technician routing and scheduling problem.  Computers & Operations Research, 125:105079, 2018.
  * [22] Ines Mathlouthi, Michel Gendreau, and Jean-Yves Potvin.  Mixed integer linear programming for a multi-attribute technician routing and scheduling problem.  INFOR: Information Systems and Operational Research, 56(1):33–49, 2018.
  * [23] Engin Pekel.  Solving technician routing and scheduling problem using improved particle swarm optimization.  Soft Computing, 24(24):19007–19015, 2020.
  * [24] Victor Pillac, Christelle Gueret, and Andrés L Medaglia.  A parallel matheuristic for the technician routing and scheduling problem.  Optimization Letters, 7(7):1525–1535, 2013.
  * [25] Christian Prins.  A simple and effective evolutionary algorithm for the vehicle routing problem.  Computers & operations research, 31(12):1985–2002, 2004.
  * [26] Martin WP Savelsbergh.  The vehicle routing problem with time windows: Minimizing route duration.  ORSA journal on computing, 4(2):146–154, 1992.
  * [27] Paul Shaw.  Using constraint programming and local search methods to solve vehicle routing problems.  In International conference on principles and practice of constraint programming, pages 417–431. Springer, 1998.
  * [28] Yong Shi, Toufik Boudouh, and Olivier Grunder.  A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times.  Transportation Research Part E: Logistics and Transportation Review, 128:52–95, 2019.
  * [29] Marius M Solomon.  Algorithms for the vehicle routing and scheduling problems with time window constraints.  Operations research, 35(2):254–265, 1987.
  * [30] Hao Tang, Elise Miller-Hooks, and Robert Tomastik.  Scheduling technicians for planned maintenance of geographically distributed equipment.  Transportation Research Part E: Logistics and Transportation Review, 43(5):591–609, 2007.
  * [31] Fabien Tricoire, Nathalie Bostel, Pierre Dejax, and Pierre Guez.  Exact and hybrid methods for the multiperiod field service routing problem.  Central European Journal of Operations Research, 21(2):359–377, 2013.
  * [32] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, and Christian Prins.  A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows.  Computers & operations research, 40(1):475–489, 2013.
  * [33] Don Weigel and Buyang Cao.  Applying gis and or techniques to solve sears technician-dispatching and home delivery problems.  Interfaces, 29(1):112–130, 1999.
  * [34] Fulin Xie, Chris N Potts, and Tolga Bektaş.  Iterated local search for workforce scheduling and routing problems.  Journal of Heuristics, 23(6):471–500, 2017.
  * [35] Jiyang Xu and Steve Y Chiu.  Effective heuristic procedures for a field technician scheduling problem.  Journal of Heuristics, 7(5):495–509, 2001.
  * [36] Ala-Eddine Yahiaoui, Aziz Moukrim, and Mehdi Serairi.  Grasp-ils and set cover hybrid heuristic for the synchronized team orienteering problem with time windows.  International Transactions in Operational Research, 2021.
  * [37] Emilio Zamorano and Raik Stolletz.  Branch-and-price approaches for the multiperiod technician routing and scheduling problem.  European Journal of Operational Research, 257(1):55–68, 2017.

##  Appendix A Detailed Results

Table 6: Detailed results of pALNS and eILS Instance | Best | pALNS | eILS
---|---|---|---
$BEST$ | $BEST$ | $AVG$ | $CPU$
$C101$ | $10685.9$ | $10717.52$ | $10685.9$ | $10743.4$ | $245.649$
$C102$ | $10228.8$ | $10239.04$ | $10228.8$ | $10262.7$ | $391.555$
$C103$ | $10281.86$ | $10281.86$ | $10285.6$ | $10308.5$ | $338.768$
$C104$ | $10107.44$ | $10107.44$ | $10120.6$ | $10136.9$ | $354.258$
$C105$ | $10570.1$ | $10584.06$ | $10570.1$ | $10592.6$ | $271.371$
$C106$ | $10321$ | $10322.6$ | $10321$ | $10355.4$ | $296.845$
$C107$ | $10356.56$ | $10356.56$ | $10370.2$ | $10419.1$ | $322.745$
$C108$ | $10251.22$ | $10251.22$ | $10260.1$ | $10282.3$ | $372.89$
$C109$ | $10107.33$ | $10107.33$ | $10117.4$ | $10132$ | $375.688$
$C201$ | $10188.4$ | $10192.98$ | $10188.4$ | $10200.2$ | $298.42$
$C202$ | $9920.53$ | $10001.52$ | $9920.53$ | $9923$ | $401.808$
$C203$ | $9962.36$ | $10001.17$ | $9962.36$ | $9978.06$ | $410.631$
$C204$ | $9858.65$ | $9890.56$ | $9858.65$ | $9869.22$ | $469.463$
$C205$ | $10142.6$ | $10208.44$ | $10142.6$ | $10161.4$ | $365.68$
$C206$ | $9918.08$ | $9983.14$ | $9918.08$ | $9920.02$ | $508.429$
$C207$ | $9839.19$ | $9849.69$ | $9839.19$ | $9847.17$ | $411.334$
$C208$ | $9898.81$ | $9981.06$ | $9898.81$ | $9918.9$ | $453.244$
$R101$ | $3134.86$ | $3134.86$ | $3138.52$ | $3162.75$ | $270.218$
$R102$ | $3034.3$ | $3039.23$ | $3034.3$ | $3068.63$ | $339.597$
$R103$ | $2421.78$ | $2421.78$ | $2424.91$ | $2454.15$ | $417.04$
$R104$ | $2277.65$ | $2285.77$ | $2277.65$ | $2301$ | $308.667$
$R105$ | $2961.04$ | $2975.42$ | $2961.04$ | $2991.34$ | $346.455$
$R106$ | $2626.38$ | $2626.38$ | $2636.44$ | $2661.16$ | $372.324$
$R107$ | $2131.73$ | $2134.36$ | $2131.73$ | $2137.79$ | $481.441$
$R108$ | $2116.05$ | $2116.05$ | $2116.24$ | $2125.77$ | $286.345$
$R109$ | $2512.89$ | $2512.89$ | $2539.55$ | $2563.16$ | $342.538$
$R110$ | $2359.42$ | $2359.42$ | $2384.74$ | $2412.67$ | $378.265$
$R111$ | $2550.5$ | $2550.5$ | $2567.22$ | $2595.9$ | $278.235$
$R112$ | $2145.76$ | $2145.76$ | $2163.34$ | $2178.27$ | $305.27$
$R201$ | $2635.07$ | $2639.7$ | $2635.07$ | $2654.05$ | $352.272$
$R202$ | $2382.87$ | $2382.87$ | $2390.13$ | $2407.44$ | $412.038$
$R203$ | $2319.49$ | $2334.58$ | $2319.49$ | $2345.65$ | $350.529$
$R204$ | $1931.19$ | $1931.19$ | $1939.22$ | $1948.32$ | $405.609$
$R205$ | $2230.52$ | $2254.82$ | $2230.52$ | $2248.26$ | $354.095$
$R206$ | $2061.3$ | $2082.8$ | $2061.3$ | $2077.93$ | $352.69$
$R207$ | $1963.57$ | $1981.76$ | $1963.57$ | $1968.31$ | $401.502$
$R208$ | $1829.73$ | $1879.49$ | $1829.73$ | $1840.72$ | $487.621$
$R209$ | $2066.32$ | $2130.5$ | $2066.32$ | $2098.59$ | $327.945$
$R210$ | $2062.32$ | $2111.92$ | $2062.32$ | $2077.98$ | $375.614$
$R211$ | $1883.63$ | $1975.42$ | $1883.63$ | $1907.86$ | $382.419$
$RC101$ | $2856.49$ | $2856.49$ | $2871.13$ | $2903.32$ | $296.846$
$RC102$ | $2843.18$ | $2843.18$ | $2851.81$ | $2883.94$ | $307.664$
$RC103$ | $2474.75$ | $2495.57$ | $2474.75$ | $2508.13$ | $323.021$
$RC104$ | $2162.51$ | $2162.51$ | $2173.1$ | $2193.21$ | $362.273$
$RC105$ | $2711.49$ | $2711.49$ | $2720.56$ | $2731.9$ | $350.05$
$RC106$ | $2761.86$ | $2761.86$ | $2799.53$ | $2816.57$ | $279.961$
$RC107$ | $2570.4$ | $2570.4$ | $2608.63$ | $2635$ | $337.183$
$RC108$ | $2354.42$ | $2354.42$ | $2364.49$ | $2397.79$ | $362.306$
$RC201$ | $2682.56$ | $2686.01$ | $2682.56$ | $2722.5$ | $352.518$
$RC202$ | $2457.65$ | $2487.73$ | $2457.65$ | $2498.4$ | $390.661$
$RC203$ | $2283.23$ | $2310.01$ | $2283.23$ | $2320.93$ | $362.624$
$RC204$ | $2016.53$ | $2064.16$ | $2016.53$ | $2030.11$ | $399.336$
$RC205$ | $2544.14$ | $2588.17$ | $2544.14$ | $2582.74$ | $355.996$
$RC206$ | $2321.21$ | $2359.7$ | $2321.21$ | $2341.35$ | $372.752$
$RC207$ | $2176.09$ | $2233.68$ | $2176.09$ | $2191.61$ | $367.595$
$RC208$ | $1895.13$ | $1914.54$ | $1895.13$ | $1903.46$ | $351.896$
$Average$ | $4739.09$ | $4758.63$ | $4744.39$ | $4766.78$ | $360.54$