11institutetext:  Institute for Computer Science, University of Hildesheim,
Hildesheim, Germany
11email<EMAIL_ADDRESS>
#  Learning to Control Local Search for Combinatorial Optimization

Jonas K. Falkner  Daniela Thyssens  Ahmad Bdeir  Lars Schmidt-Thieme

###### Abstract

Combinatorial optimization problems are encountered in many practical contexts
such as logistics and production, but exact solutions are particularly
difficult to find and usually NP-hard for considerable problem sizes. To
compute approximate solutions, a zoo of generic as well as problem-specific
variants of local search is commonly used. However, which variant to apply to
which particular problem is difficult to decide even for experts.

In this paper we identify three independent algorithmic aspects of such local
search algorithms and formalize their sequential selection over an
optimization process as Markov Decision Process (MDP). We design a deep graph
neural network as policy model for this MDP, yielding a learned controller for
local search called NeuroLS. Ample experimental evidence shows that NeuroLS is
able to outperform both, well-known general purpose local search controllers
from Operations Research as well as latest machine learning-based approaches.

###### Keywords:

combinatorial optimization local search neural networks.

##  1 Introduction

Combinatorial optimization problems (COPs) arise in many research areas and
applications. They appear in many forms and variants like vehicle routing[40],
scheduling[38] and constraint satisfaction[41] problems but share some general
properties. One of these properties is that most COPs are proven to be NP-hard
which makes their solution very complex and time consuming. Over the years
many different solution approaches were proposed. Exact methods like branch-
and-bound[23] attempt to find the global optimum of a COP based on smart and
efficient ways of searching the solution space. While they are often able to
find the optimal solution to small scale COPs in reasonable time, they require
a significant amount of time to tackle larger instances of sizes relevant for
practical applications. For that reason, heuristic methods were proposed which
usually cannot guarantee to find the global optimum but sometimes can define a
lower bound on the performance, which can be achieved at a minimum, and have
shown good empirical performance. One common and well-known heuristic method
is local search (LS)[1]. The main concept of LS is to iteratively explore the
search space of candidate solutions in the close neighborhood of the current
solution by applying small (local) changes. The simplest local search
procedure is employing a hill climbing routine which greedily applies local
changes that improve the current solution. However, this approach can easily
get stuck in bad local optima from which it cannot escape anymore. Therefore,
LS is commonly used in combination with meta-heuristics which enable the
procedure to escape from local optima and achieve better final performance.
The meta-heuristics introduced in section 2.2 are well established in the
optimization community and have demonstrated very good performance on a
plenitude of different COPs.

Since a few years however, there is an increasing interest in leveraging
methods from the growing field of machine learning (ML) to solve COPs, as
recent developments in neural network architectures, involving the
Transformer[44] and Graph Neural Networks (GNNs)[48], have led to significant
progress in this domain. Most work based on ML is concerned with auto-
regressive approaches to construct feasible solutions[45, 21, 17, 49], but
there is also some work which focuses on iterative improvement[6, 25, 47] or
exact solutions[10, 30] for COPs. While the existing iterative improvement
approaches share some similarities with meta-heuristics and local search, the
exact formulation of the methods is often problem specific and misses the
generality of the LS framework as well as a clear definition of the
intervention points which can be used to control the meta-heuristic procedure
for LS.

In this work we present a consistent formulation of learned meta-heuristics in
local search procedures and show on two representative problems how it can be
successfully applied. In our experiments we compare our method to well-known
meta-heuristics commonly used with LS at the example of capacitated vehicle
routing (CVRP) and job shop scheduling (JSSP). The results show that our GNN-
based learned meta-heuristic consistently outperforms these methods in terms
of speed and final performance. In further experiments we also establish our
method in the context of existing ML solution approaches.

Contributions

  1. 1.

We identify and describe three independent algorithmic aspects of local search
for combinatorial optimization, each with several alternatives, and formalize
their sequential selection during an iterative search run as Markov Decision
Process.

  2. 2.

We design a deep graph neural network as policy model for this MDP, yielding a
learned controller for local search called NeuroLS.

  3. 3.

We provide ample experimental evidence that NeuroLS outperforms both, well-
known general purpose local search controllers from the Operations Research
literature (so called meta-heuristics) as well as earlier machine learning-
based approaches.

##  2 Related Work

There is a plenitude of approaches and algorithms to tackle combinatorial
optimization problems. One common heuristic method is Local Search (LS)[1]. In
the classical discrete optimization literature it is often embedded into a
meta-heuristic procedure to escape local optima.

###  2.1 Construction Heuristics

Construction algorithms are concerned with finding a first feasible solution
for a given COP. They usually start with an empty solution and consecutively
assign values to the respective decision variables to construct a full
solution. Well-known methods are e.g. the Savings heuristic[7] for vehicle
routing problems or priority dispatching rules (PDR)[5] for scheduling. Most
improvement and meta-heuristic methods require a feasible initial solution
from which they can start to improve.

###  2.2 Meta-Heuristics

Meta-heuristics are the go-to method for complex discrete optimization
problems. They effectively balance the exploration of the solution space
(escaping local optima) and the exploitation of promising solutions. There are
two major types of methods:

Single Solution Methods Single solution methods include many well-known
approaches which are used in combination with LS. During the search they only
maintain a single solution at a time which is iteratively changed and adapted.
Simulated Annealing (SA) is a probabilistic acceptance strategy based on the
notion of controlled cooling of materials first proposed in [19]. The idea is
to also accept solutions which are worse than the best solution found so far
to enable exploration of the search space but with a decreasing probability to
increasingly focus on exploitation the further the search advances. Iterated
Local Search (ILS)[24] alternates between a diversification and an
intensification phase. In the diversification step the current solution is
perturbed while the alternating intensification step executes a greedy local
search with a particular neighborhood. Variable Neighborhood Search (VNS)[28]
employs a similar diversification step but focuses on a systematic control of
the LS neighborhood in the intensification phase, by changing the type of the
applied LS move frequently after each perturbation in a predefined order. Tabu
Search (TS) was proposed by Glover[12] and is based on the possible acceptance
of non-improving moves and a so called tabu list, a kind of filter preventing
moves which would keep the search stuck in local optima. This list acts as a
memory which in the simplest case stores the solutions of the last $k$
iterations and prevents changes which would move the current solution back to
solutions encountered in recent steps. Instead of using a tabu list, Guided
Local Search (GLS)[46] relies on penalties for different moves to guide the
search. These penalties are often based on problem specific features in the
solution, e.g. the edges between nodes in a routing problem, and are added to
the original objective function of the problem when the LS gets stuck.

Population-based Methods In comparison to single solution approaches
population-based methods maintain a whole pool of different solutions
throughout the search. Methods include different evolutionary algorithms,
particle swarm optimization and other bio-inspired algorithms such as ant
colony optimization [11]. Their main idea is based on different adaption,
selection and recombination schemes to refine the solution pool during search
in order to find better solutions.

While a learned population based meta-heuristic is interesting and potentially
promising, in this paper we focus on the impact and effectiveness of a learned
single solution approach. More information on advanced meta-heuristics and
their extensions can be found in [11].

###  2.3 Machine Learning based Methods

In recent years also many approaches employing ML methods have been proposed.
While some work [45, 18, 39] relies on supervised learning, most current
state-of-the-art methods use reinforcement learning (RL). A large fraction of
the work focuses on auto-regressive models which learn to sequentially
construct feasible solutions from scratch. Such methods have been proposed for
many common COPs including the TSP[3], CVRP[31, 21, 22], CVRP-TW[9] and
JSSP[49, 34, 15, 33]. The second type of methods is concerned with improvement
approaches. Chen et al.[6] design a model to rewrite sub-sequences of the
problem solution for the CVRP and JSSP based on a component which selects a
specific element of the solution and a second component parameterizing a
heuristic move to change that part of the solution. However, their model is
limited to specific problem settings with a fixed number of jobs and machines
or customers while our approach works seamlessly for different problem sizes,
as we show in the experiments in section 5.3. In contrast, the authors in [25]
learn a policy that selects a specific LS move at each iteration. However,
their method incurs prohibitively large computation times and for this reason
is not competitive with any of the recent related work [22, 20, 26]. The
authors in [16] learn a repair operator to re-construct heuristically
destroyed solutions in a Large Neighborhood Search. Finally, da Costa et
al.[32] learn a model to select node pairs for 2-opt moves in the TSP while Wu
et al.[47] learn a similar pair-wise selection scheme for 2-opt, node swap and
relocation moves in TSP and CVRP. The authors in [26] further improve on the
method in [47] by introducing the Dual-aspect collaborative Transformer (DACT)
model. Although there exist advanced inference approaches[15] to further
improve the performance of auto-regressive ML methods on COPs, here we focus
on the vanilla inference via greedy decoding or sampling.

While these methods share some similarities with our approach, they ignore the
importance of being able to reject unpromising moves to escape local optima,
whereas our approach specifically focuses on this important decision point to
effectively control the search. Moreover, our approach is also able to learn
when to apply a particular perturbation if the rejection of a sequence of
moves is not sufficient for exploration. A detailed overview of the current
machine learning approaches to COPs is given in [4, 27].

##  3 Preliminaries

###  3.1 Problem Formulation

A Combinatorial Optimization Problem $\Omega$ is defined on its domain
$D_{\Omega}$ which is the set of its instances $x\in D_{\Omega}$. A COP
instance $x$ is usually given by a pair ($S_{\Omega}$, $f_{\Omega}$) of the
solution space $S$ consisting of all feasible solutions to $\Omega$ and a
corresponding cost function $f:S\to\operatorname{\mathbb{R}}$. Combinatorial
optimization problems normally are either to be minimized or maximized. In
this paper we consider all COPs to be problems for which the cost of a
corresponding objective function has to be minimized. The main concern is to
find a solution $s^{*}\in S$ representing a global optimum, i.e. $f(s^{*})\leq
f(s)\ \forall s\in S$.

###  3.2 Local Search

LS is a heuristic search method which is based on the concept of
neighborhoods. A neighborhood $\mathcal{N}(s)\subseteq S$ of solution $s\in S$
represents a set of solutions which are somehow close to $s$. This “closeness”
is defined by the neighborhood function $\mathcal{N}^{\varphi}$ w.r.t. some
problem specific operator $\varphi\in\Phi_{\Omega}$ (e.g. an exchange of nodes
in a routing problem). Moreover, we always consider $s$ to be part of its own
neighborhood, i.e. $s\in\mathcal{N}(s)$. Then the local optimum $\hat{s}$ in
the neighborhood $\mathcal{N}$ satisfies $f(\hat{s})\leq f(s)\ \forall
s\in\mathcal{N}(\hat{s})$. A general LS procedure (see algorithm 1) iterates
through the neighborhood $\mathcal{N}(s)$ of the current solution $s$ until it
finds the local optimum $\hat{s}$.

input : cost function $f$, solution $s$, neighborhood function $\mathcal{N}$,

acceptance rule accept, stopping rule stop,

1 while  _not $\textnormal{{stop}}(s)$ _ do

2 find $s^{\prime}\in\mathcal{N}(s)$ for which
$\textnormal{{accept}}(s,s^{\prime})$

3 $s\leftarrow s^{\prime}$

return _s_

Algorithm 1 Local Search

###  3.3 Meta-Heuristics

Meta-heuristics wrap an LS procedure to enable it to escape from local optima
and to explore the solution space more efficiently. Some of the most common
meta-heuristic strategies were described in section 2.2. Algorithm 2 describes
a general formulation of a single solution meta-heuristic procedure. Each
particular strategy takes different decisions about restarting or perturbing
the current solution, configuring the local search and accepting intermediate
candidate solutions $s^{\prime}$ (see algorithm 1). Some decisions can be
fixed and are treated as hyper-parameters for some methods. For example, an SA
procedure normally does not select a specific neighborhood but just decides
about acceptance during the LS. Other approaches like VNS greedily accept all
improving moves but apply a perturbation and select a new operator
neighborhood every time a local optimum has been reached.

1

input : Solution space $S$, cost function $f$, stopping criterion

2

$s\leftarrow\textnormal{{construct}}(S)$

// Construct initial solution

3 while  _not stopping criterion_ do

$s\leftarrow\textnormal{{perturb}}(S,s)$

// Decide if to perturb/restart

$\mathcal{N}\leftarrow\textnormal{{GetNeighborhood}}(S,s)$

// Define search neighborhood

$s\leftarrow\textnormal{{LocalSearch}}(f,s,\mathcal{N},\textnormal{{accept}},\textnormal{{stop}})$

// Execute local search

4

return _s_

Algorithm 2 Meta-Heuristic (Single Solution)

##  4 Proposed Method

###  4.1 Intervention Points of Meta-Heuristics for Local Search

The application of meta-heuristic strategies to an underlying LS involves
several points of intervention, at which decisions can be done to help the
search escape local optima in order to guide it towards good solutions. In the
following, we define three such intervention points that have a significant
impact on the search:

  1. 1.

Acceptance: The first intervention point is the acceptance of candidate
solutions $s^{\prime}$ in a local search step (algorithm 1, line 2). A simple
hill climbing heuristic is completely greedy and only accepts improving moves,
which often leaves the search stuck in local optima very quickly. In contrast,
other approaches like SA will also accept non-improving moves with some
probability.

  2. 2.

Neighborhood: The second possible decision a meta-heuristic can make is the
selection of a particular operator $\varphi$ that defines the neighborhood
function $\mathcal{N}^{\varphi}$ for the LS (algorithm 2, line 4). Possible
operators for scheduling or routing problems could for example be a node
exchange. While many standard approaches like SA and ILS only use one
particular neighborhood which they treat as a hyper-parameter, VNS is an
example for a method that selects a different operator at each step.

  3. 3.

Perturbation: Many meta-heuristics like ILS and VNS employ perturbations
$\psi\in\Psi_{\Omega}$ to the current solution to move to different regions of
the search space and escape particularly persistent local optima. Such a
perturbation can simply be a restart from a new stochastically constructed
initial solution, a random permutation of (a part of) the current solution or
a random sequence of node exchanges. The decision when to employ such a
perturbation (algorithm 2, line 5) is usually done w.r.t. a specific pre-
defined number of steps without improvement.

###  4.2 Meta-Heuristics as Markov Decision Process

In this section we formulate meta-heuristics in terms of an MDP[37] to enable
the use of RL approaches to learn a parameterized policy to replace them. In
general an MDP is given by a tuple
$(\mathcal{S},\mathcal{A},\mathcal{P}(s_{t},a_{t}),\mathcal{R}(s_{t},a_{t}))$
representing the set of states $\mathcal{S}$, the set of actions
$\mathcal{A}$, a transition probability function $\mathcal{P}(s_{t},a_{t})$
and a reward function $\mathcal{R}(s_{t},a_{t})$. For our method we define
these entities in terms of meta-heuristic decisions as follows:

States We define the state $s_{t}$ of the problem at time step $t$ with slight
abuse of notation as the solution $s$ at time step $t$, combined with 1) its
cost $f(s)$, 2) the cost $f(\hat{s}_{t})$ of the best solution found so far,
3) the last acceptance decision, 4) the last operator used, 5) current time
step $t$, 6) number of LS steps without improvement and 7) the number of
perturbations or restarts.

Actions Depending on the policy we want to train, we define the action set as
the combinatorial space of

  1. 1.

Acceptance decisions: a boolean decision variable of either accepting or
rejecting the last LS step

$\mathcal{A}_{\text{A}}\coloneqq\\{0,1\\},$ (1)

  2. 2.

Acceptance-Neighborhood decisions: the joint space of the acceptance of the
last move and the set of possible operators $\varphi\in\Phi$ to apply in the
next step

$\mathcal{A}_{\text{AN}}\coloneqq\\{0,1\\}\times\Phi,$ (2)

  3. 3.

Acceptance-Neighborhood-Perturbation decisions: the joint space of acceptance
and the combined sets of operators $\varphi\in\Phi$ and perturbations
$\psi\in\Psi$

$\mathcal{A}_{\text{ANP}}\coloneqq\\{0,1\\}\times\\{\Phi\cup\Psi\\}.$ (3)

Transitions The transition probability function $\mathcal{P}(s_{t},a_{t})$
models the state transition from state $s_{t}$ to the next state $s_{t+1}$
depending on action $a_{t}$ representing the acceptance decision, the next
operator $\varphi$ and a possible perturbation or restart (part of the problem
state or action in case of $\mathcal{A}_{\text{ANP}}$).

Rewards The reward function $\mathcal{R}(s_{t},a_{t})$ defines the reward for
a transition from state $s_{t}$ to the next state $s_{t+1}$. Here we define
the reward $r_{t}$ of the transition as the relative improvement of the last
LS step (defined by action $a_{t}$) w.r.t. the cost of the best solution found
until $t$ and clamped at 0 to avoid negative rewards:

$r_{t}\coloneqq\max(f(\hat{s}_{t})-f(s_{t+1}),0)$ (4)

Policy We employ Deep Q-Learning[43] and parameterize the learned policy
$\pi_{\theta}$ via a softmax over the corresponding Q-function
$Q_{\theta}(s_{t},a_{t})$ which is represented in turn by our GNN-based
encoder-decoder model with trainable parameters $\theta$:

$\pi_{\theta}(a_{t}\mid
s_{t})=\frac{\exp(Q_{\theta}(s_{t},a_{t}))}{\sum_{\mathcal{A}}\exp(Q_{\theta}(s_{t},a_{t}))}.$
(5)

###  4.3 Model Architecture

In this section we describe our encoder and decoder models to parameterize
$Q_{\theta}(s_{t},a_{t})$. Many COPs like routing and scheduling problems have
an underlying graph structure which can be used when encoding these problems
and that provides an effective inductive bias for the corresponding learning
methods.

In general we assume a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with the
set of nodes $\mathcal{V}$, $N=|\mathcal{V}|$ and the set of directed edges
$\mathcal{E}\subseteq\\{(i,j)\subseteq\mathcal{V}\\}$. Moreover, we assume an
original node feature matrix $X\in\operatorname{\mathbb{R}}^{N\times
d_{\text{in}}}$ and edge features $e_{i,j}\in\operatorname{\mathbb{R}}$ for
each edge $(i,j)$. To leverage this structural information many authors have
used Recurrent Neural Networks (RNN)[45, 3, 6], Transformers[44, 21, 22, 26]
or Graph Neural Networks (GNN)[18, 32, 49].

Encoder
For our model we employ the 1-GNN operator of [29] which is able to work with
edge weights if they are present. One such layer is defined as

$\displaystyle h^{(l)}_{i}$
$\displaystyle=\operatorname{GNN}^{(l)}(h^{(l-1)}_{i})$
$\displaystyle=\sigma\big{(}\operatorname{MLP}^{(l)}_{1}(h^{(l-1)}_{i})+\operatorname{MLP}^{(l)}_{2}(\sum_{j\in\mathcal{H}(i)}e_{j,i}\cdot
h^{(l-1)}_{j})\big{)},$ (6)

where $h^{(l-1)}_{i}\in\operatorname{\mathbb{R}}^{1\times d_{\text{emb}}}$ is
the latent feature embedding of node $i$ at the previous layer $l-1$,
$\mathcal{H}(i)$ is the 1-hop graph neighborhood of node $i$,
$\operatorname{MLP}^{(l)}_{1}$ and $\operatorname{MLP}^{(l)}_{2}$ are Multi-
Layer Perceptrons
$\operatorname{MLP}:\operatorname{\mathbb{R}}^{d_{\text{emb}}}\to\operatorname{\mathbb{R}}^{d_{\text{emb}}}$
and $\sigma()$ is a suitable element-wise non-linearity, for which we use
GeLU[14]. Furthermore, we add residual connections and layer normalization[2]
to each layer.

In the first layer the latent feature vector $h^{(0)}_{i}$ is created by
feeding the original node features $x_{i}$ into an
$\operatorname{MLP}:\operatorname{\mathbb{R}}^{d_{\text{in}}}\to\operatorname{\mathbb{R}}^{d_{\text{emb}}}$:

$h^{(0)}_{i}=\operatorname{MLP}^{(0)}(x_{i}).$ (7)

and another
$\operatorname{MLP}^{(L)}:\operatorname{\mathbb{R}}^{d_{\text{emb}}}\to\operatorname{\mathbb{R}}^{d_{\text{emb}}}$
is placed at the end of the GNN stack.

Figure 1:  Visualization of the NeuroLS model architecture.

In order to further leverage structural information, we introduce 3 stages to
compute the latent embeddings. The first stage uses the edge set
$\mathcal{E}^{\text{stat}}$ of the static node neighborhood graph, e.g. the
$K$ nearest neighbors graph for the CVRP or the Directed Acyclic Graph (DAG)
representing the order of operations for each job in scheduling problems. This
edge set is fixed and does not change throughout the search. In contrast, the
second stage utilizes the edge set $\mathcal{E}^{\text{dyna}}$ representing
e.g. the tours in routing or the machine graph in scheduling, which is dynamic
and usually changes in every LS step. Our proposed network architecture
consists of $L^{\text{stat}}$ GNN layers for the static graph, followed by
$L^{\text{dyna}}$ layers which propagate over the dynamic graph. Finally, we
add another layer, again using the static edges, to consolidate the dynamic
information over the static graph, leading to a total of
$L=L^{\text{stat}}+L^{\text{dyna}}+1$ GNN layers.

