# A Large Neighborhood Search-based approach to tackle the very large scale Team Orienteering Problem in industrial context

Charly Chaigneau, Nathalie Bostel, Axel Grimault

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

To cite this version:

Charly Chaigneau, Nathalie Bostel, Axel Grimault. A Large Neighborhood Search-based approach to tackle the very large scale Team Orienteering Problem in industrial context. Computers and Operations Research, 2024, 10.1016/j.cor.2024.106954. hal-04867422

HAL Id: hal-04867422

https://univ-angers.hal.science/hal-04867422v1

Submitted on 6 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Journal Pre-proof

A Large Neighborhood Search-based approach to tackle the very large
scale Team Orienteering Problem in industrial context

Charly Chaigneau, Nathalie Bostel, Axel Grimault

PII: S0305-0548(24)00426-X

DOI: https://doi.org/10.1016/j.cor.2024.106954

Reference: CAOR 106954

To appear in: *Computers and Operations Research*

Received date : 12 June 2024

Revised date : 20 November 2024

Accepted date : 11 December 2024

Please cite this article as: C. Chaigneau, N. Bostel and A. Grimault, A Large Neighborhood Search-based approach to tackle the very large scale Team Orienteering Problem in industrial context. *Computers and Operations Research* (2024), doi: https://doi.org/10.1016/j.cor.2024.106954.

This is a PDF file of an article that has undergone enhancements after acceptance, such as the addition of a cover page and metadata, and formatting for readability, but it is not yet the definitive version of record. This version will undergo additional copyediting, typesetting and review before it is published in its final form, but we are providing this version to give early visibility of the article. Please note that, during the production process, errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.

© 2024 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

<figure><img src="image_3.png" /></figure>
# A Large Neighborhood Search-based approach to tackle the very large scale Team Orienteering Problem in industrial context

CHAIGNEAU Charly<sup>a</sup>, BOSTEL Nathalie<sup>a</sup>, GRIMAULT Axel<sup>b,*</sup>

<sup>a</sup>Nantes Université, LS2N, UMR 6004, F-44000, Nantes, France

<sup>b</sup>Université d'Angers, LARIS, SFR MATHSTIC, F-49000, Angers, France

## Abstract

The Team Orienteering Problem (TOP) is an optimization problem belonging to the class of Vehicle Routing Problem with Profits in which the objective is to maximize the total profit collected by visiting customers while being limited to a time limit. This paper deals with the very large scale TOP in an industrial context. In this context, computing time is decisive and classical methods may fail to provide good solutions in a reasonable computational time. To do so, we propose a Large Neighborhood Search (LNS) combined with various mechanisms in order to reduce the computational time of the method. It is applied on classical sets of instances from the literature and on a new set of very large scale instances ranging from 1001 to 5395 customers that we adapted from Kobeaga et al. (2017). On the small scale set of instances, most best-known solutions are found. On the large scale set of instances, three new best-known solutions are found while the algorithm quickly gets more than half of the other best-known solutions.

**Keywords:** Team Orienteering Problem, Very large scale, Vehicle Routing Problem, Clustering, Large Neighborhood Search

## 1. Introduction

The Orienteering Problem (OP) is an optimization problem which was first introduced in 1987 by Golden et al. (1987). Also known as the Selective Travelling Salesman Problem (Laporte and Martello, 1990), OP belongs to the class of Vehicle Routing Problem (VRP) with Profits. Like the VRP, OP is NP-Hard (Golden et al., 1987). In the OP, every customer has a profit which is collected if it is visited by the vehicle. It differs from the VRP as the vehicle is constrained by a time limit, meaning that it is usually not possible to visit every customer. Thus, the objective is then to maximize the total profit collected while respecting the time limit. The Team Orienteering Problem (TOP) is an extension of the OP where several vehicles are considered. TOP is used to modelize several applications, in particular the Tourist Trip Design Planning (TTDP)(Vansteenwegen, 2007).

In TTDP, the aim is to build a tourist trip itinerary based on a list of points of interest. As tourists usually can't visit every point of interest, the goal is to give them the best itinerary which can be characterised by their location, their preferences, the period of the year and so on. A survey on this problem can be found on Gavalas et al. (2014) and Ruiz-Meza and Montoya-Torres (2022).

This paper aims at addressing an industrial problem that can be modelized as an extension of the TOP: the subsurface imaging problem. In our context, computing time is decisive as it can be necessary to solve the problem several times an hour. Thus, we seek to obtain solutions under a budget time of 10 minutes. Industrial instances can also have more customers or more vehicles than in classical literature instances, making it even harder to solve efficiently. As in Arnold et al. (2019), we define the 'very large scale' VRP as a VRP problem where we consider several thousands of customers since the term 'large scale' is used to describe problems of several hundreds of customers. The very large scale char-

<footnote>*Corresponding author</footnote>

<footnote>Email address: axel.grimault@univ-angers.fr
(GRIMAULT Axel)</footnote>
acteristic has not been much tackled even if it
became recently a new source of dedicated re-
searches (Arnold et al., 2019, Accorsi and Vigo,
2021). The main aim of those articles is to ob-
tain very good solutions in a time allowing the
proposed algorithm to be used in the industrial
context. To do so, heuristic approaches are used
and paired with various mechanisms in order to
reduce the computational time while preserving
the quality of the final solution. The recent in-
terest for those problems can be explained by the
technological progress which eases the treatment
of such problems. However, even if very large
scale instances are tackled in some works in the
OP context (Kobeaga et al., 2017), to our knowl-
edge, this paper is the first one to address the very
large scale TOP.

To deal with it, we propose a Large Neighbor-
hood Search (LNS) combined with local search,
simulated annealing, and with specific mecha-
nisms to get very good solutions in a reason-
able time. The remaining of this paper is orga-
nized as follows. First, in Section 2, we describe
the industrial context. In Section 3, we discuss
about the state-of-the-art algorithms for both the
TOP and the very large scale VRP. In Section 4,
we present one mathematical formulation of the
problem. Then, in Section 5, we describe the
LNS and we evaluate it in Section 6. We also
propose an extension of several instances used
in the OP to build a new set of very large scale
instances for the TOP. Results on industrial in-
stances are then evaluated in Section 7. Finally,
we conclude this paper in Section 8 and propose
some perspectives of research to better deal with
such problems.

## 2. Industrial context

We are interested in a vehicle routing problem that arises in the subsurface imaging field. The aim of this field is to gather data that enables geologist to understand the structure of the subsurface, allowing environmental site characterization. Geophysical imaging provides essential knowledge on the structure of the subsurface. Applications can be found in geothermics or in the process of carbon capture. In the subsurface imaging field, several vehicles need to cover large areas to collect, on visited points, data related

to the subsurface composition. These operations
can last for several weeks with hundreds of thou-
sands points that need to be visited to ensure a
relevant cartography.

To this end, equipment getting data related to the
subsurface structure are first deployed on the area
of interest. Because of the size of the area to be
studied, the whole area is not equiped and it is
then needed to reposition the equipment through-
out the study. Vehicles then go from point to
point to collect geophysical data and to allow the
equipment repositioning. Even if not every point
is not available at the begining of the harvesting,
problems of several thousands of points are still
considered. One of the specificities of the prob-
lem is the number of hazards that happens during
the gathering operation: vehicles may need main-
tenance operations, new areas may open and new
available points appear regularly. Because of this,
it is needed to update regularly the planning to
ensure the quality of the process. This is defined
as having the highest productivity possible, com-
puted as the number of points visited during the
next hour.

Thus, this problem can be modelized as a Team
Orienteering Problem with multi-depot and open
routes (MDOTOP), where each point has a profit
of 1. The aim of our work is to propose, in a bud-
gen time of 10 minutes, solutions of high quality.
For technical reasons, it is not possible to update
continuously the planning, and this duration is as-
sociated to the time when routes can be updated.

## 3. Literature review

To our knowledge, the MDOTOP is not ad-
dressed in the literature. Thus, we review the
Team Orienteering Problem. The TOP is a rout-
ing problem consisting in the maximization of the
total profit collected by several vehicles on cus-
tomers over a time limit. It is a well-studied prob-
lem but it still remains difficult to solve. Both
exact and heuristic methods has been applied to
the problem, heuristics being the main approach
to tackle it. We review both of these methods ap-
plied to at least one of the two sets of instances
from the literature: the small scale one proposed
by Chao et al. (1996) and the large scale one in-
troduced by Dang et al. (2013a). Then, we review
the very large scale VRP. In this context, several
thousands of customers must be visited and clas-
sical methods need to be adapted to scale accord-
ingly.

3.1. *Exact methods*

Few exact methods have been developed to tackle
the TOP. Among these methods, Branch & Cut
(BC) (Dang et al., 2013b, Bianchessi et al., 2018)
has shown good results recently by finding 327
optimal solutions out of the 387 tested on the
classical set of instances proposed by Chao et al.
(1996). Branch & Price (BP) has also been
used to tackle the TOP (Boussier et al., 2007,
Keshtkaran et al., 2015) but results obtained
were not among the best. Overall, the combi-
nation of both methods, called Branch & Cut &
Price (BCP), is the method which is the most
used among exact methods (Poggi et al., 2010,
Keshtkaran et al., 2015, Pessoa et al., 2019, Orlis
et al., 2020). In particular, the state-of-the-art
method uses a BCP to solve the TOP with over-
laps (Orlis et al., 2020). It manages to find opti-
mality in 371 out of the 387 instances, and closes
33 open instances. Finally, cutting-plane meth-
ods (El-Hajj et al., 2016, Assunção and Mateus,
2019) have also been applied to the TOP. The lat-
ter solves 341 instances to optimality, showing
that cutting-plane algorithms can also be used to
tackle the TOP efficiently. Overall, exact meth-
ods have only been applied to the small scale set
of instances (Chao et al., 1996) as obtaining very
good results on this set is still a challenging task.
Obvious perspectives will be to build efficient ex-
act methods that can tackle problems from the
large scale set of instances.

3.2. *Heuristic approaches*

Based on its complexity, heuristic approaches are
more suitable to tackle the TOP. The first heuris-
tic applied to the TOP is developed by Chao et al.
(1996) and is compared to a modified version of
Tsiligirides' heuristic (Tsiligiridis, 1984) which
was applied to the stochastic OP. Results showed
that the proposed heuristic was better than the
adapted one.

Later, different methods were applied to the TOP.
Tabu Search (TS) was one of the first method
used. In Tang and Miller-Hooks (2005), the au-
thors embedded the TS in an adapative memory

procedure. According to the authors, this pro-
cedure allows diversity in the pool of solutions.
The TS alternates between small and large neigh-
borhood which enables the heuristic to be fast
while not losing quality. In their TS, greedy pro-
cedures are paired with random ones. Archetti
et al. (2007) developed two variants of the TS al-
gorithm. Both variants are mostly distinguished
by the fact that one considers infeasible solutions
while the other does not.

In the same paper, authors also apply a Vari-
able Neighborhood Search (VNS) to the TOP.
The VNS is considered in two versions depend-
ing on the computational time allocated to it.
Overall, the VNS was better than both of their
TS. A Skewed VNS (SVNS) is also proposed
by Vansteenwegen et al. (2009b) and outper-
forms their prior Guided Local Search (GLS) al-
gorithm (Vansteenwegen et al., 2009a). Vidal
et al. (2014b) developed several heuristics based
on a new neighborhood search. Among these
heuristics were a multi-start local improvement
heuristic and an Iterated Local Search (ILS).
Both heuristics performed well in terms of solu-
tion's quality with respect to the computational
time. Kim et al. (2013) proposed the first algo-
rithm based on large neighborhood search. They
used an Augmented Large Neighborhood Search
(AuLNS) paired with three improvement algo-
rithms and obtained the best known solutions
of all instances in a better computational time
than Dang et al. (2013a), outperforming all ex-
isting algorithms. Recently, a LNS proposed
by Orlis et al. (2020) finds all but one best
known solutions on the small scale set of in-
stances. In 2020, Hammami et al. (2020) pro-
posed an Hybrid Adaptive Large Neighbborhood
Search (HALNS). In their algorithm, the ALNS
framework is paired with the resolution of a set
packing problem consisting in finding the best set
of routes built during the process. Results showed
the efficiency of the method as it found all best
known solutions for both the small and large scale
sets of instances while improving one best known
solution on the last set. This method is the best
for both set of instances from the literature with
respect to the solution's quality and the associ-
ated CPU time. Other methods are proposed as
a Multi-start Simulated Annealing (MSA) algo-
rithm (Lin, 2013) that obtained 135 best known
solutions on the small scale instances, and a Simi-
larity Hybrid Harmony Search algorithm (SHHS)
(Tsakirakis et al., 2019). In the latest, the authors
proposed two versions of their algorithm, one be-
ing static while the other is dynamic. The better
one, the dynamic, found 276 best known solu-
tions out of the 328 tested instances.

Population-based algorithms have also been used
to tackle the TOP. Ke et al. (2008) proposed 4
variants of Ant Colony Optimization algorithm
based on the algorithm used to build candidate
solutions. Out of the 4 versions, the sequential
one was the best one. Bouly et al. (2008) pro-
posed a Memetic Algorithm (MA) which con-
sists in the combination of a Genetic Algorithm
(GA) and local search operators. Results ob-
tained were comparable to those of Archetti et al.
(2007). Dang et al. (2011) proposed a Particle
Swarm Optimization-based Memetic Algorithm
(PSOMA) based on the work from Bouly et al.
(2008). It showed very good performances as
it outperformed existing algorithms. In 2013,
Dang et al. (2013a) proposed a PSO-inspired Al-
gorithm (PSOiA) based on their prior work. The
proposed algorithm outperformed all existing al-
gorithms: it was the first algorithm to find ev-
ery best known solutions of the small scale set
of instances. Based on their results, the authors
showed that a new set of instances was needed
to have a new base of research for the TOP, as
already proposed in Souffriau et al. (2010). They
built a new set of larger instances based on the OP
instances constructed by Fischetti et al. (1998).
A genetic algorithm approach was then proposed
by Ferreira et al. (2014), but they only tested a
limited number of small size instances and none
of the new large scale instances. A population-
based algorithm is also proposed by Vidal et al.
(2014b). Specifically, they adapted their Uni-
fied Hybrid Genetic Search (UHGS) (Vidal et al.,
2014a) framework and obtained very good re-
sults on the subset of small scale instances tested.
Finally, in 2020, a Scatter Search Hybrid ap-
proach was proposed (Alkhazaleh et al., 2019)
and showed good results as it got 154 best known
solutions out of the 157 tested instances belong-
ing to the small scale set. Other methods in-
cludes a Pareto Mimic Algorithm (PMA) (Ke
et al., 2016) which showed very good results both

on the small and large scale sets, and a Hybrid
Scatter Search with steep descent (HISS-SD) ap-
proach (Alkhazaleh et al., 2019) which obtained
results slightly worse than PSOiA (Dang et al.,
2013a).

Heuristic approaches are described in table 1. In
particular, we report, for each method, the algo-
rithm, the set of instance considered, the number
of best known solutions found, and the average
CPU (s).

3.3. *Very large scale*