The final stage serves to refine the embedding via aggregation based on the
dynamic information of group membership which is present in the solution. Each
node normally belongs to one of $K$ (not necessarily disjoint) groups
$\mathcal{M}_{k}$ of the solution, e.g. to a particular tour or machine.
Following this idea we pool the final embeddings $\omega^{\text{node}}_{i}$
from the GNN stack w.r.t. their membership and feed them through another MLP:

$\omega^{\text{grp}}_{k}=\operatorname{MLP}^{\text{grp}}\big{(}[\operatorname{MAX}(\omega^{\text{node}}_{i}\mid
i\in\mathcal{M}_{k});\operatorname{MEAN}(\omega^{\text{node}}_{i}\mid
i\in\mathcal{M}_{k})]\big{)},$ (8)

with max and mean pooling $\operatorname{\mathbb{R}}^{N\times
d_{\text{emb}}}\to\operatorname{\mathbb{R}}^{K\times d_{\text{emb}}},K<<N$
over the node dimension $N$, $\mathcal{M}_{k}$ as membership to the $k$-th
group ($k$-th tour, $k$-th machine, etc.) and $[\ ;]$ representing
concatenation in the embedding dimension $d_{\text{emb}}$.

Finally, the additional features of the state representation (current cost,
best cost, last acceptance, etc.) described in the last section, are
concatenated and projected by a simple linear layer to create an additional
latent feature vector
$\omega^{\text{feat}}\in\operatorname{\mathbb{R}}^{d_{\text{emb}}}$.

Decoder
Our decoder takes the different embeddings created in the encoder, aggregates
the node embeddings $\omega^{\text{node}}\in\operatorname{\mathbb{R}}^{N\times
d_{\text{emb}}}$ and group embeddings
$\omega^{\text{grp}}\in\operatorname{\mathbb{R}}^{K\times d_{\text{emb}}}$ via
a simple mean over the node and group dimension and concatenates them with the
feature embedding
$\omega^{\text{feat}}\in\operatorname{\mathbb{R}}^{d_{\text{emb}}}$. This
representation is the input to a final 2-layer MLP regression head
$\operatorname{\mathbb{R}}^{3*d_{\text{emb}}}\to\operatorname{\mathbb{R}}^{|\mathcal{A}|}$
which outputs the value predictions of the Q-function. The full architecture
is shown in figure 1.

###  4.4 Reinforcement Learning Algorithm

To train our policy model we employ Double Deep Q-Learning[43] with $n$-step
returns[37] and Implicit Quantile Networks (IQN)[8]. IQNs enable a
distributional formulation of Q-Learning where the Deep Q-Network is trained
w.r.t. an underlying value distribution represented by a learned quantile
function instead of single point estimates. In order to represent this learned
quantile function IQNs are introduced as a small additional neural network
which is jointly trained to transform samples from a base distribution (e.g.
uniform) to the respective quantile values of the target distribution, i.e.
the distribution over the returns. Further details can be found in appendix A.

##  5 Experiments

###  5.1 Applications

Job Shop Scheduling Problem (JSSP) The JSSP is concerned with scheduling a
number of jobs $J$ on a set of $K$ machines denoted by $M$. Each job consists
of a sequence of operations $O_{ij}$ with fixed processing times $p_{ij}$
which need to be processed in a predefined order. In the simplest problem
variant every job has exactly one operation on each machine. A solution to the
problem consists of the exact order of the operations on all machines. In this
paper we choose to minimize the makespan, which is the longest time span from
start of the first operation until the end of the last one to finish,
corresponding to the longest path in the respective DAG representation of the
problem. In the following we denote the size of a JSSP instances as
$|J|\times|M|$. We follow [49] in creating instances for training and
validation by sampling processing times from a uniform distribution.

Capacitated Vehicle Routing Problem (CVRP) The CVRP consists of a set of $N$
customer nodes and a depot node. It is concerned with serving the demands
$q_{i}$ of the customer nodes in tours starting and ending at the depot node
by employing $K$ homogeneous vehicles with a fixed capacity $Q>0$. The tour of
vehicle $k\in K$ is a sequence of indices w.r.t. a subset of all customers
nodes representing the order in which vehicle $k$ visits the respective nodes.
A set of feasible tours serving all customer nodes represents a solution to
the problem, whereas the objective is to minimize the total length of all
tours. We follow [21] in creating the training and validation sets by
generating instances with coordinates uniformly sampled in the unit square.

###  5.2 Setup

For the JSSP we implement a custom LS solver in python. It implements four
different node moves and a perturbation operator based on a sequence of such
moves. As construction heuristic and for restarts we implement several
stochastic variants of common PDRs (see appendix C for more details). The LS
for the CVRP uses the C++ based open source solver VRPH[13] for which we
implement a custom wrapper and interface to expose and support the necessary
intervention points. VRPH includes several different LS moves and perturbation
operators including 2-opt, 3-opt and different exchange and point moves. We
provide our model code and that of our JSSP solver in our github
repository111https://github.com/jokofa/NeuroLS.

Preliminary experiments showed that the CET and 2-opt moves performed best for
the JSSP and CVRP respectively, when used for meta-heuristics which do not
select the operator. Thus, we employ these operators in our main experiments.
We train all our models for 80 epochs with 19200 transitions each and pick the
model checkpoint with the best validation performance.

Hyperparameters for NeuroLS and all meta-heuristics are tuned on a validation
set consisting of 512 generated random instances. This is in contrast to most
classical approaches which fine tune their hyper-parameters directly on the
benchmark dataset. We argue that our approach facilitates a better and more
objective comparison between these methods. Furthermore, we fix the random
seed for all experiments.

We train 3 different types of policies for NeuroLS, one for each of the action
spaces described in section 4.2. In the experiments we denote these policies
as NLS${}_{\text{A}}$, NLS${}_{\text{AN}}$ and NLS${}_{\text{ANP}}$. As
analyzed in [47], random solutions do not provide a good starting point for
improvement approaches. For that reason we initialize the solutions of NeuroLS
and the meta-heuristics with the FDD/MWKR PDR[36] for scheduling and the well
known savings construction heuristic[7] for the CVRP. Further details on
training and hyper-parameters can be found in Appendix B.

###  5.3 Results

Table 1:  Results of state-of-the-art machine learning based construction methods and local search approaches (100 iterations) on the Taillard benchmark[38]. For instances of size 50x15, 50x20 and 100x20 we use the NeuroLS model trained on instances of size 30x15 and 30x20 respectively. Percentages are the average gap to the best known upper bound. Best gap is marked in bold.  Model | Instance size | Avg
---|---|---
| 15x15 | 20x15 | 20x20 | 30x15 | 30x20 | 50x15 | 50x20 | 100x20 |
ML-based
L2D[49] | 25.92% | 30.03% | 31.58% | 32.88% | 33.64% | 22.35% | 26.37% | 13.64% | 27.05%
L2S[34] | 20.12% | 24.83% | 29.25% | 24.59% | 31.91% | 15.89% | 21.39% | 9.26% | 22.16%
SN[33] | 15.32% | 19.43% | 17.23% | 18.95% | 23.75% | 13.83% | 13.56% | 6.67% | 16.09%
Meta-heuristic + Local Search
SA | 13.92% | 17.01% | 17.16% | 17.53% | 21.59% | 12.50% | 13.11% | 6.61% | 14.93%
SA${}_{\text{restart}}$ | 13.77% | 17.01% | 17.57% | 17.62% | 21.78% | 12.54% | 13.22% | 6.75% | 15.03%
ILS | 11.57% | 13.57% | 13.85% | 16.07% | 18.72% | 12.65% | 12.15% | 6.72% | 13.16%
ILS+SA | 13.32% | 16.05% | 15.38% | 16.93% | 19.74% | 13.07% | 13.43% | 7.08% | 14.37%
VNS | 9.96% | 13.71% | 14.51% | 15.77% | 18.69% | 11.64% | 11.92% | 6.26% | 12.81%
NeuroLS
NLS${}_{\text{A}}$ |  9.76% | 13.33% | 13.02% | 15.29% | 17.94% | 11.81% | 11.96% | 6.33% | 12.43%
NLS${}_{\text{AN}}$ | 10.32% |  13.18% |  12.95% |  14.91% | 17.78% | 11.87% | 12.02% | 6.22% |  12.41%
NLS${}_{\text{ANP}}$ | 10.49% | 16.32% | 15.24% | 15.35% |  17.64% |  11.62% |  11.76% |  6.09% | 13.06%
Table 2:  Results of state-of-the-art machine learning based methods and local search approaches (200 iterations) on the Uchoa benchmark[42]. For all instances sizes we use the NeuroLS model trained on instances of size 100. Percentages are the average gap to the best known solution. Best gap is marked in bold.  Model | Instance Group | Avg
---|---|---
| n100 | n150 | n200 | n250 |
| cost | time | cost | time | cost | time | cost | time |
ML-based
POMO[22] | 17.24% | 0.3 | 12.81% | 0.4 | 20.52% | 0.4 | 15.14% | 0.4 | 16.43%
POMO[22] (aug) | 6.32% | 0.1 | 9.41% | 0.1 | 13.47% | 0.1 | 9.21% | 0.1 | 9.60%
DACT[26] | 13.19% | 15.1 | 20.26% | 21.2 | 16.91% | 27.2 | 24.93% | 33 | 18.82%
DACT[26] (aug) | 11.52% | 16.6 | 17.75% | 23.1 | 15.34% | 29.8 | 21.86% | 37.8 | 16.62%
Meta-heuristic + Local Search
ORT[35] GLS | 6.91% | 9.4 | 10.46% | 10.9 |  7.80% | 13.4 | 12.12% | 5.0 | 9.32%
ORT[35] TS | 6.78% | 39.0 | 10.55% | 109.5 | 7.85% | 126.6 | 12.13% | 7.0 | 9.33%
SA | 6.92% | 0.7 | 5.79% | 1.3 | 16.63% | 2.1 | 5.92% | 3.3 | 8.81%
SA${}_{\text{restart}}$ | 6.96% | 0.7 | 5.79% | 1.3 | 16.67% | 2.0 | 5.99% | 3.0 | 8.85%
ILS | 6.56% | 0.8 | 5.96% | 1.5 | 16.73% | 2.4 | 6.08% | 3.7 | 8.83%
ILS+SA | 6.94% | 0.6 | 6.01% | 1.2 | 16.72% | 1.9 | 6.04% | 2.8 | 8.93%
VNS | 7.99% | 0.4 | 6.55% | 0.7 | 17.27% | 0.9 | 6.36% | 1.4 | 9.54%
NeuroLS
NLS${}_{\text{A}}$ | 5.43% | 1.5 | 5.23% | 2.4 | 15.97% | 3.6 | 5.22% | 5.3 | 7.96%
NLS${}_{\text{AN}}$ |  5.42% | 1.7 |  4.90% | 2.7 | 15.85% | 4.0 |  5.08% | 5.9 |  7.81%
NLS${}_{\text{ANP}}$ |  5.42% | 1.7 |  4.90% | 2.7 | 15.85% | 4.0 |  5.08% | 6.1 |  7.81%

JSSP We evaluate all methods on the well-known benchmark dataset of
Taillard[38]. It consists of 80 instances of size 15x15 up to 100x20. We
compare our model against common meta-heuristic baselines including SA, SA
with restarts, ILS, ILS with SA acceptance and VNS. Moreover, we report the
results of three recent state-of-the-art ML-based approaches: Learning to
dispatch (L2D)[49], Learning to schedule (L2S)[34] and ScheduleNet (SN)[33].
We follow [49] in training different models for problem sizes 15x15 up to
30x20 and apply the 30x15 and 30x20 model to larger instances of size 50x15,
50x20 and 100x20 to evaluate its generalization capacity. All models are
trained for 100 LS iterations but evaluated for 50-200. The aggregated results
per group of same size are shown in table 1 (results per instance can be found
in appendix E). Results are reported as percentage gaps to the best known
solution.

First of all, the results show that NeuroLS is able to outperform all other
meta-heuristics on all sizes of instances. The different policies differ in
how well they work for different problem sizes. While NLS${}_{\text{A}}$ works
best for the smallest 15x15 instances, it is outperformed by
NLS${}_{\text{AN}}$ on medium sized instances and NLS${}_{\text{ANP}}$
achieves the best results for large instances. This is to some extent
expected, since the effect of specific LS operators and more precise
perturbations is greater for larger instances while this does not seem to be
necessary for rather small instances. VNS is the best of the meta-heuristic
approaches which is able to beat NLS${}_{\text{ANP}}$ on the smaller instances
and NLS${}_{\text{A}}$ and NLS${}_{\text{AN}}$ at least on some of the larger
ones.

In general, the iterative methods based on LS achieve much better results than
the ML-based auto-regressive methods, which can be seen by the large
improvements that can be achieved in just 100 iterations, reducing the gap by
an average of 3.7% compared to the best ML-method SN[33].

CVRP For the CVRP we use the recent benchmark dataset of Uchoa et al.[42] and
select all instance up to 300 customer nodes. We define four groups of
instances with 100-149 nodes as n100, 150-199 nodes as n150, 200-249 as n200
and 250-299 as n250. We compare against the same meta-heuristics mentioned
above and additionally to GLS and TS provided by the OR-Tools (ORT)
library[35]. Furthermore, we compare to the recent state-of-the-art ML
approaches POMO[22] and DACT[26] which outperformed all other ML methods
mentioned in section 2.3 in their experiments and provide open source code,
which is why we consider them to be sufficient for a suitable comparison.

Since most ML-based methods (POMO, DACT, etc.) do not respect the maximum
vehicle constraint for all instances of the Uchoa benchmark, we follow[26] in
removing this constraint and treat the benchmark dataset as a highly diverse
test set w.r.t. the distributions of customers and number of required
vehicles. This is also consistent with the general goal of the ML-based
methods, which is not to achieve the best known results but to find
sufficiently good results in reasonable time. In this case we control the
computational resources spent on the search by specifying a particular number
of iterations for the search. Furthermore, we evaluate all models with a batch
size of 1.

The results presented in table 2 show that NeuroLS is also able to outperform
the meta-heuristic approaches mentioned above on all instance groups.
Moreover, our approach also outperforms the best state-of-the-art ML-based
methods on all groups but n200, where [22] and [26] with additional instance
augmentations (aug) outperform NeuroLS by a small margin. The OR-Tools
implementation of GLS and TS outperforms our method only on the n200
instances, although they require prohibitively large runtimes (wall-clock
time) several magnitudes larger than our approach. In terms of runtimes we
also outperform DACT[26] by a magnitude, while the learned auto-regressive
construction method POMO[22] is the fastest over all.

Finally, the experiment results also show that our method is well able to
generalize to problem sizes as well as numbers of iterations unseen in
training. We show this on the JSSP instances of size 50x15, 50x20 and 100x20
and basically on all Uchoa instances for the CVRP, which are larger than the
100 node instances used during training.

##  6 Conclusion

In this paper we identify three important intervention points in meta-
heuristics for LS on COPs and incorporate them in a Markov Decision Process.
We then design a GNN-based controller model which is trained with RL to
parameterize three different types of learned meta-heuristics. The resulting
methods learn to control the local search by deciding about acceptance,
neighborhood selection and perturbations. In comprehensive experiments on two
common COPs in scheduling and vehicle routing, NeuroLS outperforms several
well-known meta-heuristics as well as state-of-the-art ML-based approaches,
confirming the efficacy of our method.

For future work we consider to replace the problem graph representation with a
graph representation of the corresponding local search graph, in which every
node represents a feasible solution together with its respective cost. A
Curriculum learning strategy (cp. [26]) could also yield further improvements
regarding performance and generalization.

## References

  * [1] Aarts, E., Aarts, E.H., Lenstra, J.K.: Local search in combinatorial optimization. Princeton University Press (2003)
  * [2] Ba, J.L., Kiros, J.R., Hinton, G.E.: Layer normalization. arXiv preprint arXiv:1607.06450 (2016)
  * [3] Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940 (2016)
  * [4] Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research 290(2), 405–421 (2021)
  * [5] Blackstone, J.H., Phillips, D.T., Hogg, G.L.: A state-of-the-art survey of dispatching rules for manufacturing job shop operations. The International Journal of Production Research 20(1), 27–45 (1982)
  * [6] Chen, X., Tian, Y.: Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems 32 (2019)
  * [7] Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Operations research 12(4), 568–581 (1964)
  * [8] Dabney, W., Ostrovski, G., Silver, D., Munos, R.: Implicit quantile networks for distributional reinforcement learning. In: International conference on machine learning. pp. 1096–1105. PMLR (2018)
  * [9] Falkner, J.K., Schmidt-Thieme, L.: Learning to solve vehicle routing problems with time windows through joint attention. arXiv preprint arXiv:2006.09100 (2020)
  * [10] Gasse, M., Chételat, D., Ferroni, N., Charlin, L., Lodi, A.: Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems 32 (2019)
  * [11] Gendreau, M., Potvin, J.Y., et al.: Handbook of metaheuristics, vol. 2. Springer (2010)
  * [12] Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers & operations research 13(5), 533–549 (1986)
  * [13] Groër, C., Golden, B., Wasil, E.: A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation 2(2), 79–101 (2010)
  * [14] Hendrycks, D., Gimpel, K.: Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415 (2016)
  * [15] Hottung, A., Kwon, Y.D., Tierney, K.: Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.05126 (2021)
  * [16] Hottung, A., Tierney, K.: Neural large neighborhood search for the capacitated vehicle routing problem. arXiv preprint arXiv:1911.09539 (2019)
  * [17] Hu, H., Zhang, X., Yan, X., Wang, L., Xu, Y.: Solving a new 3d bin packing problem with deep reinforcement learning method. arXiv preprint arXiv:1708.05930 (2017)
  * [18] Joshi, C.K., Laurent, T., Bresson, X.: An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227 (2019)
  * [19] Kirkpatrick, S., Gelatt Jr, C.D., Vecchi, M.P.: Optimization by simulated annealing. science 220(4598), 671–680 (1983)
  * [20] Kool, W., van Hoof, H., Gromicho, J., Welling, M.: Deep policy dynamic programming for vehicle routing problems. arXiv preprint arXiv:2102.11756 (2021)
  * [21] Kool, W., Van Hoof, H., Welling, M.: Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475 (2018)
  * [22] Kwon, Y.D., Choo, J., Kim, B., Yoon, I., Gwon, Y., Min, S.: Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems 33, 21188–21198 (2020)
  * [23] Lawler, E.L., Wood, D.E.: Branch-and-bound methods: A survey. Operations research 14(4), 699–719 (1966)
  * [24] Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search: Framework and applications. In: Handbook of metaheuristics, pp. 129–168. Springer (2019)
  * [25] Lu, H., Zhang, X., Yang, S.: A learning-based iterative method for solving vehicle routing problems. In: International conference on learning representations (2019)
  * [26] Ma, Y., Li, J., Cao, Z., Song, W., Zhang, L., Chen, Z., Tang, J.: Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems 34 (2021)
  * [27] Mazyavkina, N., Sviridov, S., Ivanov, S., Burnaev, E.: Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research 134, 105400 (2021)
  * [28] Mladenović, N., Hansen, P.: Variable neighborhood search. Computers & operations research 24(11), 1097–1100 (1997)
  * [29] Morris, C., Ritzert, M., Fey, M., Hamilton, W.L., Lenssen, J.E., Rattan, G., Grohe, M.: Weisfeiler and leman go neural: Higher-order graph neural networks. In: Proceedings of the AAAI conference on artificial intelligence. vol. 33, pp. 4602–4609 (2019)
  * [30] Nair, V., Bartunov, S., Gimeno, F., von Glehn, I., Lichocki, P., Lobov, I., O’Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., et al.: Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 (2020)
  * [31] Nazari, M., Oroojlooy, A., Snyder, L., Takác, M.: Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems 31 (2018)
  * [32] d O Costa, P.R., Rhuggenaath, J., Zhang, Y., Akcay, A.: Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In: Asian Conference on Machine Learning. pp. 465–480. PMLR (2020)
  * [33] Park, J., Bakhtiyar, S., Park, J.: Schedulenet: Learn to solve multi-agent scheduling problems with reinforcement learning. arXiv preprint arXiv:2106.03051 (2021)
  * [34] Park, J., Chun, J., Kim, S.H., Kim, Y., Park, J.: Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research 59(11), 3360–3377 (2021)
  * [35] Perron, L., Furnon, V.: Or-tools, https://developers.google.com/optimization/
  * [36] Sels, V., Gheysen, N., Vanhoucke, M.: A comparison of priority rules for the job shop scheduling problem under different flow time-and tardiness-related objective functions. International Journal of Production Research 50(15), 4255–4270 (2012)
  * [37] Sutton, R.S., Barto, A.G.: Reinforcement learning: An introduction. MIT press (2018)
  * [38] Taillard, E.: Benchmarks for basic scheduling problems. european journal of operational research 64(2), 278–285 (1993)
  * [39] Thyssens, D., Falkner, J., Schmidt-Thieme, L.: Supervised permutation invariant networks for solving the cvrp with bounded fleet size. arXiv preprint arXiv:2201.01529 (2022)
  * [40] Toth, P., Vigo, D.: The vehicle routing problem. SIAM (2002)
  * [41] Tsang, E.: Foundations of constraint satisfaction: the classic text. BoD–Books on Demand (2014)
  * [42] Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., Subramanian, A.: New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research 257(3), 845–858 (2017)
  * [43] Van Hasselt, H., Guez, A., Silver, D.: Deep reinforcement learning with double q-learning. In: Proceedings of the AAAI conference on artificial intelligence. vol. 30 (2016)
  * [44] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Advances in neural information processing systems 30 (2017)
  * [45] Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks. Advances in neural information processing systems 28 (2015)
  * [46] Voudouris, C., Tsang, E.P., Alsheddy, A.: Guided local search. In: Handbook of metaheuristics, pp. 321–361. Springer (2010)
  * [47] Wu, Y., Song, W., Cao, Z., Zhang, J., Lim, A.: Learning improvement heuristics for solving routing problems.. IEEE Transactions on Neural Networks and Learning Systems (2021)
  * [48] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Philip, S.Y.: A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems 32(1), 4–24 (2020)
  * [49] Zhang, C., Song, W., Cao, Z., Zhang, J., Tan, P.S., Chi, X.: Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in Neural Information Processing Systems 33, 1621–1632 (2020)

## Appendices

###  A Reinforcement Learning Algorithm

Let $\pi$ be a policy, then the discounted sum of future rewards is given by
the random variable

$Z^{\pi}(s,a)=\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t})$ (9)

with $s_{t}\sim P(s_{t-1},a_{t+1})$. Then the action-value function
$Q(s,a)=\mathbb{E}[Z^{\pi}(s,a)]$ can be written in terms of the Bellman
equation as

$Q^{\pi}(s_{t},a_{t})=\mathbb{E}[R(s_{t},a_{t})]+\gamma\mathbb{E}[Q^{\pi}(s_{t+1},a_{t+1})].$
(10)

Furthermore, the real action-value function can be approximated by a
parameterized value estimator $Q_{\theta}(s,a)$ which is trained via
minimization of the squared error of the temporal difference defined as

$\text{TDE}=\left[r_{t}+\gamma\max_{a^{\prime}\in\mathcal{A}}Q_{\theta}(s_{t+1},a^{\prime})-Q_{\theta}(s_{t},a_{t})\right]^{2}$
(11)

based on an $\epsilon$-greedy policy.

Distributional RL[2] aims to replace the scalar value function $Q^{\pi}$ with
a distribution over the returns $Z^{\pi}$. For the distributional case there
exist analogous formulations for the Bellman equation and the corresponding
distributional Bellman optimality operator. Implicit Quantile Networks[3] are
used to transform random samples from a base distribution to the respective
quantile values of a target distribution, in this case the distribution over
the returns. It is formulated as a risk-sensitive greedy policy (w.r.t. a
distortion measure $\beta$) represented by a weighted sum over the quantiles:

$\pi_{\beta}(s)=\operatorname*{argmax}_{a\in\mathcal{A}}Q_{\beta}(s,a).$ (12)

Then, assuming two samples $x,x^{\prime}\sim\mathcal{U}([0,1])$, the
respective TD error is defined as

$\text{TDE}_{x,x^{\prime}}=r_{t}+\gamma
Z_{x^{\prime}}(s_{t+1},\pi_{\beta}(s_{t+1}))-Z_{x}(s_{t},a_{t})$ (13)

and the corresponding loss is estimated over multiple i.i.d. samples
$x_{i},x^{\prime}_{j}\sim\mathcal{U}([0,1])$.

###  B Training and Inference Setup

For training we use the Adam optimizer[4] with a learning rate of 0.0005. We
use $\epsilon=0.95$ for our $\epsilon$-greedy policy which we discount over
the course of training to a final value of $\epsilon=0.05$. During inference
we set $\epsilon=0.0$. Moreover, we use $n$-step returns with $n=3$ and a
discount factor $\gamma=0.99$. The target network of our DQN is updated ever
500 steps. We use a replay buffer of size 32000 and prioritized experience
replay[15] with $\alpha=0.6$ and $\beta=0.4$.

All MLPs in our model have a hidden dimension of 128 and we set the embedding
dimension of all components to $d_{\text{emb}}=128$. The IQN has a hidden
dimension of 256. In the GNN encoder we use $L^{\text{stat}}=3$ and
$L^{\text{dyna}}=2$ layers.

We train all our models for 80 epochs with 19200 transitions each. All
experiments are run on an i7-7700K CPU (4.20GHz) and a NVIDIA GeForce 1080TI
GPU.

Moreover, all our networks as well as the ML-based baselines are implemented
in PyTorch[13] and we use the tianshou library[22] for an efficient RL
implementation.

The meta-heuristics use different hyper-parameter configurations which where
tuned on the validation set consisting of 512 generated instances. The exact
configurations for all methods can be found in the configuration files in our
github repository.

###  C JSSP Solver

To solve the JSSP we implement a local search solver in python. We implement
several different swap and insertion heuristics to provide a suitable number
of LS operators and corresponding neighborhoods. The first one is the CT
operator proposed by [21] which tries to swap adjacent nodes in critical
blocks. Next, we have the CET[10] and ECET[5] moves which respectively either
swap only nodes at the start or the end of a critical block or both
simultaneously. The final implemented operator is the CEI move introduced by
[1], which shifts a node in a critical block to a new position within the same
block. [5] provide a nice visualization and explanation of how all these
operators work.

In order to quickly evaluate how good some moves are, without applying them
and completely recalculating the resulting makespan, we use the potential
estimation strategies by [19] and [9] which are computed in $O(m)$ where $m$
is the number of nodes between the initial and the final position of the moved
nodes. Finally, our perturbation operator is a sequence of random CT moves
without any evaluation of potentials, somehow similar to the shaking operator
in [17]. The initial solution for our iterative solver is created by the
FDD/MWKR priority dispatching rule introduced in [16], which we implement as a
stochastic variant for restarting as proposed in [7]. We will provide the
implementation of our solver together with our model code.

###  D Additional Results

We provide more detailed results for different methods and several different
numbers of iterations in table 3 for the JSSP and table 4 for the CVRP.

Table 3:  Results of PDRs and local search methods running for 50/100/200 iterations on the Taillard benchmark. For instance sizes 50x15, 50x20 and 100x20 we use the NeuroLS model trained on instances of size 30x15 and 30x20 respectively. Percentages are the gap to the best known upper bound. Best gap is marked in bold.  Model | Instance size | Avg
---|---|---
| 15x15 | 20x15 | 20x20 | 30x15 | 30x20 | 50x15 | 50x20 | 100x20 |
PDRs |
RND | 28.90% | 36.81% | 31.71% | 34.97% | 36.30% | 22.86% | 28.05% | 16.47% | 29.51%
FIFO | 23.92% | 31.50% | 27.42% | 31.20% | 32.14% | 21.15% | 23.62% | 13.06% | 25.50%
SPT | 27.14% | 32.92% | 25.30% | 34.54% | 34.59% | 23.81% | 24.96% | 15.39% | 27.33%
MWKR | 18.72% | 23.94% | 21.52% | 23.91% | 24.97% | 16.76% | 17.54% | 8.33% | 19.46%
MOPNR | 20.54% | 23.99% | 21.60% | 22.44% | 25.10% | 17.32% | 17.96% | 9.24% | 19.77%
FDD | 22.56% | 24.79% | 22.10% | 23.40% | 27.37% | 17.48% | 18.11% | 8.14% | 20.49%
$\frac{\text{FDD}}{\text{MWKR}}$ | 17.50% | 21.30% | 20.11% | 21.39% | 24.01% | 15.55% | 15.95% | 7.75% | 17.95%
Local Search |
50 iterations |
SA | 14.61% | 18.54% | 18.87% | 18.65% | 22.80% | 13.63% | 14.24% | 7.13% | 16.06%
SA${}_{\text{restart}}$ | 14.61% | 18.54% | 18.87% | 18.65% | 22.90% | 13.63% | 14.24% | 7.15% | 16.08%
ILS | 13.03% | 15.52% | 15.14% | 16.76% | 19.67% | 13.01% | 13.18% | 7.00% | 14.16%
ILS+SA | 13.59% | 16.77% | 16.48% | 17.35% | 20.03% | 13.36% | 13.66% | 7.12% | 14.79%
VNS | 11.78% | 14.78% | 15.67% | 16.91% | 19.69% | 12.64% | 12.94% | 6.71% | 13.89%
NLS${}_{\text{A}}$ |  11.03% | 14.98% | 14.78% |  16.04% |  18.96% | 12.84% | 12.89% | 6.66% |  13.52%
NLS${}_{\text{AN}}$ | 11.27% |  14.66% |  14.46% | 16.27% | 19.27% | 12.76% | 12.79% | 6.82% | 13.54%
NLS${}_{\text{ANP}}$ | 11.67% | 16.80% | 18.60% | 16.05% | 19.39% |  12.11% |  12.47% |  6.61% | 14.21%
100 iterations |
SA | 13.92% | 17.01% | 17.16% | 17.53% | 21.59% | 12.50% | 13.11% | 6.61% | 14.93%
SA${}_{\text{restart}}$ | 13.77% | 17.01% | 17.57% | 17.62% | 21.78% | 12.54% | 13.22% | 6.75% | 15.03%
ILS | 11.57% | 13.57% | 13.85% | 16.07% | 18.72% | 12.65% | 12.15% | 6.72% | 13.16%
ILS+SA | 13.32% | 16.05% | 15.38% | 16.93% | 19.74% | 13.07% | 13.43% | 7.08% | 14.37%
VNS | 9.96% | 13.71% | 14.51% | 15.77% | 18.69% | 11.64% | 11.92% | 6.26% | 12.81%
NLS${}_{\text{A}}$ |  9.76% | 13.33% | 13.02% | 15.29% | 17.94% | 11.81% | 11.96% | 6.33% | 12.43%
NLS${}_{\text{AN}}$ | 10.32% |  13.18% |  12.95% |  14.91% | 17.78% | 11.87% | 12.02% | 6.22% |  12.41%
NLS${}_{\text{ANP}}$ | 10.49% | 16.32% | 15.24% | 15.35% |  17.64% |  11.62% |  11.76% |  6.09% | 13.06%
200 iterations |
SA | 13.12% | 15.92% | 15.58% | 15.73% | 20.02% | 11.35% | 12.22% | 6.01% | 13.74%
SA${}_{\text{restart}}$ | 13.56% | 16.25% | 16.80% | 16.83% | 21.25% | 11.62% | 12.60% | 6.12% | 14.38%
ILS | 9.55% | 12.49% | 12.39% | 15.28% | 17.51% | 11.82% | 11.51% | 6.42% | 12.12%
ILS+SA | 12.50% | 14.83% | 14.70% | 16.41% | 18.75% | 12.81% | 12.60% | 6.88% | 13.69%
VNS | 9.04% | 13.07% | 12.69% | 14.65% | 17.81% | 10.88% | 11.48% |  5.65% | 11.91%
NLS${}_{\text{A}}$ |  7.74% | 12.16% |  11.54% | 14.13% | 16.35% | 11.01% | 11.25% | 5.90% |  11.26%
NLS${}_{\text{AN}}$ | 8.74% |  11.39% | 11.64% | 14.10% | 16.53% | 10.95% | 11.18% | 5.84% | 11.29%
NLS${}_{\text{ANP}}$ | 10.44% | 16.29% | 13.83% |  13.61% |  16.06% |  10.62% |  10.88% | 5.73% | 12.18%
ML-based |
L2D[23] | 25.92% | 30.03% | 31.58% | 32.88% | 33.64% | 22.35% | 26.37% | 13.64% | 27.05%
L2S[11] | 20.12% | 24.83% | 29.25% | 24.59% | 31.91% | 15.89% | 21.39% | 9.26% | 22.16%
SN[12] | 15.32% | 19.43% | 17.23% | 18.95% | 23.75% | 13.83% | 13.56% | 6.67% | 16.09%
Table 4:  Results of state-of-the-art machine learning based methods and local search approaches (200/500/1000 iterations) on the Uchoa benchmark[20]. For all instances sizes we use the NeuroLS model trained on instances of size 100. Percentages are the average gap to the best known upper bound. Best gap is marked in bold.  Model | Instance Group | Avg
---|---|---
| n100 | n150 | n200 | n250 |
| cost | time | cost | time | cost | time | cost | time |
constructive
POMO[6] (single) | 23.49% | 0.3 | 15.65% | 0.4 | 25.86% | 0.4 | 22.93% | 0.4 | 21.98%
POMO[6] | 17.24% | 0.3 | 12.81% | 0.4 | 20.52% | 0.4 | 15.14% | 0.4 | 16.43%
POMO[6] (aug) | 6.32% | 0.1 | 9.41% | 0.1 | 13.47% | 0.1 | 9.21% | 0.1 | 9.60%
iterative (200)
ORT[14] GLS | 6.91% | 9.4 | 10.46% | 10.9 |  7.80% | 13.4 | 12.12% | 5.0 | 9.32%
ORT[14] TS | 6.78% | 39.0 | 10.55% | 109.5 | 7.85% | 126.6 | 12.13% | 7.0 | 9.33%
SA | 6.92% | 0.7 | 5.79% | 1.3 | 16.63% | 2.1 | 5.92% | 3.3 | 8.81%
SA${}_{\text{restart}}$ | 6.96% | 0.7 | 5.79% | 1.3 | 16.67% | 2.0 | 5.99% | 3.0 | 8.85%
ILS | 6.56% | 0.8 | 5.96% | 1.5 | 16.73% | 2.4 | 6.08% | 3.7 | 8.83%
ILS+SA | 6.94% | 0.6 | 6.01% | 1.2 | 16.72% | 1.9 | 6.04% | 2.8 | 8.93%
VNS | 7.99% | 0.4 | 6.55% | 0.7 | 17.27% | 0.9 | 6.36% | 1.4 | 9.54%
DACT[8] | 13.19% | 15.1 | 20.26% | 21.2 | 16.91% | 27.2 | 24.93% | 33 | 18.82%
DACT[8] (aug) | 11.52% | 16.6 | 17.75% | 23.1 | 15.34% | 29.8 | 21.86% | 37.8 | 16.62%
NLS${}_{\text{A}}$ | 5.43% | 1.5 | 5.23% | 2.4 | 15.97% | 3.6 | 5.22% | 5.3 | 7.96%
NLS${}_{\text{AN}}$ |  5.42% | 1.7 |  4.90% | 2.7 | 15.85% | 4.0 |  5.08% | 5.9 |  7.81%
NLS${}_{\text{ANP}}$ |  5.42% | 1.7 |  4.90% | 2.7 | 15.85% | 4.0 |  5.08% | 6.1 |  7.81%
iterative (500)
ORT[14] GLS | 5.69% | 39.6 | 7.91% | 64.9 |  5.06% | 83 | 8.66% | 88.7 | 6.83%
ORT[14] TS | 5.33% | 525.8 | 7.44% | 1267.1 | 5.16% | 1021.3 | 8.54% | 633.4 |  6.62%
SA | 6.92% | 1.7 | 5.79% | 3.1 | 16.63% | 4.7 | 5.92% | 7.4 | 8.81%
SA${}_{\text{restart}}$ | 6.91% | 1.7 | 5.79% | 3.1 | 16.67% | 4.7 | 5.99% | 6.9 | 8.84%
ILS | 6.22% | 2.0 | 5.70% | 3.8 | 16.66% | 6.2 | 6.08% | 9.2 | 8.67%
ILS+SA | 6.78% | 1.6 | 5.66% | 2.8 | 16.72% | 4.4 | 6.04% | 6.5 | 8.80%
VNS | 7.99% | 1.1 | 6.08% | 1.8 | 17.27% | 2.4 | 6.36% | 3.5 | 9.42%
DACT[8] | 11.09% | 37.5 | 16.95% | 53.3 | 16.70% | 67.5 | 23.02% | 84.8 | 16.94%
DACT[8] (aug) | 10.55% | 42.2 | 15.02% | 59.1 | 14.76% | 76.0 | 20.85% | 94.0 | 15.29%
NLS${}_{\text{A}}$ | 5.04% | 3.3 | 4.56% | 5.6 | 15.61% | 8.5 | 4.87% | 13.0 | 7.52%
NLS${}_{\text{AN}}$ |  4.80% | 3.9 |  4.30% | 6.4 | 15.70% | 9.6 |  4.78% | 14.4 |  7.40%
NLS${}_{\text{ANP}}$ |  4.80% | 3.8 |  4.30% | 6.5 | 15.70% | 9.6 |  4.78% | 14.4 |  7.40%
iterative (1000)
ORT[14] GLS | 4.84% | 96.3 | 6.89% | 160.4 |  4.16% | 235.7 | 6.91% | 290.4 |  5.70%
ORT[14] TS |  4.17% | 899.9 | 5.70% | 2945.4 | 4.30% | 2752.1 | 9.76% | 2752.1 | 5.98%
SA | 6.92% | 3.2 | 5.79% | 5.9 | 16.63% | 9.0 | 5.92% | 13.6 | 8.81%
SA${}_{\text{restart}}$ | 6.91% | 3.2 | 5.79% | 5.8 | 16.67% | 8.9 | 5.99% | 13.3 | 8.84%
ILS | 5.73% | 4.0 | 5.51% | 7.6 | 16.66% | 12.0 | 6.08% | 18.4 | 8.50%
ILS+SA | 6.78% | 3.2 | 5.66% | 5.7 | 16.72% | 8.8 | 6.04% | 13.0 | 8.80%
VNS | 7.71% | 2.1 | 6.08% | 3.7 | 17.27% | 4.8 | 6.36% | 7.1 | 9.35%
DACT[8] | 10.24% | 79.6 | 15.32% | 110.7 | 15.34% | 138.1 | 21.59% | 171.1 | 15.62%
DACT[8] (aug) | 10.06% | 82.9 | 14.19% | 114.5 | 14.07% | 148.2 | 20.21% | 188.0 | 14.63%
NLS${}_{\text{A}}$ |  4.33% | 6.5 | 4.12% | 11.0 | 15.37% | 16.7 | 4.60% | 25.2 | 7.10%
NLS${}_{\text{AN}}$ | 4.40% | 8.6 |  3.89% | 14.3 | 15.42% | 21.6 |  4.48% | 32.4 |  7.05%
NLS${}_{\text{ANP}}$ | 4.40% | 7.5 |  3.89% | 12.5 | 15.42% | 18.9 |  4.48% | 28.5 |  7.05%

###  E Detailed Benchmark Results

In this last section we give the per instance results on the Taillard and
Uchoa benchmark datasets for different methods and different number of
iterations.