The very large scale component has only been
tackled a few number of times in the VRP. In this
context, the number of customers is large and ex-
act methods are not suitable. The size of these
instances is obviously a key factor to choose or
adapt a method to this context. The goal is then to
obtain very good solutions in a reasonable com-
putational time based on the instance size and
the problem tackled. In Kytöjoki et al. (2007),
the authors developed a VNS that was coupled
with a GLS framework. Memory usage was opti-
mized by the use of compact information avoid-
ing the storage of the distance matrix. They also
used an appropriate representation of a solution
that eases classical operations like insertions and
removals. The algorithm managed to solve in-
stances up to 20 000 customers in a reasonable
time. Zachariadis and Kiranoudis (2010) pro-
posed a TS paired with Static Move Descriptors
(SMD), a method that greatly reduces the com-
putational complexity of local search operators
so that they cost an almost linear computational
time. Also using these SMD to diversify the ex-
ploration, they managed to solve instances up to
3 000 customers. Recently, Arnold et al. (2019)
proposed a knowledge-based heuristic based on a
prior analysis about the difference between (near-
optimal solutions and other solutions. Used to
penalize 'bad' edges in a GLS and associated to
pruning strategies and reduced information stor-
age, they managed to solve instances up to 30 000
customers. Finally, Accorsi and Vigo (2021) pro-
posed a new method based on an ILS. To reduce
the computational time, they used SMD, granular
neighborhood (Toth. and Vigo, 2003), and inten-
sify the optimization around areas that were re-
cently modified. The local search was designed
<table><caption>Table 1: Description of references method used. Based on the instance set, we report the number of best known solutions (BKS) found and the average CPU (s) reported.</caption><thead><tr><th>Method</th><th>Reference</th><th>Algorithm</th><th>Instance set</th><th># BKS</th><th>CPU (s)</th></tr></thead><tbody><tr><td>THM</td><td>Tang and Miller-Hooks (2005)</td><td>Tabu Search</td><td>Chao et al. (1996)</td><td>33/157</td><td>445.7</td></tr><tr><td>GTP</td><td>Archetti et al. (2007)</td><td>Tabu Search</td><td>Chao et al. (1996)</td><td>69/157</td><td>113.2</td></tr><tr><td>GTF</td><td>Archetti et al. (2007)</td><td>Tabu Search</td><td>Chao et al. (1996)</td><td>94/157</td><td>189.22</td></tr><tr><td>FVNS</td><td>Archetti et al. (2007)</td><td>Variable Neighborhood Search</td><td>Chao et al. (1996)</td><td>94/157</td><td>22.65</td></tr><tr><td>SVNS</td><td>Archetti et al. (2007)</td><td>Variable Neighborhood Search</td><td>Chao et al. (1996)</td><td>127/157</td><td>322.59</td></tr><tr><td>SACO</td><td>Ke et al. (2008)</td><td>Ant Colony</td><td>Chao et al. (1996)</td><td>128/157</td><td>294.61</td></tr><tr><td>DACO</td><td>Ke et al. (2008)</td><td>Ant Colony</td><td>Chao et al. (1996)</td><td>80/157</td><td>249.18</td></tr><tr><td>RACO</td><td>Ke et al. (2008)</td><td>Ant Colony</td><td>Chao et al. (1996)</td><td>81/157</td><td>238.77</td></tr><tr><td>SiACO</td><td>Ke et al. (2008)</td><td>Ant Colony</td><td>Chao et al. (1996)</td><td>84/157</td><td>250.58</td></tr><tr><td>SkVNS</td><td>Vansteenwegen et al. (2009b)</td><td>Skewed Variable Neighborhood Search</td><td>Chao et al. (1996)</td><td>44/157</td><td>4.63</td></tr><tr><td>GLS</td><td>Vansteenwegen et al. (2009b)</td><td>Guided Local Search</td><td>Chao et al. (1996)</td><td>21/157</td><td>9.24</td></tr><tr><td>FPR</td><td>Souffriau et al. (2010)</td><td>Path Relinking</td><td>Chao et al. (1996)</td><td>78/157</td><td>6.1</td></tr><tr><td>SPR</td><td>Souffriau et al. (2010)</td><td>Path Relinking</td><td>Chao et al. (1996)</td><td>126/157</td><td>260.61</td></tr><tr><td>MA</td><td>Bouly et al. (2008)</td><td>Memetic Algorithm</td><td>Chao et al. (1996)</td><td>146/157</td><td>114.77</td></tr><tr><td>PSOMA</td><td>Dang et al. (2011)</td><td>Particle Swarm</td><td>Chao et al. (1996)</td><td>146/157</td><td>50.46</td></tr><tr><td>AuLNS</td><td>Kim et al. (2013)</td><td>Augmented Large Neighborhood Search</td><td>Chao et al. (1996)</td><td>157/157</td><td>55.96</td></tr><tr><td>PSOiA</td><td>Dang et al. (2013a)</td><td>Particle Swarm</td><td>Chao et al. (1996)</td><td>157/157</td><td>128.76</td></tr><tr><td>MSA</td><td>Lin (2013)</td><td>Multi-start Simulated Annealing</td><td>Dang et al. (2013a)</td><td>71/82</td><td>11,031.04</td></tr><tr><td>UHGS</td><td>Vidal et al. (2014b)</td><td>Unified Hybrid Genetic Search</td><td>Chao et al. (1996)</td><td>133/157</td><td>41.34</td></tr><tr><td>UHGS-f</td><td>Vidal et al. (2014b)</td><td>Unified Hybrid Genetic Search</td><td>Chao et al. (1996)</td><td>155/157</td><td>192</td></tr><tr><td>MS-ILS</td><td>Vidal et al. (2014b)</td><td>Multi-start Iterated Local Search</td><td>Chao et al. (1996)</td><td>150/157</td><td>68.96</td></tr><tr><td>MS-LS</td><td>Vidal et al. (2014b)</td><td>Multi-start Local Search</td><td>Chao et al. (1996)</td><td>153/157</td><td>156</td></tr><tr><td>PMA</td><td>Ke et al. (2016)</td><td>Pareto Mimic Algorithm</td><td>Chao et al. (1996)</td><td>115/157</td><td>9.29</td></tr><tr><td>SHHS</td><td>Tsakirakis et al. (2019)</td><td>Similarity Hybrid Harmony Search</td><td>Chao et al. (1996)</td><td>157/157</td><td>66.85</td></tr><tr><td>SHHS2</td><td>Tsakirakis et al. (2019)</td><td>Similarity Hybrid Harmony Search</td><td>Dang et al. (2013a)</td><td>81/82</td><td>1,004.15</td></tr><tr><td>LNS</td><td>Orlis et al. (2020)</td><td>Large Neighborhood Search</td><td>Chao et al. (1996)</td><td>68/157</td><td>74.33</td></tr><tr><td>HALNS</td><td>Hammami et al. (2020)</td><td>Hybrid Adaptive Large Neighborhood Search</td><td>Chao et al. (1996)</td><td>105/157</td><td>74.28</td></tr><tr><td></td><td></td><td></td><td>Chao et al. (1996)</td><td>156/157</td><td>140</td></tr><tr><td></td><td></td><td></td><td>Chao et al. (1996)</td><td>157/157</td><td>23.8</td></tr><tr><td></td><td></td><td></td><td>Dang et al. (2013a)</td><td>82/82</td><td>783.36</td></tr><tr><td>HISS-SD</td><td>Alkhazaleh et al. (2019)</td><td>Hybrid Scatter Search</td><td>Chao et al. (1996)</td><td>154/157</td><td>80.95</td></tr></tbody></table>

in a Hierarchical Randomized Variable Neighborhood Descent (HRVND) to further promote the intensification and the diversification while maintaining efficient computational time. Results were better than previous works on the very large scale VRP.

With regard to the OP, Kobeaga et al. (2017) introduced a new set of very large scale instances. Authors proposed a genetic algorithm that maintains unfeasible solutions during the search. However, no specific mechanisms were introduced to address the very large scale component in their work, resulting in high computational time for the biggest instances of the set.

## 4. Problem formulation

We model the Multi-Depot Open Team Orien-
teering Problem with a graph $G = (V, A)$ where
$V = \{1, ..., N\}$ represents the set of vertices,
i.e. the customers, with $\{1, ..., m\}$ and $\{N - m, ..., N\}$ being the starting and ending points of

every route, $m$ the number of vehicles, and $A = \{(i, j) | i \in V, j \in V, i \neq j\}$ the set of edges. A profit $p_i$ is associated to each customer $i \in V$ and each edge $(i, j) \in A$ has a travel time $t_{i,j}$. Travel times to the ending points have a cost of 0 as these points are introduced to model the open path of each vehicle. The set of vehicles is noted $K = \{1, 2, ..., m\}$ and all vehicles share identical features. Every vehicle $k \in K$ must respect a time limit $D$.

We use two types of variables to model the MDO-
TOP: (1) binary variables $x_{i,j}^k$, which determine if
the vehicle $k \in K$ uses the edge $(i, j) \in A$, and (2)
binary variables $y_i^k$ which determine if the vertex
$i \in V$ is visited by the vehicle $k \in K$. Using these
variables, based on El-Hajj et al. (2016), we can
model the MDOTOP as follows:

$$z^* = \max \sum_{k \in K} \sum_{i \in V} y_i^k \times p_i \quad (1)$$
$$ \text{s.t. } \sum_{j \in V} x_{j,i}^k = \sum_{j \in V} x_{i,j}^k = y_i^k \quad \forall k \in K \\ \phantom{\text{s.t. } \sum_{j \in V} x_{j,i}^k = \sum_{j \in V} x_{i,j}^k = y_i^k \quad \forall k \in K} \forall i \in V \setminus \{1, \dots, k\} \\ \phantom{\text{s.t. } \sum_{j \in V} x_{j,i}^k = \sum_{j \in V} x_{i,j}^k = y_i^k \quad \forall k \in K} \cup \{N-k, \dots, N\} \tag{2} $$

$$ \sum_{k \in K} y_i^k \le 1 \qquad \forall i \in V \tag{3} $$

$$ \sum_{j \in V} x_{k,j}^k = \sum_{j \in V} x_{j,N-k}^k = 1 \quad \forall k \in K \tag{4} $$

$$ \sum_{i \in V} \sum_{j \in V} x_{i,j}^k \times t_{i,j} \le D \quad \forall k \in K \tag{5} $$

$$ \sum_{(i,j) \in S \times S} x_{i,j}^k \le |S| - 1 \quad \forall S \subseteq V \setminus \{1, N\}, \quad (6) \\ |S| \ge 2, \forall k \in K $$

$$ x_{i,j}^k \in \{0, 1\} \qquad \forall (i, j) \in A, \forall k \in K \tag{7} $$

$$ y_i^k \in \{0, 1\} \qquad \forall i \in V, \forall k \in K \tag{8} $$

The objective function (1) maximizes the total profit collected on customers. Constraints (2) are the flow conservation constraints and link variables $x_{ij}^k$ and $y_j^k$. Constraints (3) ensure that each customer can be visited at most once. Constraints (4) impose the starting and ending points for all vehicles. Constraints (5) guarantee that every vehicle will respect the time limit $D$. Finally, constraints (6) will make sure that there is no subtour in the solution.

To our knowledge, the MDOTOP was not considered in the literature. To compare our method with the literature, it is thus applied to the TOP. As no exact methods are applied to the large scale set of instances for the TOP, and because the best exact method (Orlis et al., 2020) already has important computational time on the small scale one, we propose a metaheuristic to address the problem.

## 5. Solution approach

In this section, we present the algorithm we have developed to tackle the very large scale TOP. As previously mentioned, the main goal of this paper is to propose an algorithm which quickly provides very good solutions so it can be used in a complex industrial context. Based on the literature, we proposed a metaheuristic which is more suitable to solve difficult and large scale routing problems in a reasonable time. We chose to develop a Large Neighborhood Search (LNS) to address the TOP. This choice is led by its high level

of performances when tackling the VRP and its variants while being highly scalable to solve industrial problems (Mara et al., 2022). LNS is first introduced in 1998 (Shaw, 1998) and then extended to the ALNS by Ropke and Pisinger (2006) who applied it on a Pickup and Delivery Problem with Time Windows (PDPTW). LNS is a metaheuristic based on the repetition of destroy and repair operators. The structure of our LNS is detailed in Algorithm 1. In the following, we first present our construction heuristic and then our LNS.

**Algorithm 1** Overall LNS framework used in this paper.

**Require:** Initial solution: $S_0$, initial temperature: $T_0$, number of non-improving iterations before increasing the size of neighborhood lists: $κ$, cooling factor: $c$, cooling step size: stepSize

$$ S_{\text{Best}} \leftarrow S_0, T \leftarrow T_0, \text{NoImp} \leftarrow 0 $$

**while** Non stopping criterion do

**for** step ← 1 to stepSize **do**

$$ S_{\text{New}} \leftarrow S_0 $$

Select a removal operator $D$ and a repairing operator $R$

Generate $q$ and remove $q$ vertices of $S_{\text{New}}$ using $D$

Repair $S_{\text{New}}$ using $R$

$$ \Delta = z(S_{\text{New}}) - z(S_0) $$

**if** $S_{\text{New}}$ meets the requirements **then**

Apply Local\_Search on $S_{\text{New}}$

**end if**

Generate $\delta \in (0, 1)$

**if** $S_{\text{New}}$ is better than $S_0$ **or** $e^{\frac{\delta}{T}} \ge \delta$ **then**

$$ S_0 \leftarrow S_{\text{New}} $$

**end if**

**if** $S_{\text{New}}$ is better than $S_{\text{Best}}$ **then**

$$ S_{\text{Best}} \leftarrow S_{\text{New}} $$

Reset the size of the neighborhood list

$$ \text{NoImp} \leftarrow 0 $$

**else**

$$ \text{NoImp} \leftarrow \text{NoImp} + 1 $$

**end if**

**if** $\text{NoImp} \ge \kappa$ **then**

Increase the size of the neighborhood list

$$ \text{NoImp} \leftarrow 0 $$

**end if**

**end for**

$$ T \leftarrow T \times c $$

**end while**

### 5.1. Construction heuristic

The LNS requires an initial solution $S_0$ that will be improved over iterations. In routing
problems, several methods exist to build an initial solution, as among the most popular ones, the Cheapest Insertion and the Clarke & Wright heuristic (Clarke and Wright, 1964). As we aim to deal with problems of thousands of points, a cluster-first route-second method is defined to build the initial solution. By partitioning the space, the construction of the initial solution is easier and the overall process might even be sped up by providing a better solution to the metaheuristic. This method has shown success in the TSP context where millions of customers can be tackled by partitioning the space before optimizing each partition independently (Taillard and Helsgaun, 2018).

### 5.1.1. Clustering-first

To do the clustering, k-means has shown good performances (Mariescu-Istodor, 2021). Based on it and proposed in Kaufman and Rousseeuw (1990), we then chose k-medoids to cluster the customers. In the TOP however, all customers are usually not visited as every route is constrained by a time limit. To take this into account, we propose an adaptation of the algorithm of Bernábe-Loranca et al. (2014). In their method, in order to build balanced clusters, the authors propose to modify the traditional function optimized in k-medoids by a weighted objective function. They apply it in a geographical context and show that using the modified k-medoids function results in better-balanced clusters. This idea of balancing clusters is interesting to represent the time limit associated to each route. It has already be shown that compact routes are usually better than routes overlapping each other and these intersections must be avoided in the VRP (Arnold and Sörensen, 2019). Having compact and non-overlapping routes should then ease the overall process of finding quickly very good solutions while the balance makes sure that each partition is equally distributed. Solutions where routes are compact, contiguous and non-overlapping also tend to be accepted more easily by the user in a realistic routing plan (Bräysy and Hasle, 2014), making the interest of the clustering even bigger for our application. The k-medoids function of Bernábe-Loranca et al. (2014) is defined by:

$$F1: \min w_{medoids} \left( \sum_{k=1}^{K} \sum_{i \in M_k} t_{i, C_k} \right) + w_{homogeneity} \left( \sqrt{\frac{\sum_{k=1}^{K} (|M_k| - B)^2}{N}} \right)$$

where $t_{i,C_k}$ is the travelling cost between the customer $i \in M_k$ and the center $C_k$ of the medoid $M_k$, $|M_k|$ the number of customers in the $k^{th}$ medoid and $B$ the balance objective equal to $\frac{N}{m}$. The first part is the classical k-medoids objective function to minimize. The second part is associated to Loranca's homogeneity function: it consists in comparing the number of customers belonging to the cluster and its balance objective to penalize the function according to this difference. An adaptation of this function is proposed to better represent the routing context. Indeed, k-medoids may associate a vehicle to a cluster which is far away from the vehicle's depot. This would induce a non-negligible cost in the vehicle's route which would not have been anticipated during the clustering process. To solve this problem, we introduce a new component to the k-medoids function proposed in Bernábe-Loranca et al. (2014):

$$F2: \min w_{medoids} \left( \sum_{k=1}^{K} \sum_{i \in M_k} t_{i, C_k} \right) + w_{homogeneity} \left( \sqrt{\frac{\sum_{k=1}^{K} (|M_k| - B)^2}{N}} \right) + w_{depot} \left( \sum_{k=1}^{K} \min_{i \in M_k} t_{k, i} \right)$$

The first two parts are Bernábe-Loranca et al. (2014) function while the last part is there to make sure that the clustering function takes into account the cost needed for a vehicle to reach its cluster. Note that in the TOP context all vehicles share a common depot but the function can easily be tuned to tackle the multi-depot variant. It is also possible to consider an unbalanced version,
for example if the fleet of vehicles is heterogeneous, to build clusters of different size based on the vehicle speed.

### 5.1.2. Routing-second

When the clustering phase is finished, each customer is inserted into its associated route (defined by its cluster) using the Cheapest Insertion heuristic while an insertion is feasible, that is an insertion which does not violate the time limit D of the route. Finally, the local search framework, detailed in Section 5.3, is applied to improve the quality of the initial solution.

## 5.2. Large Neighborhood Search

To optimize our initial solution, we chose to use a LNS. As it is often done, our LNS is paired with simulated annealing (SA) to escape local optimum by accepting slightly worse solutions (Kirkpatrick et al., 1983). Our LNS also has classical stopping criteria based on the computational time, the number of iterations and the number of iterations without improvement. Specific details are discussed next: first, we start to describe both destroy and repair operators considered in this paper. Then, we describe neighborhood lists that are used to reduce the number of evaluations done in our optimisation process. Afterwards, we present the blink that is done to diversify the neighborhood exploration. Finally, the objective function used to compare solutions is presented.

### 5.2.1. Destroy operators

Our LNS uses several destroy operators to explore a large neighborhood. The number of destroyed customers q will be picked from an interval $[q_{min}, q_{max}]$ for operators which destroy customers, and from an interval $[q_{seqmin}, q_{seqmax}]$ for operators which destroy a sequence of consecutive customers. At each iteration, the selected operator is chosen randomly to avoid redundancy. In addition, a variant based on sequences of consecutive customers is considered for most operators. Classical operators proposed by the literature and used in our algorithm are:

* Worst Cost (Sequence) destroy: criterion associated to the cost of a (sequence of) customer in the route;

* Worst Profit (Sequence) destroy: criterion associated to the profit of a (sequence of) customer;

* Random (Sequence) destroy: destroyed (sequence of) customers are chosen randomly.

* Shaw destroy: Shaw's criterion was first introduced in Shaw (1998). It consists in destroying relative customers from the route. In our work, we consider two customers i and j as relatives if the travelling time $t_{i,j}$ between them is small enough.

Dedicated operators used are:

* Rectangle destroy: geographical position is a criterion that may be useful when tackling specific instances where some areas are widely covered by customers. Introduced in Demir et al. (2012), this operator picks randomly a seed customer from the problem and deletes every customer which is in a rectangle around him (figure 1). While the number $q \in [q_{min}, q_{max}]$ of customers to delete is not reached, the rectangle is extended.

* Worst Cost-Efficiency (Sequence) destroy: the profit is a good indicator of the relevance of a customer. However, a customer can bring a small profit while not being costly in travelling time. We then define an operator based on the cost-effectiveness of a customer which deletes from the solution the $q \in [q_{min}, q_{max}]$ worse customers based on this criterion. The cost-efficiency of a customer i positioned between customers j and l, noted $CE_i$, is computed as follows:

$$CE_i = \frac{p_i}{c_{j,l}^i} \qquad (9)$$

$$c_{j,l}^i = t_{j,i} + t_{i,l} - t_{j,l} \qquad (10)$$

where $p_i$ is the customer's profit, and $c_{j,l}^i$ its cost of visit in its route as defined in Equation 8. A cost-efficient customer is then very interesting to visit because he doesn't cost much compared to the profit he brings. This operator makes a link between the objective function, which maximizes the total collected profit, and the time limit constraint associated to the routes.
<figure><img src="image_4.png" /><figcaption>Figure 1: Figure showing the principle of Rectangle De-
stroy. The customer (0) is picked as the seed, thus is the
center of the rectangle. Every customer in the resulting rect-
angle is destroyed from the solution.</figcaption></figure>

5.2.2. Repair operators

Our LNS is composed of seven repair operators.
We chose these operators based on their goal
to avoid overlapping operators while exploring a
large and diverse neighborhood. As we already
mentioned, unlike in the VRP, in the TOP it is
not possible to insert every customer into a vehi-
cle's route. Those operators aim to insert the best
customers possible while maintaining the feasi-
bility of the route. To do so, after each insertion,
we check that it is still possible to insert a cus-
tomer. The reparation process stops when the op-
erator can't insert a new customer. For all these
operators, customers are inserted into their best
feasible position, that is the position of insertion
inducing the smallest increase of cost among the
route. Our repair operators can be categorized
in two families: global insertion operators, which
is composed of operators that compare every cus-
tomer at each insertion, and sorted insertion oper-
ators, which insert customers in a pre-computed
order.

Global insertion operators. Global insertion op-
erators are more costly than sorted insertion op-
erators but they also have a better view of the
solution at each step of insertion. Most of the
time, they remain fast to compute but their com-
putational time also grows with the instance size.
This may be problematic in our context as we
want to solve very large scale instances. To avoid
this problem, they tend to be used with a smaller
probability than other insertion operators. Two
global insertion operators are evaluated in our
LNS:

* Best Cost insertion: criterion associated to the cost related to the insertion of a customer into a route;

* Cost-Efficiency insertion: criterion associ-
ated to the cost-efficiency of a customer into
a route. As the customer is not yet visited
and because customers are only inserted into
their best feasible position of insertion, this
criterion can be computed as:

$$
CE_i = \frac{p_i}{\min_{j,l} c_{j,l}^i} \quad (11)
$$

where $\min_{j,l} c_{j,l}^i$ corresponds to the minimum
feasible cost insertion of $i$ in the solution.

Sorted insertion operators. Sorted insertion op-
erators are fast to compute as they usually start
by sorting the customers based on a specific crite-
rion and then insert them in the defined order. In
opposition with global insertion operators, they
have a very limited view of the solution at each
step of insertion as the defined order is not re-
assessed after any insertion. Repair operators that
use this principle are the following:

* Best Profit insertion: criterion associated to the profit of a customer;

* Random insertion: select randomly the cus-
tomer to insert into a route;

* Order insertion: replace the customers that just got deleted from the solution. It aims at moving well-organized sequences of consecutive customers into a better place. Indeed, if a sequence of customers is well-organized, its cost might be low if globally taken. Nevertheless, this does not mean that
the sequence is at the best place in the solution. The Order insertion operator aims at correcting these kinds of issues.

* Reverse Order insertion: inserts customers in the reverse order of destruction. This means that the last customer deleted from the solution is the first to be replaced. The operator aims at reversing sequences of consecutive customers which might be well-organized but might be better placed if reversed.

* k-Regret Cost-Efficiency insertion: based on the classical regret insertion operator, this operator searches for customers that are the most critical in the insertion order. The k-regret associated to the cost-efficiency criterion of a customer i can be computed as:

$$ \sum_{j=1}^{k} CE_{i}^{0} - CE_{i}^{j} \quad (12) $$

where $CE_{i}^{j}$ is the $j^{th}$ best cost-efficiency of i. The k-Regret Cost-efficiency operator has a similar objective to the Cost-efficiency operator: to find the best customers to insert according to both the cost associated to their visit and the profit they bring. However, it does it in a smaller computational time, as customers are sorted before inserting them. In this paper, a full regret is used to compute the regret value, meaning that all feasible insertions are considered for each customer in the computation of the regret cost-efficiency value.

### 5.2.3. Neighborhood lists

To avoid the evaluation of too much possibilities during the process, neighborhood lists are used. We use similar ones as proposed by Toth and Vigo (2003), which are called granular lists. These lists aim at defining a set of neighbors for every customer based on a set of 'short' edges. In our algorithm, a customer i is a neighbor of a customer j if it follows one of the following conditions:

* $t_{i,j} < \vartheta = \beta \times \frac{cs_0}{\tau+m}$;

* j is at most the $\eta^{th}$ nearest customers from i.

where $\vartheta$ is the granularity threshold, $\beta$ is a positive sparsification parameter, $cs_0$ is the cost value of the initial heuristic solution, i.e. the sum of every route's cost, $\tau$ is the number of visited customers in the solution, and $\eta$ is the minimum number of neighbors considered for each customer. The first condition enables the algorithm to search around 'short' arcs while the second one makes sure that every customer has a minimum number of neighbors, tackling some cases where a customer might be isolated from the others. As the initial granularity threshold value might not be the best suited for the tackled problem, it may be interesting to increase the size of our lists. For this purpose, we also define a parameter $\kappa$ which corresponds to the maximum number of LNS iterations without finding a new best solution. If during the LNS process we reach this number, then the size of our lists is increased by increasing the value of $\beta$. A maximum number of neighbors per customer is also defined to avoid considering too much neighbors. These lists are used in every repair operator and in every local search operator. For example, while repairing a solution, only the insertion of a customer around its neighbors is evaluated. Similarly, only moves that imply neighbors are evaluated in the local search framework. Thus, the size of the graph considered is reduced as illustrated figure 2.

### 5.2.4. Blink

A blink is used to add a diversification process in our destroy & repair operators. Blink is introduced in Christiaens and Vanden Berghe (2020) and consists in skipping an evaluation or a movement based on a random criterion. Several types of blink were tested: blinking when finding a new best candidate in destroy & global repair operators, blinking to avoid the evaluation of a customer for destruction (Dumez et al., 2021), blinking to avoid the evaluation of a customer insertion, and blinking to avoid a position of insertion for a customer. Overall, only the first one has improved the algorithm performance, meaning that sometimes the algorithm ignores a new best candidate to remove or insert in the solution.

### 5.2.5. Objective function

Obviously, the main objective function to optimize is the total profit collected on customers.
<figure><img src="image_5.png" /><figcaption>Figure 2: Figure showing an example of the reduction in the graph size while using neighborhood lists. Edges which are more costly than a defined threshold value are not explicitly considered anymore.</figcaption></figure>

However, it is important not to overlook the cost of the solution associated to the collected profit. In the TOP, several solutions may have the same profit but differ in its routes cost. A smaller-cost route should be preferable over a bigger-cost route as it should be easier to add a new customer into the smallest one. This idea is used by Vidal et al. (2014b) and has already shown its interest. As such, solutions having a smaller cost are prioritized when comparing to solutions having the same profit.

### 5.3. Local search

The main goal of this local search framework is to quickly get to, or near, the local optimum. By pairing this framework and the destroy & repair process, we hope to cover a very wide number of local optima and, by extension, to find the global optimum. The local search framework is composed of several operators which are applied in the given order while there is an improvement: 1-1 Exchange, Replace, 3-opt, and Cross-Exchange. This order is chosen based on the computational complexity of local search operators. For all but 3-opt, the best-improvement

criterion is used to determine the move to apply. For 3-opt, a first-improvement strategy is used. If the local search framework improves the solution, it tries to insert new customers using the Cost-efficient repair operator as a compromise between the additional profit gained by visiting a new customer and the remaining time available in the associated route. This process is repeated while it improves the quality of the solution.

#### 5.3.1. Restricted candidate list

Following the same principle than the neighborhood lists, we define a Restricted Candidate List (RCL). Our choice of using it is based on Arnold et al. (2019) where authors show that, in very large scale problems, it is important not to lose time in the evaluation of already good area, while intensifying the optimisation around bad areas will lead to an overall better solution. It is then necessary to define what is a good area and a bad one in a solution. This definition might be problem dependent. In their work, Arnold and Sörensen (2017) study how different are (near-) optimal solutions from non-optimal solutions based on several metrics on a VRP problem. Using these metrics, they managed to predict the quality of a solution with an accuracy up to 93%, which shows that these metrics can be used to differentiate these solutions. They finally use the width, the cost and the depth implied by an edge to define a 'bad' edge, and use this definition to build a very competitive heuristic for the VRP. In the TOP context, profit is at least as important as the cost of a customer and these observations might not hold. However, the cost of a route is still a key factor while optimizing a solution since it might be possible to insert another customer by reducing it. In our work, we characterize customers and not edges as profit is customer-dependent. A customer *i* positioned between customers *j* and *l* is then evaluated by his profit *p*<sub>*i*</sub>, his cost *c*<sup>*i*</sup><sub>*j*,*l*</sub> (see Equation 10), his depth *depth*<sub>*i*</sub> and his width *width*<sup>*i*</sup><sub>*j*,*l*</sub> that can be computed as:

$$ width_{j,l}^{i} = width(j, i) + width(i, l) \quad (13) $$

Both the depth of a customer and its width are represented in figure 3. To compute the width *width*(*i*, *j*), first build the parallel straight line
from (0, G) going through i, with G the route's center of gravity. width(i, j) is then computed as the distance between j and its projection on the previously built straight line. The resulting function used to evaluate a customer is then:

$$V_i = (w_p \times p_i + w_w \times width_{j,l}^i + w_c \times c_{j,l}^i) \times \left( \frac{depth_i}{maxDepth} \right)^{\frac{w_d}{2}} \quad (14)$$

where maxDepth is the maximum depth in the route, and $w_p, w_w, w_c$ and $w_d \in \{0, 1\}$ are the weight applied to each metrics considered. The RCL is only used in the 1-1 Exchange, Best Replace and Cross-exchange operators, to limit the number of evaluated customers while targeting the 'bad' ones. It is composed of the $\phi$ worst customers of the solution based on Equation 14.

<figure><img src="image_6.png" /><figcaption>Figure 3: Illustration of the metrics used to characterize the restricted candidate list. (G) is the route's center of gravity. The depth of (i) corresponds to the distance between the depot and i.</figcaption></figure>

## 6. Numerical results on literature instances

Our algorithm is implemented in C++11. We evaluate it on an Intel Xeon processor E5-2690, 2.60GHZ with 8 GB of RAM. The LNS is tested in the same conditions as in Hammami et al. (2020): we report the best solutions obtained from twenty independent runs which are performed on each instance. Tests are performed on two sets of existing instances, and on a new set of very large scale instances that we built for

the TOP based on the instances of Kobeaga et al. (2017) for the OP. Instances are described in Section 6.1.

### 6.1. Instances description

To evaluate our algorithm, we apply it to popular TOP instances from the literature and on a newly introduced set of very large scale instances. These instances are classified into three different categories which are small scale, large scale and very large scale, based on their size.

#### 6.1.1. Small scale instances

The small scale instances are those introduced in Chao et al. (1996). These instances are separated into seven sets based on their size, which vary from 21 to 102 customers. In each set, the number of customers and their position stay the same, but the time limit and the number of vehicles vary. According to Souffriau et al. (2010), out of the 387 instances of this set, only 157 are relevant as every algorithm got the same results on the remaining instances of this set. Therefore, only these 157 instances are considered in this paper.

#### 6.1.2. Large scale instances

We also test our LNS on a larger set of instances. This set is the one reported by Dang et al. (2013a). It was introduced to give a new area of research on the TOP as PSOIA (Dang et al., 2013a) found all best known solutions when applied to the small scale set of instances. This set is composed of 333 instances which were adapted from the OP (Fischetti et al., 1998) and derived from the Capacitated VRP (CVRP) and the TSP. For the CVRP, customers'demand became their profit, whereas for the TSP instances, profits were created using three ways:

* Every customer has a profit of 1 (gen1);

* Every customer's profit is computed by a pseudo-random function so that the value can't be less than 1 and more than 100 (gen2);

* Every customer has a profit dependent on its distance from the depots. The further the customer, the bigger the profit (gen3).
These instances are larger than the previous set, ranging from 101 to 400 customers. Still, they are not big enough to model some industrial problems which can have several thousands of customers to consider.

### 6.1.3. Very large scale instances

The main goal of our algorithm is to tackle instances of several thousands of customers. To our knowledge, such instances are not available in the literature in the TOP context. A new set of instances based on the literature (Kobeaga et al., 2017) is built by adapting the very large scale instances from the OP. The time limit $D^{TOP}$ of the TOP is based on the time limit $D^{OP}$ of the OP and determined as in Chao et al. (1996): $D^{TOP} = \frac{D^{OP}}{m}$, where *m* is the number of vehicles considered. Instances can be found at https://github.com/CharlyChgn/VLS-Team-Orienteering-Problem. It consists in 24 problems associated to 3 classes of profit generation (gen1, gen2 and gen3) as in Dang et al. (2013a) (and explained previously for large instances) and with 4 variations on the number of vehicles, resulting in a total of 288 instances. As these instances are bigger, it is easier to consider more vehicles while still having a large number of customers per route. This is consistent with our goal to tackle industrial problems as the number of vehicles can be bigger in realistic problems. In this set of instances, the number of vehicles varies between 2, 3, 8 and 10 vehicles while the number of customers ranges from 1001 to 5395.

## 6.2. Parameters

As previously mentioned, our LNS is composed of numerous parameters. A summary of their notations and definitions can be found in table 2. To evaluate our algorithm, these parameters values need to be fixed. As our main goal is to show that our algorithm is competitive to tackle big instances, a subset of 14 instances from the large and the newly introduced very large scale set are used. These instances are selected to cover different types of instances based on the depot position, and all kinds of profit generation are considered. They range from 195 to 3795 customers. The algorithm is applied 10 times on each selected instance with different parameters values

picked from the literature. Parameters' values are fixed one by one based on their impact on the solution's quality and the computational time. Final results are also summarized in table 2. A similar task is done to evaluate the interest of our destroy and repair operators. Table 3 sums the remaining operators used in the final algorithm. It is noteworthy that, even if random operators manage to bring slightly better solutions, we chose not to use them as they have low chances to be of interest when applied to the very large scale set of instances.

According to the results, local search is applied differently based on the set of instances tackled: it is only applied when a new best solution is found for the small and large scale set of instances, while it is applied each time the obtained solution is better than the solution before the destroy & repair process for the very large scale set. To ensure consistency in computational time, the stopping criterion is 250 000 iterations or 100 000 iterations without improvement for the small and large scale set, and 100 000 iterations for the very large scale set. This high number of iterations without improvement is explained by the time needed to extend the neighborhood lists which enables a larger exploration. The maximal computational time allowed is one hour but we aim to obtain very good solutions in a budget time of 10 minutes.

### 6.2.1. Clustering

The proposed clustering is based on three terms associated to the compactness (corresponding to the classical k-medoids function), the balance and the cost for a vehicle to reach its associated cluster. Figure 4 shows two examples of differences between the clustering method proposed by Bernábe-Loranca et al. (2014) and our adapted method. As can be seen, vehicles are closer to their depot using our method than the clustering function used by Bernábe-Loranca et al. (2014). To have a better view of the impact of each part of the proposed function, we apply our clustering algorithm to the large scale set of instances. We ignore instances that only differs in the profit generation as the clustering function would then yield the same clusters. Results reported in table 4 show the average value of each part and for different weights. These values need to be the small-
<table><caption>Table 2: Parameters description and values after the calibration phase.</caption><thead><tr><th>Parameters</th><th>Description</th><th>Value</th></tr></thead><tbody><tr><td rowspan="3">Clustering</td><td>w<sub>medoids</sub></td><td>Weight of the medoids cost in the k-medoids function</td><td>0.2</td></tr><tr><td>w<sub>homogeneity</sub></td><td>Weight of the balance cost in the k-medoids function</td><td>0.7</td></tr><tr><td>w<sub>depot</sub></td><td>Weight of the depot-to-cluster cost in the k-medoids function</td><td>0.1</td></tr><tr><td rowspan="2">Destroy operators</td><td>[q<sub>seqmin</sub>, q<sub>seqmax</sub>]</td><td>Number of customers removed by destroy operators (%)</td><td>[1,20]</td></tr><tr><td>[q<sub>seqmin</sub>, q<sub>seqmax</sub>]</td><td>Number of customer removed by sequential destroy operators (%)</td><td>[1,20]</td></tr><tr><td rowspan="3">SA framework</td><td>δ</td><td>Degradation used to compute the initial temperature (%)</td><td>1</td></tr><tr><td>c</td><td>Cooling factor</td><td>0.99975</td></tr><tr><td>stepSize</td><td>Cooling step size</td><td>50</td></tr><tr><td rowspan="4">Stopping criterion</td><td>CPU<sub>max</sub></td><td>Maximum computational time (s)</td><td>3600</td></tr><tr><td>itermax</td><td>Maximum number of iterations for small scale and large instances</td><td>250 000</td></tr><tr><td>NoImp<sub>max</sub></td><td>Maximum number of iterations for very large scale instances</td><td>100 000</td></tr><tr><td></td><td>Maximum number of iterations without improvement</td><td>100 000</td></tr><tr><td rowspan="7">Neighborhood lists</td><td>β<sub>0</sub></td><td>Initial sparsification parameter</td><td>1</td></tr><tr><td>β<sub>max</sub></td><td>Maximum sparsification parameter</td><td>15</td></tr><tr><td>β<sub>+</sub></td><td>Value of increment of β</td><td>0.5</td></tr><tr><td>η</td><td>Minimum number of neighbors per customer</td><td>10</td></tr><tr><td>γ</td><td>Maximum number of neighbors per customer</td><td>25</td></tr><tr><td>κ</td><td>Number of non-improving iteration before increasing the size of neighborhood lists</td><td>1000</td></tr><tr><td>φ</td><td>Number of customers considered in local search (%)</td><td>5</td></tr><tr><td rowspan="5">Local search</td><td>w<sub>p</sub></td><td>Weight applied to the profit value used to evaluate a customer</td><td>1</td></tr><tr><td>w<sub>c</sub></td><td>Weight applied to the cost value used to evaluate a customer</td><td>1</td></tr><tr><td>w<sub>w</sub></td><td>Weight applied to the width value used to evaluate a customer</td><td>1</td></tr><tr><td>w<sub>d</sub></td><td>Weight applied to the depth value used to evaluate a customer</td><td>1</td></tr></tbody></table>

<table><caption>Table 3: Results for the operator selection.</caption><thead><tr><th>Type of operator</th><th>Operator</th><th>State</th><th>Score</th></tr></thead><tbody><tr><td rowspan="7">Destroy Operator</td><td>Worst Cost Destroy</td><td>✓</td><td>1</td></tr><tr><td>Worst Cost Sequence Destroy</td><td>✓</td><td>1</td></tr><tr><td>Random Destroy</td><td>✗</td><td>-</td></tr><tr><td>Random Sequence Destroy</td><td>✓</td><td>1</td></tr><tr><td>Shaw Destroy</td><td>✓</td><td>3</td></tr><tr><td>Rectangle Destroy</td><td>✓</td><td>1</td></tr><tr><td>Worst Profit Destroy</td><td>✓</td><td>2</td></tr><tr><td rowspan="5">Repair Operator</td><td>Worst Profit Sequence Destroy</td><td>✗</td><td>-</td></tr><tr><td>Worst Cost-efficiency Destroy</td><td>✓</td><td>2</td></tr><tr><td>Worst Cost-efficiency Sequence Destroy</td><td>✓</td><td>1</td></tr><tr><td>Best Cost Insertion</td><td>✗</td><td>-</td></tr><tr><td>Random Insertion</td><td>✗</td><td>-</td></tr><tr><td>Order Insertion</td><td>✓</td><td>4</td></tr><tr><td>Reverse Order Insertion</td><td>✓</td><td>4</td></tr><tr><td>Best Profit Insertion</td><td>✓</td><td>4</td></tr><tr><td>Best Cost-efficiency Insertion</td><td>✓</td><td>1</td></tr><tr><td>Regret Cost-efficiency Insertion</td><td>✓</td><td>4</td></tr></tbody></table>

est possible. Overall, it shows that each component add a control over the associated criterion, thus confirming the relevance of the latter one in a routing context. The impact of the weights on the final solution is evaluated in table 5 based on the relative percentage error (RPE), the average relative percentage error (ARPE) and the computational time. RPE and ARPE are computed as:

$$RPE = \frac{z(S_{BKS}) - z(S_{Best})}{z(S_{BKS})} \quad (15)$$

$$ARPE = \frac{z(S_{BKS}) - z(S_{mean})}{z(S_{BKS})} \quad (16)$$

with $z(S_{BKS})$ the objective function of the best known solution, $z(S_{Best})$ the profit of the best found solution, and $z(S_{mean})$ the average profit obtained along the whole set of executions. Note
that, for the very large scale instances of the subset of calibration, $z(S_{BKS})$ values are computed using the best value obtained while modifying the parameter's value.

Results show how each term may change the quality of the average solution found and the associated computational time. In particular, considering all three terms of the function gives slightly better solutions in average while also being faster to compute. Final weights used in this paper can be found in table 2.

<table><caption>Table 4: Summary results of the clustering function when applied on the large scale set of instances with different weights ($w_{medoids}$, $w_{homogeneity}$, $w_{depot}$). Compactness (C) is associated to the classical k-medoids function, balance (B) to the added part of Bernábe-Loranca et al. (2014), and depot-to-cluster (DtC) to the cost for a vehicle to reach its associated cluster. Values are computed for each clusters independently and then averaged. Values reported correspond to the average across the whole set of instances. For each criterion, we aim for the smallest value possible.</caption><thead><tr><th>Weights</th><th>C</th><th>B</th><th>DtC</th></tr></thead><tbody><tr><td>(1,0,0)</td><td>713.16</td><td>3.22</td><td>514.98</td></tr><tr><td>(0,1,0)</td><td>1007.38</td><td>0.47</td><td>568.60</td></tr><tr><td>(0,0,1)</td><td>1063.48</td><td>4.88</td><td>236.63</td></tr><tr><td>(0.3,0.7,0)</td><td>807.85</td><td>0.75</td><td>662.38</td></tr><tr><td>(0.2,0.7,0.1)</td><td>870.84</td><td>0.55</td><td>656.62</td></tr></tbody></table>

<table><caption>Table 5: Impact of the weight used in the clustering function on the calibration subset, with $w_{Cl} = (w_{medoids}, w_{homogeneity}, w_{depot})$.</caption><thead><tr><th>Parameters</th><th>RPE (%)</th><th>ARPE (%)</th><th>CPU (s)</th></tr></thead><tbody><tr><td>w<sub>Cl</sub> = (1, 0, 0)</td><td>1.09</td><td>2.98</td><td>344.99</td></tr><tr><td>w<sub>Cl</sub> = (0, 1, 0)</td><td>0.88</td><td>1.88</td><td>306.86</td></tr><tr><td>w<sub>Cl</sub> = (0, 0, 1)</td><td>0.88</td><td>1.92</td><td>296.55</td></tr><tr><td>w<sub>Cl</sub> = (0.3, 0.7, 0)</td><td>0.50</td><td>2.00</td><td>302.36</td></tr><tr><td>w<sub>Cl</sub> = (0.2, 0.7, 0.1)</td><td><strong>0.17</strong></td><td><strong>1.78</strong></td><td><strong>293.62</strong></td></tr></tbody></table>

### 6.2.2. Adaptive layer

LNS can be extended to the ALNS by adding an Adaptive layer. In the ALNS framework, operators are attributed a score based on their past performance in the algorithm. Although this might be interesting to prioritize specific operators which might be different based on the instance tackled, a recent study (Turkeš et al., 2021) showed that the added value was quite small. Nevertheless, during the calibration phase,

we also tried using the adaptive layer. Results showed that the adaptive layer is not useful for our algorithm as better results were obtained without it (table 6). As LNS can have better results by fixing operators' score (Dumez et al., 2021), several values were tested for the best operators according to both their performance and their computational time. Final score for each operator can be found in table 3.

<table><caption>Table 6: Impact of the adaptive layer on the calibration subset.</caption><thead><tr><th>Parameters</th><th>RPE (%)</th><th>ARPE (%)</th><th>CPU (s)</th></tr></thead><tbody><tr><td>LNS</td><td><strong>0.25</strong></td><td><strong>1.87</strong></td><td><strong>293.62</strong></td></tr><tr><td>σ = (33, 9, 13)</td><td>0.98</td><td>2.87</td><td>525.09</td></tr><tr><td>σ = (33, 20, 13)</td><td>0.49</td><td>2.85</td><td>511.75</td></tr><tr><td>σ = (1, 1, 1)</td><td>0.98</td><td>2.58</td><td>491.66</td></tr></tbody></table>

### 6.2.3. Blink

The blink process is evaluated. In our algorithm, it consists in skipping a new best candidate for both deletion and insertion in our destroy & repair process. Results on the calibration subset are summarized in table 7. Note how this process is, in average, beneficial as it improves the quality of the algorithm (+0.12%) by adding more diversification while also decreasing the computational time needed to compute the solution (-20s).

<table><caption>Table 7: Impact of the blink process on the calibration subset.</caption><thead><tr><th>Parameters</th><th>RPE (%)</th><th>ARPE (%)</th><th>CPU (s)</th></tr></thead><tbody><tr><td>Blink = 0.0</td><td>0.68</td><td>1.96</td><td>370.77</td></tr><tr><td>Blink = 0.1</td><td><strong>0.22</strong></td><td><strong>1.84</strong></td><td><strong>349.90</strong></td></tr><tr><td>Blink = 0.3</td><td>0.65</td><td>1.98</td><td>385.18</td></tr></tbody></table>

### 6.2.4. Restricted candidate list

The RCL is also evaluated in table 8 where its use and different cost function are considered. In particular, we compare the classical function used to evaluate a customer and only based on its cost, the function introduced by Arnold et al. (2019) which adds relevant metrics, and ours which adapts the latest to the TOP context. Results show that the RCL is beneficial for the algorithm, and that our adapted function also bring a better gain to the process. RCL reduces the computational time of more than 600 seconds while
<figure><img src="image_7.png" /><figcaption>Figure 4: Examples of differences between Loranca's clustering (right) and the adapted function used in this paper (left).</figcaption></figure>

improving the quality of obtained solutions of 0.31% in average. Note that for the biggest instances (3795 customers), when the RCL is not used, the stopping criterion is the maximum computational time (3600s). Results also confirm that Arnold et al. (2019) cost function is better than the classical cost used to evaluate a customer (+0.4%), while the addition of the profit further increases the solution's quality (+0.25%).

## 6.3. Benchmark

### 6.3.1. Small scale instances

We first test our algorithm on the small scale set of instances. Our method, named LNS2, is compared with several algorithms (described in table 1) based on their results: a throughout comparison can be seen in figures 5 and 6. The best solutions obtained for each set of instances are reported in tables 17 to 20. On these instances, our algorithm finds 152 out of the 157 best known solutions (BKS) in a smaller computational time

than methods obtaining similar results. Our algorithm is indeed very good on this criterion with respect to the number of best known solutions found, outperforming existing literature. The relative percentage error (RPE) is then computed and compared with existing literature. Results are summarized in tables 9 to 11 and also show that our algorithm is competitive to quickly get very good solutions. Figures 5 and 6 show that our algorithm (LNS2) belongs to the pareto front on both the number of BKS found and the RPE, depending on the computing time. In fact, our algorithm, the SkVNS (Vansteenwegen et al., 2009b) and the HALNS (Hammami et al., 2020) compose the pareto front on both criteria as at least one of these methods dominates the others. Overall, results are particularly good as the algorithm parameters were not trained on this set of instances.
<figure><img src="image_8.png" /><figcaption>Figure 5: Number of BKS found based on the average computational time and the algorithm used for the small scale set of instances.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 6: RPE based on the average computational time and the algorithm used for the small scale set of instances.</figcaption></figure>
<table><caption>Table 8: Impact of the Restricted Candidate List framework on the calibration subset. We compare the use of restricted candidate list with different values for each weight $w_{LS} = (w_p, w_c, w_w, w_d)$. In particular, we compare the algorithm without RCL ($\varphi = 100$), the use of RCL only considering the cost of a customer in the route ($w_{LS} = (0, 1, 0, 0)$), the RCL with the function of Arnold et al. (2019) ($w_{LS} = (0, 1, 1, 1)$) and with ours ($w_{LS} = (1, 1, 1, 1)$). When considering a RCL, value of $\varphi$ is 5.</caption><thead><tr><th>Parameters</th><th>RPE (%)</th><th>ARPE (%)</th><th>CPU (s)</th></tr></thead><tbody><tr><td>φ = 100</td><td>0.78</td><td>2.15</td><td>1045.88</td></tr><tr><td>w<sub>LS</sub> = (0, 1, 0, 0)</td><td>0.51</td><td>2.49</td><td>326.57</td></tr><tr><td>w<sub>LS</sub> = (0, 1, 1, 1)</td><td>0.44</td><td>2.09</td><td>379.52</td></tr><tr><td>w<sub>LS</sub> = (1, 1, 1, 1)</td><td><strong>0.22</strong></td><td><strong>1.84</strong></td><td><strong>349.90</strong></td></tr></tbody></table>

<table><caption>Table 9: Average CPU time (s) based on the small scale data set considered.</caption><thead><tr><th>Instances</th><th>SkVNS</th><th>GLS</th><th>FPR</th><th>MA</th><th>AuLNS</th><th>PSOiA</th><th>UHGS</th><th>MS-ILS</th><th>MS-LS</th><th>PMA</th><th>LNS</th><th>HALNS</th><th>HISS-SD</th><th>LNS2</th></tr></thead><tbody><tr><td>4</td><td>7.4</td><td>11.4</td><td>8.6</td><td>182.36</td><td>77.3</td><td>218.58</td><td>236.35</td><td>202.68</td><td>15.9</td><td>109.3</td><td>218.02</td><td>32.24</td><td>80.39</td><td><strong>5.16</strong></td></tr><tr><td>5</td><td><strong>1.5</strong></td><td>3.5</td><td>2.9</td><td>35.33</td><td>22.1</td><td>49.5</td><td>138.02</td><td>89.34</td><td>3.36</td><td>22.9</td><td>66.39</td><td>11.63</td><td>50.24</td><td>3.72</td></tr><tr><td>6</td><td><strong>1.9</strong></td><td>4.3</td><td>2.1</td><td>39.07</td><td>12.3</td><td>47.08</td><td>91.02</td><td>56.35</td><td>1.97</td><td>36.4</td><td>42.79</td><td>9.67</td><td>62.02</td><td>3.65</td></tr><tr><td>7</td><td><strong>4.3</strong></td><td>12.1</td><td>6.3</td><td>112.75</td><td>66.8</td><td>97.47</td><td>228.01</td><td>201.87</td><td>9.76</td><td>54.6</td><td>152.95</td><td>30.89</td><td>120.39</td><td>5.34</td></tr><tr><td>Avgset</td><td><strong>3.78</strong></td><td>7.83</td><td>4.98</td><td>92.38</td><td>44.63</td><td>103.16</td><td>173.35</td><td>137.56</td><td>7.75</td><td>55.8</td><td>120.04</td><td>21.1</td><td>78.26</td><td>4.47</td></tr><tr><td>Avg</td><td><strong>4.63</strong></td><td>9.24</td><td>6.1</td><td>114.77</td><td>55.96</td><td>128.76</td><td>192</td><td>156</td><td>9.29</td><td>66.85</td><td>140</td><td>23.8</td><td>80.95</td><td>4.65</td></tr></tbody></table>

<table><caption>Table 10: Average RPE to the best known solution based on the small scale data set considered.</caption><thead><tr><th>Instances</th><th>BKS</th><th>SkVNS</th><th>GLS</th><th>FPR</th><th>MA</th><th>AuLNS</th><th>PSOiA</th><th>UHGS</th><th>MS-ILS</th><th>MS-LS</th><th>PMA</th><th>LNS</th><th>HALNS</th><th>HISS-SD</th><th>LNS2</th></tr></thead><tbody><tr><td>4</td><td>54</td><td>1.470</td><td>2.967</td><td>0.725</td><td>0.029</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.004</td><td>0.012</td><td>0.190</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.001</td><td>0.034</td></tr><tr><td>5</td><td>45</td><td>0.622</td><td>2.515</td><td>0.230</td><td>0.062</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.057</td><td><strong>0.000</strong></td><td>0.007</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td></tr><tr><td>6</td><td>15</td><td>0.520</td><td>1.776</td><td>0.112</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.032</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td></tr><tr><td>7</td><td>43</td><td>1.309</td><td>3.079</td><td>0.540</td><td>0.013</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.142</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.007</td><td>0.071</td></tr><tr><td>AVG set</td><td>157</td><td>0.980</td><td>2.584</td><td>0.402</td><td>0.026</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.001</td><td>0.003</td><td>0.105</td><td><strong>0.000</strong></td><td>0.002</td><td><strong>0.000</strong></td><td>0.002</td><td>0.026</td></tr><tr><td>AVG all</td><td>157</td><td>1.089</td><td>2.719</td><td>0.473</td><td>0.031</td><td><strong>0.000</strong></td><td><strong>0.000</strong></td><td>0.001</td><td>0.004</td><td>0.123</td><td><strong>0.000</strong></td><td>0.002</td><td><strong>0.000</strong></td><td>0.002</td><td>0.031</td></tr></tbody></table>

<table><caption>Table 11: Number of best known solutions found for each set of the small scale instances.</caption><thead><tr><th>Instances</th><th>BKS</th><th>SkVNS</th><th>GLS</th><th>FPR</th><th>MA</th><th>AuLNS</th><th>PSOiA</th><th>UHGS</th><th>MS-ILS</th><th>MS-LS</th><th>PMA</th><th>LNS</th><th>HALNS</th><th>HISS-SD</th><th>LNS2</th></tr></thead><tbody><tr><td>4</td><td>54</td><td>7</td><td>6</td><td>17</td><td>49</td><td><strong>54</strong></td><td><strong>54</strong></td><td>52</td><td>50</td><td>30</td><td><strong>54</strong></td><td><strong>54</strong></td><td><strong>54</strong></td><td>53</td><td>52</td></tr><tr><td>5</td><td>45</td><td>21</td><td>9</td><td>33</td><td>40</td><td><strong>45</strong></td><td><strong>45</strong></td><td><strong>45</strong></td><td><strong>45</strong></td><td>40</td><td><strong>45</strong></td><td>44</td><td><strong>45</strong></td><td><strong>45</strong></td><td><strong>45</strong></td></tr><tr><td>6</td><td>15</td><td>10</td><td>4</td><td>12</td><td><strong>15</strong></td><td><strong>15</strong></td><td><strong>15</strong></td><td><strong>15</strong></td><td><strong>15</strong></td><td>14</td><td><strong>15</strong></td><td><strong>15</strong></td><td><strong>15</strong></td><td><strong>15</strong></td><td><strong>15</strong></td></tr><tr><td>7</td><td>43</td><td>6</td><td>2</td><td>16</td><td>42</td><td><strong>43</strong></td><td><strong>43</strong></td><td><strong>43</strong></td><td><strong>43</strong></td><td>31</td><td><strong>43</strong></td><td><strong>43</strong></td><td><strong>43</strong></td><td>41</td><td>40</td></tr><tr><td>All</td><td>157</td><td>44</td><td>21</td><td>78</td><td>146</td><td>157</td><td>157</td><td>155</td><td>153</td><td>115</td><td>157</td><td>156</td><td>157</td><td>154</td><td>152</td></tr></tbody></table>

### 6.3.2. Large scale instances

The algorithm is then tested on the set of large scale instances. Results can be seen in table 21 where they are compared with PSOiA (Dang et al., 2013a), PAM (Ke et al., 2016) and HALNS (Hammami et al., 2020), these algorithms being the only ones applied on this set. Our algorithm finds 54 out of 82 best known solutions among which three new best known solutions for gr229_gen2_m4, gr229_gen3_m4 and rd400_gen1_m2. A detailed description of these solutions, i.e. ordered sets of customers visited by each vehicle, is available at https://github.com/CharlyChgn/VLS-Team-Orienteering-Problem. A checker of solution is also joined to verify the

integrity of constraints, such as tour duration. In average, it finds solutions which are most of the time very close to the best known solutions while doing so very quickly as shown by its RPE value and its computational time (table 12). When finding the best known solution, our algorithm is clearly faster than any of the other methods. Out of the 4 compared methods, results for the ARPE value are slightly worse but stay very good as, in average, solutions are less than 0.7% worse than the best known solution of the problem. In average, for a computational time 40 times lower, results are only 0.4% worse when compared to the HALNS. Overall, for the large scale set of instances, based on preferences, both HALNS and our LNS are good options as seen
in figure 7, while PSOiA and PMA are both dominated by HALNS. Nevertheless, we believe that our algorithm is more suitable to be used in industrial context as it finds these solutions very quickly at a very low cost of solutions's quality.

### 6.3.3. Very large scale instances

Finally, we apply the algorithm to the new set of instances ranging from 1001 to 5394 customers, and from 2 to 10 vehicles. As the set is newly introduced to the TOP context, we can only judge the performance of the algorithm based on two values: the average deviation and the time needed to compute the solution. Table 22 reports for each instance the best solution obtained, the CPU time (s) associated, the average solution, the average CPU time (s) and the ARPE value of the algorithm on the instance. Out of the 288 built instances, in three instances the total profit collected is 0, thus are not considered in the results. Overall, the algorithm remains quite fast to compute since for most of the instances it ends in less than one hour, the average computational time being even smaller than the actual processing time of HALNS on the large scale set while having no less than 9.3 times more customers in average. As can be seen in table 13, the ARPE value is higher than in the prior set of instances (1.52%) but is still relevant for such big instances.

### 6.4. Results analysis based on the number of vehicles

The impact of the number of vehicles is also studied and results are summarized in table 14. Results are interesting as in both the small and large scale sets, the worse results are obtained when the number of vehicles is $m = 3$ while the best results are obtained with the highest number of vehicles $m = 4$. For the newly introduced set of instances, worse results are also obtained when $m = 3$ while results are similar for instances with a higher number of vehicles. We can also note the impact of the number of customers per route on the computational time as the average CPU is higher when considering a smaller number of vehicles. This shows that longer routes take more time to optimize using our algorithm.

### 6.5. Results analysis based on profit generation

We also study the impact of the profit generation on the results obtained by the algorithm. Results

are summarized in table 15. For the large scale set of instances, it shows that the algorithm is in average better on the generation 2 instances corresponding to the random distributed profit on every criterion. When applied to generation 1 instances, where every customer has the same profit of 1, the algorithm performs better than on generation 3, where every customer has a profit depending on its distance from the depot. As both of these types of instances are particular cases of the generation 2, if given more freedom (for example in our neighborhood lists or our restricted candidate list), the algorithm might be able to obtain solutions that are at least as good as in generation 2. On the very large scale set of instances, the algorithm shows similar performances on generation 1 and 2 even if it is slower on generation 1 instances. Worse results are again obtained for generation 3 instances. This behavior might be caused by the clustering that partitions the area and which might not be relevant for this specific kind of instances. Overall, our algorithm remains very competitive on every kind of profit distributed instances.

### 6.6. Convergence

We then analyse the average convergence of the algorithm based on the set of instances tackled. Results are very interesting as our algorithm quickly converge independently of the set of instances tackled: for the small scale set, solutions reach 99% of the profit of the final solution in 0.075s. For the large scale set, the same value is reached in 0.39s while it is reached in 125s for the very large scale set. Overall, initial solutions worsen with the increase in size of the instance tackled, going from 88.43% for the small scale set to 75.18% for the very large scale set. This shows that the heuristic used to build the initial solution doesn't scale well with the instance size, which seems reasonable as these instances are harder to solve. For every set of instances, most of the time the algorithm does not improve much the solution's quality when getting close to one of the stopping criterion, thus confirming their relevance. It is also of interest to note that, based on its convergence, our algorithm can be stopped earlier in an industrial context where a bigger compromise between the solution's quality and its associated computational time may be
<figure><img src="image_10.png" /><figcaption>Figure 7: RPE based on the average computational time and the algorithm used for the large scale set of instances.</figcaption></figure>

<table><thead><tr><th>Criteria</th><th>PSOIA</th><th>PMA</th><th>HALNS</th><th>LNS2</th></tr></thead><tbody><tr><td># BKS</td><td>70</td><td>78</td><td><strong>79</strong></td><td>54*</td></tr><tr><td>RPE (%)</td><td>0.04688</td><td>0.00722</td><td><strong>0.00712</strong></td><td>0.14027</td></tr><tr><td>ARPE (%)</td><td>0.50529</td><td>0.42899</td><td><strong>0.30205</strong></td><td>0.68628</td></tr><tr><td>Average CPU (s)</td><td>11,031.04</td><td>1,004.15</td><td>783.36</td><td><strong>20.58</strong></td></tr></tbody></table>

<caption>Table 12: Summary results for the set of large scale instances.</caption>

<footnote>* 3 new best known solutions</footnote>
<table><caption>Table 13: Summary results for the set of very large scale instances.</caption><thead><tr><th>Instances</th><th>#</th><th>ARPE (%)</th><th>CPU (s)</th></tr></thead><tbody><tr><td>1000-1500</td><td>117</td><td>1.571</td><td>164.891</td></tr><tr><td>1500-2000</td><td>60</td><td>1.496</td><td>259.342</td></tr><tr><td>2000-3000</td><td>48</td><td>1.248</td><td>400.172</td></tr><tr><td>3000-6000</td><td>60</td><td>1.670</td><td>1699.364</td></tr><tr><td>All</td><td>285</td><td>1.521</td><td>547.449</td></tr></tbody></table>

<table><caption>Table 14: Impact of the number of vehicles.</caption><thead><tr><th>Instance set</th><th>m</th><th>#</th><th>RPE (%)</th><th>ARPE (%)</th><th>Average CPU (s)</th></tr></thead><tbody><tr><td rowspan="3">Small scale</td><td>2</td><td>60</td><td>0.031</td><td>0.252</td><td>4.492</td></tr><tr><td>3</td><td>52</td><td>0.051</td><td>0.237</td><td>4.583</td></tr><tr><td>4</td><td>45</td><td>0.009</td><td>0.177</td><td>4.940</td></tr><tr><td rowspan="3">Large scale</td><td>2</td><td>29</td><td>0.151</td><td>0.701</td><td>19.320</td></tr><tr><td>3</td><td>29</td><td>0.190</td><td>0.799</td><td>20.565</td></tr><tr><td>4</td><td>24</td><td>0.067</td><td>0.532</td><td>22.138</td></tr><tr><td rowspan="4">Very large scale</td><td>2</td><td>72</td><td>-</td><td>1.617</td><td>705.736</td></tr><tr><td>3</td><td>72</td><td>-</td><td>2.068</td><td>588.653</td></tr><tr><td>8</td><td>72</td><td>-</td><td>1.214</td><td>442.164</td></tr><tr><td>10</td><td>69</td><td>-</td><td>1.173</td><td>449.145</td></tr></tbody></table>

<table><caption>Table 15: Impact of profit generation.</caption><thead><tr><th>Instance set</th><th>Profit generation</th><th>#</th><th>RPE (%)</th><th>ARPE (%)</th><th>Average CPU (s)</th></tr></thead><tbody><tr><td rowspan="3">Large scale</td><td>Gen 1</td><td>17</td><td>0.120</td><td>0.807</td><td>21.910</td></tr><tr><td>Gen 2</td><td>45</td><td>0.096</td><td>0.523</td><td>18.612</td></tr><tr><td>Gen 3</td><td>20</td><td>0.207</td><td>0.952</td><td>22.920</td></tr><tr><td rowspan="3">Very large scale</td><td>Gen 1</td><td>95</td><td>-</td><td>1.298</td><td>566.911</td></tr><tr><td>Gen 2</td><td>95</td><td>-</td><td>1.373</td><td>539.418</td></tr><tr><td>Gen 3</td><td>95</td><td>-</td><td>1.893</td><td>536.017</td></tr></tbody></table>

needed. Thus, the algorithm meets the requirements linked to the computational time that we were aiming for.

## 7. Numerical results on industrial instances

Our algorithm is then evaluated on industrial instances. In this context, each vehicle has its own depot and they don't need to finish their route on their depot. The algorithm is adapted to solve MDOTOP instances from TOP ones: each depot is specific to each vehicle, and final depots are dummy points having no cost to reach.

### 7.1. Industrial instances

Our algorithm is tested on 10 industrial instances ranging from 3133 to 7358 customers and considering 6 to 18 vehicles. We consider a time limit *D* of two hours with vehicles moving at an average speed of 4 km/h. Industrial solutions considered are computed based on geographical information as in practice, and validated by an industrial expert. As our goal is to propose new solutions every 10 minutes, the associated parameter is set to this value. This won't degrade much the quality of the proposed solution as our algorithm is very fast to converge. Moreover, in our industrial context, computing time is as important as the
solution's quality since hazards regularly change the initial planning. Thus, stopping the algorithm at 10 minutes is reasonable to tackle subsurface imaging instances. The set of parameters introduced for the very large scale set of instances is used for the other parameters as these instances are similar. An example of instance is illustrated figure 8.

## 7.2. Benchmark

To evaluate the method, we compare 10 executions of our algorithm on all industrial instances considered. The ARPE value, based on the best solution found, is compared for both industrial and algorithmic methods. Results can be seen in table 16 where industrial solutions are compared with solutions obtained using our metaheuristic.

It shows that our algorithm outperforms the traditional way to build solutions used in this industrial context. In particular, the number of points visited is 38% lower using industrial solutions based on LNS2 results. The algorithm is, most of the time, stopped by the maximum computational time of 10mn which is higher than the algorithm based on pre-computed geographical informations used to build industrial solutions, which is immediate. Our algorithm obtains similar results among the executions, as shown by the average ARPE value (0.47%), showing that the budget time of 10 minutes doesn't have much effect on the convergence of the algorithm for an industrial application. Overall, the results obtained using our metaheuristic are way more interesting than the classical way to build solutions in the subsurface imaging field, improving in average by 62% the number of visited points.

# 8. Conclusion and perspectives

We proposed a LNS to tackle the very large scale MDOTOP. To our knowledge, this is the first time this problem is treated in the literature. Our LNS is paired with mechanisms which aim at reducing the number of evaluations during the algorithm. Results on literature instances for the TOP are promising since it finds a good number of the best known solutions while being much quicker than state-of-the-art algorithms. Three best-known solutions were improved for the large scale set of instances. Our LNS is also applied on

a new set of very large scale instances based on OP instances. Results show that our algorithm is fast for most of these instances but is slower the longer the routes are. The algorithm is shown to be very good independently of the type of instance tackled, even if worse results are obtained when customers' profit is based on their distance from the depot.

Our algorithm is then applied on industrial instances from the subsurface imaging field. On these instances, our algorithm greatly improves the performance of vehicles, increasing in average by 62% their productivity. Overall, the simplicity of our method associated to the quality of the obtained results based on its computational time makes our algorithm very interesting to be applied in most industrial contexts with large size problems.

Perspectives includes the application of our algorithm on different industrial contexts. The use of Static Move Descriptors should also be interesting to avoid some evaluations and may bring more diversification in the process. Finally, further work can be done around pre-processing and memory management to avoid some computations and better scale with the instance size. Both these mechanisms might be needed to tackle instances even bigger like it is done in the VRP.
<figure><img src="image_11.png" /><figcaption>Figure 8: Example of instance considered when solving the subsurface imaging problem.</figcaption></figure>

<table><caption>Table 16: Results on industrial instances. CPU time higher than 600s are met when the algorithm is stopped from the CPU stopping criterion.</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">N</th><th rowspan="2">m</th><th rowspan="2">Industrial solution</th><th colspan="3">LNS2</th><th colspan="2">ARPE (%)</th></tr><tr><th>Best</th><th>Average</th><th>CPU (s)</th><th>Industrial</th><th>LNS2</th></tr></thead><tbody><tr><td>Instance 1</td><td>3133</td><td>8</td><td>1424</td><td><strong>2297</strong></td><td>2290</td><td>587.53</td><td>38.01</td><td><strong>0.3</strong></td></tr><tr><td>Instance 2</td><td>3155</td><td>7</td><td>1299</td><td><strong>2042</strong></td><td>2033.4</td><td>606.91</td><td>36.39</td><td><strong>0.42</strong></td></tr><tr><td>Instance 3</td><td>3673</td><td>6</td><td>1052</td><td><strong>1749</strong></td><td>1740.9</td><td>614.46</td><td>39.85</td><td><strong>0.46</strong></td></tr><tr><td>Instance 4</td><td>3745</td><td>11</td><td>2005</td><td><strong>3102</strong></td><td>3087.9</td><td>603.67</td><td>35.36</td><td><strong>0.45</strong></td></tr><tr><td>Instance 5</td><td>3953</td><td>9</td><td>1675</td><td><strong>2588</strong></td><td>2572.1</td><td>607.84</td><td>35.28</td><td><strong>0.61</strong></td></tr><tr><td>Instance 6</td><td>4116</td><td>10</td><td>1897</td><td><strong>2899</strong></td><td>2885.5</td><td>606.75</td><td>34.56</td><td><strong>0.47</strong></td></tr><tr><td>Instance 7</td><td>4144</td><td>9</td><td>1383</td><td><strong>2535</strong></td><td>2526.2</td><td>608.02</td><td>45.44</td><td><strong>0.35</strong></td></tr><tr><td>Instance 8</td><td>4836</td><td>17</td><td>2881</td><td><strong>4628</strong></td><td>4617.6</td><td>604.22</td><td>37.75</td><td><strong>0.22</strong></td></tr><tr><td>Instance 9</td><td>6116</td><td>18</td><td>3365</td><td><strong>5092</strong></td><td>5058.7</td><td>608.01</td><td>33.92</td><td><strong>0.65</strong></td></tr><tr><td>Instance 10</td><td>7358</td><td>10</td><td>1550</td><td><strong>2864</strong></td><td>2842.3</td><td>650.58</td><td>45.88</td><td><strong>0.76</strong></td></tr></tbody><tfoot><tr><td>Average</td><td>4422.9</td><td>10.5</td><td>1853.1</td><td>2979.6</td><td>2965.46</td><td>609.8</td><td>38.24</td><td><strong>0.47</strong></td></tr></tfoot></table>
## 9. Appendix

### 9.1. Results on the small scale set of instances

<table><caption>Table 17: Results for the small scale instances set 4.</caption><thead><tr><th>Instances</th><th>BKS</th><th>SkVNS</th><th>GLS</th><th>FPR</th><th>MA</th><th>AuLNS</th><th>PSOIA</th><th>UHGS</th><th>MS-ILS</th><th>MS-LS</th><th>PMA</th><th>LNS</th><th>HALNS</th><th>HISS-SD</th><th>LNS2</th></tr></thead><tbody><tr><td>p4.2.a</td><td>206</td><td>202</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td><td>206</td></tr><tr><td>p4.2.b</td><td>341</td><td>341</td><td>303</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td><td>341</td></tr><tr><td>p4.2.c</td><td>452</td><td>452</td><td>447</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td><td>452</td></tr><tr><td>p4.2.d</td><td>531</td><td>528</td><td>526</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td><td>531</td></tr><tr><td>p4.2.e</td><td>618</td><td>593</td><td>602</td><td>612</td><td>618</td><td>618</td><td>618</td><td>618</td><td>618</td><td>618</td><td>618</td><td>618</td><td>618</td><td>618</td><td>618</td></tr><tr><td>p4.2.f</td><td>687</td><td>675</td><td>651</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td><td>687</td></tr><tr><td>p4.2.g</td><td>757</td><td>750</td><td>734</td><td>757</td><td>757</td><td>757</td><td>757</td><td>757</td><td>757</td><td>757</td><td>752</td><td>757</td><td>757</td><td>757</td><td>757</td></tr><tr><td>p4.2.h</td><td>835</td><td>819</td><td>797</td><td>835</td><td>835</td><td>835</td><td>835</td><td>835</td><td>835</td><td>825</td><td>835</td><td>835</td><td>835</td><td>835</td><td>827</td></tr><tr><td>p4.2.i</td><td>918</td><td>916</td><td>826</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td><td>918</td></tr><tr><td>p4.2.j</td><td>965</td><td>962</td><td>939</td><td>962</td><td>965</td><td>965</td><td>965</td><td>965</td><td>965</td><td>964</td><td>965</td><td>965</td><td>965</td><td>965</td><td>965</td></tr><tr><td>p4.2.k</td><td>1022</td><td>1007</td><td>994</td><td>1013</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1013</td></tr><tr><td>p4.2.l</td><td>1074</td><td>1051</td><td>1051</td><td>1064</td><td>1074</td><td>1074</td><td>1074</td><td>1074</td><td>1074</td><td>1073</td><td>1074</td><td>1074</td><td>1074</td><td>1074</td><td>1074</td></tr><tr><td>p4.2.m</td><td>1132</td><td>1051</td><td>1051</td><td>1130</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td><td>1132</td></tr><tr><td>p4.2.n</td><td>1174</td><td>1124</td><td>1117</td><td>1161</td><td>1174</td><td>1174</td><td>1174</td><td>1174</td><td>1174</td><td>1172</td><td>1174</td><td>1174</td><td>1174</td><td>1174</td><td>1174</td></tr><tr><td>p4.2.o</td><td>1218</td><td>1195</td><td>1191</td><td>1206</td><td>1218</td><td>1218</td><td>1218</td><td>1218</td><td>1218</td><td>1213</td><td>1218</td><td>1218</td><td>1218</td><td>1218</td><td>1218</td></tr><tr><td>p4.2.p</td><td>1242</td><td>1237</td><td>1214</td><td>1240</td><td>1242</td><td>1242</td><td>1242</td><td>1242</td><td>1242</td><td>1239</td><td>1242</td><td>1242</td><td>1242</td><td>1242</td><td>1242</td></tr><tr><td>p4.2.q</td><td>1268</td><td>1239</td><td>1248</td><td>1257</td><td>1268</td><td>1268</td><td>1268</td><td>1267</td><td>1267</td><td>1262</td><td>1268</td><td>1268</td><td>1268</td><td>1267</td><td>1268</td></tr><tr><td>p4.2.r</td><td>1292</td><td>1279</td><td>1267</td><td>1278</td><td>1292</td><td>1292</td><td>1292</td><td>1292</td><td>1287</td><td>1285</td><td>1292</td><td>1292</td><td>1292</td><td>1292</td><td>1292</td></tr><tr><td>p4.2.s</td><td>1304</td><td>1295</td><td>1286</td><td>1293</td><td>1304</td><td>1304</td><td>1304</td><td>1302</td><td>1304</td><td>1301</td><td>1304</td><td>1304</td><td>1304</td><td>1304</td><td>1304</td></tr><tr><td>p4.2.t</td><td>1306</td><td>1305</td><td>1294</td><td>1299</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td><td>1306</td></tr><tr><td>p4.3.c</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td><td>193</td></tr><tr><td>p4.3.d</td><td>335</td><td>331</td><td>335</td><td>333</td><td>335</td><td>335</td><td>335</td><td>335</td><td>335</td><td>335</td><td>335</td><td>335</td><td>335</td><td>335</td><td>335</td></tr><tr><td>p4.3.e</td><td>468</td><td>460</td><td>444</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td><td>468</td></tr><tr><td>p4.3.f</td><td>579</td><td>556</td><td>564</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td><td>579</td></tr><tr><td>p4.3.g</td><td>653</td><td>651</td><td>644</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td><td>653</td></tr><tr><td>p4.3.h</td><td>729</td><td>718</td><td>706</td><td>725</td><td>729</td><td>729</td><td>729</td><td>729</td><td>729</td><td>728</td><td>729</td><td>729</td><td>729</td><td>729</td><td>729</td></tr><tr><td>p4.3.i</td><td>809</td><td>807</td><td>806</td><td>797</td><td>809</td><td>809</td><td>809</td><td>809</td><td>809</td><td>809</td><td>809</td><td>809</td><td>809</td><td>809</td><td>809</td></tr><tr><td>p4.3.j</td><td>861</td><td>854</td><td>826</td><td>858</td><td>861</td><td>861</td><td>861</td><td>861</td><td>861</td><td>861</td><td>861</td><td>861</td><td>861</td><td>861</td><td>861</td></tr><tr><td>p4.3.k</td><td>919</td><td>902</td><td>864</td><td>918</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td></tr><tr><td>p4.3.l</td><td>979</td><td>969</td><td>960</td><td>968</td><td>979</td><td>979</td><td>979</td><td>979</td><td>979</td><td>979</td><td>979</td><td>979</td><td>979</td><td>979</td><td>979</td></tr><tr><td>p4.3.m</td><td>1063</td><td>1047</td><td>1030</td><td>1043</td><td>1063</td><td>1063</td><td>1063</td><td>1063</td><td>1063</td><td>1051</td><td>1063</td><td>1063</td><td>1063</td><td>1063</td><td>1063</td></tr><tr><td>p4.3.n</td><td>1121</td><td>1106</td><td>1113</td><td>1108</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td><td>1121</td></tr><tr><td>p4.3.o</td><td>1172</td><td>1136</td><td>1121</td><td>1165</td><td>1172</td><td>1172</td><td>1172</td><td>1172</td><td>1172</td><td>1170</td><td>1172</td><td>1172</td><td>1172</td><td>1172</td><td>1172</td></tr><tr><td>p4.3.p</td><td>1222</td><td>1200</td><td>1190</td><td>1209</td><td>1222</td><td>1222</td><td>1222</td><td>1222</td><td>1222</td><td>1208</td><td>1222</td><td>1222</td><td>1222</td><td>1222</td><td>1222</td></tr><tr><td>p4.3.q</td><td>1253</td><td>1236</td><td>1210</td><td>1246</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td><td>1253</td></tr><tr><td>p4.3.r</td><td>1273</td><td>1250</td><td>1239</td><td>1257</td><td>1273</td><td>1273</td><td>1273</td><td>1273</td><td>1272</td><td>1271</td><td>1273</td><td>1273</td><td>1273</td><td>1273</td><td>1273</td></tr><tr><td>p4.3.s</td><td>1295</td><td>1280</td><td>1279</td><td>1276</td><td>1295</td><td>1295</td><td>1295</td><td>1295</td><td>1295</td><td>1290</td><td>1295</td><td>1295</td><td>1295</td><td>1295</td><td>1295</td></tr><tr><td>p4.3.t</td><td>1305</td><td>1299</td><td>1290</td><td>1294</td><td>1305</td><td>1305</td><td>1305</td><td>1305</td><td>1304</td><td>1301</td><td>1305</td><td>1305</td><td>1305</td><td>1305</td><td>1305</td></tr><tr><td>p4.4.e</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td><td>183</td></tr><tr><td>p4.4.f</td><td>324</td><td>319</td><td>312</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td><td>324</td></tr><tr><td>p4.4.g</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td><td>461</td></tr><tr><td>p4.4.h</td><td>571</td><td>553</td><td>565</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td><td>571</td></tr><tr><td>p4.4.i</td><td>657</td><td>657</td><td>657</td><td>653</td><td>657</td><td>657</td><td>657</td><td>657</td><td>657</td><td>657</td><td>657</td><td>657</td><td>657</td><td>657</td><td>657</td></tr><tr><td>p4.4.j</td><td>732</td><td>723</td><td>691</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td><td>732</td></tr><tr><td>p4.4.k</td><td>821</td><td>821</td><td>815</td><td>820</td><td>821</td><td>821</td><td>821</td><td>821</td><td>821</td><td>821</td><td>821</td><td>821</td><td>821</td><td>821</td><td>821</td></tr><tr><td>p4.4.l</td><td>880</td><td>876</td><td>852</td><td>875</td><td>880</td><td>880</td><td>880</td><td>880</td><td>880</td><td>880</td><td>880</td><td>880</td><td>880</td><td>880</td><td>880</td></tr><tr><td>p4.4.m</td><td>919</td><td>903</td><td>910</td><td>914</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td><td>919</td></tr><tr><td>p4.4.n</td><td>976</td><td>948</td><td>942</td><td>953</td><td>976</td><td>976</td><td>976</td><td>976</td><td>976</td><td>967</td><td>976</td><td>976</td><td>976</td><td>976</td><td>976</td></tr><tr><td>p4.4.o</td><td>1061</td><td>1030</td><td>937</td><td>1033</td><td>1061</td><td>1061</td><td>1061</td><td>1061</td><td>1061</td><td>1057</td><td>1061</td><td>1061</td><td>1061</td><td>1061</td><td>1061</td></tr><tr><td>p4.4.p</td><td>1124</td><td>1120</td><td>1091</td><td>1098</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td><td>1124</td></tr><tr><td>p4.4.q</td><td>1161</td><td>1149</td><td>1106</td><td>1139</td><td>1161</td><td>1161</td><td>1161</td><td>1161</td><td>1161</td><td>1159</td><td>1161</td><td>1161</td><td>1161</td><td>1161</td><td>1161</td></tr><tr><td>p4.4.r</td><td>1216</td><td>1193</td><td>1148</td><td>1196</td><td>1216</td><td>1216</td><td>1216</td><td>1216</td><td>1216</td><td>1207</td><td>1216</td><td>1216</td><td>1216</td><td>1216</td><td>1216</td></tr><tr><td>p4.4.s</td><td>1260</td><td>1213</td><td>1242</td><td>1231</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1259</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td></tr><tr><td>p4.4.t</td><td>1285</td><td>1281</td><td>1250</td><td>1256</td><td>1285</td><td>1285</td><td>1285</td><td>1285</td><td>1285</td><td>1280</td><td>1285</td><td>1285</td><td>1285</td><td>1285</td><td>1285</td></tr></tbody></table>
<table><caption>Table 18: Results for the small scale instances set 5.</caption><thead><tr><th>Instances</th><th>BKS</th><th>SkVNS</th><th>GLS</th><th>FPR</th><th>MA</th><th>AuLNS</th><th>PSOIa</th><th>UHGS</th><th>MS-ILS</th><th>MS-LS</th><th>PMA</th><th>LNS</th><th>HALNS</th><th>HISS-SD</th><th>LNS2</th></tr></thead><tbody><tr><td>p5.2.h</td><td>410</td><td>395</td><td>385</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td><td>410</td></tr><tr><td>p5.2.j</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td></tr><tr><td>p5.2.k</td><td>670</td><td>670</td><td>665</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td><td>670</td></tr><tr><td>p5.2.l</td><td>800</td><td>770</td><td>760</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td><td>800</td></tr><tr><td>p5.2.m</td><td>860</td><td>860</td><td>830</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td></tr><tr><td>p5.2.n</td><td>925</td><td>920</td><td>920</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td><td>925</td></tr><tr><td>p5.2.o</td><td>1020</td><td>1020</td><td>1010</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td><td>1020</td></tr><tr><td>p5.2.p</td><td>1150</td><td>1150</td><td>1030</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td><td>1150</td></tr><tr><td>p5.2.q</td><td>1195</td><td>1195</td><td>1145</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td><td>1195</td></tr><tr><td>p5.2.r</td><td>1260</td><td>1260</td><td>1225</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td></tr><tr><td>p5.2.s</td><td>1340</td><td>1325</td><td>1325</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td><td>1340</td></tr><tr><td>p5.2.t</td><td>1400</td><td>1380</td><td>1360</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td><td>1400</td></tr><tr><td>p5.2.u</td><td>1460</td><td>1450</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td><td>1460</td></tr><tr><td>p5.2.v</td><td>1505</td><td>1500</td><td>1500</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td><td>1505</td></tr><tr><td>p5.2.w</td><td>1565</td><td>1560</td><td>1560</td><td>1560</td><td>1565</td><td>1565</td><td>1565</td><td>1565</td><td>1565</td><td>1560</td><td>1565</td><td>1560</td><td>1565</td><td>1565</td><td>1565</td></tr><tr><td>p5.2.x</td><td>1610</td><td>1600</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td><td>1610</td></tr><tr><td>p5.2.y</td><td>1645</td><td>1630</td><td>1630</td><td>1645</td><td>1645</td><td>1645</td><td>1645</td><td>1645</td><td>1645</td><td>1640</td><td>1645</td><td>1645</td><td>1645</td><td>1645</td><td>1645</td></tr><tr><td>p5.2.z</td><td>1680</td><td>1665</td><td>1680</td><td>1670</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td><td>1680</td></tr><tr><td>p5.3.k</td><td>495</td><td>495</td><td>470</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td><td>495</td></tr><tr><td>p5.3.l</td><td>595</td><td>595</td><td>545</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td><td>595</td></tr><tr><td>p5.3.n</td><td>755</td><td>755</td><td>720</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td><td>755</td></tr><tr><td>p5.3.o</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td><td>870</td></tr><tr><td>p5.3.q</td><td>1070</td><td>1065</td><td>1045</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td><td>1070</td></tr><tr><td>p5.3.r</td><td>1125</td><td>1125</td><td>1090</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td><td>1125</td></tr><tr><td>p5.3.s</td><td>1190</td><td>1185</td><td>1145</td><td>1185</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td><td>1190</td></tr><tr><td>p5.3.t</td><td>1260</td><td>1260</td><td>1240</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td></tr><tr><td>p5.3.u</td><td>1345</td><td>1345</td><td>1305</td><td>1335</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td><td>1345</td></tr><tr><td>p5.3.v</td><td>1425</td><td>1425</td><td>1425</td><td>1420</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td><td>1425</td></tr><tr><td>p5.3.w</td><td>1485</td><td>1475</td><td>1460</td><td>1465</td><td>1485</td><td>1485</td><td>1485</td><td>1485</td><td>1485</td><td>1480</td><td>1485</td><td>1485</td><td>1485</td><td>1485</td><td>1485</td></tr><tr><td>p5.3.x</td><td>1555</td><td>1535</td><td>1520</td><td>1540</td><td>1555</td><td>1555</td><td>1555</td><td>1555</td><td>1555</td><td>1535</td><td>1555</td><td>1555</td><td>1555</td><td>1555</td><td>1555</td></tr><tr><td>p5.3.y</td><td>1595</td><td>1580</td><td>1590</td><td>1590</td><td>1595</td><td>1595</td><td>1595</td><td>1595</td><td>1595</td><td>1590</td><td>1595</td><td>1595</td><td>1595</td><td>1595</td><td>1595</td></tr><tr><td>p5.3.z</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td><td>1635</td></tr><tr><td>p5.4.m</td><td>555</td><td>550</td><td>550</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td><td>555</td></tr><tr><td>p5.4.o</td><td>690</td><td>690</td><td>680</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td><td>690</td></tr><tr><td>p5.4.p</td><td>765</td><td>760</td><td>760</td><td>760</td><td>765</td><td>765</td><td>765</td><td>765</td><td>765</td><td>765</td><td>765</td><td>765</td><td>765</td><td>765</td><td>765</td></tr><tr><td>p5.4.q</td><td>860</td><td>835</td><td>830</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td><td>860</td></tr><tr><td>p5.4.r</td><td>960</td><td>960</td><td>890</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td><td>960</td></tr><tr><td>p5.4.s</td><td>1030</td><td>1020</td><td>1020</td><td>1005</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td><td>1030</td></tr><tr><td>p5.4.t</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td><td>1160</td></tr><tr><td>p5.4.u</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td><td>1300</td></tr><tr><td>p5.4.v</td><td>1320</td><td>1320</td><td>1245</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td><td>1320</td></tr><tr><td>p5.4.w</td><td>1390</td><td>1380</td><td>1330</td><td>1380</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td><td>1390</td></tr><tr><td>p5.4.x</td><td>1450</td><td>1440</td><td>1410</td><td>1430</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td><td>1450</td></tr><tr><td>p5.4.y</td><td>1520</td><td>1500</td><td>1485</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td><td>1520</td></tr><tr><td>p5.4.z</td><td>1620</td><td>1600</td><td>1590</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td><td>1620</td></tr></tbody></table>

<table><caption>Table 19: Results for the small scale instances set 6.</caption><thead><tr><th>Instances</th><th>BKS</th><th>SkVNS</th><th>GLS</th><th>FPR</th><th>MA</th><th>AuLNS</th><th>PSOIa</th><th>UHGS</th><th>MS-ILS</th><th>MS-LS</th><th>PMA</th><th>LNS</th><th>HALNS</th><th>HISS-SD</th><th>LNS2</th></tr></thead><tbody><tr><td>p6.2.d</td><td>192</td><td>192</td><td>180</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td><td>192</td></tr><tr><td>p6.2.j</td><td>948</td><td>948</td><td>948</td><td>942</td><td>948</td><td>948</td><td>948</td><td>948</td><td>948</td><td>948</td><td>948</td><td>948</td><td>948</td><td>948</td><td>948</td></tr><tr><td>p6.2.l</td><td>1116</td><td>1116</td><td>1104</td><td>1110</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td><td>1116</td></tr><tr><td>p6.2.m</td><td>1188</td><td>1188</td><td>1164</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td><td>1188</td></tr><tr><td>p6.2.n</td><td>1260</td><td>1248</td><td>1254</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1254</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td></tr><tr><td>p6.3.g</td><td>282</td><td>276</td><td>264</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td><td>282</td></tr><tr><td>p6.3.h</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td><td>444</td></tr><tr><td>p6.3.i</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td><td>642</td></tr><tr><td>p6.3.k</td><td>894</td><td>894</td><td>882</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td><td>894</td></tr><tr><td>p6.3.l</td><td>1002</td><td>996</td><td>990</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td></tr><tr><td>p6.3.m</td><td>1080</td><td>1080</td><td>1068</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td><td>1080</td></tr><tr><td>p6.3.n</td><td>1170</td><td>1152</td><td>1140</td><td>1164</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td><td>1170</td></tr><tr><td>p6.4.j</td><td>366</td><td>366</td><td>360</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td></tr><tr><td>p6.4.k</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td><td>528</td></tr><tr><td>p6.4.l</td><td>696</td><td>678</td><td>678</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td><td>696</td></tr></tbody></table>
<table><caption>Table 20: Results for the small scale instances set 7.</caption><thead><tr><th>Instances</th><th>BKS</th><th>SkVNS</th><th>GLS</th><th>FPR</th><th>MA</th><th>AuLNS</th><th>PSOIA</th><th>UHGS</th><th>MS-ILS</th><th>MS-LS</th><th>PMA</th><th>LNS</th><th>HALNS</th><th>HISS-SD</th><th>LNS2</th></tr></thead><tbody><tr><td>p7.2.d</td><td>190</td><td>182</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td><td>190</td></tr><tr><td>p7.2.e</td><td>290</td><td>289</td><td>279</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td><td>290</td></tr><tr><td>p7.2.f</td><td>387</td><td>387</td><td>340</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td><td>387</td></tr><tr><td>p7.2.g</td><td>459</td><td>457</td><td>440</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td><td>459</td></tr><tr><td>p7.2.h</td><td>521</td><td>521</td><td>517</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td><td>521</td></tr><tr><td>p7.2.i</td><td>580</td><td>579</td><td>568</td><td>578</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td><td>580</td></tr><tr><td>p7.2.j</td><td>646</td><td>632</td><td>633</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td></tr><tr><td>p7.2.k</td><td>705</td><td>700</td><td>691</td><td>702</td><td>705</td><td>705</td><td>705</td><td>705</td><td>705</td><td>705</td><td>705</td><td>705</td><td>705</td><td>705</td><td>705</td></tr><tr><td>p7.2.l</td><td>767</td><td>758</td><td>748</td><td>759</td><td>767</td><td>767</td><td>767</td><td>767</td><td>767</td><td>767</td><td>767</td><td>767</td><td>767</td><td>767</td><td>767</td></tr><tr><td>p7.2.m</td><td>827</td><td>827</td><td>798</td><td>816</td><td>827</td><td>827</td><td>827</td><td>827</td><td>827</td><td>827</td><td>827</td><td>827</td><td>827</td><td>827</td><td>827</td></tr><tr><td>p7.2.n</td><td>888</td><td>866</td><td>861</td><td>888</td><td>888</td><td>888</td><td>888</td><td>888</td><td>888</td><td>884</td><td>888</td><td>888</td><td>888</td><td>888</td><td>888</td></tr><tr><td>p7.2.o</td><td>945</td><td>928</td><td>897</td><td>932</td><td>945</td><td>945</td><td>945</td><td>945</td><td>945</td><td>945</td><td>945</td><td>945</td><td>945</td><td>945</td><td>945</td></tr><tr><td>p7.2.p</td><td>1002</td><td>955</td><td>954</td><td>993</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td><td>1002</td></tr><tr><td>p7.2.q</td><td>1044</td><td>1029</td><td>1031</td><td>1043</td><td>1044</td><td>1044</td><td>1044</td><td>1044</td><td>1044</td><td>1044</td><td>1044</td><td>1044</td><td>1044</td><td>1043</td><td>1044</td></tr><tr><td>p7.2.r</td><td>1094</td><td>1069</td><td>1075</td><td>1076</td><td>1094</td><td>1094</td><td>1094</td><td>1094</td><td>1094</td><td>1085</td><td>1094</td><td>1094</td><td>1094</td><td>1094</td><td>1094</td></tr><tr><td>p7.2.s</td><td>1136</td><td>1118</td><td>1102</td><td>1125</td><td>1136</td><td>1136</td><td>1136</td><td>1136</td><td>1136</td><td>1133</td><td>1136</td><td>1136</td><td>1136</td><td>1136</td><td>1136</td></tr><tr><td>p7.2.t</td><td>1179</td><td>1154</td><td>1142</td><td>1168</td><td>1179</td><td>1179</td><td>1179</td><td>1179</td><td>1179</td><td>1170</td><td>1179</td><td>1179</td><td>1179</td><td>1179</td><td>1179</td></tr><tr><td>p7.3.h</td><td>425</td><td>425</td><td>418</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td><td>425</td></tr><tr><td>p7.3.i</td><td>487</td><td>480</td><td>480</td><td>485</td><td>487</td><td>487</td><td>487</td><td>487</td><td>487</td><td>487</td><td>487</td><td>487</td><td>487</td><td>487</td><td>487</td></tr><tr><td>p7.3.j</td><td>564</td><td>543</td><td>539</td><td>560</td><td>564</td><td>564</td><td>564</td><td>564</td><td>564</td><td>564</td><td>564</td><td>564</td><td>564</td><td>564</td><td>564</td></tr><tr><td>p7.3.k</td><td>633</td><td>633</td><td>586</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td><td>633</td></tr><tr><td>p7.3.l</td><td>684</td><td>681</td><td>668</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td><td>684</td></tr><tr><td>p7.3.m</td><td>762</td><td>743</td><td>735</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td><td>762</td></tr><tr><td>p7.3.n</td><td>820</td><td>804</td><td>789</td><td>813</td><td>820</td><td>820</td><td>820</td><td>820</td><td>820</td><td>820</td><td>820</td><td>820</td><td>820</td><td>820</td><td>820</td></tr><tr><td>p7.3.o</td><td>874</td><td>841</td><td>833</td><td>859</td><td>874</td><td>874</td><td>874</td><td>874</td><td>874</td><td>874</td><td>874</td><td>874</td><td>874</td><td>874</td><td>874</td></tr><tr><td>p7.3.p</td><td>929</td><td>918</td><td>912</td><td>925</td><td>929</td><td>929</td><td>929</td><td>929</td><td>929</td><td>925</td><td>929</td><td>929</td><td>929</td><td>927</td><td>929</td></tr><tr><td>p7.3.q</td><td>987</td><td>966</td><td>945</td><td>970</td><td>987</td><td>987</td><td>987</td><td>987</td><td>987</td><td>984</td><td>987</td><td>987</td><td>987</td><td>987</td><td>987</td></tr><tr><td>p7.3.r</td><td>1026</td><td>1009</td><td>1015</td><td>1017</td><td>1026</td><td>1026</td><td>1026</td><td>1026</td><td>1026</td><td>1024</td><td>1026</td><td>1026</td><td>1026</td><td>1026</td><td>1026</td></tr><tr><td>p7.3.s</td><td>1081</td><td>1070</td><td>1054</td><td>1076</td><td>1081</td><td>1081</td><td>1081</td><td>1081</td><td>1081</td><td>1074</td><td>1081</td><td>1081</td><td>1081</td><td>1081</td><td>1081</td></tr><tr><td>p7.3.t</td><td>1120</td><td>1109</td><td>1080</td><td>1111</td><td>1120</td><td>1120</td><td>1120</td><td>1120</td><td>1120</td><td>1113</td><td>1120</td><td>1120</td><td>1120</td><td>1120</td><td>1120</td></tr><tr><td>p7.4.g</td><td>217</td><td>217</td><td>209</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td><td>217</td></tr><tr><td>p7.4.h</td><td>285</td><td>283</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td><td>285</td></tr><tr><td>p7.4.i</td><td>366</td><td>364</td><td>359</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td><td>366</td></tr><tr><td>p7.4.k</td><td>520</td><td>518</td><td>511</td><td>518</td><td>520</td><td>520</td><td>520</td><td>520</td><td>520</td><td>520</td><td>520</td><td>520</td><td>520</td><td>520</td><td>518</td></tr><tr><td>p7.4.l</td><td>590</td><td>575</td><td>573</td><td>581</td><td>590</td><td>590</td><td>590</td><td>590</td><td>590</td><td>590</td><td>590</td><td>590</td><td>590</td><td>590</td><td>590</td></tr><tr><td>p7.4.m</td><td>646</td><td>639</td><td>638</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td><td>646</td></tr><tr><td>p7.4.n</td><td>730</td><td>723</td><td>698</td><td>723</td><td>730</td><td>730</td><td>730</td><td>730</td><td>730</td><td>726</td><td>730</td><td>730</td><td>730</td><td>730</td><td>730</td></tr><tr><td>p7.4.o</td><td>781</td><td>778</td><td>761</td><td>780</td><td>781</td><td>781</td><td>781</td><td>781</td><td>781</td><td>777</td><td>781</td><td>781</td><td>781</td><td>781</td><td>781</td></tr><tr><td>p7.4.p</td><td>846</td><td>841</td><td>803</td><td>842</td><td>846</td><td>846</td><td>846</td><td>846</td><td>846</td><td>846</td><td>846</td><td>846</td><td>846</td><td>846</td><td>846</td></tr><tr><td>p7.4.q</td><td>909</td><td>896</td><td>899</td><td>902</td><td>909</td><td>909</td><td>909</td><td>909</td><td>909</td><td>904</td><td>909</td><td>909</td><td>909</td><td>909</td><td>909</td></tr><tr><td>p7.4.r</td><td>970</td><td>964</td><td>937</td><td>961</td><td>970</td><td>970</td><td>970</td><td>970</td><td>970</td><td>970</td><td>970</td><td>970</td><td>970</td><td>970</td><td>970</td></tr><tr><td>p7.4.s</td><td>1022</td><td>1019</td><td>1005</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td><td>1022</td></tr><tr><td>p7.4.t</td><td>1077</td><td>1073</td><td>1020</td><td>1066</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td><td>1077</td></tr></tbody></table>
## 9.2. Results on the large scale set of instances

<table><thead><tr><th rowspan="2">Instance</th><th colspan="2">Best known</th><th colspan="3">PSOiA</th><th colspan="3">PAM</th><th colspan="3">HALNS</th><th colspan="3">LNS2</th></tr><tr><th>Solution</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th></tr></thead><tbody><tr><td>bier127_gen1_m2</td><td>106</td><td>7.233</td><td><b>106</b></td><td>104.8</td><td>1153.87</td><td><b>106</b></td><td>105</td><td>673.5</td><td><b>106</b></td><td>105.5</td><td>207.2</td><td><b>106</b></td><td>105.35</td><td><b>7.233</b></td></tr><tr><td>bier127_gen1_m3</td><td>103</td><td>10.52</td><td><b>103</b></td><td>102.4</td><td>591.89</td><td><b>103</b></td><td>102.5</td><td>470.1</td><td><b>103</b></td><td>102.6</td><td>209.55</td><td><b>103</b></td><td>102.15</td><td><b>10.52</b></td></tr><tr><td>bier127_gen2_m2</td><td>5464</td><td>7.572</td><td><b>5464</b></td><td>5446.8</td><td>1132.57</td><td><b>5464</b></td><td>5454.9</td><td>398.8</td><td><b>5464</b></td><td>5460.2</td><td>301.33</td><td><b>5464</b></td><td>5442.45</td><td><b>7.572</b></td></tr><tr><td>bier127_gen2_m3</td><td>5393</td><td>5.457</td><td><b>5393</b></td><td>5376.2</td><td>648.08</td><td><b>5393</b></td><td>5386.9</td><td>359.3</td><td><b>5393</b></td><td>5390.1</td><td>227.51</td><td><b>5393</b></td><td>5392.6</td><td><b>5.457</b></td></tr><tr><td>bier127_gen2_m4</td><td>5123</td><td>355.99</td><td>5122</td><td>5119.2</td><td>657.57</td><td><b>5123</b></td><td>5120.2</td><td>383.8</td><td><b>5123</b></td><td>5121</td><td><b>355.99</b></td><td>5122</td><td>5121.15</td><td>7.081</td></tr><tr><td>bier127_gen3_m2</td><td>2885</td><td>6.168</td><td><b>2885</b></td><td>2884.3</td><td>1301.27</td><td><b>2885</b></td><td>2884.7</td><td>296.7</td><td><b>2885</b></td><td>2884.5</td><td>184.99</td><td><b>2885</b></td><td>2872.85</td><td><b>6.168</b></td></tr><tr><td>bier127_gen3_m3</td><td>2706</td><td>6.164</td><td><b>2706</b></td><td>2703.8</td><td>711.74</td><td><b>2706</b></td><td>2705.2</td><td>509.6</td><td><b>2706</b></td><td>2705.6</td><td>69.36</td><td><b>2706</b></td><td>2703.7</td><td><b>6.164</b></td></tr><tr><td>bier127_gen3_m4</td><td>2402</td><td>5.746</td><td><b>2402</b></td><td>2384.6</td><td>680.79</td><td><b>2402</b></td><td>2398.6</td><td>227.7</td><td><b>2402</b></td><td>2399.4</td><td>222.4</td><td><b>2402</b></td><td>2402</td><td><b>5.746</b></td></tr><tr><td>cmt101c_m3</td><td>1300</td><td>4.816</td><td><b>1300</b></td><td>1299</td><td>111.11</td><td><b>1300</b></td><td>1299</td><td>42</td><td><b>1300</b></td><td>1299.4</td><td>23.1</td><td><b>1300</b></td><td>1288</td><td><b>4.816</b></td></tr><tr><td>cmt151b_m3</td><td>1385</td><td>10.015</td><td><b>1385</b></td><td>1373.8</td><td>754.01</td><td><b>1385</b></td><td>1374.5</td><td>169.9</td><td><b>1385</b></td><td>1384</td><td>164.65</td><td><b>1385</b></td><td>1382.45</td><td><b>10.015</b></td></tr><tr><td>cmt151c_m2</td><td>1964</td><td>13.971</td><td><b>1963</b></td><td>1962</td><td>1799.64</td><td><b>1964</b></td><td>1962</td><td>368.5</td><td><b>1964</b></td><td>1962.2</td><td>131.96</td><td><b>1964</b></td><td>1960.6</td><td><b>13.971</b></td></tr><tr><td>cmt151c_m3</td><td>1916</td><td>355.61</td><td><b>1916</b></td><td>1909.1</td><td>1376.24</td><td><b>1916</b></td><td>1909.2</td><td>441.5</td><td><b>1916</b></td><td>1914.4</td><td><b>355.61</b></td><td>1911</td><td>1908.95</td><td>12.14</td></tr><tr><td>cmt151c_m4</td><td>1880</td><td>9.371</td><td><b>1880</b></td><td>1875.6</td><td>881.11</td><td><b>1880</b></td><td>1877.6</td><td>826.5</td><td><b>1880</b></td><td>1878.2</td><td>107.89</td><td><b>1880</b></td><td>1875.5</td><td><b>9.371</b></td></tr><tr><td>cmt200b_m2</td><td>2096</td><td>17.186</td><td><b>2096</b></td><td>2088.2</td><td>4180.99</td><td><b>2096</b></td><td>2086.8</td><td>669.4</td><td><b>2096</b></td><td>2090.2</td><td>183.28</td><td><b>2096</b></td><td>2094.2</td><td><b>17.186</b></td></tr><tr><td>cmt200b_m3</td><td>2019</td><td>21.687</td><td><b>2019</b></td><td>2005</td><td>2711.66</td><td><b>2019</b></td><td>2009.4</td><td>1351.7</td><td><b>2019</b></td><td>2004.4</td><td>386.33</td><td><b>2019</b></td><td>2011.5</td><td><b>21.687</b></td></tr><tr><td>cmt200b_m4</td><td>1894</td><td>12.826</td><td><b>1894</b></td><td>1889.7</td><td>1515.19</td><td><b>1894</b></td><td>1891.6</td><td>974.5</td><td><b>1894</b></td><td>1891</td><td>324.31</td><td><b>1894</b></td><td>1892.75</td><td><b>12.826</b></td></tr><tr><td>cmt200c_m2</td><td>2818</td><td>368.424</td><td><b>2818</b></td><td>2810.1</td><td>7320.26</td><td><b>2818</b></td><td>2810.6</td><td>1048.3</td><td><b>2818</b></td><td>2810</td><td>368.42</td><td><b>2809</b></td><td>2801.3</td><td>22.181</td></tr><tr><td>cmt200c_m3</td><td>2766</td><td>16.684</td><td><b>2766</b></td><td>2751.2</td><td>4217.29</td><td><b>2766</b></td><td>2751.8</td><td>1200</td><td><b>2766</b></td><td>2751.8</td><td>273.01</td><td><b>2766</b></td><td>2756.3</td><td><b>16.684</b></td></tr><tr><td>cmt200c_m4</td><td>2712</td><td>395.91</td><td><b>2712</b></td><td>2700.6</td><td>3004.1</td><td><b>2712</b></td><td>2703.3</td><td>1411.4</td><td><b>2712</b></td><td>2704.4</td><td>395.91</td><td><b>2711</b></td><td>2703.3</td><td>23.224</td></tr><tr><td>eil101b_m3</td><td>916</td><td>5.893</td><td><b>916</b></td><td>913.8</td><td>134.39</td><td><b>916</b></td><td>914.6</td><td>160.6</td><td><b>916</b></td><td>915.8</td><td>69.44</td><td><b>916</b></td><td>910.5</td><td><b>5.893</b></td></tr><tr><td>eil101c_m2</td><td>1305</td><td>4.705</td><td><b>1305</b></td><td>1304.8</td><td>452.79</td><td><b>1305</b></td><td>1304.8</td><td>250.5</td><td><b>1305</b></td><td>1304.7</td><td>153.85</td><td><b>1305</b></td><td>1305</td><td><b>4.705</b></td></tr><tr><td>eil101c_m3</td><td>1251</td><td>10.159</td><td><b>1251</b></td><td>1244.1</td><td>227.61</td><td><b>1251</b></td><td>1244.2</td><td>95</td><td><b>1251</b></td><td>1248.6</td><td>116.15</td><td><b>1251</b></td><td>1247.4</td><td><b>10.159</b></td></tr><tr><td>gil262_gen1_m3</td><td>101</td><td>13.271</td><td><b>101</b></td><td>100.9</td><td>1769.31</td><td><b>101</b></td><td>100.2</td><td>482.6</td><td><b>101</b></td><td>100.8</td><td>709.66</td><td><b>101</b></td><td>100.9</td><td><b>13.271</b></td></tr><tr><td>gil262_gen1_m4</td><td>78</td><td>11.605</td><td><b>78</b></td><td>77.1</td><td>155.76</td><td><b>78</b></td><td>77</td><td>123.5</td><td><b>78</b></td><td>77.95</td><td>76.98</td><td><b>78</b></td><td>77.9</td><td><b>11.605</b></td></tr><tr><td>gil262_gen2_m2</td><td>7498</td><td>16.072</td><td><b>7498</b></td><td>7457.8</td><td>7356.65</td><td><b>7498</b></td><td>7458.4</td><td>742.1</td><td><b>7498</b></td><td>7466.2</td><td>387</td><td><b>7498</b></td><td>7444.5</td><td><b>16.072</b></td></tr><tr><td>gil262_gen2_m3</td><td>5615</td><td>352.386</td><td><b>5615</b></td><td>5608.2</td><td>3304.55</td><td><b>5615</b></td><td>5604.9</td><td>1163.8</td><td><b>5615</b></td><td>5609.7</td><td>352.39</td><td><b>5614</b></td><td>5590.1</td><td>22.556</td></tr><tr><td>gil262_gen3_m2</td><td>7183</td><td>14.639</td><td><b>7183</b></td><td>7182.8</td><td>9129.3</td><td><b>7183</b></td><td>7180</td><td>284.2</td><td><b>7183</b></td><td>7182.5</td><td>532.11</td><td><b>7183</b></td><td>7168.4</td><td><b>14.639</b></td></tr><tr><td>gil262_gen3_m4</td><td>2507</td><td>11.092</td><td><b>2507</b></td><td>2499.8</td><td>276.42</td><td><b>2507</b></td><td>2500.1</td><td>308.8</td><td><b>2507</b></td><td>2501.2</td><td>227.15</td><td><b>2507</b></td><td>2505.25</td><td><b>11.092</b></td></tr><tr><td>gil262a_m2</td><td>4078</td><td>451.764</td><td><b>4078</b></td><td>4056.4</td><td>5907.29</td><td><b>4078</b></td><td>4066.3</td><td>2100</td><td><b>4078</b></td><td>4068.8</td><td>451.76</td><td><b>4038</b></td><td>4016.15</td><td>17.931</td></tr><tr><td>gil262a_m4</td><td>3175</td><td>10.696</td><td><b>3175</b></td><td>3174.2</td><td>271.83</td><td><b>3175</b></td><td>3175</td><td>222.6</td><td><b>3175</b></td><td>3175</td><td>133.79</td><td><b>3175</b></td><td>3175</td><td><b>10.696</b></td></tr><tr><td>gil262b_m2</td><td>8081</td><td>545.166</td><td><b>8081</b></td><td>8061.1</td><td>7473.18</td><td><b>8081</b></td><td>8074.1</td><td>1267.8</td><td><b>8081</b></td><td>8078.5</td><td>545.17</td><td><b>8072</b></td><td>8071.75</td><td>15.836</td></tr><tr><td>gil262b_m3</td><td>7585</td><td>463.187</td><td><b>7585</b></td><td>7574.9</td><td>7276.8</td><td><b>7585</b></td><td>7566.6</td><td>1027.2</td><td><b>7585</b></td><td>7569</td><td>463.19</td><td><b>7544</b></td><td>7411.95</td><td>29.904</td></tr><tr><td>gil262b_m4</td><td>6781</td><td>329.098</td><td><b>6781</b></td><td>6742</td><td>4878.64</td><td><b>6781</b></td><td>6756.7</td><td>912.6</td><td><b>6781</b></td><td>6761.3</td><td>329.1</td><td><b>6780</b></td><td>6760.55</td><td>31.56</td></tr><tr><td>gil262c_m2</td><td>11030</td><td>731.25</td><td><b>11030</b></td><td>1102.0</td><td>27500.87</td><td><b>11030</b></td><td>11016.5</td><td>1309</td><td><b>11030</b></td><td>11022.4</td><td>731.25</td><td><b>11008</b></td><td>10934.85</td><td>29.83</td></tr><tr><td>gil262c_m3</td><td>10757</td><td>650.871</td><td><b>10757</b></td><td>10714.6</td><td>14553.76</td><td><b>10757</b></td><td>10715.2</td><td>1375.6</td><td><b>10757</b></td><td>10713.1</td><td>650.87</td><td><b>10755</b></td><td>10683.7</td><td>31.52</td></tr><tr><td>gil262c_m4</td><td>10281</td><td>516.497</td><td><b>10281</b></td><td>10259.4</td><td>8472.01</td><td><b>10281</b></td><td>10267.3</td><td>1997</td><td><b>10281</b></td><td>10262.8</td><td>516.5</td><td><b>10280</b></td><td>10264.5</td><td>31.707</td></tr><tr><td>gr229_gen1_m4</td><td>223</td><td>46.6</td><td><b>223</b></td><td>220.8</td><td>11922.02</td><td><b>223</b></td><td>220.3</td><td><b>46.6</b></td><td><b>223</b></td><td>221</td><td>344.28</td><td><b>222</b></td><td>220.7</td><td>23.234</td></tr><tr><td>gr229_gen2_m3</td><td>11566</td><td>20.222</td><td><b>11566</b></td><td>11551.3</td><td>14197.21</td><td><b>11566</b></td><td>11557.8</td><td>1665.3</td><td><b>11566</b></td><td>11559.2</td><td>441.8</td><td><b>11566</b></td><td>11563.25</td><td><b>20.222</b></td></tr><tr><td>gr229_gen2_m4*</td><td>11359</td><td>20.572</td><td><b>11355</b></td><td>11255.3</td><td>18799.5</td><td><b>11355</b></td><td>11328.1</td><td>2272</td><td><b>11355</b></td><td>11355</td><td>377.28</td><td><b>11359</b></td><td>11334.45</td><td><b>20.572</b></td></tr><tr><td>gr229_gen3_m3</td><td>8056</td><td>19.351</td><td><b>8056</b></td><td>8051.6</td><td>14090.06</td><td><b>8056</b></td><td>8052.2</td><td>1065.3</td><td><b>8056</b></td><td>8055.4</td><td>938.75</td><td><b>8056</b></td><td>8047.5</td><td><b>19.351</b></td></tr><tr><td>gr229_gen3_m4*</td><td>7660</td><td>19.833</td><td><b>7621</b></td><td>7600</td><td>11399.71</td><td><b>7651</b></td><td>7610.5</td><td>781.5</td><td><b>7651</b></td><td>7622.9</td><td>828.68</td><td><b>7660</b></td><td>7610.75</td><td><b>19.833</b></td></tr><tr><td>kroA150_gen2_m2</td><td>4335</td><td>7.697</td><td><b>4335</b></td><td>4334.4</td><td>892.98</td><td><b>4335</b></td><td>4335</td><td>495.9</td><td><b>4335</b></td><td>4333.2</td><td>392.3</td><td><b>4335</b></td><td>4335</td><td><b>7.697</b></td></tr><tr><td>kroA150_gen3_m3</td><td>2726</td><td>168.809</td><td><b>2726</b></td><td>2719.6</td><td>538.01</td><td><b>2726</b></td><td>2725.2</td><td>597.2</td><td><b>2726</b></td><td>2725.8</td><td>168.81</td><td><b>2710</b></td><td>2664.15</td><td>14.682</td></tr><tr><td>kroA200_gen1_m4</td><td>81</td><td>9.827</td><td><b>81</b></td><td>80.4</td><td>560.29</td><td><b>81</b></td><td>80.6</td><td>503.4</td><td><b>81</b></td><td>81</td><td>114.61</td><td><b>81</b></td><td>80.45</td><td><b>9.827</b></td></tr><tr><td>kroB200_gen1_m2</td><td>111</td><td>10.339</td><td><b>111</b></td><td>110.4</td><td>2344.53</td><td><b>111</b></td><td>110.3</td><td>663.9</td><td><b>111</b></td><td>111</td><td>295.3</td><td><b>111</b></td><td>111</td><td><b>10.339</b></td></tr><tr><td>kroB200_gen2_m2</td><td>6185</td><td>12.176</td><td><b>6185</b></td><td>6182.2</td><td>3467.26</td><td><b>6185</b></td><td>6183.4</td><td>426.7</td><td><b>6185</b></td><td>6184.8</td><td>438.32</td><td><b>6185</b></td><td>6181.5</td><td><b>12.176</b></td></tr><tr><td>kroB200_gen2_m4</td><td>4944</td><td>8.506</td><td><b>4944</b></td><td>4942.2</td><td>640.66</td><td><b>4944</b></td><td>4942.4</td><td>582.4</td><td><b>4944</b></td><td>4942.5</td><td>360.44</td><td><b>4944</b></td><td>4944</td><td><b>8.506</b></td></tr><tr><td>kroB200_gen3_m2</td><td>4765</td><td>470.103</td><td><b>4765</b></td><td>4757.8</td><td>6306.62</td><td><b>4765</b></td><td>4762.4</td><td>513.9</td><td><b>4765</b></td><td>4765</td><td>470.1</td><td><b>4703</b></td><td>4669.5</td><td>17.803</td></tr><tr><td>kroB200_gen3_m3</td><td>3028</td><td>9.103</td><td><b>3028</b></td><td>3016</td><td>1713.88</td><td><b>3028</b></td><td>3022.4</td><td>741.5</td><td><b>3028</b></td><td>3022.9</td><td>547.22</td><td><b>3028</b></td><td>3014.8</td><td><b>9.103</b></td></tr><tr><td>lin318_gen1_m2</td><td>180</td><td>26.906</td><td><b>180</b></td><td>170.1</td><td>20667.24</td><td><b>180</b></td><td>175.3</td><td>1168.3</td><td><b>180</b></td><td>174.5</td><td>2702.83</td><td><b>180</b></td><td>173.7</td><td>26.906</td></tr><tr><td>lin318_gen1_m3</td><td>149</td><td>203.513</td><td><b>149</b></td><td>148.6</td><td>9014.64</td><td><b>149</b></td><td>147.9</td><td>721.4</td><td><b>149</b></td><td>148.4</td><td>203.51</td><td><b>148</b></td><td>148</td><td>16.169</td></tr><tr><td>lin318_gen2_m2</td><td>9544</td><td>21.127</td><td><b>9544</b></td><td>9533.8</td><td>23804.82</td><td><b>9544</b></td><td>9537.5</td><td>1924.6</td><td><b>9544</b></td><td>9539.2</td><td>1962.14</td><td><b>9544</b></td><td>9493.95</td><td><b>21.127</b></td></tr><tr><td>lin318_gen2_m3</td><td>7807</td><td>28.337</td><td><b>7786</b></td><td>7782.1</td><td>9773.63</td><td><b>7807</b></td><td>7769.6</td><td>1413.5</td><td><b>7807</b></td><td>7775.8</td><td>1600.58</td><td><b>7807</b></td><td>7741</td><td><b>28.337</b></td></tr><tr><td>lin318_gen3_m2</td><td>7936</td><td>19.965</td><td><b>7936</b></td><td>7905.6</td><td>44029</td><td><b>7936</b></td><td>7923.3</td><td>1547.3</td><td><b>7936</b></td><td>7919.2</td><td>581.27</td><td><b>7936</b></td><td>7842.45</td><td><b>19.965</b></td></tr><tr><td>lin318_gen3_m4</td><td>3797</td><td>22.165</td><td><b>3797</b></td><td>3796.4</td><td>1446.26</td><td><b>3797</b></td><td>3795.5</td><td>970.7</td><td><b>3797</b></td><td>3796</td><td>128.84</td><td><b>3797</b></td><td>3796.05</td><td><b>22.165</b></td></tr><tr><td>pr136_gen1_m2</td><td>63</td><td>8.055</td><td><b>63</b></td><td>62.7</td><td>451.13</td><td><b>63</b></td><td>62.8</td><td>107.5</td><td><b>63</b></td><td>62.9</td><td>70.72</td><td><b>63</b></td><td>63</td><td><b>8.055</b></td></tr><tr><td>pr136_gen2_m2</td><td>3646</td><td>6.444</td><td><b>3641</b></td><td>3631.8</td><td>601.31</td><td><b>3646</b></td><td>3637.4</td><td>281.6</td><td><b>3646</b></td><td>3642.8</td><td>95.62</td><td><b>3646</b></td><td>3639.1</td><td><b>6.444</b></td></tr><tr><td>pr264_gen1_m4</td><td>107</td><td>12.052</td><td><b>107</b></td><td>106.6</td><td>503.07</td><td><b>107</b></td><td>106.7</td><td>289.8</td><td><b>107</b></td><td>106.6</td><td>195.83</td><td><b>107</b></td><td>106.65</td><td><b>12.052</b></td></tr><tr><td>pr264_gen2_m2</td><td>6635</td><td>642.978</td><td><b>6635</b></td><td>6634.2</td><td>2048.2</td><td><b>6635</b></td><td>6632</td><td>719</td><td><b>6635</b></td><td>6634.4</td><td>642.98</td><td><b>6631</b></td><td>6627.1</td><td>15.713</td></tr><tr><td>pr264_gen2_m3</td><td>6420</td><td>11.334</td><td><b>6420</b></td><td>6410.7</td><td>938.39</td><td><b>6420</b></td><td>6417</td><td>859</td><td><b>6420</b></td><td>6418</td><td>527.27</td><td><b>6420</b></td><td>6400.5</td><td><b>11.334</b></td></tr><tr><td>pr264_gen2_m4</td><td>5584</td><td>25.988</td><td><b>5584</b></td><td>5564.5</td><td>590.79</td><td><b>5584</b></td><td>5565.1</td><td>663.2</td><td><b>5584</b></td><td>5566.2</td><td>294.7</td><td><b>5584</b></td><td>5566</td><td><b>25.988</b></td></tr><tr><td>pr264_gen3_m3</td><td>2772</td><td>16.526</td><td><b>2772</b></td><td>2770</td><td>1037.51</td><td><b>2772</b></td><td>2769.8</td><td>922.5</td><td><b>2772</b></td><td>2770</td><td>1490.82</td><td><b>2772</b></td><td>2761.65</td><td><b>16.526</b></td></tr><tr><td>pr299_gen1_m2</td><td>139</td><td>14.544</td><td><b>139</b></td><td>138.5</td><td>4775.93</td><td><b>139</b></td><td>138.3</td><td>573.4</td><td><b>139</b></td><td>138.8</td><td>355.26</td><td><b>139</b></td><td>138.25</td><td><b>14.544</b></td></tr><tr><td>pr299_gen1_m3</td><td>111</td><td>33.519</td><td><b>111</b></td><td>110.1</td><td>1303.73</td><td><b>111</b></td><td>109.2</td><td>506</td><td><b>111</b></td><td>110.2</td><td>413.78</td><td><b>111</b></td><td>109.2</td><td><b>33.519</b></td></tr></tbody></table>

(To be continued)
<table><caption>Table 21: Summary results for the set of large scale instances.</caption><thead><tr><th rowspan="2">Instance</th><th colspan="2">Best known</th><th colspan="3">PSOiA</th><th colspan="3">PAM</th><th colspan="3">HALNS</th><th colspan="3">LNS2</th></tr><tr><th>Solution</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Best</th><th>Mean</th><th>CPU (s)</th></tr></thead><tbody><tr><td>pr299_gen1_m4</td><td>84</td><td>34.302</td><td><strong>84</strong></td><td>83.6</td><td>383.48</td><td><strong>84</strong></td><td>83.6</td><td>340.3</td><td><strong>84</strong></td><td>83.4</td><td>191.29</td><td><strong>84</strong></td><td>83.8</td><td>34.302</td></tr><tr><td>pr299_gen2_m3</td><td>6018</td><td>690.41</td><td><strong>6018</strong></td><td>5966.7</td><td>1446.05</td><td><strong>6018</strong></td><td>5979.2</td><td>909.7</td><td><strong>6018</strong></td><td>5978.5</td><td><strong>690.41</strong></td><td>6005</td><td>5961.6</td><td>32.493</td></tr><tr><td>pr299_gen2_m4</td><td>4457</td><td>32.49</td><td><strong>4457</strong></td><td>4453</td><td>593.41</td><td><strong>4457</strong></td><td>4455.2</td><td>767.7</td><td><strong>4457</strong></td><td>4454.8</td><td>257.75</td><td><strong>4457</strong></td><td>4446.2</td><td><strong>32.49</strong></td></tr><tr><td>pr299_gen3_m2</td><td>5729</td><td>692.124</td><td><strong>5729</strong></td><td>5728.6</td><td>11872.55</td><td><strong>5729</strong></td><td>5709.8</td><td>1489.5</td><td><strong>5729</strong></td><td>5729</td><td>692.12</td><td>5728</td><td>5715.95</td><td>41.758</td></tr><tr><td>pr299_gen3_m3</td><td>3655</td><td>31.122</td><td><strong>3655</strong></td><td>3611</td><td>2705.82</td><td><strong>3655</strong></td><td>3611.6</td><td>1058.2</td><td><strong>3655</strong></td><td>3648.2</td><td>644.38</td><td><strong>3655</strong></td><td>3607.8</td><td><strong>31.122</strong></td></tr><tr><td>pr299_gen3_m4</td><td>2268</td><td>29.293</td><td><strong>2268</strong></td><td>2258</td><td>455.64</td><td><strong>2268</strong></td><td>2261.8</td><td>402.4</td><td><strong>2268</strong></td><td>2262.3</td><td>271.94</td><td><strong>2268</strong></td><td>2183.65</td><td><strong>29.293</strong></td></tr><tr><td>rat195_gen2_m2</td><td>5148</td><td>335.533</td><td><strong>5148</strong></td><td>5145.6</td><td>2156.98</td><td><strong>5148</strong></td><td>5145.9</td><td>886.6</td><td><strong>5148</strong></td><td>5147.6</td><td>335.53</td><td>5145</td><td>5135.75</td><td>17.739</td></tr><tr><td>rat195_gen3_m3</td><td>2574</td><td>15.321</td><td><strong>2574</strong></td><td>2571.2</td><td>721.82</td><td><strong>2574</strong></td><td>2569.9</td><td>369.5</td><td><strong>2574</strong></td><td>2570.2</td><td>276.84</td><td><strong>2574</strong></td><td>2574</td><td><strong>15.321</strong></td></tr><tr><td>rd400_gen1_m2*</td><td>233</td><td>51.437</td><td>230</td><td>227.8</td><td>56767.29</td><td>232</td><td>228.5</td><td>3066.6</td><td>232</td><td>227.9</td><td>3925.58</td><td><strong>233</strong></td><td>230.7</td><td><strong>51.437</strong></td></tr><tr><td>rd400_gen1_m3</td><td>224</td><td>2844</td><td>222</td><td>221.7</td><td>62476.08</td><td><strong>224</strong></td><td>221.3</td><td><strong>2844</strong></td><td><strong>224</strong></td><td>221.4</td><td>4178</td><td>223</td><td>221.65</td><td>48.846</td></tr><tr><td>rd400_gen1_m4</td><td>213</td><td>1985.4</td><td><strong>213</strong></td><td>210.6</td><td>34744.8</td><td><strong>213</strong></td><td>209.9</td><td><strong>1985.4</strong></td><td><strong>213</strong></td><td>210.8</td><td>3000.9</td><td>212</td><td>210</td><td>40.603</td></tr><tr><td>rd400_gen2_m2</td><td>13045</td><td>3220.6</td><td>12993</td><td>12787.5</td><td>77049.22</td><td><strong>13045</strong></td><td>12873</td><td><strong>3220.6</strong></td><td><strong>13045</strong></td><td>12872.4</td><td>4035.08</td><td>13018</td><td>12873.15</td><td>49.308</td></tr><tr><td>rd400_gen2_m3</td><td>12646</td><td>2814.581</td><td>12645</td><td>12372.1</td><td>53707.14</td><td>12645</td><td>12543.9</td><td>2852.7</td><td><strong>12646</strong></td><td>12555.8</td><td>2814.58</td><td>12362</td><td>12299.4</td><td>51.986</td></tr><tr><td>rd400_gen2_m4</td><td>12032</td><td>3299.3</td><td><strong>12032</strong></td><td>11953.5</td><td>42001.58</td><td><strong>12032</strong></td><td>11969.7</td><td><strong>3299.3</strong></td><td><strong>12032</strong></td><td>11981.2</td><td>4070.44</td><td>12031</td><td>11895.65</td><td>50.686</td></tr><tr><td>rd400_gen3_m2</td><td>12431</td><td>2418.4</td><td>12428</td><td>12274.1</td><td>96178.7</td><td><strong>12431</strong></td><td>12312.2</td><td><strong>2418.4</strong></td><td><strong>12431</strong></td><td>12308</td><td>2814.66</td><td>12291</td><td>12240.45</td><td>47.492</td></tr><tr><td>rd400_gen3_m3</td><td>11639</td><td>3500</td><td><strong>11639</strong></td><td>11629.5</td><td>68074.77</td><td><strong>11639</strong></td><td>11549.8</td><td><strong>3500</strong></td><td><strong>11639</strong></td><td>11609.8</td><td>3811.24</td><td>11579</td><td>11291.65</td><td>46.578</td></tr><tr><td>rd400_gen3_m4</td><td>10436</td><td>3500</td><td>10417</td><td>10383.1</td><td>48462.77</td><td><strong>10436</strong></td><td>10345.4</td><td><strong>3500</strong></td><td><strong>10436</strong></td><td>10392.6</td><td>3615.46</td><td>10374</td><td>10282.95</td><td>46.846</td></tr><tr><td>ts225_gen2_m2</td><td>5859</td><td>18.454</td><td><strong>5859</strong></td><td>5858.5</td><td>2998.43</td><td><strong>5859</strong></td><td>5859</td><td>759.6</td><td><strong>5859</strong></td><td>5858.6</td><td>686.54</td><td><strong>5859</strong></td><td>5728.1</td><td><strong>18.454</strong></td></tr></tbody></table>

## 9.3. Results on very large scale set of instances

<table><thead><tr><th>Instance</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Instance</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Instance</th><th>Best</th><th>Mean</th><th>CPU (s)</th></tr></thead><tbody><tr><td>pr1002_gen1_m10</td><td>215</td><td>210.45</td><td>104.118</td><td>fl1400_gen1_m3</td><td>538</td><td>529.85</td><td>211.396</td><td>u2152_gen1_m2</td><td>1079</td><td>1067.55</td><td>448.405</td></tr><tr><td>pr1002_gen1_m2</td><td>550</td><td>529.9</td><td>117.181</td><td>fl1400_gen1_m8</td><td>288</td><td>281</td><td>148.402</td><td>u2152_gen1_m3</td><td>1069</td><td>1056.15</td><td>381.973</td></tr><tr><td>pr1002_gen1_m3</td><td>496</td><td>490.05</td><td>109.458</td><td>fl1400_gen2_m10</td><td>5331</td><td>5331</td><td>117.348</td><td>u2152_gen1_m8</td><td>844</td><td>836.4</td><td>331.438</td></tr><tr><td>pr1002_gen1_m8</td><td>265</td><td>260.3</td><td>115.722</td><td>fl1400_gen2_m2</td><td>45519</td><td>45459.9</td><td>307.618</td><td>u2152_gen2_m10</td><td>39930</td><td>39612.05</td><td>329.565</td></tr><tr><td>pr1002_gen2_m10</td><td>11928</td><td>11711.05</td><td>102.929</td><td>fl1400_gen2_m3</td><td>29911</td><td>29110.05</td><td>187.739</td><td>u2152_gen2_m2</td><td>60946</td><td>60131.45</td><td>415.845</td></tr><tr><td>pr1002_gen2_m2</td><td>30461</td><td>28949.05</td><td>125.856</td><td>fl1400_gen2_m8</td><td>14594</td><td>14579.6</td><td>162.858</td><td>u2152_gen2_m3</td><td>58881</td><td>58499.5</td><td>391.487</td></tr><tr><td>pr1002_gen2_m3</td><td>27175</td><td>26791.75</td><td>108.35</td><td>fl1400_gen3_m10</td><td>1450</td><td>1434.7</td><td>123.051</td><td>u2152_gen2_m8</td><td>45701</td><td>45311.3</td><td>316.243</td></tr><tr><td>pr1002_gen2_m8</td><td>14183</td><td>13868.45</td><td>111.789</td><td>fl1400_gen3_m2</td><td>38339</td><td>36457.65</td><td>295.203</td><td>u2152_gen3_m10</td><td>20347</td><td>20075.9</td><td>328.789</td></tr><tr><td>pr1002_gen3_m10</td><td>5565</td><td>5548.15</td><td>103.095</td><td>fl1400_gen3_m3</td><td>20796</td><td>16407.65</td><td>217.344</td><td>u2152_gen3_m2</td><td>67950</td><td>67022</td><td>405.896</td></tr><tr><td>pr1002_gen3_m2</td><td>34637</td><td>34092.3</td><td>115.28</td><td>fl1400_gen3_m8</td><td>5112</td><td>5094</td><td>154.688</td><td>u2152_gen3_m3</td><td>61520</td><td>60683.1</td><td>345.428</td></tr><tr><td>pr1002_gen3_m3</td><td>27333</td><td>26701.6</td><td>101.344</td><td>u1432_gen1_m10</td><td>641</td><td>633.55</td><td>189.197</td><td>u2152_gen3_m8</td><td>26383</td><td>26053.85</td><td>320.334</td></tr><tr><td>pr1002_gen3_m8</td><td>7739</td><td>7518.8</td><td>104.374</td><td>u1432_gen1_m2</td><td>740</td><td>735.1</td><td>237.625</td><td>u2139_gen1_m10</td><td>1067</td><td>1062</td><td>451.098</td></tr><tr><td>u1060_gen1_m10</td><td>292</td><td>288.5</td><td>127.988</td><td>u1432_gen1_m3</td><td>728</td><td>722.1</td><td>217.797</td><td>u2139_gen1_m2</td><td>1166</td><td>1164.3</td><td>615.41</td></tr><tr><td>u1060_gen1_m2</td><td>605</td><td>595.25</td><td>142.994</td><td>u1432_gen1_m8</td><td>667</td><td>659.4</td><td>201.458</td><td>u2139_gen1_m3</td><td>1163</td><td>1161.2</td><td>576.607</td></tr><tr><td>u1060_gen1_m3</td><td>563</td><td>553.85</td><td>138.828</td><td>u1432_gen2_m10</td><td>34889</td><td>34591.5</td><td>202.634</td><td>u2139_gen1_m8</td><td>1109</td><td>1102.75</td><td>472.08</td></tr><tr><td>u1060_gen1_m8</td><td>391</td><td>384.6</td><td>117.293</td><td>u1432_gen2_m2</td><td>45074</td><td>44655.75</td><td>224.796</td><td>u2139_gen2_m10</td><td>65270</td><td>64825.6</td><td>433.703</td></tr><tr><td>u1060_gen2_m10</td><td>15174</td><td>14963.6</td><td>132.918</td><td>u1432_gen2_m3</td><td>44406</td><td>43812.15</td><td>214.047</td><td>u2139_gen2_m2</td><td>77763</td><td>77315.75</td><td>576.063</td></tr><tr><td>u1060_gen2_m2</td><td>33655</td><td>33051.8</td><td>138.517</td><td>u1432_gen2_m8</td><td>37724</td><td>37344.5</td><td>191.346</td><td>u2139_gen2_m3</td><td>77407</td><td>76794.7</td><td>539.57</td></tr><tr><td>u1060_gen2_m3</td><td>31283</td><td>30470.35</td><td>128.437</td><td>u1432_gen3_m10</td><td>18759</td><td>18559.7</td><td>172.361</td><td>u2139_gen2_m8</td><td>70603</td><td>69863.05</td><td>405.996</td></tr><tr><td>u1060_gen2_m8</td><td>20607</td><td>20502.15</td><td>123.422</td><td>u1432_gen3_m2</td><td>44906</td><td>44695.95</td><td>248.799</td><td>u2139_gen3_m10</td><td>45807</td><td>45428.4</td><td>455.556</td></tr><tr><td>u1060_gen3_m10</td><td>5718</td><td>5633</td><td>120.408</td><td>u1432_gen3_m3</td><td>42393</td><td>42118.8</td><td>191.488</td><td>u2139_gen3_m2</td><td>76452</td><td>76013.15</td><td>757.645</td></tr><tr><td>u1060_gen3_m2</td><td>33931</td><td>32963.1</td><td>122.56</td><td>u1432_gen3_m8</td><td>23179</td><td>22914.95</td><td>175.678</td><td>u2139_gen3_m3</td><td>73609</td><td>73246.9</td><td>567.175</td></tr><tr><td>u1060_gen3_m3</td><td>27044</td><td>26607.25</td><td>103.197</td><td>fl1577_gen1_m10</td><td>294</td><td>290.3</td><td>198.441</td><td>u2139_gen3_m8</td><td>54524</td><td>54219.25</td><td>414.717</td></tr><tr><td>u1060_gen3_m8</td><td>9040</td><td>8991.55</td><td>111.938</td><td>fl1577_gen1_m2</td><td>821</td><td>810.7</td><td>238.721</td><td>pr2392_gen1_m10</td><td>780</td><td>775.4</td><td>366.129</td></tr><tr><td>vm1084_gen1_m10</td><td>422</td><td>420.25</td><td>161.439</td><td>fl1577_gen1_m3</td><td>775</td><td>745.4</td><td>217.173</td><td>pr2392_gen1_m2</td><td>1267</td><td>1252.5</td><td>567.095</td></tr><tr><td>vm1084_gen1_m2</td><td>739</td><td>733.2</td><td>190.626</td><td>fl1577_gen1_m8</td><td>397</td><td>387.6</td><td>201.181</td><td>pr2392_gen1_m3</td><td>1228</td><td>1216.55</td><td>491.994</td></tr><tr><td>vm1084_gen1_m3</td><td>690</td><td>685.7</td><td>161.704</td><td>fl1577_gen2_m10</td><td>15676</td><td>15586</td><td>206</td><td>pr2392_gen1_m8</td><td>916</td><td>905.75</td><td>383.213</td></tr><tr><td>vm1084_gen1_m8</td><td>465</td><td>460.3</td><td>159.598</td><td>fl1577_gen2_m2</td><td>43958</td><td>42670.1</td><td>224.016</td><td>pr2392_gen2_m10</td><td>41579</td><td>41123.2</td><td>396.523</td></tr><tr><td>vm1084_gen2_m10</td><td>21134</td><td>20976.4</td><td>183.81</td><td>fl1577_gen2_m3</td><td>40608</td><td>39831.9</td><td>218.282</td><td>pr2392_gen2_m2</td><td>71250</td><td>69946.4</td><td>556.238</td></tr><tr><td>vm1084_gen2_m2</td><td>40141</td><td>38879.15</td><td>193.154</td><td>fl1577_gen2_m8</td><td>22309</td><td>22222.7</td><td>198.312</td><td>pr2392_gen2_m3</td><td>68643</td><td>67748.05</td><td>478.978</td></tr><tr><td>vm1084_gen2_m3</td><td>37038</td><td>36381.15</td><td>170.173</td><td>fl1577_gen3_m10</td><td>4748</td><td>4732.55</td><td>194.489</td><td>pr2392_gen2_m8</td><td>49361</td><td>48963.25</td><td>418.866</td></tr><tr><td>vm1084_gen2_m8</td><td>23703</td><td>23550.35</td><td>159.189</td><td>fl1577_gen3_m2</td><td>33172</td><td>32952.15</td><td>267.03</td><td>pr2392_gen3_m10</td><td>24484</td><td>24220.55</td><td>380.322</td></tr><tr><td>vm1084_gen3_m10</td><td>7892</td><td>7859.9</td><td>163.761</td><td>fl1577_gen3_m3</td><td>26374</td><td>25044.8</td><td>193.18</td><td>pr2392_gen3_m2</td><td>79487</td><td>78705.55</td><td>570.504</td></tr><tr><td>vm1084_gen3_m2</td><td>34872</td><td>34566.3</td><td>164.207</td><td>fl1577_gen3_m8</td><td>8462</td><td>8376.25</td><td>221.178</td><td>pr2392_gen3_m3</td><td>74225</td><td>73293.25</td><td>439.969</td></tr><tr><td>vm1084_gen3_m3</td><td>32582</td><td>32157.6</td><td>136.939</td><td>d1655_gen1_m10</td><td>16</td><td>16</td><td>104.819</td><td>pr2392_gen3_m8</td><td>33824</td><td>33360.25</td><td>370.884</td></tr><tr><td>vm1084_gen3_m8</td><td>10047</td><td>9944.2</td><td>152.159</td><td>d1655_gen1_m2</td><td>755</td><td>742</td><td>225.14</td><td>pcb3038_gen1_m10</td><td>1231</td><td>1221.4</td><td>615.156</td></tr><tr><td>pcb1173_gen1_m10</td><td>319</td><td>318.15</td><td>130.556</td><td>d1655_gen1_m3</td><td>592</td><td>580</td><td>205.651</td><td>pcb3038_gen1_m2</td><td>1615</td><td>1599.95</td><td>1054.969</td></tr><tr><td>pcb1173_gen1_m2</td><td>633</td><td>629</td><td>165.288</td><td>d1655_gen1_m8</td><td>107</td><td>105.8</td><td>125.122</td><td>pcb3038_gen1_m3</td><td>1617</td><td>1594.9</td><td>828.263</td></tr><tr><td>pcb1173_gen1_m3</td><td>612</td><td>605.6</td><td>163.247</td><td>d1655_gen2_m10</td><td>698</td><td>698</td><td>109.471</td><td>pcb3038_gen1_m8</td><td>1350</td><td>1338.05</td><td>616.676</td></tr><tr><td>pcb1173_gen1_m8</td><td>417</td><td>415.45</td><td>135.601</td><td>d1655_gen2_m2</td><td>41425</td><td>40941.65</td><td>222.491</td><td>pcb3038_gen2_m10</td><td>67239</td><td>66686.65</td><td>577.361</td></tr></tbody></table>

(To be continued)
<table><caption>Table 22: Results for the set of very large scale instances.</caption><thead><tr><th>Instance</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Instance</th><th>Best</th><th>Mean</th><th>CPU (s)</th><th>Instance</th><th>Best</th><th>Mean</th><th>CPU (s)</th></tr></thead><tbody><tr><td>pcb1173_gen2_m10</td><td>16665</td><td>16556.4</td><td>134.288</td><td>d1655_gen2_m3</td><td>34701</td><td>33707.4</td><td>192.853</td><td>pcb3038_gen2_m2</td><td>91808</td><td>91013.2</td><td>886.666</td></tr><tr><td>pcb1173_gen2_m2</td><td>34723</td><td>34391.65</td><td>160.813</td><td>d1655_gen2_m8</td><td>5490</td><td>5447.05</td><td>137.195</td><td>pcb3038_gen2_m3</td><td>90632</td><td>90150.4</td><td>781.123</td></tr><tr><td>pcb1173_gen2_m3</td><td>33706</td><td>33230.3</td><td>152.4</td><td>d1655_gen3_m10</td><td>511</td><td>511</td><td>105.376</td><td>pcb3038_gen2_m8</td><td>75638</td><td>74826.6</td><td>617.63</td></tr><tr><td>pcb1173_gen2_m8</td><td>21921</td><td>21714.8</td><td>142.331</td><td>d1655_gen3_m2</td><td>49683</td><td>45426.3</td><td>199.828</td><td>pcb3038_gen3_m10</td><td>44547</td><td>44179.85</td><td>665.562</td></tr><tr><td>pcb1173_gen3_m10</td><td>8953</td><td>8894.25</td><td>129.79</td><td>d1655_gen3_m3</td><td>35146</td><td>33708.15</td><td>169.953</td><td>pcb3038_gen3_m2</td><td>101395</td><td>100463.4</td><td>1063.779</td></tr><tr><td>pcb1173_gen3_m2</td><td>37660</td><td>37225.5</td><td>156.218</td><td>d1655_gen3_m8</td><td>3827</td><td>3793.05</td><td>127.774</td><td>pcb3038_gen3_m3</td><td>96597</td><td>95961.4</td><td>777.048</td></tr><tr><td>pcb1173_gen3_m3</td><td>33994</td><td>33435.05</td><td>130.341</td><td>vm1748_gen1_m10</td><td>603</td><td>599.65</td><td>272.704</td><td>pcb3038_gen3_m8</td><td>56937</td><td>56345.05</td><td>562.118</td></tr><tr><td>pcb1173_gen3_m8</td><td>13463</td><td>13405.85</td><td>136.932</td><td>vm1748_gen1_m2</td><td>1230</td><td>1221.35</td><td>426.532</td><td>fl3795_gen1_m10</td><td>410</td><td>410</td><td>793.287</td></tr><tr><td>d1291_gen1_m2</td><td>598</td><td>593.85</td><td>136.857</td><td>vm1748_gen1_m3</td><td>1230</td><td>1224</td><td>358.198</td><td>fl3795_gen1_m2</td><td>1989</td><td>1917.25</td><td>1300.893</td></tr><tr><td>d1291_gen1_m3</td><td>486</td><td>479.4</td><td>123.49</td><td>vm1748_gen1_m8</td><td>793</td><td>785.2</td><td>268.893</td><td>fl3795_gen1_m3</td><td>1859</td><td>1762.45</td><td>1041.273</td></tr><tr><td>d1291_gen1_m8</td><td>39</td><td>39</td><td>82.937</td><td>vm1748_gen2_m10</td><td>32540</td><td>31870.35</td><td>283.007</td><td>fl3795_gen1_m8</td><td>565</td><td>560.35</td><td>724.526</td></tr><tr><td>d1291_gen2_m2</td><td>31656</td><td>31121.05</td><td>140.718</td><td>vm1748_gen2_m2</td><td>65707</td><td>65370.4</td><td>424.636</td><td>fl3795_gen2_m10</td><td>24311</td><td>23464.4</td><td>787.527</td></tr><tr><td>d1291_gen2_m3</td><td>25419</td><td>24897</td><td>129.694</td><td>vm1748_gen2_m3</td><td>65731</td><td>65053.8</td><td>352.004</td><td>fl3795_gen2_m2</td><td>106336</td><td>105453.9</td><td>1042.231</td></tr><tr><td>d1291_gen2_m8</td><td>2013</td><td>2013</td><td>82.029</td><td>vm1748_gen2_m8</td><td>42184</td><td>41231</td><td>285.625</td><td>fl3795_gen2_m3</td><td>100818</td><td>99137.2</td><td>826.789</td></tr><tr><td>d1291_gen3_m2</td><td>31965</td><td>31045.5</td><td>119.418</td><td>vm1748_gen3_m10</td><td>18111</td><td>17768.1</td><td>259.586</td><td>fl3795_gen2_m8</td><td>34262</td><td>34031.9</td><td>619.511</td></tr><tr><td>d1291_gen3_m3</td><td>23942</td><td>22953.6</td><td>107.009</td><td>vm1748_gen3_m2</td><td>69111</td><td>68818.05</td><td>529.487</td><td>fl3795_gen3_m10</td><td>7518</td><td>7274.7</td><td>943.546</td></tr><tr><td>d1291_gen3_m8</td><td>1166</td><td>1166</td><td>80.31</td><td>vm1748_gen3_m3</td><td>66755</td><td>66326.15</td><td>391.11</td><td>fl3795_gen3_m2</td><td>77042</td><td>75552.25</td><td>648.336</td></tr><tr><td>rl1304_gen1_m10</td><td>463</td><td>458.4</td><td>196.221</td><td>vm1748_gen3_m8</td><td>28302</td><td>27693.05</td><td>298.117</td><td>fl3795_gen3_m3</td><td>57135</td><td>54359.05</td><td>783.672</td></tr><tr><td>rl1304_gen1_m2</td><td>774</td><td>759.4</td><td>234.356</td><td>u1817_gen1_m10</td><td>542</td><td>536.75</td><td>257.277</td><td>fl3795_gen3_m8</td><td>12286</td><td>12083.6</td><td>795.271</td></tr><tr><td>rl1304_gen1_m3</td><td>760</td><td>738</td><td>186.646</td><td>u1817_gen1_m2</td><td>919</td><td>906.05</td><td>303.575</td><td>fnl4461_gen1_m10</td><td>2138</td><td>2119.75</td><td>1424.848</td></tr><tr><td>rl1304_gen1_m8</td><td>537</td><td>534.35</td><td>172.057</td><td>u1817_gen1_m3</td><td>890</td><td>880.35</td><td>262.182</td><td>fnl4461_gen1_m2</td><td>2414</td><td>2391.2</td><td>2445.002</td></tr><tr><td>rl1304_gen2_m10</td><td>24416</td><td>24085.4</td><td>180.04</td><td>u1817_gen1_m8</td><td>637</td><td>630.35</td><td>229.776</td><td>fnl4461_gen1_m3</td><td>2400</td><td>2377.95</td><td>2076.616</td></tr><tr><td>rl1304_gen2_m2</td><td>41120</td><td>39766.15</td><td>217.164</td><td>u1817_gen2_m10</td><td>28636</td><td>28413.9</td><td>253.325</td><td>fnl4461_gen1_m8</td><td>2232</td><td>2214.65</td><td>1458.891</td></tr><tr><td>rl1304_gen2_m3</td><td>39157</td><td>38405.6</td><td>194.536</td><td>u1817_gen2_m2</td><td>50796</td><td>50100.4</td><td>292.257</td><td>fnl4461_gen2_m10</td><td>123087</td><td>121837.7</td><td>1240.387</td></tr><tr><td>rl1304_gen2_m8</td><td>28708</td><td>28278.7</td><td>175.155</td><td>u1817_gen2_m3</td><td>49486</td><td>48839.3</td><td>275.61</td><td>fnl4461_gen2_m2</td><td>141676</td><td>140707.25</td><td>1935.007</td></tr><tr><td>rl1304_gen3_m10</td><td>9502</td><td>9373.15</td><td>187.925</td><td>u1817_gen2_m8</td><td>34042</td><td>33731.85</td><td>247.567</td><td>fnl4461_gen2_m3</td><td>140947</td><td>139495.15</td><td>1684.085</td></tr><tr><td>rl1304_gen3_m2</td><td>39532</td><td>38334.65</td><td>160.461</td><td>u1817_gen3_m10</td><td>14054</td><td>13650.7</td><td>258.418</td><td>fnl4461_gen2_m8</td><td>129519</td><td>128014.85</td><td>1303.958</td></tr><tr><td>rl1304_gen3_m3</td><td>36891</td><td>34841.5</td><td>185.188</td><td>u1817_gen3_m2</td><td>57808</td><td>57417.85</td><td>262.001</td><td>fnl4461_gen3_m10</td><td>96728</td><td>94751.3</td><td>1129.311</td></tr><tr><td>rl1304_gen3_m8</td><td>13141</td><td>12831.1</td><td>154.157</td><td>u1817_gen3_m3</td><td>49806</td><td>49253.15</td><td>224.523</td><td>fnl4461_gen3_m2</td><td>139885</td><td>131961.1</td><td>2573.647</td></tr><tr><td>rl1323_gen1_m10</td><td>352</td><td>348</td><td>174.686</td><td>u1817_gen3_m8</td><td>18583</td><td>17939.55</td><td>238.898</td><td>fnl4461_gen3_m3</td><td>136181</td><td>135203.15</td><td>1757.353</td></tr><tr><td>rl1323_gen1_m2</td><td>769</td><td>758.7</td><td>196.641</td><td>rl1889_gen1_m10</td><td>462</td><td>452.95</td><td>286.04</td><td>fnl4461_gen3_m8</td><td>110719</td><td>109059.65</td><td>1046.82</td></tr><tr><td>rl1323_gen1_m3</td><td>723</td><td>707.85</td><td>182.443</td><td>rl1889_gen1_m2</td><td>1138</td><td>1114.7</td><td>369.783</td><td>rl5915_gen1_m10</td><td>2733</td><td>2690.9</td><td>2077.884</td></tr><tr><td>rl1323_gen1_m8</td><td>457</td><td>455.35</td><td>182.067</td><td>rl1889_gen1_m3</td><td>1091</td><td>1080.15</td><td>355.116</td><td>rl5915_gen1_m2</td><td>3477</td><td>3405.5</td><td>3568.756</td></tr><tr><td>rl1323_gen2_m10</td><td>18296</td><td>18128.8</td><td>178.89</td><td>rl1889_gen1_m8</td><td>636</td><td>628.55</td><td>283.385</td><td>rl5915_gen1_m3</td><td>3457</td><td>3393.9</td><td>3050.192</td></tr><tr><td>rl1323_gen2_m2</td><td>41481</td><td>40466.3</td><td>202.354</td><td>rl1889_gen2_m10</td><td>24728</td><td>24453.7</td><td>290.245</td><td>rl5915_gen1_m8</td><td>3040</td><td>2966.85</td><td>2263.107</td></tr><tr><td>rl1323_gen2_m3</td><td>38791</td><td>38536.7</td><td>180.256</td><td>rl1889_gen2_m2</td><td>59936</td><td>59136.45</td><td>377.037</td><td>rl5915_gen2_m10</td><td>144675</td><td>142173</td><td>2110.743</td></tr><tr><td>rl1323_gen2_m8</td><td>23830</td><td>23644</td><td>176.487</td><td>rl1889_gen2_m3</td><td>57521</td><td>56929.85</td><td>327.585</td><td>rl5915_gen2_m2</td><td>182690</td><td>180305.8</td><td>3469.629</td></tr><tr><td>rl1323_gen3_m10</td><td>7351</td><td>7273.65</td><td>164.084</td><td>rl1889_gen2_m8</td><td>33968</td><td>33566.95</td><td>287.128</td><td>rl5915_gen2_m3</td><td>182018</td><td>178997.85</td><td>3010.962</td></tr><tr><td>rl1323_gen3_m2</td><td>43907</td><td>42881.75</td><td>197.115</td><td>rl1889_gen3_m10</td><td>10700</td><td>10587.8</td><td>271.358</td><td>rl5915_gen2_m8</td><td>159789</td><td>156982.4</td><td>2039.985</td></tr><tr><td>rl1323_gen3_m3</td><td>38072</td><td>37123.85</td><td>159.29</td><td>rl1889_gen3_m2</td><td>64900</td><td>64271.6</td><td>370.993</td><td>rl5915_gen3_m10</td><td>104482</td><td>101300.65</td><td>1848.89</td></tr><tr><td>rl1323_gen3_m8</td><td>11491</td><td>11434.65</td><td>170.393</td><td>rl1889_gen3_m3</td><td>58696</td><td>58236.1</td><td>289.093</td><td>rl5915_gen3_m2</td><td>198737</td><td>195990.35</td><td>3600.635</td></tr><tr><td>nrw1379_gen1_m10</td><td>629</td><td>620.35</td><td>204.062</td><td>rl1889_gen3_m8</td><td>18359</td><td>17891.75</td><td>293.784</td><td>rl5915_gen3_m3</td><td>195470</td><td>192648.05</td><td>2873.377</td></tr><tr><td>nrw1379_gen1_m2</td><td>785</td><td>774.05</td><td>258.487</td><td>d2103_gen1_m10</td><td>191</td><td>188.6</td><td>191.32</td><td>rl5915_gen3_m8</td><td>140636</td><td>135635.05</td><td>1861.404</td></tr><tr><td>nrw1379_gen1_m3</td><td>774</td><td>760.05</td><td>224.215</td><td>d2103_gen1_m2</td><td>1017</td><td>1001.5</td><td>351.286</td><td>rl5934_gen1_m10</td><td>2370</td><td>2314.2</td><td>1758.814</td></tr><tr><td>nrw1379_gen1_m8</td><td>677</td><td>671.45</td><td>199.835</td><td>d2103_gen1_m3</td><td>916</td><td>889.6</td><td>281.483</td><td>rl5934_gen1_m2</td><td>3363</td><td>3276.7</td><td>3600.345</td></tr><tr><td>nrw1379_gen2_m10</td><td>33914</td><td>33688.2</td><td>217.036</td><td>d2103_gen1_m8</td><td>323</td><td>321.5</td><td>224.683</td><td>rl5934_gen1_m3</td><td>3341</td><td>3270.45</td><td>2964.668</td></tr><tr><td>nrw1379_gen2_m2</td><td>45225</td><td>45019.25</td><td>259.447</td><td>d2103_gen2_m10</td><td>10548</td><td>10303.05</td><td>213.89</td><td>rl5934_gen1_m8</td><td>2642</td><td>2580.4</td><td>1979.486</td></tr><tr><td>nrw1379_gen2_m3</td><td>44463</td><td>44138.35</td><td>220.819</td><td>d2103_gen2_m2</td><td>56431</td><td>53576.65</td><td>363.469</td><td>rl5934_gen2_m10</td><td>122321</td><td>120639.2</td><td>1739.486</td></tr><tr><td>nrw1379_gen2_m8</td><td>37552</td><td>37259.4</td><td>202.48</td><td>d2103_gen2_m3</td><td>48508</td><td>46559.7</td><td>295.177</td><td>rl5934_gen2_m2</td><td>180470</td><td>177031.95</td><td>3601.828</td></tr><tr><td>nrw1379_gen3_m10</td><td>15375</td><td>15070.9</td><td>206.396</td><td>d2103_gen2_m8</td><td>18498</td><td>18355.55</td><td>218.114</td><td>rl5934_gen2_m3</td><td>178631</td><td>174893.4</td><td>2867.982</td></tr><tr><td>nrw1379_gen3_m2</td><td>40448</td><td>40200.1</td><td>223.57</td><td>d2103_gen3_m10</td><td>5887</td><td>5829.6</td><td>198.967</td><td>rl5934_gen3_m8</td><td>138437</td><td>135501.75</td><td>1913.607</td></tr><tr><td>nrw1379_gen3_m3</td><td>38276</td><td>37916.15</td><td>179.829</td><td>d2103_gen3_m2</td><td>69480</td><td>68094.3</td><td>369.836</td><td>rl5934_gen3_m10</td><td>87227</td><td>84321.75</td><td>1622.863</td></tr><tr><td>nrw1379_gen3_m8</td><td>19178</td><td>18707.95</td><td>175.773</td><td>d2103_gen3_m3</td><td>57293</td><td>54366.55</td><td>257.5</td><td>rl5934_gen3_m2</td><td>205202</td><td>202564.65</td><td>3600.209</td></tr><tr><td>fl1400_gen1_m10</td><td>103</td><td>102.25</td><td>117.246</td><td>d2103_gen3_m8</td><td>10038</td><td>9985.7</td><td>208.133</td><td>rl5934_gen3_m3</td><td>197516</td><td>195185.2</td><td>3062.074</td></tr><tr><td>fl1400_gen1_m2</td><td>865</td><td>864.25</td><td>236.562</td><td>u2152_gen1_m10</td><td>751</td><td>746.95</td><td>332.637</td><td>rl5934_gen3_m8</td><td>120936</td><td>117290.95</td><td>2045.778</td></tr></tbody></table>
## References

L. Accorsi and D. Vigo. A fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems. Transportation Science, 55:832–856, 2021. doi: 10.1287/trsc.2021.1059.

H. Alkhazaleh, N. Abdallah, A. Ibrahim, M. Habli, and T. Zeki. A scatter search hybrid approach for team orienteering problem. GIS Business, 14:767–782, 12 2019. doi: 10.26643/gis.v14i6.15249.

C. Archetti, A. Hertz, and M. G. Speranza. Metaheuristics for the team orienteering problem. J. Heuristics, 13:49–76, 02 2007. doi: 10.1007/s10732-006-9004-0.

F. Arnold and K. Sörensen. A simple, deterministic, and efficient knowledge-driven heuristic for the vehicle routing problem. Working Papers 2017012, University of Antwerp, Faculty of Business and Economics, December 2017.

F. Arnold and K. Sörensen. What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Computers & Operations Research, 106:280–288, 2019. ISSN 0305-0548. doi: 10.1016/j.cor.2018.02.007.

F. Arnold, M. Gendreau, and K. Sörensen. Efficiently solving very large-scale routing problems. Computers & Operations Research, 107:32–42, 2019. ISSN 0305-0548. doi: 10.1016/j.cor.2019.03.006.

L. Assunção and G. Mateus. A cutting-plane algorithm for the steiner team orienteering problem. Computers & Industrial Engineering, 135, 06 2019. doi: 10.1016/j.cie.2019.06.051.

B. Bernábe-Loranca, R. Gonzalez-Velázquez, E. Olivares-Benítez, J. Ruiz-Vanoye, and J. Martínez-Flores. Extensions to k-medoids with balance restrictions over the cardinality of the partitions. Journal of Applied Research and Technology, 12 (3):396–408, 2014. ISSN 1665-6423. doi: 10.1016/S1665-6423(14)71621-9.

N. Bianchessi, R. Mansini, and M. G. Speranza. A branch-and-cut algorithm for the team orienteering problem. International Transactions in Operational Research, 25(2):627–635, 2018. doi: 10.1111/itor.12422.

H. Bouly, DC. Dang, and A. Moukrim. A memetic algorithm for the team orienteering problem. In Applications of Evolutionary Computing, pages 649–658, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540-78761-7. doi: 10.1007/978-3-540-78761-7_71.

S. Boussier, D. Feillet, and M. Gendreau. An exact algorithm for team orienteering problems. 4OR quarterly journal of the Belgian, French and Italian Operations Research Societies, 5:211–230, 09 2007. doi: 10.1007/s10288-006-0009-1.

O. Bräysy and G. Hasle. Chapter 12: Software Tools and Emerging Technologies for Vehicle Routing and Intermodal Transportation, pages 351–380. 11 2014. ISBN 978-1-61197-358-7. doi: 10.1137/1.9781611973594.ch12.

I. Chao, B. L. Golden, and E. A. Wasil. The team orienteering problem. European Journal of Operational Research, 88(3): 464–474, 1996. ISSN 0377-2217.

J. Christiaens and G. Vanden Berghe. Slack induction by string removals for vehicle routing problems. Transportation Science, 54, 01 2020. doi: 10.1287/trsc.2019.0914.

G. Clarke and J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4):568–581, 1964. doi: 10.1287/opre.12.4.568.