Table 5: Detailed Results on the Taillard benchmark[18]. Instance |  | BKS | PDRs
---|---|---|---
|  |  | RND | FIFO | SPT | MWKR | MOPNR | FDD | $\frac{\text{FDD}}{\text{MWKR}}$
15x15 |
ta01 | cost | 1231 | 1655 | 1486 | 1462 | 1491 | 1438 | 1439 | 1417
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta02 | cost | 1244 | 1682 | 1486 | 1450 | 1449 | 1452 | 1447 | 1413
| time |  | 0.04 | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta03 | cost | 1218 | 1596 | 1461 | 1526 | 1426 | 1418 | 1618 | 1423
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta04 | cost | 1175 | 1478 | 1575 | 1730 | 1382 | 1457 | 1453 | 1442
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta05 | cost | 1224 | 1672 | 1457 | 1618 | 1494 | 1448 | 1532 | 1431
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta06 | cost | 1238 | 1463 | 1528 | 1522 | 1369 | 1486 | 1453 | 1398
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta07 | cost | 1227 | 1650 | 1497 | 1434 | 1470 | 1456 | 1543 | 1368
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta08 | cost | 1217 | 1467 | 1496 | 1563 | 1491 | 1482 | 1425 | 1429
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta09 | cost | 1274 | 1605 | 1642 | 1622 | 1541 | 1594 | 1627 | 1603
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
ta10 | cost | 1241 | 1572 | 1600 | 1697 | 1476 | 1582 | 1524 | 1516
| time |  | 0.04 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03 | 0.03
20x15 |
ta11 | cost | 1357 | 1748 | 1701 | 1865 | 1685 | 1665 | 1766 | 1663
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta12 | cost | 1367 | 1957 | 1810 | 1667 | 1692 | 1739 | 1631 | 1712
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta13 | cost | 1342 | 1715 | 1882 | 1843 | 1690 | 1642 | 1619 | 1644
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta14 | cost | 1345 | 1746 | 1795 | 1635 | 1563 | 1662 | 1687 | 1553
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta15 | cost | 1339 | 1927 | 1788 | 1835 | 1700 | 1682 | 1659 | 1674
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta16 | cost | 1360 | 1911 | 1696 | 1965 | 1584 | 1638 | 1681 | 1608
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta17 | cost | 1462 | 2141 | 1899 | 2059 | 1851 | 1856 | 1950 | 1816
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta18 | cost | 1396 | 1872 | 1833 | 1770 | 1751 | 1710 | 1721 | 1684
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta19 | cost | 1332 | 1777 | 1716 | 1789 | 1696 | 1651 | 1659 | 1590
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
ta20 | cost | 1348 | 1878 | 1827 | 1713 | 1703 | 1677 | 1658 | 1611
| time |  | 0.05 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04 | 0.04
Table 6: Detailed Results on the Taillard benchmark[18]. Instance |  | BKS | PDRs
---|---|---|---
|  |  | RND | FIFO | SPT | MWKR | MOPNR | FDD | $\frac{\text{FDD}}{\text{MWKR}}$
20x20 |
ta21 | cost | 1642 | 2075 | 2089 | 2175 | 2044 | 1964 | 1962 | 1930
| time |  | 0.07 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.05
ta22 | cost | 1600 | 1985 | 2146 | 1893 | 1914 | 1905 | 1921 | 1928
| time |  | 0.07 | 0.06 | 0.06 | 0.05 | 0.05 | 0.06 | 0.06
ta23 | cost | 1557 | 2194 | 2010 | 1990 | 1954 | 1922 | 1945 | 1833
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.05 | 0.06 | 0.06
ta24 | cost | 1644 | 2092 | 1989 | 2073 | 1982 | 1918 | 1903 | 1946
| time |  | 0.07 | 0.06 | 0.06 | 0.06 | 0.06 | 0.05 | 0.06
ta25 | cost | 1595 | 2172 | 2160 | 1950 | 1905 | 1912 | 1959 | 1901
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.05 | 0.06 | 0.06
ta26 | cost | 1643 | 2231 | 2182 | 1955 | 1967 | 2018 | 1958 | 1997
| time |  | 0.07 | 0.06 | 0.06 | 0.06 | 0.08 | 0.06 | 0.05
ta27 | cost | 1680 | 2094 | 2112 | 2096 | 2091 | 2160 | 2080 | 2140
| time |  | 0.07 | 0.06 | 0.06 | 0.06 | 0.07 | 0.06 | 0.06
ta28 | cost | 1603 | 2420 | 1980 | 1968 | 1997 | 1952 | 2032 | 1875
| time |  | 0.07 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06
ta29 | cost | 1625 | 2112 | 1999 | 2166 | 1860 | 1899 | 2081 | 1948
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06
ta30 | cost | 1584 | 1926 | 1941 | 1999 | 1939 | 2017 | 1906 | 1927
| time |  | 0.08 | 0.05 | 0.07 | 0.06 | 0.06 | 0.05 | 0.06
30x15 |
ta31 | cost | 1764 | 2207 | 2277 | 2335 | 2134 | 2143 | 2240 | 2116
| time |  | 0.08 | 0.06 | 0.06 | 0.07 | 0.06 | 0.06 | 0.06
ta32 | cost | 1784 | 2411 | 2322 | 2432 | 2211 | 2188 | 2308 | 2273
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.06 | 0.08 | 0.06
ta33 | cost | 1791 | 2527 | 2481 | 2428 | 2349 | 2308 | 2340 | 2278
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.07 | 0.06 | 0.07
ta34 | cost | 1829 | 2635 | 2507 | 2534 | 2245 | 2187 | 2158 | 2168
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.07 | 0.07 | 0.06
ta35 | cost | 2007 | 2612 | 2478 | 2497 | 2226 | 2255 | 2195 | 2225
| time |  | 0.08 | 0.06 | 0.07 | 0.06 | 0.07 | 0.06 | 0.08
ta36 | cost | 1819 | 2379 | 2393 | 2364 | 2365 | 2307 | 2236 | 2186
| time |  | 0.1 | 0.06 | 0.07 | 0.06 | 0.07 | 0.07 | 0.06
ta37 | cost | 1771 | 2393 | 2254 | 2664 | 2151 | 2190 | 2233 | 2232
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06
ta38 | cost | 1673 | 2344 | 2355 | 2201 | 2076 | 2179 | 2163 | 1991
| time |  | 0.08 | 0.06 | 0.07 | 0.06 | 0.07 | 0.06 | 0.06
ta39 | cost | 1795 | 2494 | 2352 | 2465 | 2220 | 2135 | 2189 | 2154
| time |  | 0.08 | 0.06 | 0.06 | 0.06 | 0.07 | 0.07 | 0.06
ta40 | cost | 1669 | 2160 | 2069 | 2166 | 2205 | 2028 | 2029 | 2109
| time |  | 0.08 | 0.07 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06
Table 7: Detailed Results on the Taillard benchmark[18]. Instance |  | BKS | PDRs
---|---|---|---
|  |  | RND | FIFO | SPT | MWKR | MOPNR | FDD | $\frac{\text{FDD}}{\text{MWKR}}$
30x20 |
ta41 | cost | 2005 | 2863 | 2556 | 2463 | 2620 | 2538 | 2445 | 2537
| time |  | 0.11 | 0.08 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09
ta42 | cost | 1937 | 2664 | 2648 | 2773 | 2424 | 2448 | 2567 | 2388
| time |  | 0.11 | 0.08 | 0.09 | 0.08 | 0.08 | 0.09 | 0.09
ta43 | cost | 1846 | 2468 | 2442 | 2412 | 2348 | 2425 | 2269 | 2354
| time |  | 0.11 | 0.09 | 0.09 | 0.08 | 0.09 | 0.09 | 0.09
ta44 | cost | 1979 | 2622 | 2687 | 2906 | 2493 | 2419 | 2402 | 2423
| time |  | 0.11 | 0.08 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09
ta45 | cost | 2000 | 2577 | 2607 | 2734 | 2524 | 2522 | 2511 | 2450
| time |  | 0.11 | 0.09 | 0.08 | 0.09 | 0.09 | 0.09 | 0.09
ta46 | cost | 2004 | 2778 | 2606 | 2650 | 2447 | 2498 | 2646 | 2525
| time |  | 0.11 | 0.09 | 0.08 | 0.08 | 0.08 | 0.09 | 0.09
ta47 | cost | 1889 | 2682 | 2471 | 2531 | 2282 | 2286 | 2660 | 2400
| time |  | 0.11 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09
ta48 | cost | 1941 | 2630 | 2606 | 2620 | 2356 | 2371 | 2420 | 2280
| time |  | 0.11 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09
ta49 | cost | 1961 | 2602 | 2604 | 2652 | 2382 | 2399 | 2492 | 2431
| time |  | 0.12 | 0.08 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09
ta50 | cost | 1923 | 2673 | 2520 | 2483 | 2474 | 2469 | 2406 | 2376
| time |  | 0.11 | 0.08 | 0.09 | 0.09 | 0.09 | 0.09 | 0.09
50x15 |
ta51 | cost | 2760 | 3518 | 3705 | 3856 | 3435 | 3567 | 3263 | 3486
| time |  | 0.14 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11
ta52 | cost | 2756 | 3429 | 3368 | 3266 | 3394 | 3278 | 3332 | 3276
| time |  | 0.14 | 0.11 | 0.11 | 0.11 | 0.1 | 0.1 | 0.11
ta53 | cost | 2717 | 3296 | 3199 | 3273 | 3090 | 3115 | 3188 | 3059
| time |  | 0.15 | 0.1 | 0.1 | 0.1 | 0.1 | 0.11 | 0.11
ta54 | cost | 2839 | 3498 | 3221 | 3167 | 3294 | 3265 | 3223 | 3053
| time |  | 0.17 | 0.1 | 0.1 | 0.1 | 0.11 | 0.11 | 0.11
ta55 | cost | 2679 | 3367 | 3267 | 3289 | 3198 | 3279 | 3174 | 3103
| time |  | 0.16 | 0.1 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11
ta56 | cost | 2781 | 3385 | 3326 | 3554 | 3134 | 3100 | 3293 | 3302
| time |  | 0.14 | 0.1 | 0.11 | 0.1 | 0.11 | 0.11 | 0.11
ta57 | cost | 2943 | 3444 | 3654 | 3745 | 3261 | 3335 | 3420 | 3298
| time |  | 0.14 | 0.11 | 0.11 | 0.11 | 0.11 | 0.11 | 0.12
ta58 | cost | 2885 | 3481 | 3370 | 3459 | 3380 | 3420 | 3382 | 3311
| time |  | 0.14 | 0.11 | 0.11 | 0.11 | 0.1 | 0.11 | 0.12
ta59 | cost | 2655 | 3352 | 3357 | 3341 | 3080 | 3139 | 3121 | 3156
| time |  | 0.14 | 0.1 | 0.1 | 0.1 | 0.1 | 0.11 | 0.11
ta60 | cost | 2723 | 3309 | 3137 | 3393 | 3122 | 3044 | 3191 | 3006
| time |  | 0.15 | 0.1 | 0.11 | 0.11 | 0.1 | 0.11 | 0.11
Table 8: Detailed Results on the Taillard benchmark[18]. Instance |  | BKS | PDRs
---|---|---|---
|  |  | RND | FIFO | SPT | MWKR | MOPNR | FDD | $\frac{\text{FDD}}{\text{MWKR}}$
50x20 |
ta61 | cost | 2868 | 3523 | 3690 | 3587 | 3343 | 3329 | 3303 | 3366
| time |  | 0.22 | 0.15 | 0.15 | 0.15 | 0.16 | 0.15 | 0.15
ta62 | cost | 2869 | 3810 | 3672 | 3487 | 3423 | 3417 | 3415 | 3437
| time |  | 0.2 | 0.15 | 0.17 | 0.15 | 0.16 | 0.15 | 0.16
ta63 | cost | 2755 | 3408 | 3320 | 3277 | 3233 | 3226 | 3247 | 3139
| time |  | 0.19 | 0.16 | 0.15 | 0.15 | 0.16 | 0.15 | 0.15
ta64 | cost | 2702 | 3547 | 3161 | 3627 | 3173 | 3118 | 3138 | 3122
| time |  | 0.19 | 0.16 | 0.16 | 0.16 | 0.16 | 0.15 | 0.15
ta65 | cost | 2725 | 3559 | 3263 | 3313 | 3429 | 3287 | 3267 | 3298
| time |  | 0.2 | 0.15 | 0.15 | 0.15 | 0.15 | 0.16 | 0.15
ta66 | cost | 2845 | 3589 | 3594 | 3595 | 3287 | 3366 | 3309 | 3324
| time |  | 0.2 | 0.15 | 0.16 | 0.15 | 0.15 | 0.22 | 0.16
ta67 | cost | 2825 | 3779 | 3612 | 3401 | 3305 | 3411 | 3374 | 3251
| time |  | 0.22 | 0.17 | 0.15 | 0.15 | 0.15 | 0.16 | 0.16
ta68 | cost | 2784 | 3626 | 3380 | 3440 | 3203 | 3276 | 3380 | 3157
| time |  | 0.2 | 0.15 | 0.16 | 0.16 | 0.15 | 0.15 | 0.16
ta69 | cost | 3071 | 3653 | 3675 | 3811 | 3550 | 3526 | 3655 | 3530
| time |  | 0.21 | 0.16 | 0.16 | 0.15 | 0.15 | 0.16 | 0.15
ta70 | cost | 2995 | 3922 | 3790 | 3998 | 3482 | 3590 | 3500 | 3352
| time |  | 0.2 | 0.17 | 0.15 | 0.16 | 0.15 | 0.15 | 0.15
100x20 |
ta71 | cost | 5464 | 6436 | 6203 | 6377 | 5979 | 5938 | 6102 | 5863
| time |  | 0.42 | 0.33 | 0.33 | 0.32 | 0.31 | 0.32 | 0.32
ta72 | cost | 5181 | 6002 | 5672 | 6080 | 5583 | 5639 | 5543 | 5539
| time |  | 0.43 | 0.36 | 0.35 | 0.32 | 0.32 | 0.31 | 0.32
ta73 | cost | 5568 | 6605 | 6302 | 6371 | 6047 | 6161 | 6098 | 6233
| time |  | 0.41 | 0.36 | 0.33 | 0.33 | 0.31 | 0.34 | 0.32
ta74 | cost | 5339 | 6026 | 5903 | 6283 | 5669 | 5634 | 5727 | 5628
| time |  | 0.43 | 0.33 | 0.32 | 0.34 | 0.32 | 0.32 | 0.32
ta75 | cost | 5392 | 6801 | 6361 | 6208 | 5997 | 6212 | 6122 | 6062
| time |  | 0.42 | 0.33 | 0.36 | 0.33 | 0.32 | 0.33 | 0.32
ta76 | cost | 5342 | 6096 | 6213 | 6583 | 5902 | 5936 | 5799 | 5851
| time |  | 0.44 | 0.34 | 0.33 | 0.33 | 0.32 | 0.33 | 0.32
ta77 | cost | 5436 | 5972 | 5836 | 5915 | 5905 | 5829 | 5706 | 5736
| time |  | 0.42 | 0.32 | 0.31 | 0.32 | 0.31 | 0.31 | 0.32
ta78 | cost | 5394 | 6280 | 6331 | 6156 | 5738 | 5895 | 5793 | 5762
| time |  | 0.44 | 0.32 | 0.33 | 0.32 | 0.32 | 0.34 | 0.32
ta79 | cost | 5358 | 6186 | 6006 | 6029 | 5743 | 5652 | 5598 | 5667
| time |  | 0.44 | 0.35 | 0.33 | 0.32 | 0.32 | 0.33 | 0.32
ta80 | cost | 5183 | 6088 | 5839 | 5912 | 5565 | 5720 | 5538 | 5476
| time |  | 0.44 | 0.33 | 0.32 | 0.31 | 0.31 | 0.31 | 0.33