D. Dang, R. Guibadj, and A. Moukrim. An effective pso-inspired algorithm for the team orienteering problem. European Journal of Operational Research, 229:332–344, 09 2013a. doi: 10.1016/j.ejor.2013.02.049.

DC. Dang, R.N. Guibadj, and A. Moukrim. A pso-based memetic algorithm for the team orienteering problem. In Applications of Evolutionary Computation, pages 471–480. Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-20520-0. doi: 10.1007/978-3-642-20520-0_48.

DC. Dang, R. El-Hajj, and A. Moukrim. A branch-and-cut algorithm for solving the team orienteering problem. 05 2013b. ISBN 978-3-642-38170-6. doi: 10.1007/978-3-642-38171-3_23.

E. Demir, T. Bektaş, and G. Laporte. An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223:346–359, 12 2012. doi: 10.1016/j.ejor.2012.06.044.

D. Dumez, F. Lehuédé, and O. Péton. A large neighborhood search approach to the vehicle routing problem with delivery options. Transportation Research Part B: Methodological, 144:103–132, 02 2021. doi: 10.1016/j.trb.2020.11.012.

R. El-Hajj, DC. Dang, and A. Moukrim. Solving the team orienteering problem with cutting planes. Computers & Operations Research, 74, 04 2016. doi: 10.1016/j.cor.2016.04.008.

J. Ferreira, A. Quintas, J. A. Oliveira, G. A. B. Pereira, and L. Dias. Solving the team orienteering problem: Developing a solution tool using a genetic algorithm approach. In Soft Computing in Industrial Applications, pages 365–375, Cham, 2014. Springer International Publishing. ISBN 978-3-319-00930-8. doi: 10.1007/978-3-319-00930-8_32.

M. Fischetti, Salazar G. J. J., and P. Toth. Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, 10:133–148, 05 1998. doi: 10.1287/ijoc.10.2.133.

D. Gavalas, C. Konstantopoulos, K. Mastakas, and G. Pantziou. A survey on algorithmic approaches for solving tourist trip design problems. Journal of Heuristics, 20:291–328, 06 2014. doi: 10.1007/s10732-014-9242-5.

B. Golden, L. Levy, and R. Vohra. The orienteering problem. Nav Res Logist, 34:307–318, 06 1987. doi: 10.1002/ 1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D.

F. Hammami, M. Rekik, and L. C. Coelho. A hybrid adaptive large neighborhood search heuristic for the team orienteering problem. Computers & Operations Research, 123:105034, 2020. ISSN 0305-0548. doi: 10.1016/j.cor.2020.105034.

L. Kaufman and P. J. Rousseeuw. Partitioning Around Medoids (Program PAM), chapter 2, pages 68–125. John Wiley & Sons, Ltd, 1990. ISBN 9780470316801. doi: 10.1002/9780470316801.ch2.