Table 9: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
15x15 |  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
ta01 | cost | 1378 | 1378 | 1378 | 1378 | 1378 | 1378 | 1365 | 1352 | 1352 | 1365 | 1365 | 1365 | 1361 | 1361 | 1361 | 1346 | 1346 | 1320 | 1359 | 1339 | 1331 | 1365 | 1365 | 1350
| time | 0.39 | 0.78 | 1.57 | 0.39 | 0.81 | 1.66 | 0.43 | 0.87 | 1.88 | 0.42 | 0.78 | 1.5 | 1 | 2.18 | 4.74 | 0.88 | 1.62 | 2.96 | 1.03 | 1.89 | 4.01 | 1.07 | 1.94 | 3.75
ta02 | cost | 1387 | 1387 | 1386 | 1387 | 1387 | 1387 | 1376 | 1351 | 1332 | 1376 | 1376 | 1376 | 1361 | 1326 | 1326 | 1333 | 1311 | 1311 | 1369 | 1369 | 1326 | 1369 | 1369 | 1369
| time | 0.43 | 0.79 | 1.58 | 0.4 | 0.82 | 1.64 | 0.47 | 0.97 | 1.93 | 0.43 | 0.9 | 1.77 | 0.96 | 2.02 | 4.51 | 0.87 | 1.56 | 3.07 | 1.02 | 1.92 | 3.67 | 1.04 | 1.94 | 3.85
ta03 | cost | 1391 | 1391 | 1383 | 1391 | 1391 | 1391 | 1333 | 1332 | 1321 | 1353 | 1333 | 1333 | 1373 | 1330 | 1330 | 1334 | 1333 | 1318 | 1333 | 1333 | 1333 | 1353 | 1339 | 1339
| time | 0.46 | 0.78 | 1.59 | 0.4 | 0.82 | 1.88 | 0.43 | 0.95 | 1.96 | 0.35 | 0.82 | 1.72 | 1.01 | 2.11 | 4.63 | 0.84 | 1.57 | 3.09 | 0.96 | 1.86 | 3.94 | 1.01 | 1.87 | 3.69
ta04 | cost | 1426 | 1426 | 1393 | 1426 | 1412 | 1405 | 1396 | 1396 | 1349 | 1416 | 1416 | 1396 | 1371 | 1350 | 1343 | 1377 | 1347 | 1287 | 1364 | 1354 | 1321 | 1364 | 1364 | 1358
| time | 0.42 | 0.79 | 1.66 | 0.43 | 0.82 | 1.64 | 0.43 | 0.88 | 1.86 | 0.39 | 0.8 | 1.51 | 0.93 | 1.99 | 4.74 | 0.86 | 1.55 | 2.94 | 1.04 | 1.92 | 3.75 | 1.08 | 2.11 | 3.76
ta05 | cost | 1364 | 1360 | 1345 | 1364 | 1360 | 1360 | 1364 | 1322 | 1292 | 1379 | 1370 | 1356 | 1333 | 1330 | 1329 | 1356 | 1334 | 1323 | 1356 | 1328 | 1292 | 1356 | 1328 | 1328
| time | 0.4 | 0.79 | 1.6 | 0.4 | 0.8 | 1.65 | 0.42 | 0.9 | 1.88 | 0.35 | 0.71 | 1.55 | 0.93 | 2.09 | 4.9 | 0.94 | 1.57 | 3 | 1.04 | 1.89 | 3.62 | 1.07 | 1.94 | 3.74
ta06 | cost | 1392 | 1368 | 1329 | 1392 | 1368 | 1365 | 1363 | 1363 | 1330 | 1370 | 1370 | 1363 | 1355 | 1355 | 1329 | 1345 | 1335 | 1311 | 1362 | 1349 | 1326 | 1355 | 1328 | 1361
| time | 0.39 | 0.78 | 1.66 | 0.39 | 0.8 | 1.64 | 0.42 | 0.85 | 1.82 | 0.38 | 0.72 | 1.46 | 1.09 | 2.19 | 4.68 | 0.86 | 1.53 | 2.97 | 1.03 | 1.92 | 3.8 | 0.99 | 1.83 | 3.84
ta07 | cost | 1315 | 1315 | 1315 | 1315 | 1315 | 1315 | 1309 | 1294 | 1284 | 1310 | 1309 | 1294 | 1315 | 1315 | 1304 | 1294 | 1294 | 1270 | 1309 | 1309 | 1309 | 1294 | 1294 | 1294
| time | 0.38 | 0.78 | 1.61 | 0.38 | 0.82 | 1.63 | 0.4 | 0.83 | 1.75 | 0.36 | 0.73 | 1.47 | 1.16 | 2.19 | 4.6 | 0.84 | 1.56 | 2.95 | 1.02 | 1.86 | 3.77 | 1.01 | 1.92 | 3.7
ta08 | cost | 1384 | 1381 | 1380 | 1384 | 1381 | 1379 | 1395 | 1387 | 1342 | 1395 | 1395 | 1395 | 1366 | 1350 | 1350 | 1337 | 1333 | 1305 | 1332 | 1310 | 1295 | 1332 | 1332 | 1324
| time | 0.38 | 0.79 | 1.6 | 0.4 | 0.79 | 1.59 | 0.47 | 1.01 | 2.03 | 0.43 | 0.88 | 1.77 | 1.01 | 2.12 | 4.79 | 0.91 | 1.97 | 3.09 | 0.96 | 1.84 | 3.6 | 0.99 | 1.87 | 4.02
ta09 | cost | 1587 | 1533 | 1533 | 1587 | 1533 | 1533 | 1531 | 1531 | 1487 | 1534 | 1531 | 1531 | 1478 | 1458 | 1390 | 1500 | 1492 | 1461 | 1492 | 1492 | 1461 | 1540 | 1493 | 1484
| time | 0.39 | 0.79 | 1.58 | 0.4 | 0.84 | 1.61 | 0.46 | 0.96 | 2.03 | 0.43 | 0.86 | 1.79 | 0.93 | 2.08 | 4.69 | 0.86 | 1.52 | 2.9 | 0.97 | 2.02 | 3.64 | 1.02 | 1.95 | 4.22
ta10 | cost | 1461 | 1461 | 1459 | 1461 | 1456 | 1442 | 1458 | 1383 | 1373 | 1461 | 1461 | 1416 | 1424 | 1338 | 1338 | 1422 | 1364 | 1334 | 1398 | 1374 | 1369 | 1395 | 1366 | 1365
| time | 0.38 | 0.78 | 1.58 | 0.38 | 0.81 | 1.63 | 0.46 | 0.98 | 1.88 | 0.42 | 0.88 | 1.81 | 1.01 | 2.03 | 4.49 | 0.93 | 1.61 | 3.07 | 1.02 | 1.9 | 3.68 | 1.02 | 1.82 | 3.68
Table 10: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
20x15 |  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
ta11 | cost | 1615 | 1615 | 1579 | 1615 | 1615 | 1615 | 1601 | 1579 | 1556 | 1611 | 1609 | 1579 | 1611 | 1579 | 1553 | 1575 | 1555 | 1555 | 1579 | 1568 | 1549 | 1608 | 1611 | 1611
| time | 0.55 | 1 | 2.12 | 0.51 | 1.09 | 2.23 | 0.66 | 1.28 | 2.68 | 0.6 | 1.17 | 2.47 | 1.42 | 2.86 | 5.97 | 1.38 | 2.08 | 4.44 | 1.16 | 2.26 | 5.08 | 1.31 | 3.21 | 6.79
ta12 | cost | 1642 | 1642 | 1611 | 1642 | 1642 | 1597 | 1571 | 1507 | 1485 | 1575 | 1571 | 1571 | 1594 | 1532 | 1509 | 1537 | 1512 | 1510 | 1542 | 1523 | 1472 | 1594 | 1594 | 1573
| time | 0.49 | 1.01 | 2.12 | 0.51 | 1.07 | 2.24 | 0.52 | 1.07 | 2.29 | 0.47 | 0.95 | 2.05 | 1.3 | 2.66 | 5.72 | 0.97 | 2.11 | 4.35 | 1.12 | 2.29 | 4.5 | 1.31 | 3.08 | 7.32
ta13 | cost | 1605 | 1556 | 1556 | 1605 | 1556 | 1556 | 1559 | 1548 | 1532 | 1564 | 1559 | 1558 | 1559 | 1559 | 1539 | 1541 | 1539 | 1496 | 1559 | 1541 | 1530 | 1556 | 1559 | 1559
| time | 0.53 | 1.03 | 2.14 | 0.55 | 1.03 | 2.23 | 0.52 | 1.14 | 2.42 | 0.47 | 0.96 | 2.17 | 1.24 | 2.87 | 6.01 | 0.99 | 1.95 | 4.28 | 1.25 | 2.37 | 4.84 | 1.21 | 3.03 | 6.86
ta14 | cost | 1497 | 1488 | 1484 | 1497 | 1488 | 1488 | 1489 | 1470 | 1470 | 1492 | 1492 | 1484 | 1492 | 1492 | 1487 | 1476 | 1474 | 1474 | 1473 | 1474 | 1448 | 1494 | 1480 | 1480
| time | 0.5 | 1.02 | 2.13 | 0.5 | 1.02 | 2.22 | 0.6 | 1.17 | 2.41 | 0.56 | 1.13 | 2.56 | 1.26 | 2.87 | 6.13 | 1.11 | 2 | 4.41 | 1.16 | 2.53 | 4.82 | 1.27 | 2.94 | 6.67
ta15 | cost | 1652 | 1553 | 1552 | 1652 | 1553 | 1553 | 1576 | 1547 | 1525 | 1598 | 1573 | 1554 | 1530 | 1530 | 1530 | 1556 | 1553 | 1526 | 1557 | 1551 | 1512 | 1624 | 1624 | 1624
| time | 0.5 | 1 | 2.12 | 0.5 | 1.01 | 2.19 | 0.51 | 1.14 | 2.35 | 0.47 | 0.96 | 2.14 | 0.97 | 2.6 | 5.78 | 1 | 1.9 | 4.54 | 1.18 | 2.26 | 4.83 | 1.36 | 3.17 | 7.22
ta16 | cost | 1605 | 1599 | 1599 | 1605 | 1599 | 1599 | 1565 | 1517 | 1508 | 1565 | 1565 | 1547 | 1550 | 1547 | 1543 | 1559 | 1559 | 1536 | 1539 | 1539 | 1539 | 1560 | 1560 | 1560
| time | 0.49 | 1.01 | 2.14 | 0.5 | 1.07 | 2.23 | 0.62 | 1.21 | 2.57 | 0.55 | 1.16 | 2.44 | 1.26 | 2.74 | 5.96 | 1.07 | 2.25 | 4.5 | 1.23 | 2.44 | 4.87 | 1.19 | 3.26 | 7.19
ta17 | cost | 1766 | 1760 | 1711 | 1766 | 1760 | 1711 | 1696 | 1663 | 1640 | 1751 | 1749 | 1696 | 1661 | 1661 | 1661 | 1742 | 1631 | 1628 | 1683 | 1606 | 1594 | 1745 | 1710 | 1738
| time | 0.49 | 0.99 | 2.11 | 0.6 | 1.01 | 2.12 | 0.51 | 1.1 | 2.33 | 0.47 | 0.95 | 2.09 | 1.01 | 2.67 | 5.88 | 1.12 | 1.96 | 4.19 | 1.12 | 2.13 | 4.58 | 1.39 | 3.23 | 6.77
ta18 | cost | 1644 | 1620 | 1611 | 1644 | 1620 | 1611 | 1663 | 1649 | 1630 | 1663 | 1663 | 1663 | 1620 | 1571 | 1571 | 1663 | 1606 | 1578 | 1663 | 1619 | 1560 | 1663 | 1641 | 1636
| time | 0.5 | 1.01 | 2.09 | 0.57 | 1.02 | 2.2 | 0.64 | 1.23 | 2.42 | 0.57 | 1.16 | 2.34 | 1.17 | 2.53 | 5.79 | 1.15 | 1.99 | 4.27 | 1.33 | 2.39 | 4.71 | 1.4 | 3.24 | 6.83
ta19 | cost | 1581 | 1581 | 1563 | 1581 | 1581 | 1581 | 1542 | 1516 | 1507 | 1586 | 1553 | 1516 | 1516 | 1516 | 1507 | 1535 | 1535 | 1516 | 1545 | 1526 | 1518 | 1566 | 1566 | 1566
| time | 0.51 | 1.04 | 2.15 | 0.5 | 1.08 | 2.3 | 0.53 | 1.07 | 2.34 | 0.46 | 0.97 | 2.11 | 1.07 | 2.7 | 5.84 | 1.07 | 2.1 | 4.48 | 1.24 | 2.49 | 4.93 | 1.53 | 3.41 | 7.1
ta20 | cost | 1572 | 1555 | 1555 | 1572 | 1555 | 1555 | 1504 | 1504 | 1499 | 1532 | 1504 | 1504 | 1532 | 1532 | 1532 | 1509 | 1503 | 1488 | 1509 | 1500 | 1480 | 1531 | 1531 | 1524
| time | 0.5 | 1.03 | 2.15 | 0.57 | 1.04 | 2.2 | 0.5 | 1.12 | 2.37 | 0.46 | 0.98 | 2.24 | 1.13 | 2.75 | 5.98 | 0.98 | 1.88 | 4.34 | 1.16 | 2.45 | 4.66 | 1.23 | 2.91 | 6.57
Table 11: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
20x20 |  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
ta21 | cost | 1930 | 1880 | 1865 | 1930 | 1930 | 1904 | 1835 | 1813 | 1795 | 1848 | 1835 | 1824 | 1871 | 1867 | 1858 | 1835 | 1819 | 1806 | 1835 | 1800 | 1803 | 1898 | 1863 | 1867
| time | 0.65 | 1.34 | 2.83 | 0.7 | 1.44 | 2.95 | 0.67 | 1.54 | 3.09 | 0.66 | 1.33 | 2.66 | 1.59 | 3.66 | 7.8 | 1.27 | 2.41 | 4.57 | 1.41 | 2.8 | 5.93 | 2.13 | 3.74 | 7.01
ta22 | cost | 1914 | 1871 | 1867 | 1914 | 1871 | 1871 | 1798 | 1796 | 1787 | 1812 | 1798 | 1796 | 1808 | 1808 | 1781 | 1789 | 1786 | 1772 | 1829 | 1774 | 1793 | 1911 | 1848 | 1821
| time | 0.66 | 1.33 | 2.74 | 0.65 | 1.32 | 2.83 | 0.65 | 1.46 | 3.11 | 0.59 | 1.3 | 2.82 | 1.46 | 3.71 | 7.53 | 1.19 | 2.38 | 4.75 | 1.36 | 2.76 | 6.16 | 2.28 | 3.7 | 7.01
ta23 | cost | 1811 | 1788 | 1786 | 1811 | 1791 | 1791 | 1745 | 1738 | 1722 | 1745 | 1745 | 1742 | 1796 | 1796 | 1757 | 1745 | 1745 | 1736 | 1765 | 1729 | 1736 | 1793 | 1804 | 1761
| time | 0.66 | 1.33 | 2.81 | 0.66 | 1.39 | 2.89 | 0.74 | 1.72 | 3.18 | 0.69 | 1.52 | 3.03 | 1.97 | 3.89 | 7.71 | 1.24 | 2.43 | 4.77 | 1.52 | 2.86 | 6.36 | 2.15 | 4.01 | 6.86
ta24 | cost | 1931 | 1897 | 1883 | 1931 | 1931 | 1931 | 1915 | 1838 | 1777 | 1937 | 1917 | 1882 | 1917 | 1880 | 1810 | 1882 | 1809 | 1809 | 1859 | 1820 | 1794 | 1946 | 1852 | 1825
| time | 0.76 | 1.32 | 2.81 | 0.66 | 1.45 | 2.95 | 0.69 | 1.39 | 2.94 | 0.65 | 1.33 | 2.6 | 1.82 | 3.67 | 7.57 | 1.36 | 2.57 | 5 | 1.38 | 2.72 | 5.8 | 2.21 | 3.74 | 6.9
ta25 | cost | 1852 | 1842 | 1793 | 1852 | 1842 | 1793 | 1796 | 1778 | 1778 | 1862 | 1796 | 1780 | 1796 | 1796 | 1796 | 1844 | 1790 | 1775 | 1787 | 1788 | 1772 | 1901 | 1812 | 1758
| time | 0.68 | 1.35 | 2.76 | 0.67 | 1.35 | 2.81 | 0.69 | 1.48 | 3.33 | 0.61 | 1.35 | 2.77 | 1.54 | 3.57 | 7.81 | 1.26 | 2.51 | 5.1 | 1.46 | 2.68 | 5.87 | 2.36 | 3.86 | 6.66
ta26 | cost | 1997 | 1977 | 1932 | 1997 | 1944 | 1942 | 1918 | 1906 | 1870 | 1935 | 1918 | 1918 | 1940 | 1879 | 1879 | 1918 | 1893 | 1855 | 1890 | 1894 | 1857 | 1925 | 1932 | 1874
| time | 0.65 | 1.32 | 2.73 | 0.81 | 1.35 | 2.87 | 0.76 | 1.58 | 3.36 | 0.73 | 1.69 | 3.06 | 1.84 | 3.46 | 7.74 | 1.3 | 2.42 | 5 | 1.41 | 2.86 | 5.75 | 2.11 | 3.81 | 6.87
ta27 | cost | 2116 | 2050 | 2004 | 2116 | 2050 | 2004 | 2050 | 2010 | 2008 | 2075 | 2049 | 2050 | 1990 | 1990 | 1969 | 2008 | 1990 | 1915 | 2022 | 1978 | 1928 | 2094 | 1993 | 1983
| time | 0.7 | 1.33 | 2.72 | 0.66 | 1.47 | 2.76 | 0.77 | 1.45 | 3.1 | 0.62 | 1.23 | 2.53 | 1.23 | 3.33 | 7.48 | 1.28 | 2.45 | 4.96 | 1.47 | 2.75 | 5.82 | 2.33 | 3.84 | 6.7
ta28 | cost | 1868 | 1866 | 1859 | 1868 | 1866 | 1866 | 1832 | 1816 | 1779 | 1855 | 1848 | 1827 | 1860 | 1860 | 1808 | 1823 | 1805 | 1783 | 1810 | 1814 | 1777 | 1871 | 1805 | 1828
| time | 0.78 | 1.36 | 2.77 | 0.66 | 1.45 | 2.92 | 0.84 | 1.62 | 3.78 | 0.73 | 1.49 | 3.1 | 1.8 | 3.91 | 7.62 | 1.27 | 2.35 | 4.67 | 1.33 | 2.84 | 5.99 | 2.32 | 3.76 | 7.01
ta29 | cost | 1911 | 1899 | 1845 | 1911 | 1911 | 1909 | 1856 | 1842 | 1787 | 1882 | 1876 | 1856 | 1882 | 1827 | 1780 | 1846 | 1813 | 1785 | 1844 | 1813 | 1801 | 1915 | 1840 | 1831
| time | 0.69 | 1.34 | 2.75 | 0.76 | 1.51 | 2.9 | 0.74 | 1.48 | 3.24 | 0.72 | 1.49 | 2.8 | 1.76 | 3.69 | 7.67 | 1.26 | 2.33 | 4.65 | 1.34 | 2.82 | 5.84 | 2.2 | 3.71 | 6.83
ta30 | cost | 1895 | 1879 | 1859 | 1895 | 1879 | 1879 | 1876 | 1876 | 1874 | 1887 | 1879 | 1876 | 1848 | 1816 | 1788 | 1874 | 1828 | 1803 | 1871 | 1858 | 1795 | 1927 | 1888 | 1862
| time | 0.7 | 1.36 | 2.77 | 0.68 | 1.42 | 2.91 | 0.68 | 1.47 | 3.18 | 0.62 | 1.24 | 2.58 | 1.45 | 3.27 | 7.2 | 1.32 | 2.45 | 4.94 | 1.44 | 2.9 | 5.78 | 2.29 | 3.77 | 7.1
Table 12: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
30x15 |  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
ta31 | cost | 2089 | 2081 | 2049 | 2089 | 2089 | 2089 | 2085 | 2077 | 2058 | 2089 | 2089 | 2077 | 2072 | 2072 | 2026 | 2072 | 2049 | 2001 | 2072 | 2067 | 2046 | 2081 | 2079 | 2048
| time | 0.81 | 1.56 | 3.12 | 0.76 | 1.62 | 3.53 | 0.91 | 1.83 | 3.65 | 0.84 | 1.57 | 3.35 | 1.93 | 4.2 | 8.78 | 1.43 | 2.72 | 5.26 | 1.64 | 3.45 | 7 | 1.77 | 4.24 | 6.77
ta32 | cost | 2148 | 2124 | 2065 | 2148 | 2124 | 2065 | 2125 | 2125 | 2125 | 2125 | 2125 | 2125 | 2125 | 2125 | 2125 | 2102 | 2065 | 2054 | 2125 | 2084 | 2058 | 2120 | 2087 | 2031
| time | 0.77 | 1.55 | 3.16 | 0.77 | 1.71 | 3.5 | 0.96 | 2.17 | 4.39 | 0.78 | 1.73 | 3.73 | 1.64 | 4.06 | 8.94 | 1.32 | 2.57 | 5.76 | 1.53 | 2.91 | 6.7 | 1.53 | 3.39 | 6.94
ta33 | cost | 2228 | 2200 | 2158 | 2228 | 2200 | 2172 | 2187 | 2154 | 2138 | 2255 | 2194 | 2154 | 2182 | 2134 | 2101 | 2169 | 2157 | 2133 | 2206 | 2130 | 2125 | 2169 | 2153 | 2099
| time | 0.8 | 1.6 | 3.15 | 0.82 | 1.7 | 3.47 | 0.89 | 1.91 | 3.83 | 0.81 | 1.72 | 3.48 | 1.24 | 2.96 | 7.22 | 1.27 | 2.58 | 5.92 | 1.46 | 3.11 | 6.7 | 1.27 | 3.2 | 6.16
ta34 | cost | 2082 | 2082 | 2067 | 2082 | 2082 | 2082 | 2076 | 2076 | 2070 | 2076 | 2076 | 2076 | 2076 | 2076 | 2066 | 2076 | 2076 | 2046 | 2067 | 2050 | 2055 | 2056 | 2056 | 2056
| time | 0.72 | 1.71 | 3.09 | 0.76 | 1.69 | 3.48 | 0.97 | 2.16 | 3.89 | 0.82 | 1.77 | 3.51 | 2.06 | 4.26 | 9 | 1.46 | 2.95 | 5.66 | 1.62 | 3.33 | 7.12 | 1.66 | 3.86 | 6.71
ta35 | cost | 2201 | 2173 | 2146 | 2201 | 2163 | 2163 | 2159 | 2138 | 2109 | 2178 | 2178 | 2178 | 2178 | 2159 | 2159 | 2159 | 2159 | 2130 | 2155 | 2122 | 2122 | 2149 | 2149 | 2122
| time | 0.76 | 1.67 | 3.11 | 0.83 | 1.75 | 3.58 | 0.94 | 2.06 | 3.84 | 0.82 | 1.7 | 3.15 | 2.04 | 4.25 | 9.07 | 1.52 | 2.74 | 5.36 | 1.69 | 3.1 | 6.86 | 1.79 | 3.86 | 7.27
ta36 | cost | 2154 | 2150 | 2140 | 2154 | 2154 | 2154 | 2150 | 2150 | 2150 | 2150 | 2150 | 2150 | 2150 | 2112 | 2112 | 2136 | 2136 | 2113 | 2135 | 2104 | 2118 | 2132 | 2105 | 2064
| time | 0.78 | 1.6 | 3.15 | 0.79 | 1.87 | 3.65 | 0.83 | 1.88 | 3.63 | 0.75 | 1.49 | 2.88 | 2.11 | 3.98 | 8.77 | 1.48 | 2.89 | 5.59 | 1.6 | 3.17 | 6.93 | 1.51 | 3.5 | 6.32
ta37 | cost | 2201 | 2149 | 2121 | 2201 | 2149 | 2121 | 2131 | 2108 | 2084 | 2131 | 2131 | 2108 | 2079 | 2079 | 2060 | 2084 | 2084 | 2075 | 2101 | 2060 | 2060 | 2118 | 2095 | 2075
| time | 0.74 | 1.56 | 3.08 | 0.77 | 1.69 | 3.26 | 0.96 | 1.93 | 3.76 | 0.85 | 1.76 | 3.27 | 1.61 | 3.82 | 8.54 | 1.31 | 2.51 | 5.57 | 1.58 | 3.04 | 6.79 | 1.73 | 3.73 | 6.64
ta38 | cost | 1991 | 1978 | 1961 | 1991 | 1991 | 1991 | 1961 | 1946 | 1911 | 1961 | 1961 | 1952 | 1974 | 1974 | 1919 | 1971 | 1946 | 1919 | 1938 | 1976 | 1889 | 1933 | 1933 | 1917
| time | 0.71 | 1.55 | 3.12 | 0.83 | 1.75 | 3.58 | 0.85 | 1.71 | 3.66 | 0.69 | 1.43 | 2.85 | 2.22 | 4.54 | 8.97 | 1.58 | 2.88 | 5.59 | 1.6 | 3.58 | 6.59 | 1.53 | 3.79 | 7.25
ta39 | cost | 2123 | 2100 | 2074 | 2123 | 2100 | 2074 | 2051 | 2043 | 2043 | 2066 | 2051 | 2043 | 2056 | 2041 | 2041 | 2043 | 2043 | 2036 | 2056 | 2043 | 2043 | 2056 | 2046 | 1991
| time | 0.78 | 1.57 | 3.15 | 0.77 | 1.67 | 3.5 | 0.83 | 1.85 | 4.15 | 0.83 | 1.73 | 3.51 | 1.6 | 3.69 | 8.53 | 1.42 | 2.72 | 5.68 | 1.5 | 3.19 | 7.29 | 1.56 | 3.57 | 7.26
ta40 | cost | 2023 | 2004 | 1937 | 2023 | 2004 | 2004 | 1977 | 1961 | 1949 | 1977 | 1977 | 1977 | 2037 | 1954 | 1915 | 1961 | 1925 | 1924 | 1959 | 1935 | 1911 | 1962 | 1947 | 1936
| time | 0.74 | 1.57 | 3.16 | 0.82 | 1.74 | 3.64 | 0.92 | 1.9 | 3.94 | 0.78 | 1.69 | 3.62 | 1.99 | 3.83 | 8.26 | 1.46 | 2.69 | 5.56 | 1.48 | 3.02 | 7.02 | 1.47 | 3.48 | 7.26
Table 13: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
30x20 |  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
ta41 | cost | 2490 | 2465 | 2429 | 2490 | 2465 | 2465 | 2427 | 2405 | 2404 | 2465 | 2427 | 2405 | 2465 | 2442 | 2442 | 2423 | 2414 | 2384 | 2434 | 2413 | 2372 | 2430 | 2408 | 2351
| time | 0.95 | 2.02 | 4.12 | 1.08 | 2.12 | 4.37 | 1.03 | 2.28 | 4.92 | 1.07 | 2.16 | 4.52 | 2.42 | 5.13 | 11.14 | 1.68 | 3.39 | 7.39 | 1.88 | 4.1 | 8.26 | 1.88 | 3.89 | 7.94
ta42 | cost | 2355 | 2331 | 2309 | 2374 | 2354 | 2307 | 2341 | 2330 | 2302 | 2341 | 2341 | 2333 | 2315 | 2277 | 2277 | 2291 | 2291 | 2254 | 2295 | 2295 | 2285 | 2291 | 2241 | 2233
| time | 0.98 | 2.03 | 4.16 | 1.29 | 2.15 | 4.3 | 1.25 | 2.61 | 5.16 | 1.08 | 2.26 | 4.7 | 2.38 | 5.13 | 11.29 | 1.63 | 3.39 | 7.29 | 1.93 | 4.14 | 8.44 | 1.96 | 3.95 | 8.61
ta43 | cost | 2354 | 2342 | 2308 | 2354 | 2296 | 2282 | 2297 | 2248 | 2247 | 2297 | 2297 | 2248 | 2268 | 2251 | 2216 | 2259 | 2228 | 2208 | 2272 | 2253 | 2201 | 2265 | 2232 | 2182
| time | 1.01 | 2.08 | 4.15 | 1.23 | 2.1 | 4.38 | 1.11 | 2.33 | 5.37 | 0.99 | 2.21 | 4.52 | 2.1 | 4.91 | 10.7 | 1.67 | 3.26 | 7.21 | 1.83 | 3.88 | 7.97 | 1.98 | 3.92 | 8.57
ta44 | cost | 2399 | 2388 | 2346 | 2399 | 2399 | 2399 | 2317 | 2317 | 2304 | 2318 | 2317 | 2317 | 2318 | 2309 | 2309 | 2317 | 2305 | 2260 | 2308 | 2308 | 2291 | 2303 | 2301 | 2280
| time | 0.98 | 2.02 | 4.15 | 1.09 | 2.14 | 4.7 | 1.08 | 2.41 | 5.5 | 1.02 | 2.2 | 4.53 | 2.05 | 4.97 | 11.03 | 1.62 | 3.45 | 7.16 | 1.81 | 4.1 | 8.42 | 1.89 | 3.9 | 8.55
ta45 | cost | 2421 | 2362 | 2344 | 2421 | 2362 | 2362 | 2278 | 2251 | 2241 | 2278 | 2274 | 2241 | 2278 | 2278 | 2243 | 2278 | 2262 | 2241 | 2278 | 2248 | 2228 | 2278 | 2244 | 2241
| time | 0.98 | 2.04 | 4.16 | 1.09 | 2.09 | 4.31 | 0.87 | 2.07 | 4.6 | 0.91 | 2.04 | 4.28 | 1.2 | 4.21 | 9.81 | 1.41 | 3.14 | 6.65 | 1.42 | 3.46 | 8.23 | 1.53 | 3.41 | 8.04
ta46 | cost | 2525 | 2489 | 2432 | 2525 | 2525 | 2525 | 2424 | 2395 | 2320 | 2437 | 2424 | 2395 | 2433 | 2366 | 2366 | 2424 | 2358 | 2324 | 2437 | 2371 | 2322 | 2437 | 2366 | 2324
| time | 0.97 | 2.03 | 4.36 | 1.25 | 2.2 | 4.63 | 0.94 | 2.04 | 4.31 | 0.88 | 2.01 | 3.82 | 2.08 | 4.55 | 10.59 | 1.57 | 3.22 | 6.46 | 1.9 | 3.75 | 7.93 | 2 | 3.58 | 7.76
ta47 | cost | 2350 | 2308 | 2259 | 2350 | 2308 | 2274 | 2281 | 2269 | 2252 | 2295 | 2295 | 2269 | 2269 | 2269 | 2237 | 2252 | 2246 | 2192 | 2247 | 2209 | 2209 | 2281 | 2235 | 2213
| time | 0.98 | 2.21 | 4.17 | 1.21 | 2.05 | 4.9 | 1.14 | 2.42 | 5.16 | 1.01 | 2.21 | 4.69 | 1.92 | 4.96 | 10.59 | 1.63 | 3.37 | 7.16 | 1.87 | 3.51 | 7.99 | 2.16 | 3.71 | 8.22
ta48 | cost | 2279 | 2264 | 2242 | 2279 | 2264 | 2257 | 2253 | 2243 | 2227 | 2256 | 2256 | 2243 | 2264 | 2227 | 2227 | 2256 | 2233 | 2217 | 2268 | 2230 | 2230 | 2268 | 2253 | 2225
| time | 0.96 | 2.16 | 4.15 | 1.06 | 2.01 | 4.69 | 1.1 | 2.5 | 5.71 | 1.1 | 2.22 | 4.59 | 2.73 | 5.38 | 11.69 | 1.73 | 3.51 | 6.86 | 2.3 | 4.14 | 8.7 | 2.43 | 4.3 | 8.92
ta49 | cost | 2398 | 2395 | 2395 | 2398 | 2398 | 2398 | 2368 | 2351 | 2335 | 2368 | 2368 | 2356 | 2352 | 2352 | 2352 | 2356 | 2356 | 2333 | 2359 | 2356 | 2314 | 2378 | 2353 | 2324
| time | 0.99 | 2.07 | 4.18 | 1.25 | 2.11 | 4.44 | 1.12 | 2.39 | 5.15 | 1 | 2.2 | 4.59 | 1.71 | 4.69 | 10.86 | 1.6 | 3.4 | 6.8 | 1.85 | 4.1 | 8.14 | 2.13 | 3.97 | 8.73
ta50 | cost | 2357 | 2348 | 2321 | 2357 | 2357 | 2357 | 2332 | 2324 | 2264 | 2332 | 2332 | 2331 | 2359 | 2356 | 2286 | 2323 | 2288 | 2257 | 2342 | 2266 | 2253 | 2332 | 2289 | 2242
| time | 0.99 | 2.14 | 4.1 | 1.24 | 2.18 | 5.1 | 1.01 | 2.3 | 4.76 | 0.96 | 1.97 | 4.05 | 2.83 | 5.8 | 10.91 | 1.72 | 3.19 | 6.62 | 2.14 | 3.68 | 7.95 | 2.18 | 3.86 | 9.01
Table 14: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
50x15 |  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
ta51 | cost | 3444 | 3381 | 3320 | 3444 | 3381 | 3320 | 3391 | 3355 | 3333 | 3391 | 3391 | 3355 | 3326 | 3287 | 3283 | 3391 | 3314 | 3273 | 3387 | 3300 | 3281 | 3373 | 3361 | 3281
| time | 1.34 | 2.65 | 5.51 | 1.37 | 2.71 | 5.37 | 1.46 | 2.9 | 6.31 | 1.33 | 2.81 | 5.66 | 1.71 | 4.38 | 12.36 | 2.25 | 4.22 | 8.48 | 2.23 | 4.31 | 9.56 | 2.29 | 4.83 | 9.99
ta52 | cost | 3254 | 3225 | 3210 | 3254 | 3225 | 3210 | 3228 | 3224 | 3198 | 3276 | 3240 | 3228 | 3276 | 3193 | 3160 | 3267 | 3231 | 3188 | 3240 | 3231 | 3161 | 3231 | 3231 | 3205
| time | 1.33 | 2.62 | 5.25 | 1.31 | 2.64 | 5.21 | 1.48 | 3.16 | 6.63 | 1.48 | 2.88 | 5.98 | 3.72 | 5.69 | 13.07 | 2.55 | 4.95 | 9.53 | 2.91 | 5.23 | 10.11 | 2.52 | 5.6 | 10.37
ta53 | cost | 2998 | 2987 | 2933 | 2998 | 2998 | 2998 | 3000 | 2994 | 2994 | 3014 | 3005 | 2994 | 2994 | 2968 | 2967 | 3010 | 2980 | 2974 | 2994 | 2990 | 2974 | 2983 | 2983 | 2974
| time | 1.27 | 2.58 | 5.19 | 1.33 | 2.7 | 5.55 | 1.51 | 3.31 | 6.81 | 1.41 | 2.89 | 5.85 | 2.63 | 5.84 | 13.65 | 2.39 | 4.54 | 9.45 | 2.43 | 5.06 | 10.75 | 2.43 | 5.3 | 10.43
ta54 | cost | 2989 | 2944 | 2935 | 2989 | 2944 | 2943 | 3011 | 2997 | 2956 | 3011 | 3011 | 3011 | 2981 | 2961 | 2941 | 2953 | 2923 | 2914 | 2960 | 2930 | 2910 | 2961 | 2924 | 2924
| time | 1.26 | 2.81 | 5.25 | 1.24 | 2.68 | 5.2 | 1.66 | 3.36 | 6.82 | 1.39 | 2.9 | 5.84 | 3.09 | 6.54 | 13.93 | 1.95 | 3.94 | 8.34 | 2.26 | 4.39 | 9.73 | 2.56 | 4.89 | 9.94
ta55 | cost | 3071 | 3057 | 3037 | 3071 | 3057 | 3037 | 3063 | 3059 | 3059 | 3065 | 3063 | 3059 | 3063 | 3052 | 3026 | 3059 | 3027 | 3027 | 3063 | 3044 | 3026 | 3059 | 3027 | 3026
| time | 1.32 | 2.75 | 5.41 | 1.3 | 2.7 | 5.49 | 1.59 | 3.42 | 6.97 | 1.4 | 3.16 | 5.94 | 2.87 | 6.42 | 13.61 | 2.24 | 4.57 | 8.9 | 2.45 | 4.96 | 10.46 | 2.47 | 4.99 | 10.28
ta56 | cost | 3177 | 3102 | 3068 | 3177 | 3102 | 3068 | 3117 | 3117 | 3062 | 3150 | 3117 | 3117 | 3117 | 3117 | 3087 | 3116 | 3082 | 3082 | 3140 | 3096 | 3062 | 3078 | 3078 | 3015
| time | 1.31 | 2.68 | 5.38 | 1.3 | 2.69 | 5.34 | 1.51 | 3.31 | 6.36 | 1.38 | 3.07 | 5.73 | 2.43 | 6.21 | 13.08 | 2.24 | 4.48 | 9.21 | 2.37 | 4.95 | 10.48 | 2.11 | 5 | 9.71
ta57 | cost | 3248 | 3228 | 3213 | 3248 | 3228 | 3213 | 3266 | 3266 | 3239 | 3266 | 3266 | 3266 | 3266 | 3243 | 3213 | 3266 | 3266 | 3219 | 3239 | 3225 | 3207 | 3221 | 3213 | 3204
| time | 1.32 | 2.62 | 5.4 | 1.29 | 2.65 | 5.36 | 1.66 | 3.62 | 7.27 | 1.41 | 2.94 | 5.88 | 3.27 | 6.43 | 13.91 | 2.49 | 4.86 | 9.54 | 2.4 | 5.02 | 10.7 | 2.21 | 4.91 | 9.99
ta58 | cost | 3243 | 3223 | 3217 | 3243 | 3223 | 3201 | 3249 | 3223 | 3217 | 3249 | 3249 | 3249 | 3237 | 3217 | 3176 | 3261 | 3229 | 3206 | 3249 | 3219 | 3223 | 3208 | 3204 | 3185
| time | 1.27 | 2.59 | 5.18 | 1.28 | 2.54 | 5.29 | 1.71 | 3.38 | 6.95 | 1.43 | 2.91 | 5.96 | 3.17 | 6.47 | 13.38 | 2.48 | 4.71 | 9.23 | 2.71 | 5.31 | 11.32 | 2.39 | 5.25 | 10.29
ta59 | cost | 3119 | 3083 | 3007 | 3119 | 3083 | 3007 | 3015 | 3006 | 2982 | 3015 | 3015 | 3006 | 3015 | 2988 | 2974 | 3015 | 3009 | 2961 | 3015 | 3004 | 2953 | 3015 | 2973 | 2945
| time | 1.32 | 2.68 | 5.37 | 1.34 | 2.61 | 5.32 | 1.4 | 3.21 | 6.43 | 1.28 | 2.82 | 5.73 | 2.2 | 5.66 | 12.98 | 1.98 | 4.39 | 8.41 | 2.13 | 4.63 | 10.53 | 2.23 | 4.51 | 9.12
ta60 | cost | 2977 | 2974 | 2945 | 2977 | 2974 | 2964 | 3006 | 3006 | 2977 | 3006 | 3006 | 3006 | 2968 | 2940 | 2929 | 2961 | 2953 | 2948 | 2991 | 2991 | 2977 | 2968 | 2968 | 2926
| time | 1.31 | 2.64 | 5.4 | 1.31 | 2.61 | 5.37 | 1.77 | 3.62 | 7.16 | 1.5 | 3.05 | 6.12 | 2.71 | 5.68 | 13.28 | 2.27 | 4.42 | 9.24 | 2.67 | 5.43 | 11.57 | 2.33 | 5.5 | 9.58
Table 15: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
50x20 |  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
ta61 | cost | 3252 | 3236 | 3205 | 3252 | 3236 | 3217 | 3215 | 3196 | 3175 | 3215 | 3196 | 3196 | 3204 | 3192 | 3192 | 3208 | 3167 | 3143 | 3208 | 3196 | 3181 | 3208 | 3188 | 3173
| time | 1.71 | 3.5 | 7 | 1.71 | 3.47 | 7.24 | 1.55 | 3.38 | 7.09 | 1.55 | 3.31 | 6.47 | 2.25 | 6.33 | 16.52 | 2.26 | 4.47 | 9.85 | 2.2 | 5.39 | 12.45 | 2.21 | 5.56 | 13.09
ta62 | cost | 3368 | 3337 | 3299 | 3368 | 3337 | 3299 | 3321 | 3321 | 3317 | 3321 | 3321 | 3321 | 3329 | 3329 | 3308 | 3329 | 3321 | 3296 | 3329 | 3295 | 3290 | 3322 | 3290 | 3269
| time | 1.66 | 3.44 | 7.02 | 1.67 | 3.42 | 7.19 | 1.72 | 3.59 | 7.99 | 1.7 | 3.28 | 6.5 | 3.31 | 8.29 | 18.25 | 2.79 | 5.74 | 12.01 | 2.96 | 5.69 | 12.79 | 3.09 | 5.89 | 13.02
ta63 | cost | 3095 | 3090 | 3065 | 3095 | 3090 | 3090 | 3076 | 3046 | 3030 | 3076 | 3076 | 3054 | 3076 | 3033 | 3025 | 3058 | 3049 | 3019 | 3058 | 3058 | 3011 | 3053 | 3028 | 3009
| time | 1.73 | 3.45 | 6.76 | 1.74 | 3.52 | 7.35 | 1.85 | 3.89 | 8.4 | 1.68 | 3.77 | 7.63 | 3.08 | 6.68 | 16.19 | 2.65 | 5.65 | 10.94 | 2.54 | 6.16 | 11.96 | 2.7 | 5.77 | 12.45
ta64 | cost | 3084 | 3066 | 3057 | 3084 | 3066 | 3056 | 3080 | 3058 | 2996 | 3080 | 3080 | 3080 | 3080 | 3069 | 3009 | 3074 | 3028 | 2998 | 3071 | 3047 | 3001 | 3055 | 3045 | 3003
| time | 1.7 | 3.5 | 7.02 | 1.71 | 3.49 | 7.19 | 1.72 | 3.77 | 7.68 | 1.54 | 3.16 | 6.71 | 3.9 | 7.86 | 16.36 | 2.74 | 5.02 | 10.43 | 2.97 | 5.8 | 13.44 | 2.59 | 6.48 | 12.73
ta65 | cost | 3257 | 3188 | 3150 | 3257 | 3188 | 3150 | 3224 | 3182 | 3150 | 3270 | 3252 | 3188 | 3190 | 3148 | 3119 | 3213 | 3166 | 3140 | 3219 | 3169 | 3111 | 3209 | 3195 | 3103
| time | 1.65 | 3.35 | 6.95 | 1.65 | 3.35 | 6.92 | 1.91 | 3.93 | 8.12 | 1.87 | 3.79 | 7.79 | 3.72 | 8.05 | 17.31 | 2.6 | 5.12 | 10.67 | 2.92 | 5.88 | 12 | 2.64 | 5.9 | 11.58
ta66 | cost | 3264 | 3204 | 3171 | 3264 | 3204 | 3171 | 3227 | 3166 | 3163 | 3273 | 3273 | 3163 | 3179 | 3166 | 3166 | 3202 | 3170 | 3166 | 3194 | 3157 | 3157 | 3166 | 3166 | 3150
| time | 1.7 | 3.52 | 7.15 | 1.7 | 3.52 | 7.33 | 1.89 | 3.61 | 8.25 | 1.85 | 3.71 | 7.82 | 2.73 | 7.1 | 17.28 | 2.48 | 6.32 | 11.58 | 2.5 | 5.25 | 12.52 | 2.38 | 6.07 | 13.64
ta67 | cost | 3242 | 3203 | 3190 | 3242 | 3203 | 3190 | 3195 | 3181 | 3168 | 3211 | 3194 | 3184 | 3224 | 3155 | 3155 | 3211 | 3152 | 3137 | 3180 | 3169 | 3158 | 3185 | 3142 | 3122
| time | 1.7 | 3.46 | 6.76 | 1.7 | 3.46 | 6.99 | 1.84 | 4.06 | 8.43 | 1.74 | 3.68 | 8.01 | 4.51 | 7.11 | 17.44 | 2.83 | 5.45 | 11.31 | 2.78 | 6.12 | 13.15 | 2.89 | 5.43 | 12.47
ta68 | cost | 3115 | 3097 | 3071 | 3115 | 3127 | 3127 | 3114 | 3042 | 3029 | 3115 | 3114 | 3114 | 3114 | 3035 | 3031 | 3091 | 3083 | 3039 | 3101 | 3062 | 3021 | 3068 | 3029 | 3015
| time | 1.64 | 3.28 | 6.78 | 1.68 | 3.47 | 7.2 | 1.72 | 3.4 | 7.27 | 1.57 | 3.14 | 6.3 | 4.39 | 5.95 | 15.78 | 2.6 | 5.6 | 10.97 | 2.91 | 5.8 | 11.68 | 2.63 | 5.47 | 12.5
ta69 | cost | 3487 | 3434 | 3411 | 3487 | 3434 | 3429 | 3443 | 3427 | 3408 | 3472 | 3459 | 3431 | 3431 | 3410 | 3408 | 3427 | 3413 | 3413 | 3427 | 3416 | 3407 | 3427 | 3409 | 3407
| time | 1.73 | 3.47 | 6.97 | 1.71 | 3.51 | 7.33 | 1.98 | 4.19 | 8.68 | 1.82 | 3.82 | 7.7 | 3.1 | 7 | 16.89 | 2.56 | 5.4 | 12.13 | 2.75 | 6.05 | 13.65 | 2.92 | 6.1 | 13.69
ta70 | cost | 3325 | 3313 | 3294 | 3325 | 3313 | 3294 | 3292 | 3276 | 3275 | 3292 | 3292 | 3292 | 3292 | 3292 | 3292 | 3292 | 3292 | 3288 | 3289 | 3289 | 3281 | 3292 | 3292 | 3283
| time | 1.69 | 3.45 | 6.85 | 1.67 | 3.43 | 6.88 | 1.7 | 3.55 | 7.48 | 1.52 | 3.12 | 6.4 | 3.9 | 8.62 | 18.89 | 2.7 | 5.86 | 11.83 | 3.14 | 6.58 | 13.89 | 3.11 | 6.63 | 14.51
Table 16: Detailed Results on the Taillard benchmark[18]. Inst. | LS |
---|---|---
|  | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
|  | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200
100x20 |  |
ta71 | cost | 5855 | 5822 | 5813 | 5855 | 5855 | 5807 | 5855 | 5855 | 5855 | 5855 | 5855 | 5855 | 5848 | 5820 | 5810 | 5832 | 5817 | 5811 | 5855 | 5821 | 5811 | 5842 | 5810 | 5799
| time | 3.79 | 7.22 | 14.21 | 4.11 | 8.33 | 15.63 | 4.85 | 9.83 | 19.8 | 3.94 | 8.1 | 16.26 | 9.97 | 18.47 | 38.01 | 6.06 | 11.69 | 24.48 | 7.48 | 13.23 | 26.77 | 7.17 | 12.63 | 25.61
ta72 | cost | 5531 | 5528 | 5490 | 5531 | 5531 | 5531 | 5499 | 5474 | 5460 | 5499 | 5499 | 5480 | 5496 | 5496 | 5458 | 5480 | 5471 | 5446 | 5480 | 5465 | 5448 | 5480 | 5445 | 5431
| time | 3.61 | 7.19 | 14.75 | 3.58 | 7.99 | 16.08 | 3.8 | 8.16 | 17.58 | 3.66 | 7.74 | 15.61 | 5.56 | 15.53 | 31.26 | 4.27 | 10.56 | 22.76 | 4.5 | 11.51 | 26.33 | 4.69 | 10.54 | 24.12
ta73 | cost | 6178 | 6142 | 6091 | 6178 | 6142 | 6091 | 6173 | 6173 | 6173 | 6173 | 6173 | 6173 | 6148 | 6102 | 6032 | 6118 | 6079 | 6079 | 6173 | 6090 | 6042 | 6149 | 6149 | 6123
| time | 3.56 | 7.04 | 14.28 | 3.56 | 7.1 | 14.44 | 4.2 | 9.11 | 19.5 | 3.65 | 7.85 | 16.33 | 6.3 | 14.01 | 28.39 | 4.69 | 10.25 | 24.22 | 6.26 | 12.2 | 25.01 | 5.91 | 12.78 | 27.29
ta74 | cost | 5590 | 5561 | 5537 | 5590 | 5561 | 5537 | 5556 | 5534 | 5534 | 5556 | 5556 | 5536 | 5556 | 5523 | 5502 | 5556 | 5531 | 5495 | 5556 | 5534 | 5504 | 5556 | 5534 | 5524
| time | 3.53 | 7.1 | 14.54 | 3.61 | 7.14 | 14.5 | 3.86 | 7.8 | 17.69 | 3.5 | 7.67 | 15.61 | 6.04 | 11.97 | 29.92 | 4.9 | 10.18 | 20.99 | 5.39 | 11.32 | 24.27 | 5.44 | 11.94 | 25.85
ta75 | cost | 6000 | 5965 | 5914 | 6000 | 5965 | 5914 | 5966 | 5928 | 5909 | 5966 | 5966 | 5937 | 5957 | 5911 | 5911 | 5966 | 5940 | 5900 | 5966 | 5966 | 5966 | 5966 | 5937 | 5903
| time | 3.57 | 7.16 | 14.67 | 3.59 | 7.2 | 14.93 | 3.74 | 7.84 | 17.02 | 3.35 | 7.47 | 15.51 | 5.1 | 9.92 | 30.23 | 4.8 | 10.97 | 21.83 | 5.05 | 12.37 | 27.38 | 5.06 | 11.31 | 25.26
ta76 | cost | 5812 | 5782 | 5755 | 5812 | 5782 | 5755 | 5836 | 5836 | 5775 | 5836 | 5836 | 5836 | 5789 | 5758 | 5694 | 5795 | 5785 | 5736 | 5798 | 5770 | 5715 | 5795 | 5728 | 5701
| time | 3.83 | 7.16 | 15.01 | 3.66 | 7.4 | 14.89 | 4.86 | 10.01 | 19.1 | 3.91 | 7.99 | 16.19 | 7.16 | 14.52 | 29.82 | 5.64 | 11.39 | 22 | 6.48 | 12.65 | 23.72 | 5.67 | 10.47 | 22.87
ta77 | cost | 5682 | 5629 | 5585 | 5682 | 5629 | 5585 | 5718 | 5690 | 5644 | 5736 | 5718 | 5718 | 5677 | 5647 | 5593 | 5644 | 5624 | 5593 | 5662 | 5598 | 5552 | 5636 | 5596 | 5593
| time | 3.55 | 7.15 | 15.47 | 3.64 | 7.26 | 14.6 | 4.66 | 9.18 | 17.58 | 3.97 | 8.23 | 16.1 | 7.83 | 15.29 | 31.8 | 5.5 | 10.43 | 22.2 | 6.08 | 10.8 | 22.99 | 5.56 | 11.25 | 25.24
ta78 | cost | 5732 | 5719 | 5688 | 5732 | 5719 | 5688 | 5726 | 5726 | 5724 | 5756 | 5756 | 5726 | 5726 | 5724 | 5723 | 5749 | 5724 | 5695 | 5756 | 5726 | 5724 | 5756 | 5726 | 5724
| time | 3.63 | 7.27 | 15.32 | 3.62 | 7.25 | 15.19 | 4.37 | 9.33 | 19.33 | 3.92 | 8.36 | 16.4 | 9.17 | 19.11 | 39.43 | 6.62 | 12.62 | 24.92 | 7.36 | 13.07 | 27.1 | 7.78 | 13.6 | 27.5
ta79 | cost | 5640 | 5622 | 5586 | 5640 | 5622 | 5586 | 5641 | 5600 | 5584 | 5641 | 5641 | 5641 | 5616 | 5590 | 5547 | 5649 | 5649 | 5649 | 5649 | 5606 | 5606 | 5606 | 5586 | 5531
| time | 3.72 | 7.44 | 14.32 | 3.57 | 7.25 | 14.52 | 4.55 | 9.26 | 18.53 | 3.89 | 8.07 | 16.64 | 7.73 | 16.25 | 33.4 | 6.18 | 12.55 | 24.73 | 7.1 | 13.58 | 27.64 | 6.34 | 12.9 | 25.11
ta80 | cost | 5464 | 5433 | 5421 | 5474 | 5474 | 5445 | 5445 | 5445 | 5445 | 5457 | 5457 | 5445 | 5445 | 5445 | 5421 | 5440 | 5431 | 5419 | 5421 | 5421 | 5421 | 5420 | 5413 | 5405
| time | 3.62 | 7.05 | 14.61 | 3.99 | 7.81 | 15.33 | 4.21 | 9.42 | 19.11 | 3.92 | 8.15 | 16.19 | 8.47 | 18.83 | 36.55 | 5.83 | 11.28 | 24.77 | 5.32 | 12.84 | 27.61 | 5.28 | 11.65 | 25.99