L. Ke, C. Archetti, and Z. Feng. Ants can solve the team orienteering problem. Computers & Industrial Engineering, 54: 648–665, 04 2008. doi: 10.1016/j.cie.2007.10.001.
L. Ke, L. Zhai, J. Li, and F. T.S. Chan. Pareto mimic algorithm: An approach to the team orienteering problem. Omega, 61: 155-166, 2016. ISSN 0305-0483. doi: 10.1016/j.omega.2015.08.003.

M. Keshtkaran, K. Ziarati, A. Bettinelli, and D. Vigo. Enhanced exact solution methods for the team orienteering problem. International Journal of Production Research, ahead-of-print:1–11, 07 2015. doi: 10.1080/00207543.2015.1058982.

BI. Kim, H. Li, and A. Johnson. An augmented large neighborhood search method for solving the team orienteering problem. Expert Systems with Applications, 40:3065-3072, 06 2013. doi: 10.1016/j.eswa.2012.12.022.

S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science (New York, N.Y.), 220:671-80, 06 1983. doi: 10.1126/science.220.4598.671.

G. Kobeaga, M. Merino, and J. Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers & Operations Research, 90, 09 2017. doi: 10.1016/j.cor.2017.09.003.

J. Kytöjoki, T. Nuortio, O. Bräysy, and M. Gendreau. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 34:2743-2757, 09 2007. doi: 10.1016/j.cor.2005.10.010.

G. Laporte and S. Martello. The selective travelling salesman problem. Discrete Applied Mathematics, 26(2):193-207, 1990. ISSN 0166-218X. doi: 10.1016/0166-218X(90)90100-Q.

SW. Lin. Solving the team orienteering problem using effective multi-start simulated annealing. Applied Soft Computing, 13: 1064-1073, 02 2013. doi: 10.1016/j.asoc.2012.09.022.

S.T. Windras Mara, R. Norcahyo, P. Jodiawan, L. Lusiantoro, and A. P. Rifai. A survey of adaptive large neighborhood search algorithms and applications. Computers & Operations Research, 146:105903, 2022. ISSN 0305-0548. doi: 10.1016/j.cor. 2022.105903.

R. Mariescu-Istodor. Solving the large-scale tsp problem in 1 h: Santa claus challenge 2020. Frontiers in Robotics and AI, 8, 10 2021. doi: 10.3389/frobt.2021.689908.

C. Orlis, N. Bianchessi, R. Roberti, and W. Dullaert. The team orienteering problem with overlaps: An application in cash logistics. Transportation Science, 54:470-487, 03 2020. doi: 10.1287/trsc.2019.0923.

A. Pessoa, R. Sadykov, E. Uchoa, and F. Vanderbeck. A Generic Exact Solver for Vehicle Routing and Related Problems, pages 354-369. 04 2019. ISBN 978-3-030-17952-6. doi: 10.1007/978-3-030-17953-3_27.