Table 17: Detailed Results on the Uchoa benchmark[20]. Instance |  | BKS | POMO[6] | VRPH |
---|---|---|---|---|---
n100 |  |  | single | multi | aug=8 | Sweep | Savings
X-n101-k25 | cost | 27591 | 29627 | 29025 | 28596 | 35807 | 29674
| k |  | 28 | 27 | 27 | 30 | 30
| time |  | 0.29 | 0.3 | 0.04 | 0 | 0
X-n106-k14 | cost | 26362 | 27521 | 27140 | 26849 | 34811 | 27442
| k |  | 14 | 14 | 14 | 14 | 14
| time |  | 0.28 | 0.29 | 0.04 | 0 | 0
X-n110-k13 | cost | 14971 | 15850 | 15316 | 15278 | 20435 | 15883
| k |  | 14 | 13 | 13 | 14 | 13
| time |  | 0.28 | 0.29 | 0.04 | 0 | 0
X-n115-k10 | cost | 12747 | 13523 | 13192 | 13192 | 18727 | 13585
| k |  | 10 | 10 | 10 | 11 | 11
| time |  | 0.28 | 0.29 | 0.04 | 0 | 0
X-n120-k6 | cost | 13332 | 14077 | 13846 | 13614 | 33166 | 14745
| k |  | 6 | 6 | 6 | 6 | 6
| time |  | 0.28 | 0.29 | 0.04 | 0 | 0
X-n125-k30 | cost | 55539 | 79994 | 74465 | 59504 | 71695 | 60561
| k |  | 41 | 38 | 32 | 36 | 34
| time |  | 0.31 | 0.32 | 0.04 | 0 | 0
X-n129-k18 | cost | 28940 | 29576 | 29220 | 29220 | 48717 | 30407
| k |  | 18 | 18 | 18 | 19 | 18
| time |  | 0.3 | 0.3 | 0.04 | 0 | 0
X-n134-k13 | cost | 10916 | 11803 | 11601 | 11377 | 19640 | 11415
| k |  | 14 | 14 | 14 | 14 | 14
| time |  | 0.3 | 0.3 | 0.04 | 0 | 0
X-n139-k10 | cost | 13590 | 14714 | 14147 | 13900 | 22174 | 14726
| k |  | 11 | 11 | 10 | 11 | 11
| time |  | 0.3 | 0.3 | 0.04 | 0 | 0
X-n143-k7 | cost | 15700 | 16195 | 16138 | 16138 | 41910 | 17664
| k |  | 7 | 7 | 7 | 7 | 7
| time |  | 0.3 | 0.31 | 0.04 | 0 | 0
X-n148-k46 | cost | 43448 | 72057 | 64407 | 52085 | 61758 | 48048
| k |  | 77 | 66 | 52 | 57 | 53
| time |  | 0.34 | 0.35 | 0.05 | 0 | 0
Table 18: Detailed Results on the Uchoa benchmark[20]. Instance |  | BKS | POMO[6] | VRPH |
---|---|---|---|---|---
n150 |  |  | single | multi | aug=8 | Sweep | Savings
X-n153-k22 | cost | 21220 | 25709 | 24591 | 23833 | 31639 | 22649
| k |  | 27 | 26 | 26 | 29 | 26
| time |  | 0.67 | 0.39 | 0.05 | 0 | 0
X-n157-k13 | cost | 16876 | 17544 | 17331 | 17164 | 25353 | 19171
| k |  | 13 | 13 | 13 | 15 | 15
| time |  | 0.33 | 0.43 | 0.04 | 0 | 0
X-n162-k11 | cost | 14138 | 15142 | 14844 | 14813 | 24262 | 15708
| k |  | 11 | 11 | 11 | 11 | 11
| time |  | 0.32 | 0.37 | 0.04 | 0 | 0
X-n167-k10 | cost | 20557 | 22039 | 21564 | 21390 | 47099 | 22004
| k |  | 10 | 10 | 10 | 10 | 10
| time |  | 0.33 | 0.35 | 0.04 | 0 | 0
X-n172-k51 | cost | 45607 | 61768 | 60867 | 55635 | 61324 | 48634
| k |  | 69 | 66 | 56 | 63 | 57
| time |  | 0.37 | 0.39 | 0.05 | 0 | 0
X-n176-k26 | cost | 47812 | 55315 | 53233 | 52723 | 79892 | 52866
| k |  | 28 | 28 | 28 | 33 | 29
| time |  | 0.35 | 0.36 | 0.05 | 0 | 0
X-n181-k23 | cost | 25569 | 26255 | 26101 | 26101 | 33162 | 26561
| k |  | 23 | 23 | 23 | 23 | 23
| time |  | 0.35 | 0.38 | 0.05 | 0 | 0
X-n186-k15 | cost | 24145 | 25673 | 24683 | 24683 | 48964 | 25690
| k |  | 15 | 15 | 15 | 15 | 15
| time |  | 0.35 | 0.39 | 0.05 | 0 | 0
X-n190-k8 | cost | 16980 | 20053 | 19642 | 18550 | 40624 | 17816
| k |  | 8 | 8 | 8 | 8 | 8
| time |  | 0.55 | 0.38 | 0.05 | 0 | 0
X-n195-k51 | cost | 44225 | 51016 | 49771 | 48308 | 60623 | 45976
| k |  | 56 | 55 | 54 | 62 | 55
| time |  | 0.41 | 0.46 | 0.06 | 0 | 0
Table 19: Detailed Results on the Uchoa benchmark[20]. Instance |  | BKS | POMO[6] | VRPH |
---|---|---|---|---|---
n200 |  |  | single | multi | aug=8 | Sweep | Savings
X-n200-k36 | cost | 58578 | 63316 | 61811 | 61512 | 72574 | 61911
| k |  | 37 | 37 | 37 | 39 | 38
| time |  | 0.39 | 0.38 | 0.06 | 0 | 0
X-n204-k19 | cost | 19565 | 21581 | 20853 | 20657 | 33405 | 21004
| k |  | 20 | 19 | 19 | 19 | 19
| time |  | 0.37 | 0.37 | 0.06 | 0 | 0
X-n209-k16 | cost | 30656 | 33346 | 32316 | 32145 | 66836 | 32793
| k |  | 16 | 16 | 16 | 17 | 16
| time |  | 0.36 | 0.38 | 0.05 | 0 | 0
X-n214-k11 | cost | 10856 | 17074 | 14923 | 14129 | 25760 | 11949
| k |  | 20 | 15 | 14 | 12 | 12
| time |  | 0.38 | 0.38 | 0.06 | 0 | 0
X-n219-k73 | cost | 117595 | 164917 | 157869 | 148715 | 199383 | 172876
| k |  | 104 | 101 | 87 | 109 | 109
| time |  | 0.44 | 0.44 | 0.07 | 0 | 0
X-n223-k34 | cost | 40437 | 42884 | 42162 | 42161 | 56590 | 42639
| k |  | 34 | 35 | 35 | 37 | 36
| time |  | 0.4 | 0.4 | 0.06 | 0 | 0
X-n228-k23 | cost | 25742 | 30048 | 28727 | 27596 | 44883 | 27296
| k |  | 24 | 24 | 23 | 29 | 25
| time |  | 0.38 | 0.4 | 0.06 | 0 | 0
X-n233-k16 | cost | 19230 | 27044 | 25061 | 20983 | 33749 | 20585
| k |  | 17 | 17 | 17 | 17 | 17
| time |  | 0.38 | 0.4 | 0.06 | 0 | 0
X-n237-k14 | cost | 27042 | 29262 | 29041 | 28835 | 71726 | 30571
| k |  | 14 | 14 | 14 | 14 | 14
| time |  | 0.37 | 0.4 | 0.07 | 0 | 0
X-n242-k48 | cost | 82751 | 85689 | 85463 | 85325 | 123830 | 89918
| k |  | 48 | 48 | 48 | 55 | 52
| time |  | 0.4 | 0.41 | 0.07 | 0 | 0.01
X-n247-k50 | cost | 37274 | 76015 | 67888 | 50926 | 56494 | 41935
| k |  | 94 | 81 | 58 | 65 | 59
| time |  | 0.43 | 0.47 | 0.08 | 0 | 0.01
Table 20: Detailed Results on the Uchoa benchmark[20]. Instance |  | BKS | POMO[6] | VRPH |
---|---|---|---|---|---
n250 |  |  | single | multi | aug=8 | Sweep | Savings
X-n251-k28 | cost | 38684 | 41465 | 40784 | 40466 | 60078 | 40285
| k |  | 28 | 28 | 28 | 29 | 28
| time |  | 0.43 | 0.43 | 0.07 | 0 | 0.01
X-n256-k16 | cost | 18839 | 39858 | 29117 | 22825 | 28514 | 20518
| k |  | 35 | 23 | 19 | 17 | 17
| time |  | 0.42 | 0.41 | 0.08 | 0 | 0.01
X-n261-k13 | cost | 26558 | 30107 | 29300 | 28842 | 70523 | 28638
| k |  | 13 | 13 | 13 | 13 | 13
| time |  | 0.39 | 0.4 | 0.07 | 0 | 0.01
X-n266-k58 | cost | 75478 | 81464 | 80122 | 80122 | 115703 | 81046
| k |  | 60 | 60 | 60 | 67 | 64
| time |  | 0.41 | 0.44 | 0.08 | 0 | 0.01
X-n270-k35 | cost | 35291 | 39142 | 38535 | 38367 | 48710 | 37181
| k |  | 36 | 37 | 37 | 38 | 37
| time |  | 0.41 | 0.45 | 0.08 | 0 | 0.01
X-n275-k28 | cost | 21245 | 28811 | 25833 | 23360 | 35048 | 24177
| k |  | 32 | 29 | 28 | 31 | 31
| time |  | 0.41 | 0.42 | 0.08 | 0 | 0.01
X-n280-k17 | cost | 33503 | 36961 | 36503 | 35835 | 88461 | 35951
| k |  | 17 | 17 | 17 | 21 | 18
| time |  | 0.41 | 0.41 | 0.08 | 0 | 0.01
X-n284-k15 | cost | 20215 | 47812 | 38875 | 25404 | 44890 | 21924
| k |  | 35 | 24 | 16 | 15 | 15
| time |  | 0.44 | 0.45 | 0.09 | 0 | 0.01
X-n289-k60 | cost | 95151 | 104199 | 101303 | 99850 | 146744 | 99808
| k |  | 66 | 64 | 63 | 70 | 65
| time |  | 0.44 | 0.54 | 0.09 | 0 | 0.01
X-n294-k50 | cost | 47161 | 58954 | 55642 | 55011 | 67614 | 49307
| k |  | 54 | 53 | 53 | 56 | 53
| time |  | 0.43 | 0.47 | 0.1 | 0 | 0.01
X-n298-k31 | cost | 34231 | 39956 | 37929 | 37363 | 57847 | 35996
| k |  | 32 | 32 | 32 | 33 | 32
| time |  | 0.43 | 0.44 | 0.09 | 0 | 0.01