M. Poggi, H. Viana, and E. Uchoa. The team orienteering problem: Formulations and branch-cut and price. volume 14, pages 142-155, 01 2010. doi: 10.4230/OASIcs.ATMOS.2010.142.

S. Ropke and D. Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40:455-472, 11 2006. doi: 10.1287/trsc.1050.0135.

J. Ruiz-Meza and J. R. Montoya-Torres. A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines. Operations Research Perspectives, 9:100228, 2022. ISSN 2214-7160. doi: 10.1016/j. orp.2022.100228.

P. Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In Michael Maher and Jean-Francois Puget, editors, Principles and Practice of Constraint Programming — CP98, pages 417-431, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. ISBN 978-3-540-49481-2. doi: 10.1007/3-540-49481-2_30.

W. Souffriau, P. Vansteenwegen, and G. Vanden Berghe. A path relinking approach for the team orienteering problem. Computers & Operations Research, 37:1853-1859, 11 2010. doi: 10.1016/j.cor.2009.05.002.

É. Taillard and K. Helsgaun. Popmusic for the travelling salesman problem. European Journal of Operational Research, 272, 06 2018. doi: 10.1016/j.ejor.2018.06.039.

H. Tang and E. Miller-Hooks. A tabu search heuristic for the team orienteering problem. Computers & Operations Research, 32:1379-1407, 06 2005. doi: 10.1016/j.cor.2003.11.008.