Table 21: Detailed Results on the Uchoa benchmark[20] (200 iterations). Instance |  | BKS | ORTools[14] | Meta-VRPH | DACT[8] | NeuroLS
---|---|---|---|---|---|---
n100 |  |  | GLS | TS | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | aug=1 | aug=8 | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
X-n101-k25 | cost | 27591 | 28906 | 29804 | 29181 | 29243 | 28845 | 29243 | 29674 | 30927 | 29562 | 28506 | 28444 | 28444
| k |  | 26 | 26 | 30 | 30 | 27 | 30 | 30 | 27 | 28 | 27 | 27 | 27
| time |  | 2.09 | 5.73 | 0.59 | 0.47 | 0.5 | 0.43 | 0.27 | 12.37 | 13.36 | 1.07 | 1.23 | 1.25
X-n106-k14 | cost | 26362 | 27182 | 27182 | 27099 | 27099 | 27442 | 27099 | 27442 | 28323 | 28085 | 26928 | 27057 | 27057
| k |  | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14
| time |  | 2.53 | 5.52 | 0.45 | 0.48 | 0.54 | 0.44 | 0.27 | 12.89 | 14.01 | 1.17 | 1.31 | 1.36
X-n110-k13 | cost | 14971 | 16266 | 15956 | 15883 | 15883 | 15883 | 15883 | 15883 | 17071 | 16376 | 15883 | 15738 | 15738
| k |  | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13
| time |  | 11.93 | 86.13 | 0.55 | 0.5 | 0.58 | 0.46 | 0.3 | 13.7 | 14.48 | 1.15 | 1.36 | 1.48
X-n115-k10 | cost | 12747 | 13169 | 13169 | 13567 | 13585 | 13553 | 13585 | 13585 | 15535 | 14454 | 13381 | 13382 | 13382
| k |  | 10 | 10 | 11 | 11 | 11 | 11 | 11 | 10 | 10 | 11 | 11 | 11
| time |  | 4.13 | 5.92 | 0.69 | 0.62 | 0.83 | 0.56 | 0.42 | 14.61 | 14.97 | 1.39 | 1.58 | 1.67
X-n120-k6 | cost | 13332 | 13988 | 13981 | 14643 | 14655 | 14745 | 14655 | 14745 | 15713 | 16316 | 14745 | 14487 | 14487
| k |  | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6
| time |  | 30.55 | 8.72 | 0.77 | 0.79 | 0.9 | 0.68 | 0.55 | 14.53 | 16.03 | 1.49 | 1.68 | 1.75
X-n125-k30 | cost | 55539 | 58333 | 58352 | 59239 | 59239 | 58461 | 59239 | 60561 | 60585 | 59489 | 57805 | 57774 | 57774
| k |  | 31 | 31 | 34 | 34 | 32 | 34 | 34 | 31 | 31 | 32 | 32 | 32
| time |  | 1.88 | 1.46 | 0.65 | 0.66 | 0.74 | 0.65 | 0.36 | 14.99 | 17.04 | 1.4 | 1.63 | 1.75
X-n129-k18 | cost | 28940 | 31063 | 30827 | 30407 | 30407 | 30407 | 30407 | 30407 | 33014 | 32825 | 30407 | 30407 | 30407
| k |  | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18
| time |  | 11.15 | 30.97 | 0.73 | 0.67 | 0.77 | 0.6 | 0.36 | 15.68 | 17.41 | 1.46 | 1.67 | 1.74
X-n134-k13 | cost | 10916 | 12514 | 12520 | 11415 | 11415 | 11415 | 11415 | 11415 | 13240 | 13182 | 11415 | 11415 | 11415
| k |  | 13 | 13 | 14 | 14 | 14 | 14 | 14 | 15 | 14 | 14 | 14 | 14
| time |  | 3.76 | 10.06 | 0.86 | 0.79 | 0.94 | 0.7 | 0.4 | 16 | 18.18 | 1.64 | 1.85 | 2.03
X-n139-k10 | cost | 13590 | 14995 | 14560 | 14726 | 14726 | 14726 | 14726 | 14726 | 16436 | 15261 | 14635 | 14552 | 14552
| k |  | 10 | 10 | 11 | 11 | 11 | 11 | 11 | 13 | 11 | 10 | 10 | 10
| time |  | 13.36 | 261.77 | 0.93 | 0.82 | 0.98 | 0.76 | 0.43 | 16.6 | 18.05 | 1.65 | 1.93 | 1.9
X-n143-k7 | cost | 15700 | 17544 | 17258 | 17598 | 17598 | 17126 | 17544 | 17664 | 20067 | 19960 | 16932 | 17243 | 17243
| k |  | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7
| time |  | 10.22 | 7.38 | 1.12 | 1.09 | 1.29 | 1.03 | 0.82 | 17.08 | 18.57 | 2.01 | 2.24 | 2.17
X-n148-k46 | cost | 43448 | 47362 | 47362 | 47593 | 47593 | 47789 | 47606 | 48048 | 46923 | 47938 | 46788 | 46891 | 46891
| k |  | 46 | 46 | 53 | 53 | 51 | 53 | 53 | 49 | 48 | 51 | 49 | 49
| time |  | 11.84 | 5.44 | 0.79 | 0.81 | 1.02 | 0.78 | 0.45 | 18.02 | 20.12 | 1.65 | 1.96 | 2.02
Table 22: Detailed Results on the Uchoa benchmark[20] (200 iterations). Instance |  | BKS | ORTools[14] | Meta-VRPH | DACT[8] | NeuroLS
---|---|---|---|---|---|---
n100 |  |  | GLS | TS | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | aug=1 | aug=8 | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
X-n153-k22 | cost | 21220 | 24812 | 24812 | 22597 | 22597 | 22649 | 22597 | 22649 | 26294 | 25312 | 22587 | 22548 | 22548
| k |  | 25 | 25 | 26 | 26 | 26 | 26 | 26 | 26 | 25 | 26 | 26 | 26
| time |  | 0.74 | 0.76 | 1.12 | 1.01 | 1.27 | 0.93 | 0.49 | 19.78 | 20.39 | 2.09 | 2.24 | 2.21
X-n157-k13 | cost | 16876 | 17257 | 17286 | 18963 | 18963 | 19050 | 19171 | 19171 | 18556 | 18352 | 18782 | 18810 | 18810
| k |  | 13 | 13 | 15 | 15 | 15 | 15 | 15 | 13 | 13 | 15 | 15 | 15
| time |  | 13.77 | 10.37 | 0.96 | 1.01 | 1.2 | 0.86 | 0.49 | 19.44 | 20.86 | 1.98 | 2.16 | 2.08
X-n162-k11 | cost | 14138 | 14782 | 14920 | 14898 | 14898 | 15227 | 14898 | 15708 | 17539 | 16034 | 14958 | 14847 | 14847
| k |  | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 12 | 12 | 11 | 11 | 11
| time |  | 11.89 | 629.62 | 1.26 | 1.22 | 1.36 | 1.21 | 0.6 | 19.65 | 21.05 | 2.1 | 2.41 | 2.71
X-n167-k10 | cost | 20557 | 22629 | 22678 | 21656 | 21656 | 22004 | 22004 | 22004 | 25399 | 25062 | 21695 | 21836 | 21836
| k |  | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10
| time |  | 17.69 | 7.74 | 1.4 | 1.44 | 1.64 | 1.16 | 0.72 | 19.95 | 22.11 | 2.37 | 2.64 | 2.67
X-n172-k51 | cost | 45607 | 50686 | 50779 | 47924 | 47924 | 47790 | 47924 | 47921 | 55282 | 51166 | 47125 | 46846 | 46846
| k |  | 52 | 52 | 57 | 57 | 54 | 57 | 57 | 55 | 54 | 53 | 54 | 54
| time |  | 8.46 | 71.76 | 1.1 | 1.08 | 1.32 | 1.04 | 0.62 | 21 | 24.02 | 2.09 | 2.45 | 2.79
X-n176-k26 | cost | 47812 | 55614 | 55614 | 51382 | 51382 | 50872 | 51433 | 51783 | 61411 | 60630 | 51241 | 50822 | 50822
| k |  | 27 | 27 | 29 | 29 | 28 | 29 | 29 | 29 | 29 | 28 | 28 | 28
| time |  | 0.66 | 0.63 | 1.43 | 1.39 | 1.54 | 1.25 | 0.64 | 21.13 | 23.29 | 2.46 | 2.68 | 2.78
X-n181-k23 | cost | 25569 | 26346 | 26277 | 26355 | 26355 | 26561 | 26352 | 26561 | 27557 | 27939 | 26324 | 26301 | 26301
| k |  | 23 | 23 | 23 | 23 | 23 | 23 | 23 | 23 | 23 | 23 | 23 | 23
| time |  | 33.52 | 274.17 | 1.17 | 1.19 | 1.4 | 1.17 | 0.54 | 21.94 | 23.81 | 2.38 | 2.56 | 2.66
X-n186-k15 | cost | 24145 | 26063 | 26073 | 25690 | 25690 | 25690 | 25690 | 25690 | 28652 | 28979 | 25595 | 25493 | 25493
| k |  | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 16 | 15 | 15 | 15
| time |  | 12.37 | 91.63 | 1.5 | 1.35 | 1.71 | 1.27 | 0.66 | 22.14 | 24.14 | 2.59 | 2.89 | 2.99
X-n190-k8 | cost | 16980 | 17949 | 17949 | 17742 | 17742 | 17816 | 17742 | 17816 | 19990 | 20064 | 17709 | 17689 | 17689
| k |  | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8
| time |  | 7.86 | 6.1 | 2.16 | 2.1 | 2.37 | 1.87 | 1.67 | 23.28 | 24.99 | 3.4 | 3.59 | 3.58
X-n195-k51 | cost | 44225 | 49975 | 49975 | 45976 | 45976 | 45976 | 45976 | 45976 | 52594 | 52788 | 45612 | 45520 | 45520
| k |  | 52 | 52 | 55 | 55 | 55 | 55 | 55 | 53 | 54 | 54 | 54 | 54
| time |  | 2.03 | 2.06 | 1.37 | 1.3 | 1.6 | 1.23 | 0.66 | 23.5 | 26.25 | 2.5 | 2.92 | 3.01
Table 23: Detailed Results on the Uchoa benchmark[20] (200 iterations). Instance |  | BKS | ORTools[14] | Meta-VRPH | DACT[8] | NeuroLS
---|---|---|---|---|---|---
n100 |  |  | GLS | TS | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | aug=1 | aug=8 | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
X-n200-k36 | cost | 58578 | 61080 | 61080 | 60902 | 60913 | 61051 | 60920 | 61911 | 64205 | 64746 | 60373 | 60337 | 60337
| k |  | 37 | 37 | 38 | 38 | 38 | 38 | 38 | 37 | 38 | 37 | 37 | 37
| time |  | 4.99 | 9.32 | 1.57 | 1.49 | 1.65 | 1.35 | 0.66 | 24.31 | 26.05 | 2.76 | 3.03 | 3.12
X-n204-k19 | cost | 19565 | 21828 | 21922 | 20906 | 20970 | 21004 | 21004 | 21004 | 24188 | 23259 | 20925 | 20587 | 20587
| k |  | 19 | 19 | 19 | 19 | 19 | 19 | 19 | 20 | 19 | 19 | 19 | 19
| time |  | 25.3 | 12.72 | 1.71 | 1.58 | 2.02 | 1.55 | 0.7 | 25.05 | 28.41 | 2.88 | 3.26 | 3.41
X-n209-k16 | cost | 30656 | 32553 | 32724 | 32793 | 32793 | 32793 | 32793 | 32793 | 35254 | 36933 | 32636 | 32602 | 32602
| k |  | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16
| time |  | 10.64 | 59.37 | 1.77 | 1.71 | 2.18 | 1.6 | 0.81 | 25.14 | 27.97 | 3.25 | 3.52 | 3.63
X-n214-k11 | cost | 10856 | 12498 | 12507 | 11910 | 11949 | 11949 | 11949 | 11949 | 14626 | 14231 | 11756 | 11915 | 11915
| k |  | 11 | 11 | 12 | 12 | 12 | 12 | 12 | 11 | 12 | 12 | 12 | 12
| time |  | 16.36 | 17.37 | 2.36 | 2.07 | 2.65 | 1.94 | 1.21 | 26.41 | 27.61 | 3.79 | 4.06 | 4.1
X-n219-k73 | cost | 117595 | 118423 | 118373 | 172876 | 172876 | 172876 | 172876 | 172876 | 120142 | 120293 | 172876 | 172876 | 172876
| k |  | 73 | 73 | 109 | 109 | 109 | 109 | 109 | 73 | 73 | 109 | 109 | 109
| time |  | 77.09 | 1280.43 | 1.41 | 1.39 | 1.79 | 1.31 | 0.72 | 26.31 | 28.92 | 2.81 | 3.22 | 3.35
X-n223-k34 | cost | 40437 | 44320 | 44320 | 42343 | 42343 | 42639 | 42299 | 42639 | 51570 | 47983 | 42190 | 42230 | 42230
| k |  | 34 | 34 | 36 | 36 | 36 | 36 | 36 | 35 | 34 | 35 | 35 | 35
| time |  | 1.57 | 1.61 | 1.82 | 1.81 | 2.17 | 1.74 | 0.8 | 27.24 | 28.34 | 3.28 | 3.68 | 3.55
X-n228-k23 | cost | 25742 | 32143 | 32143 | 27076 | 27076 | 27296 | 27105 | 27296 | 35231 | 33820 | 27064 | 26996 | 26996
| k |  | 23 | 23 | 25 | 25 | 25 | 25 | 25 | 25 | 26 | 24 | 24 | 24
| time |  | 1.49 | 1.58 | 2.36 | 2.29 | 2.61 | 2.19 | 0.93 | 28.31 | 30.94 | 3.78 | 4.12 | 4.18
X-n233-k16 | cost | 19230 | 23128 | 23128 | 20478 | 20585 | 20585 | 20585 | 20585 | 27821 | 25915 | 20432 | 20385 | 20385
| k |  | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 20 | 18 | 17 | 17 | 17
| time |  | 2.08 | 2.25 | 2.41 | 2.38 | 3.05 | 2.19 | 1.15 | 29.32 | 30.83 | 4.31 | 4.74 | 4.99
X-n237-k14 | cost | 27042 | 29175 | 29175 | 30341 | 30341 | 30571 | 30433 | 30571 | 32205 | 32948 | 30003 | 29828 | 29828
| k |  | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14.00 | 14 | 14 | 14
| time |  | 4.81 | 4.86 | 2.46 | 2.45 | 2.95 | 2.32 | 1.19 | 29.15 | 31.69 | 4.09 | 4.75 | 4.59
X-n242-k48 | cost | 82751 | 87069 | 87069 | 88179 | 88179 | 88320 | 88179 | 88696 | 95420 | 94,852.00 | 86973 | 87097 | 87097
| k |  | 48 | 48 | 52 | 52 | 52 | 52 | 52 | 48 | 48.00 | 50 | 50 | 50
| time |  | 1.64 | 1.66 | 2.08 | 2.07 | 2.48 | 2.13 | 0.95 | 29.05 | 32.75 | 3.75 | 4.19 | 4.06
X-n247-k50 | cost | 37274 | 44134 | 44134 | 40022 | 40022 | 39246 | 40123 | 40508 | 48507 | 46782 | 39514 | 39349 | 39349
| k |  | 52 | 52 | 59 | 59 | 55 | 59 | 59 | 54 | 54 | 55 | 55 | 55
| time |  | 1.02 | 0.99 | 2.68 | 2.71 | 3.01 | 2.4 | 1.19 | 28.92 | 33.92 | 4.4 | 4.88 | 5.06
Table 24: Detailed Results on the Uchoa benchmark[20] (200 iterations). Instance |  | BKS | ORTools[14] | Meta-VRPH | DACT[8] | NeuroLS
---|---|---|---|---|---|---
n100 |  |  | GLS | TS | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | aug=1 | aug=8 | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
X-n251-k28 | cost | 38684 | 40417 | 40424 | 40279 | 40285 | 40285 | 40285 | 40285 | 42297 | 42545 | 40285 | 40285 | 40285
| k |  | 28 | 28 | 28 | 28 | 28 | 28 | 28 | 28 | 28 | 28 | 28 | 28
| time |  | 14.7 | 32.3 | 2.63 | 2.23 | 2.82 | 2.09 | 0.95 | 30.17 | 34.44 | 4.04 | 4.73 | 4.5
X-n256-k16 | cost | 18839 | 21363 | 21361 | 20518 | 20518 | 20518 | 20518 | 20518 | 23949 | 22469 | 20390 | 20185 | 20185
| k |  | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 17
| time |  | 5.47 | 5.27 | 3.11 | 2.66 | 3.94 | 2.49 | 1.24 | 31.66 | 35.04 | 4.98 | 5.31 | 5.54
X-n261-k13 | cost | 26558 | 30665 | 30665 | 28638 | 28638 | 28638 | 28638 | 28638 | 36604 | 34448 | 28638 | 28638 | 28638
| k |  | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 14 | 13 | 13 | 13
| time |  | 4.07 | 4.2 | 3.51 | 3.33 | 4.12 | 3 | 1.86 | 31.61 | 36.04 | 5.49 | 6.09 | 6.72
X-n266-k58 | cost | 75478 | 80064 | 80064 | 80553 | 80553 | 80792 | 80657 | 80979 | 83468 | 83310 | 79913 | 79308 | 79308
| k |  | 59 | 59 | 64 | 64 | 64 | 64 | 64 | 61 | 61 | 62 | 61 | 61
| time |  | 6.33 | 5.7 | 2.34 | 2.36 | 2.85 | 2.22 | 1.04 | 32 | 36.59 | 4.54 | 4.94 | 5.28
X-n270-k35 | cost | 35291 | 39152 | 39152 | 37181 | 37181 | 37181 | 37181 | 37181 | 40547 | 40415 | 36862 | 36529 | 36529
| k |  | 36 | 36 | 37 | 37 | 37 | 37 | 37 | 37 | 37 | 36 | 36 | 36
| time |  | 5.67 | 5.22 | 2.78 | 2.36 | 3.13 | 2.39 | 1.08 | 32.6 | 37.08 | 4.59 | 5.21 | 5.53
X-n275-k28 | cost | 21245 | 22562 | 22591 | 23907 | 23907 | 24177 | 24177 | 24177 | 26052 | 26044 | 23961 | 23776 | 23776
| k |  | 28 | 28 | 31 | 31 | 31 | 31 | 31 | 31 | 32 | 31 | 31 | 31
| time |  | 9.36 | 15.92 | 2.87 | 2.82 | 3.33 | 2.56 | 1.08 | 32.71 | 37.01 | 4.86 | 5.49 | 5.66
X-n280-k17 | cost | 33503 | 40878 | 40878 | 35951 | 35951 | 35951 | 35951 | 35951 | 46179 | 45719 | 35531 | 35760 | 35760
| k |  | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 17 | 18 | 18
| time |  | 1.7 | 1.69 | 4.5 | 3.64 | 4.95 | 3.52 | 2 | 33.58 | 38.56 | 6.47 | 7.23 | 7.27
X-n284-k15 | cost | 20215 | 23695 | 23695 | 21924 | 21924 | 21924 | 21924 | 21924 | 26201 | 26436 | 21891 | 21757 | 21757
| k |  | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 16 | 15 | 15 | 15
| time |  | 1.98 | 1.87 | 4.01 | 3.91 | 4.78 | 3.48 | 2.12 | 33.8 | 39.2 | 6.55 | 7.24 | 7.84
X-n289-k60 | cost | 95151 | 103936 | 103936 | 98648 | 98824 | 98743 | 98686 | 99808 | 117218 | 113473 | 97618 | 98070 | 98070
| k |  | 62 | 62 | 65 | 65 | 65 | 65 | 65 | 62 | 63 | 63 | 63 | 63
| time |  | 2.06 | 1.51 | 3.39 | 2.99 | 3.62 | 2.9 | 1.29 | 34.1 | 39.93 | 5.35 | 6.21 | 5.92
X-n294-k50 | cost | 47161 | 54834 | 54834 | 49169 | 49307 | 49307 | 49307 | 49307 | 66687 | 62413 | 48934 | 48947 | 48947
| k |  | 51 | 51 | 53 | 53 | 53 | 53 | 53 | 59 | 54 | 52 | 52 | 52
| time |  | 1.57 | 1.48 | 3.51 | 2.99 | 3.61 | 2.77 | 1.31 | 35.26 | 39.9 | 5.39 | 6.22 | 6.08
X-n298-k31 | cost | 34231 | 42908 | 42908 | 35996 | 35996 | 35996 | 35996 | 35996 | 48423 | 46636 | 35617 | 35767 | 35767
| k |  | 31 | 31 | 32 | 32 | 32 | 32 | 32 | 31 | 32 | 32 | 32 | 32
| time |  | 1.76 | 2.15 | 3.58 | 3.18 | 4.1 | 3.03 | 1.37 | 35.89 | 41.82 | 5.74 | 6.44 | 7.07
Table 25: Detailed Results on the Uchoa benchmark[20] (500 iterations). Instance |  | BKS | ORTools[14] | Meta-VRPH | DACT[8] | NeuroLS
---|---|---|---|---|---|---
n100 |  |  | GLS | TS | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | aug=1 | aug=8 | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
X-n101-k25 | cost | 27591 | 28725 | 29430 | 29181 | 29211 | 28845 | 29243 | 29674 | 29561 | 29554 | 28458 | 28309 | 28309
| k |  | 26 | 26 | 30 | 30 | 27 | 30 | 30 | 27 | 27 | 27 | 27 | 27
| time |  | 18.79 | 134.68 | 1.08 | 1.06 | 1.31 | 1.01 | 0.71 | 31.32 | 34.52 | 2.32 | 2.75 | 2.74
X-n106-k14 | cost | 26362 | 27182 | 27182 | 27099 | 27099 | 27442 | 27099 | 27442 | 28052 | 28085 | 26875 | 26747 | 26747
| k |  | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14
| time |  | 20.28 | 38.39 | 1.15 | 1.19 | 1.34 | 1.14 | 0.77 | 32.58 | 36.42 | 2.62 | 2.96 | 2.79
X-n110-k13 | cost | 14971 | 15698 | 15568 | 15883 | 15883 | 15883 | 15883 | 15883 | 16389 | 16170 | 15612 | 15738 | 15738
| k |  | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13
| time |  | 36.63 | 199.29 | 1.23 | 1.21 | 1.4 | 1.11 | 0.73 | 32.8 | 37.45 | 2.57 | 3.04 | 3.06
X-n115-k10 | cost | 12747 | 13169 | 13138 | 13567 | 13585 | 13553 | 13585 | 13585 | 15033 | 13868 | 13362 | 13382 | 13382
| k |  | 10 | 10 | 11 | 11 | 11 | 11 | 11 | 11 | 10 | 11 | 11 | 11
| time |  | 31.74 | 917.03 | 1.56 | 1.58 | 1.84 | 1.4 | 0.98 | 33.91 | 38.87 | 3.07 | 3.58 | 3.54
X-n120-k6 | cost | 13332 | 13899 | 13730 | 14643 | 14655 | 14745 | 14655 | 14745 | 15713 | 16047 | 14554 | 14456 | 14456
| k |  | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6
| time |  | 85.32 | 740.25 | 1.76 | 1.89 | 2.11 | 1.61 | 1.43 | 35.76 | 40.68 | 3.27 | 4 | 3.85
X-n125-k30 | cost | 55539 | 57951 | 57916 | 59239 | 59239 | 57845 | 59239 | 60561 | 60115 | 59489 | 57597 | 57549 | 57549
| k |  | 31 | 31 | 34 | 34 | 31 | 34 | 34 | 32 | 31 | 32 | 32 | 32
| time |  | 25.07 | 145 | 1.57 | 1.6 | 1.91 | 1.53 | 0.95 | 38 | 43.3 | 3.11 | 3.71 | 3.69
X-n129-k18 | cost | 28940 | 31061 | 30448 | 30407 | 30407 | 30407 | 30407 | 30407 | 32572 | 32832 | 30302 | 30407 | 30407
| k |  | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18 | 18
| time |  | 37.55 | 171.38 | 1.71 | 1.58 | 1.99 | 1.54 | 0.95 | 38.36 | 43.12 | 3.2 | 3.82 | 3.79
X-n134-k13 | cost | 10916 | 11964 | 12152 | 11415 | 11415 | 11415 | 11415 | 11415 | 13140 | 13182 | 11374 | 11320 | 11320
| k |  | 13 | 13 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 13 | 13 | 13
| time |  | 28.02 | 183.34 | 1.9 | 1.91 | 2.23 | 1.78 | 1.06 | 40.06 | 45.47 | 3.75 | 4.3 | 4.22
X-n139-k10 | cost | 13590 | 14489 | 14457 | 14726 | 14726 | 14619 | 14726 | 14726 | 15616 | 15261 | 14635 | 14514 | 14514
| k |  | 10 | 10 | 11 | 11 | 10 | 11 | 11 | 13 | 11 | 10 | 10 | 10
| time |  | 47.74 | 1779.76 | 2.06 | 2.11 | 2.49 | 1.84 | 1.15 | 41.82 | 46.71 | 3.78 | 4.48 | 4.43
X-n143-k7 | cost | 15700 | 16975 | 16675 | 17598 | 17598 | 17126 | 17115 | 17664 | 20067 | 19499 | 16847 | 16696 | 16696
| k |  | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7
| time |  | 40.74 | 1105.7 | 2.51 | 2.53 | 3.16 | 2.54 | 2.18 | 41.76 | 47.04 | 4.63 | 5.25 | 5.27
X-n148-k46 | cost | 43448 | 47003 | 46473 | 47593 | 47494 | 47621 | 47606 | 48048 | 46059 | 46905 | 46788 | 46653 | 46653
| k |  | 46 | 46 | 53 | 53 | 50 | 53 | 53 | 48 | 48 | 51 | 49 | 49
| time |  | 63.94 | 369.25 | 1.88 | 1.97 | 2.33 | 1.84 | 1.24 | 46.1 | 50.66 | 3.71 | 4.55 | 4.6
Table 26: Detailed Results on the Uchoa benchmark[20] (500 iterations). Instance |  | BKS | ORTools[14] | Meta-VRPH | DACT[8] | NeuroLS
---|---|---|---|---|---|---
n100 |  |  | GLS | TS | SA | SA${}_{\text{re}}$ | ILS | ILS+SA | VNS | aug=1 | aug=8 | NLS${}_{\text{A}}$ | NLS${}_{\text{AN}}$ | NLS${}_{\text{ANP}}$
X-n153-k22 | cost | 21220 | 22507 | 22670 | 22597 | 22597 | 22649 | 22597 | 22649 | 25709 | 24538 | 22587 | 22495 | 22495
| k |  | 25 | 25 | 26 | 26 | 26 | 26 | 26 | 25 | 24 | 26 | 25 | 25
| time |  | 19.98 | 327.65 | 2.55 | 2.52 | 3.16 | 2.3 | 1.25 | 46.37 | 51.29 | 4.78 | 5.23 | 5.5
X-n157-k13 | cost | 16876 | 17238 | 17286 | 18963 | 18963 | 19050 | 19171 | 19171 | 18556 | 18352 | 18782 | 18696 | 18696
| k |  | 13 | 13 | 15 | 15 | 15 | 15 | 15 | 13 | 13 | 15 | 15 | 15
| time |  | 47.88 | 564.82 | 2.31 | 2.32 | 2.93 | 2.11 | 1.19 | 48.52 | 52.49 | 4.51 | 5.04 | 5.55
X-n162-k11 | cost | 14138 | 14782 | 14746 | 14898 | 14898 | 15215 | 14898 | 15708 | 17524 | 16034 | 14958 | 14847 | 14847
| k |  | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 12 | 12 | 11 | 11 | 11
| time |  | 79.83 | 3074.87 | 2.97 | 2.81 | 3.45 | 2.66 | 1.53 | 49.46 | 54.97 | 5.01 | 5.74 | 5.8
X-n167-k10 | cost | 20557 | 22561 | 22394 | 21656 | 21656 | 22004 | 22004 | 22004 | 24880 | 25062 | 21695 | 21836 | 21836
| k |  | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10
| time |  | 101 | 2112.88 | 3.25 | 3.24 | 3.96 | 2.82 | 1.93 | 50.64 | 55.89 | 5.53 | 6.4 | 6.45
X-n172-k51 | cost | 45607 | 49782 | 48519 | 47924 | 47924 | 47790 | 47924 | 47921 | 50753 | 49283 | 47114 | 46846 | 46846