P. Toth. and D. Vigo. The granular tabu search and its application to the vehicle-routing problem. INFORMS Journal on Computing, 15:333-346, 11 2003. doi: 10.1287/ijoc.15.4.333.24890

E. Tsakirakis, M. Marinaki, Y. Marinakis, and N. Matsatsinis. A similarity hybrid harmony search algorithm for the team orienteering problem. Applied Soft Computing, 80, 05 2019. doi: 10.1016/j.asoc.2019.04.038.

T. Tsiligiridis. Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35:797-809, 09 1984. doi: 10.1057/jors.1984.162.

R. Turkeš, K. Sörensen, and L. M. Hvattum. Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search. European Journal of Operational Research, 292(2):423-442, 2021. ISSN 0377-2217. doi: 10.1016/j.ejor.2020.10.045.

P. Vansteenwegen. The mobile tourist guide: An or opportunity. OR Insight, 20:21-27, 07 2007. doi: 10.1057/ori.2007.17.

P. Vansteenwegen, W. Souffriau, G. Vanden Berghe, and D. Van Oudheusden. A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research, 196(1):118-127, 2009a. ISSN 0377-2217. doi: 10.1016/j.ejor.2008.02.037.

P. Vansteenwegen, W. Souffriau, and G. Vanden Berghe. Metaheuristics for Tourist Trip Planning, volume 624, pages 15-31. 05 2009b. ISBN 978-3-642-00938-9. doi: 10.1007/978-3-642-00939-6_2.

T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins. A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234:658-673, 05 2014a. doi: 10.1016/j.ejor.2013.09.045.

T. Vidal, N. Maculan, P. Penna, and L. Ochi. Large neighborhoods with implicit customer selection for vehicle routing problems with profits. Transportation Science, 50, 01 2014b. doi: 10.1287/trsc.2015.0584.

E. Zachariadis and C. Kiranoudis. A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem. Computers & Operations Research, 37:2089-2105, 12 2010. doi: 10.1016/j.cor.2010.02.009.