Many-Objective Pareto Local Search
Andrzej Jaszkiewicz

arXiv:1707.07899v2 [cs.DS] 14 Dec 2017

Poznan University of Technology, Faculty of Computing, Institute of Computing Science,
ul. Piotrowo 2, 60-965 Poznan, andrzej.jaszkiewicz@put.poznan.pl

Abstract
We propose a new Pareto Local Search Algorithm for the many-objective
combinatorial optimization. Pareto Local Search proved to be a very effective tool in the case of the bi-objective combinatorial optimization and
it was used in a number of the state-of-the-art algorithms for problems of
this kind. On the other hand, the standard Pareto Local Search algorithm
becomes very inefficient for problems with more than two objectives. We
build an effective Many-Objective Pareto Local Search algorithm using three
new mechanisms: the efficient update of large Pareto archives with ND-Tree
data structure, a new mechanism for the selection of the promising solutions
for the neighborhood exploration, and a partial exploration of the neighborhoods. We apply the proposed algorithm to the instances of two different
problems, i.e. the traveling salesperson problem and the traveling salesperson problem with profits with up to 5 objectives showing high effectiveness
of the proposed algorithm.
Keywords: Metaheuristics, Multiobjective optimization, Combinatorial
optimization, Pareto Local Search
1. Introduction
Combinatorial optimization problems find numerous applications in transportation, logistics, scheduling, design, etc. (Yu, 2013). On the other hand,
real-life optimization problems often require taking into account multiple
points of view corresponding to multiple objectives. Since, multiple objective combinatorial optimization problems are usually NP-Hard, multiobjective metaheuristics are often used to solve them approximately (Talbi et al.,
2012).

Preprint submitted to European Journal of Operational Research

December 15, 2017

Effective single objective algorithms for combinatorial optimization problems usually use some kind of local search as one of their components. Pareto
Local Search (PLS) (Angel et al., 2004; Paquete & Stutzle, 2006; Paquete
et al., 2007) is a very natural extension of the concept of the local search
to the multiobjective case. PLS works with a Pareto archive, i.e. a set of
potentially Pareto-optimal solutions that are not dominated by any other
solution obtained so far. PLS explores neighborhood of each solution in the
archive and uses the neighbor solutions to update the Pareto archive.
Alike the single objective local search, PLS when used as a standalone
algorithm started with an initial archive of a low quality is not very effective,
however, it is an important component of a number of the state-of-the-art hybrid algorithms e.g. for the bi-objective knapsack (Lust & Teghem, 2012), the
bi-objective traveling salesperson problem (TSP) (Lust & Teghem, 2010; Lust
& Jaszkiewicz, 2010; Liangjun et al., 2014; Jaszkiewicz & Lust, 2017; Cornu
et al., 2017), various bi-objective permutation flowshop problems (DuboisLacoste et al., 2011), the bi-objective set covering problem (Lust & Tuyttens,
2014), and the risk-cost optimization for procurement planning (Mori et al.,
2017).
The effectiveness of PLS as a component of the hybrid algorithms may
be explained by the fact that it has different characteristics than most other
multiobjective metaheuristics. As noticed by Lara et al. (2010) each multiobjective metaheuristic should search both towards and along the Pareto
front. The search towards the Pareto front means generating new solutions
lying closer to the Pareto front than known solutions, and the search along
the Pareto front means generating new potentially Pareto-optimal solutions
improving the representation of the Pareto front. PLS is very effective in the
search along Pareto front when started from a seed of high quality solutions.
For example in the case of the bi-objective traveling salesperson problem
such a seed may be generated with the use of the Lin-Kernighan (Lin &
Kernighan, 1973) heuristic (Lust & Teghem, 2010; Lust & Jaszkiewicz, 2010;
Liangjun et al., 2014; Cornu et al., 2017).
The standard PLS algorithm becomes, however, very inefficient in the case
of more than two objectives because the number of Pareto-optimal solutions
grows very fast with the number of objectives. Thus PLS has to search neighborhoods of a huge number of solutions and the process of updating large
Pareto archives with new solutions becomes very time-consuming. Indeed,
with very few exceptions (e.g. Liangjun et al. (2014); Cornu et al. (2017)),
majority of the publications on PLS concerns bi-objective optimization only.
2

In this paper we propose a new Many-objective PLS algorithm (MPLS)
dedicated to the problems with more than two objectives. Please note, that
we use the term ”Many-objective” in somehow non-standard way, since it
usually describes problems with ≥ 4 objectives (Chand & Wagner, 2015).
However, in the context of PLS, three objectives is already a high number.
The proposed algorithm is based on the following three new mechanisms
that differ it from the standard PLS:
• The use of a recently proposed ND-Tree data structure (Jaszkiewicz &
Lust, 2016) for the efficient update of the Pareto archive.
• The use of a new mechanism for the selection of the promising solutions for the exploration of their neighborhoods based on the randomly
selected weighted Chebycheff scalarizing functions.
• The partial exploration of the neighborhoods, i.e. testing only some of
the neighborhood solutions.
The first mechanism reduces the time needed to update the Pareto archive,
while the two latter mechanisms improve the quality of the archive with a
limited number of the neighborhood solutions tested.
We apply MPLS to two different multiobjective combinatorial optimization problems: the multiobjective traveling salesperson problem (MTSP) and
the multiobjective traveling salesperson problem with profits (MTSPWP)
with up to 5 objectives. Through a computational study we show that
MPLS produces archives of much better quality than the standard PLS in the
same time. We also show that each of the three new mechanisms described
above contributes to the effectiveness of the proposed method. Furthermore,
since for the bi-objective traveling salesperson problem the best results have
been obtained by properly balancing the CPU time assigned to the LinKernighan heuristic and to PLS (Lust & Teghem, 2010; Lust & Jaszkiewicz,
2010; Liangjun et al., 2014; Jaszkiewicz & Lust, 2017; Cornu et al., 2017) we
test whether a similar situation holds in the case of MTSP with more than
two objectives.
The paper is organized in the following way. In the next section we describe the proposed Many-objective Pareto Local Search algorithm. Then
the computational experiment is presented. In section 4, related works are
discussed. Finally, conclusions and directions for further research are presented.
3

2. Many-objective Pareto Local Search algorithm
We start the description of the proposed MPLS algorithm with a short
presentation of the standard PLS that is a basis for our algorithm. Then we
describe the three new mechanisms used in MPLS. Finally, we present the
whole algorithm of MPLS.
2.1. Pareto Local Search
PLS is a relatively straightforward adaptation of the idea of the single
objective local search to the multiobjective case. In PLS the acceptance of
a new neighborhood solution is based on the dominance relation.
Consider a general multiobjective optimization problem with a feasible
set X and d objective functions yk (x). Without loss of generality we assume
that the objectives are maximized. The image of a feasible solution x in the
objective space Rd is a point y(x) = (y1 (x), y2 (x), . . . , yd (x)). We say that
a point y 1 ∈ Rd dominates a point y 2 ∈ Rd if, and only if, yj1 ≥ yj2 ∀ j ∈
{1, . . . , d} ∧ ∃ j ∈ {1, . . . , d} : yj1 > yj2 . We denote this relation by y 1  y 2 .
For the sake of simplicity we will use the dominance relation with respect
to the corresponding solutions as well. The solutions not dominated by any
other feasible solution are called Pareto-optimal and the image of the set of
Pareto-optimal solutions in the objective space is the Pareto front.
A set of distinct and mutually non-dominated solutions, i.e. solutions
such that none of them dominates any other, is called a Pareto archive.
In the context of multiobjective metaheuristics the Pareto archive is used to
store the set of potentially Pareto-optimal solutions generated by the method
till a given iteration.
PLS works with a Pareto archive. It starts with some initial Pareto
archive and then searches whole neighborhoods of all solutions whose neighborhoods have not been searched yet for new potentially Pareto-optimal solutions until no such new solution can be found in any of the neighborhoods
(see Algorithm 1 based on the particular version of PLS used e.g. in Lust &
Teghem (2010)).
2.2. Mechanism I: Efficient update of the Pareto archive with the use of NDTree
Whenever a new neighbor solution not dominated by the current solution
is found, the Pareto archive needs to be updated. Updating a Pareto archive
A with a new solution x0 means that:
4

Algorithm 1 PLS
Parameter l: A: an initial Pareto archive
P ←A
Pa ← ∅
while P 6= ∅ do
for all x ∈ P do
for all x0 ∈ N (x) do
if y(x)  y(x0 ) and y(x) 6= y(x0 ) then
if Update(A l,x0 ↓) then
Pa ← Pa ∪ {x0 }
end if
end if
end for
end for
P ← Pa
Pa ← ∅
end while
where N (x) denotes the neighborhood of x and Update() updates the
Pareto archive A.
• x0 is added to A if it is not dominated nor equal to any solution in A,
• all solutions dominated by x0 are removed from A.
Since the neighborhood solutions for many combinatorial problems may
be generated in a very short time and the number of Pareto-optimal solutions
grows fast with growing number of objectives, the process of updating the
Pareto archive may easily become the main factor influencing the running
time of PLS.
The simplest approach to the update of the Pareto archive is to organize
it as a simple list of solutions and compare the new solution to each solution
in this list until a dominating or equal solution has been found or all solutions
have been compared. This approach is, however, very time consuming for
large Pareto archives. In the bi-objective case the Pareto archive may be
efficiently updated using the binary search in an archive sorted according
to the values of the objectives (Jaszkiewicz & Lust, 2016). This approach,
5

however, cannot be extended to the case of more than two objectives.
In MPLS we use a recently proposed ND-Tree data structure (Jaszkiewicz
& Lust, 2016). In ND-Tree the Pareto archive is recursively split into disjoint
subsets. For each subset approximate local ideal and approximate local nadir
points, i.e. points in the objective space respectively dominating and dominated by all solutions in this subset, are kept. In other words, all solutions
from each subset are contained in the hyper-box defined by the two points.
These hyper-boxes may in general overlap, but the tree is built such that the
subsets contain close solutions contained in small hyper-boxes. By comparing
the new solution to the approximate local ideal and the approximate local
nadir points many branches of the tree can be omitted. The computational
complexity of updating the Pareto archive with ND-Tree is sub-linear with
respect to the size of the archive for any number of objectives under mild
assumptions (Jaszkiewicz & Lust, 2016). Thus the overall running time of
MPLS can be significantly reduced with the use of this data structure.
2.3. Mechanism II: Selection of the promising solutions for the exploration
of their neighborhoods
The standard PLS algorithm ends-up with a Pareto-archive being locally
optimal, i.e. when no solution being a neighbor of any solution in the archive
can improve this archive. Obtaining a locally optimal Pareto-archive is,
however, usually prohibitively time-consuming in the case of three and more
objectives even with the use of ND-Tree. On the other hand, the algorithm
when stopped earlier may produce an archive of a low quality, because there
could be high variations in the CPU times spent in exploring various regions
of the Pareto front. Dubois-Lacoste et al. (2011, 2015) proposed anytime
PLS algorithm for the bi-objective case whose goal is to generate archives
of a good quality at any iteration. One of the main mechanisms of that
algorithm is the selection of solutions whose neighborhood exploration has a
high potential to improve the current archive. Dubois-Lacoste et al. use the
so-called optimistic hypervolume to select such solutions in the bi-objective
case. This mechanism, however, cannot be directly extended to the case
of more than two objectives. Thus, we propose a new selection mechanism
described below.
In each iteration we would like to generate a new solution highly improving the quality of the Pareto archive. Since the neighbor solutions are
usually similar to the original solutions, it is natural to expect that new good
solutions may be found in the neighborhoods of known good solutions.
6

Assume that an indicator of the quality of the Pareto archive is used.
A good solution is a solution that substantially contributes to the value of
this indicator, i.e. its removal would substantially deteriorate the value of
this indicator. A number of indicators for the evaluation of the quality of
Pareto archives have been proposed. An often used quality indicator is the
hypervolume of the space dominated by the set of points (see e.g. (Zitzler
et al., 2003)). Our approach is motivated by another quality indicator - the
expected value of the weighted Chebycheff scalarizing functions (Jaszkiewicz,
2002). Such functions are defined in the following way:
s∞ (y(x), y 0 , Λ) = max {λk (yk0 − yk (x))}
k=1,...,d

where y 0 is a reference point, Λ = [λ1 , ..., λd ] is a weight vector such that λk ≥
0 ∀k. Each weighted Chebycheff scalarizing function has at least one global
minimum belonging to the set of Pareto-optimal solutions. For each Paretooptimal solution x there exists a weighted Chebycheff scalarizing function s∞
such that x is a global minimum of s∞ (see (Steuer, 1986), ch. 14.8).
The quality indicator is defined as:
R(A, L) = EΛ∈L (mins∞ (y, y 0 , Λ))
y∈A

where L is a set of all weight vectors.
Although the two indicators, i.e. the hypervolume and the expected value
of the weighted Chebycheff scalarizing functions, are defined in quite different terms, they are in fact closely related, which is illustrated in Figure 1.
Consider the non-dominated border of the dominated area used in the hypervolume indicator. Each point lying on this border is optimum of one or
more weighted Chebycheff scalarizing functions and has the same values of
these scalarizing functions as some of the solutions in the archive. In other
words, the hyper-facets of this border belong to the same isoquants of multiple Chebycheff functions as some solutions from the archive. In result, any
improvement of the hypervolume implies an improvement of the best values
of some weighted Chebycheff scalarizing functions.
An important advantage of the expected value of the weighted Chebycheff
scalarizing functions indicator is that to select good solutions we do not
need to explicitly calculate the contribution of each solution to this quality
indicator. Instead in each iteration we draw a random weight vector defining
a weighted Chebycheff scalarizing function and select from the Pareto archive
7

Figure 1: Comparison of the hypervolume and the expected value of the weighted Chebycheff scalarizing functions indicators

the solution that minimizes the value of this function. Thus, solutions being
minima of many scalarizing functions, and so having high impact on the
expected value, have higher chance to be selected. For example, in Figure 1
solutions xa and xb have higher chance to be selected than solutions xc , xd ,
and xe .
This mechanism not only selects promising solutions but also assures
a uniform coverage of all regions of the objective space. If the solutions
were selected at random with uniform probability, regions that have more
dense representation in the current archive would have a higher chance to be
explored further. Thus, any random differences in the density would tend to
be further increased, since the dense regions would be explored more than
regions with a low density of solutions.
Naive approach for finding the solution minimizing a given scalarizing
function through evaluation of each solution would be very time consuming.
However, ND-Tree data structure used to update the Pareto archive may also

8

be used to efficiently find the solution with the best value using Algorithm 2
proposed in this paper. Let us remind that in ND-Tree the Pareto archive is
recursively split into disjoint subsets associated with approximate local ideal
points. The algorithm is based on the observation that the value of each
weighted Chebycheff scalarizing function for any solution in a subset is not
lower than its value for the approximate local ideal point of this subset. Thus,
if a value of this function for a solution is already known (upper bound) and
this value is not worse than the value for the approximate local ideal point,
the whole subset could be omitted (see Figure 2). If this subset corresponds
to an internal node, its whole subtree could be omitted. To find quickly a
solution with a good value of the scalarizing function defining a good upper
bound at each internal node we select first the sub-node with the best value
for its approximate local ideal point.

Figure 2: Set S(n) that could be omitted due to the knowledge of the scalarizing function
value for solution x

Since Algorithm 2 is a new contribution reported in this paper, we analyze
the computational complexity of this algorithm. This analysis is similar to
9

the analysis of the algorithm for updating the Pareto archive with ND-Tree
presented in (Jaszkiewicz & Lust, 2016). We start by formally defining the
ND-Tree data structure :
Definition 1. ND-Tree data structure is a tree with the following properties:
1. With each node n is associated a set of solutions S(n).
2. Each leaf node contains a list L(n) of solutions and S(n) = L(n).
3. For each internal node n, S(n) is the union of disjoint sets associated
with all sub-nodes of n.
4. Each node n stores an approximate ideal point yb∗ (S(n)) such that yb∗ (S(n)) 
x ∀x ∈ S(n) and a approximate nadir point yb∗ (S(n)) such that x 
yb∗ (S(n)) ∀x ∈ S(n).
5. If n0 is a sub-node of n, then yb∗ (S(n))  yb∗ (S(n0 )) and yb∗ (S(n0 )) 
yb∗ (S(n)).
In the worst case, at each intermediate node we need to analyze each subnode. Thus, all solutions will need to be evaluated and the computational
complexity of Algorithm 2 is Θ(N ) where N is the number of solutions in
the archive.
In the best case, at each intermediate node only one sub-node has to be
analyzed and the solutions are equally split into a predefined number of subnodes. In this case the number of evaluated solutions and points is described
by the following recurrence:
T (N ) = 2 + T (N/C) = Θ(logC N )

(1)

where C is the number of sub-nodes. Please note, that it is possible to
consider even more optimistic scenarios, e.g. when only one solution needs
to be evaluated, however, the scenario analyzed above is much more realistic.
The most interesting but also the most difficult to analyze or even define is
the average case. Consider the case when each internal node has exactly two
sub-nodes. Assume that the number of solutions in one of the sub-nodes is
drawn from the uniform distribution, i.e. each number of solutions is equally
likely. The other sub-node will contain the remaining number of solutions.
In an internal node, either one or both sub-nodes will be processed. Assume
that the probability p2 of processing both nodes is constant. In this case:
N
−1
X
1
T (k)
T (N ) = 2 + (1 + p2 )
N
k=1

10

(2)

Multiply both sides by N :
N T (N ) = 2N + (1 + p2 )

N
−1
X

T (k)

(3)

k=1

Assume that N ≥ 2:
(N − 1)T (N − 1) = 2(N − 1) + (1 + p2 )

N
−2
X

T (k)

(4)

k=1

Subtract equations 3 and 4:
N T (N ) − (N − 1)T (N − 1) =
2N − 2(N − 1) + (1 + p2 )

N
−1
X

T (k) −

k=1

T (N ) =

N
−2
X

T (k)



=⇒

(5)

k=1

N + p2
2
+
T (N − 1)
N
N

The above recurrence has the following solution:
T (N ) =

Γ(p2 + N + 1)
2
−
Γ(N + 1)
p2

(6)

where Γ denotes the Gamma function being an extension of the factorial to
real number arguments.
Since
Γ(N + α)
lim
=1
(7)
N →∞ Γ(N )N α
=⇒
T (N ) = Θ(N p2 )
(8)
The Algorithm 2 is sub-linear for any p2 < 1 under the above assumptions.
Of course, it is still a very simplified analysis of the practical behavior of the
algorithm. For example, the probability p2 will not, in general, be constant.
In fact, it may happen that none of the sub-nodes will need to be processed,
since the ideal points of all sub-nodes will have the values of the scalarizing
function above the current upper bound. Such situations, would further
improve the practical efficiency of the algorithm.

11

Algorithm 2 MinimizeChebycheffScalarizingFunction
Parameter ↓: A node n
Parameter ↓: A weighted Chebycheff scalarizing function s∞ (. . . , Λ)
Parameter l: Minimum value of the scalarizing function known so far s∗
Parameter ↑: Solution x minimizing the scalarizing function
if n is a leaf node then
Calculate the value of s∞ (. . . , Λ) for each solution in the subset
if the best value is better than s∗ then
Return the best solution and update s∗
end if
else
Select the sub-node n0 with the minimum value of s∞ (zb∗ (S(n0 )), . . . , Λ)
if s∞ (zb∗ (S(n0 )), . . . , Λ) < s∗ then
MinimizeChebycheffScalarizingFunction (n0 , s∞ (. . . , Λ), s∗ , x)
for all Remaining sub-nodes n00 do
if s∞ (zb∗ (S(n00 )), . . . , Λ) < s∗ then
MinimizeChebycheffScalarizingFunction (n00 , s∞ (. . . , Λ), s∗ ,
x)
end if
end for
end if
end if
2.4. Mechanism III: Partial exploration of the neighborhoods
In the standard PLS the whole neighborhood of each solution is explored.
This strategy is not well adapted, however, to the goal of obtaining a good
anytime behavior since it may lead to the situations where some regions
of the Pareto front will be intensively explored while other regions will be
underexplored. Dubois-Lacoste et al. (2011, 2015) and Liefooghe et al. (2012)
observed that the anytime behavior of PLS can be improved by a partial
exploration of the neighborhoods, i.e. testing only some neighbor solutions.
On the other hand, the algorithm may become ineffective if too few
neighbor solutions are tested. Please note, that before exploring a neighborhood, the solution for the exploration needs to be selected which takes
non-negligible CPU time even with the use of ND-Tree. Thus the optimum
strategy may be to test a randomly selected subset of neighbor solutions.
12

Dubois-Lacoste et al. and Liefooghe et al. consider several options for partial exploration of the neighborhoods. Our approach is slightly different since
we use the number of tested moves as a parameter of the method.
2.5. MPLS algorithm
The proposed method is summarized in Algorithm 3. To draw a random weight vector we use the algorithm proposed in (Jaszkiewicz, 2002).
Weighted Chebycheff scalarizing functions are applied to the objective values normalized on-line to the range [0, 1] based on the ranges of the objectives
in the current archive, which is in fact achieved by dividing each individual
weight by the range of the corresponding objective.
Algorithm 3 defines the general scheme of MPLS. To apply it to a given
problem a neighborhood structure has to be defined. The choice of the neighborhood structure may of course highly influence the performance of the algorithm.
3. Computational experiment
To test the effectiveness of the proposed algorithm we use two different
combinatorial optimization problems. All algorithms were implemented in
C++ sharing as much of the code as possible. The experiment has been run
on an Intel Core i7-5500U CPU at 2.4 GHz. The source code, the instances,
and the detailed numerical results are available on-line 1 .
3.1. Multiobjective Traveling Salesperson Problem
As one of the test problems we use the Multiobjective Traveling Salesperson Problem (MTSP) which is a typical benchmark problem for multiple
objective metaheuristics.
Given a set {v1 , v2 , · · · , vN } of nodes and d costs c1 (vi , vj ) . . . cd (vi , vj )
between each pair of distinct nodes {vi , vj }, the multiobjective traveling
salesperson problem (MTSP) consists of finding an order π of the nodes,
minimizing the following costs (k = 1, . . . , d):
“minimize”yk (π) =

N
−1
X

ck (vπ(i) , vπ(i+1) ) + ck (vπ(N ) , vπ(1) )

i=1

1

https://sites.google.com/view/mopls/mpls

13

Algorithm 3 MPLS
Parameter ↓: Maximum running time T
Parameter ↓: Number of neighborhood moves M
Parameter l: A: an initial Pareto archive
while total running time is lower than T do
Use as the reference point y 0 the point composed of the maximum values
of particular objectives in the current archive increased by 10% of the
range of a given objective in this archive
Draw at random a weight vector Λ defining a Chebycheff scalarizing
function s∞ (. . . , y 0 , Λ)
Find in A the solution x minimizing s∞ (. . . , y 0 , Λ), i.e.
call
MinimizeChebycheffScalarizingFunction (rn, s∞ (. . . , y 0 , Λ), ∞, x)
with rn being a root node of ND-Tree
for M times do
Generate a random neighbor x0 of x
if y(x)  y(x0 ) and y(x) 6= y(x0 ) then
UpdateNDTree(A l,x0 ↓)
end if
end for
end while
where N (x) denotes the neighborhood of x and UpdateNDTree() updates
the Pareto archive A using ND-Tree data structure.
In the computational experiment, we used the symmetric multiobjective
traveling salesperson problem with ck (vi , vj ) = ck (vj , vi ) for 1 ≤ i, j ≤ N .
We used Euclidean instances with 100 and 200 nodes in which the costs
of the edges correspond to the Euclidean distance between two points in a
plane, and each objective corresponds to a different plane. For the purpose
of this experiment, we generated 10 instances for each size and each number
of objectives.
Following the successful methods proposed for the bi-objective case, we
used a two-phase approach (Lust & Teghem, 2010). In the first phase we
used Lin-Kernighan heuristic (Lin & Kernighan, 1973) to generate an initial
Pareto archive for the second phase in which MPLS was run. Precisely we
used the efficient implementation of this heuristic from the Concorde project
14

(http://www.math.uwaterloo.ca/tsp/concorde.html).
We used the 2-edge exchange move in MPLS. Alike Lust & Jaszkiewicz
(2010) and Jaszkiewicz & Lust (2017) we used the mechanisms of candidate
moves to speed-up the calculations.
3.2. Comparison of the various versions of PLS
In the first experiment we compare MPLS to the standard PLS and to
several other versions of PLS. Particular versions of PLS allow us to show not
only that MPLS performs better than the standard PLS but also that each of
the three new mechanisms used in MPLS indeed influences its effectiveness.
The following methods are compared in this experiment:
• ”MPLS 100” described by Algorithm 3 with 100 random moves tested
in each neighborhood, which is a relatively good value of this parameter
according to our preliminary experiments.
• ”MPLS full neighborhood” - the algorithm equivalent to ”MPLS 100”
but with the full exploration of each neighborhood. This algorithm
allows us to show that the partial exploration of the neighborhoods
improves the performance of MPLS.
• ”MPLS 1” described by Algorithm 3 with just one random move tested
in each neighborhood. We use this algorithm to show that too small
number of tested moves deteriorates the effectiveness of MPLS.
• ”MPLS 100 Random” - the algorithm equivalent to ”MPLS 100” but
with the random selection of solutions with uniform probability. This
algorithm allows us to show that the selection of solutions based on the
randomly selected weighted Chebycheff scalarizing functions improves
the performance of MPLS.
• ”MPLS 100 List” - the algorithm equivalent to ”MPLS 100” but with
the Pareto archive organized as a simple list. This algorithm allows us
to show that the use of ND-Tree data structure improves the performance of MPLS.
• ”Standard PLS tree” described by Algorithm 1 but using ND-Tree data
structure. This algorithm allows us to show that the selection of solutions based on the randomly selected weighted Chebycheff scalarizing
functions and the partial exploration of the neighborhoods improves
the performance of MPLS.
15

• ”Standard PLS List” described by Algorithm 1. This algorithm is the
straightforward adaptation of the algorithm used in the bi-objective
case to the many-objective case without any of the three new mechanisms used in MPLS.
The number of neighborhood moves M was set to 100 for all instances.
It should not be considered, however, as the best value of this parameter in
each case. We use this setting to proof that the best results may be achieved
with some intermediate approach between testing just one move or the whole
neighborhood.
Please note, that in fact the standard PLS algorithm (see Algorithm 1)
does not specify in which order set P is processed. In our experiment we
processed set P in the natural order in which the solutions were added to
this set.
In the first phase, we used 1000, 2000, and 3000 random weight vectors
for d = 3, 4, 5, respectively. For each of the weight vectors the Lin-Kernighan
heuristic was run optimizing a weighted sum of the objectives. Then, in the
second phase MPLS/PLS was allowed to run for the maximum time equal to
the running time of the first phase.
The results of this experiment are presented in Figures 3 to 6. For each
size and each number of objectives 10 different instances were used. As the
quality measure we report the hypervolume indicator, but we calculated also
the R indicator, i.e. average value of the weighted Chebycheff scalarizing
functions Jaszkiewicz (2002) (i.e. approximation of the expected value) with
exactly the same conclusions. The detailed numerical results of the two quality indicators are available on-line 2 . Each point represents the average value
and the range of the hypervolume indicator on 10 different instances obtained
by a given method. The first point always corresponds to the Pareto archive
obtained after the first phase. Since we used different instances we normalize
the values of the hypervolume such that it is equal to 1 after the first phase.
The reference points for the hypervolume were set to approximate nadir
points of each instance with objective values multiplied by 1.5. To obtain an
approximate nadir point for a given instance, each objective was optimized individually with either Lin-Kernighan heuristic (MTSP) or local search (MTSPWP). Then the worst obtained values of each objective were used as the
coordinates of the approximate nadir point.
2

https://sites.google.com/view/mopls/mpls

16

The reported running times include also the running times of the first
phase. For each instance, the maximum running time in the second phase
was equal to the running time of the first phase. The values of the quality
indicators were calculated in time steps equal to 10% of the running time
of the first phase. The running times were averaged over 10 runs in 10
instances. Since the variations of the running times of the first phase were
relatively low, we report just the average times.
The main observations are:
• The relative differences between the methods grow with the growing
number of objectives. In other words, the more objectives the more
important are the three new mechanisms used in MPLS.
• Each of the three new mechanisms of MPLS is important for the final performance of the method. The comparison of ”MPLS 100” to
”MPLS 100 List” indicates that the mechanism with the highest influence on the effectiveness of MPLS is the use of ND-Tree data structure
to update the Pareto archive and to select the best solution for a given
scalarizing function. The comparison of ”MPLS 100” to ”Standard
PLS Tree” indicates that the second mechanism with the highest influence on the effectiveness of MPLS is the selection of solutions based on
the randomly selected weighted Chebycheff scalarizing functions. Furthermore, the comparison to ”MPLS 100 Random” indicates that the
random selection of solutions with uniform probability is even worse
that the selection mechanism used in the standard PLS. The comparison of ”MPLS 100” to ”MPLS Full neighborhood” and ”MPLS 1”
indicates that the partial exploration of the neighborhoods also substantially improves the performance of MPLS.
• ”Standard PLS List”, i.e. the algorithm that uses none of the three
new mechanisms used in MPLS is the worst algorithm in all cases.
In order to test the significance of the differences we used the nonparametric statistical test of Mann-Whitney (Ferguson, 1967). The level
of risk of the test has been fixed to 5%. The final results of ”MPLS 100”
were significantly better than the final results of all other methods in all cases
except of ”MPLS full neighborhood” with d = 3.
We have made some additional experiments with full MPLS using 1 and
1≺ stopping conditions described in Liefooghe et al. (2012). With these stopping conditions the exploration of a neighborhood was stopped after finding the
17

first solution non-dominated with respect to the current one (1 ) or the first
solution dominating the current one (1≺ ). These results are available on-line
(see Section 3) but not included in this paper since they were very similar
to other algorithms tested. 1≺ version behaved very similarly to ”MPLS full
neighborhood”. This is because unlike Liefooghe et al. (2012) we initialize the
archive with very high quality solutions. In result we observed that only very
rarely a dominating solution was found in a neighborhood. Thus, in most
cases the whole neighborhood was tested as in ”MPLS full neighborhood”.
On the other hand 1 stopping condition resulted in testing very few moves
(often just one) since a solution non-dominated with respect to the current
one was quickly found. Again please note, that unlike Liefooghe et al. (2012)
we use the concept of candidate moves that increases the chance of testing
high quality moves only.
In addition, we compared MPLS to the Multiobjective Genetic Local Search
(MOGLS) algorithm with path relinking (Jaszkiewicz & Zielniewicz, 2009) for
the multiobjective traveling salesperson problem. According to our knowledge
the only methods reported in the literature that improved the results of this
version of MOGLS are those using PLS. In this paper, we used a newer, in
fact simplified, version of MOGLS in which the solutions for recombination
are selected directly from the Pareto archive without any additional population
of solution (Aghabeig & Jaszkiewicz, 2017). The initial archive of MOGLS
was exactly the same as in the case of MPLS. The expected rank of recombined
solutions was set to 20 based on preliminary experiments. MOGLS outperformed several variants of PLS/MPLS including ”Standard PLS List” and
”MPLS 100 Random” but was significantly outperformed by the full version
of MPLS, i.e. ”MPLS 100”.
3.3. MPLS with various number of runs of the Lin-Kernighan heuristic
In the above experiment we have shown that MPLS performs better than
other versions of PLS. The question remains, however, whether it is competitive to Lin-Kernighan heuristic standalone applied alike in the initial phase.
Since, in the bi-objective case the best results have been obtained combining
the phases of the Lin-Kernighan heuristic and of PLS (Lust & Teghem, 2010;
Lust & Jaszkiewicz, 2010; Liangjun et al., 2014; Jaszkiewicz & Lust, 2017;
Cornu et al., 2017), we test whether MPLS can improve the results obtained
with Lin-Kernighan heuristic standalone also in the many-objective case.
Precisely, we ask the following question: Having some predefined CPU time,

18

Figure 3: Hypervolume indicator for 3-objective MTSP instances with 100 nodes

can we obtain the best result with the use of the Lin-Kernighan heuristic
standalone, or by combining it with MPLS in two phases.
In the first phase, we used 2000, 4000, and 6000 as the maximum number
of random weight vectors for d = 3, 4, 5, respectively. For each of the weight
vectors the Lin-Kernighan heuristic was run optimizing a weighted sum of
the objectives. The time needed for all runs of the Lin-Kernighan heuristic
was then used as the maximum running time. Then, the number of LinKernighan heuristic runs was reduced to 90%, . . . , 10% and the remaining
running time was allocated to MPLS. The numbers of weight vectors and
thus the numbers of Lin-Kernighan heuristic runs were twice higher than in
the previous experiment (see Section 3.2). Please note, however, that in the
first experiment the same CPU time as in the fist phase was then allocated
to MPLS/PLS. In the second experiment the number of weight vectors was
gradually reduced and only the remaining time was allocated to MPLS/PLS.
Thus, the total running time was approximately the same in both experiments.
The results are presented in Figures 7 to 10. The values of the hypervolume are again normalized such that it is 1 after the first phase with the
maximum number of the Lin-Kernighan heuristic runs. Please note, that
for the lower numbers of the Lin-Kernighan heuristic runs the quality after
19

Figure 4: Hypervolume indicator for 4-objective MTSP instances with 100 nodes

the first phase is not shown since it was much lower and the figures would
become incomprehensible.
The main observations are:
• In almost all cases, the results with the use of MPLS are better than
with the use of the Lin-Kernighan heuristic standalone even with the
lowest number of runs of the Lin-Kernighan heuristic. The only exception is the result for the 5-objective instances with 200 nodes with the
smallest number of the Lin-Kernighan heuristic runs. This exception
is caused by the fact that as observed in Jaszkiewicz & Lust (2017) the
number of Lin-Kernighan heuristic runs should grow with the size of
an instance, while in our case, we used the same numbers for instances
with 100 and 200 nodes in our experiment.
• The overall best results were obtained for 1000, 2400, 4200, and 4800
runs of the Lin-Kernighan heuristic, for d = 3, 4, 5 with 100 nodes
and d = 5 with 200 nodes, respectively, i.e. the best results were
obtained with 50% or less of the CPU time allocated to MPLS. In
other words, alike in the bi-objective case the best results are obtained
by properly balancing the CPU time allocated to the phases of the
20

Figure 5: Hypervolume indicator for 5-objective MTSP instances with 100 nodes

Lin-Kernighan heuristic runs and MLPS. Please note, that the LinKernighan heuristic, and especially its efficient implementation from
the Concorde project, is an advanced method for TSP, while MPLS
uses the very basic 2-edge exchange move.
• The standard PLS algorithm was able to improve the results obtained
with the Lin-Kernighan heuristic standalone only in the 3-objective
case. In the 4- and 5-objective cases, the standard PLS algorithm
was not able to improve the results obtained with the Lin-Kernighan
heuristic standalone for any reduction of the number of runs in the
first phase. Thus, the use of this algorithm in these cases would not be
beneficial.
3.4. Multiobjective Traveling Salesperson Problem with profits
Given a set {v1 , · · · , vN } of nodes and d1 costs c1 (vi , vj ) . . . cd1 (vi , vj ) between each pair of distinct nodes {vi , vj }, and d2 profits pr1 (vi ) . . . prd2 (vi )
associated with each node {vi }, the multiobjective traveling salesperson problem with profits (MTSPWP) consists of choosing a subset of nodes SN and
21

Figure 6: Hypervolume indicator for 5-objective MTSP instances with 200 nodes

finding an order π of these nodes, optimizing the following objectives:
|SN |−1

“minimize”yk (π) =

X

ck (vπ(i) , vπ(i+1) ) + ck (vπ(|SN |) , vπ(1) ), k = 1, . . . , d1

i=1
|SN |

“maximize”yd1 +l (π) =

X

prl (vπ(i) ), l = 1, . . . , d2

i=1

In other words, d1 objectives correspond to the minimization of d1 costs
of the routes, while d2 objectives correspond to the maximization of d2 profits
associated with the selected nodes.
We used the symmetric costs where ck (vi , vj ) = ck (vj , vi ) for 1 ≤ i, j ≤
N . For the purpose of this experiment we generated 10 instances with 200
nodes for each number of objectives. For d = 3, we used one cost objective
and two profit objectives, for d = 4, we used two cost objectives and two
profit objectives, and for d = 5, we used two cost objectives and three profit
objectives. The cost objectives were generated using Euclidean distances,
i.e. the costs of the edges correspond to the Euclidean distance between two
points in a plane, and each objective corresponds to a different plane. Profits
were drawn at random with a uniform distribution from a range [0, 2000].
22

Figure 7: Hypervolume indicator for 3-objective MTSP instances with 100 nodes with
various numbers of the Lin-Kernighan heuristic runs and constant total CPU time

Please note, that despite of the similar names MTSPWP differs substantially from MTSP. In particular:
• The two problems have different solution spaces. In MTSPWP the
solutions are defined by both a choice of the nodes, and an order of
the selected nodes. In result, MTSPWP requires a different set of the
neighborhood moves described below.
• MTSPWP exhibits a specific pattern of positive/negative correlations
of objectives. The cost objectives are in general positively correlated
because all of them improve with reducing the number of selected nodes.
The profit objectives also are in general positively correlated because
all of them improve with the growing number of selected nodes. On
the other hand, the two groups of objectives are negatively correlated
for the same reasons.
• The cost and profit objectives are defined by heterogeneous mathematical formulas.

23

Figure 8: Hypervolume indicator for 4-objective MTSP instances with 100 nodes with
various numbers of the Lin-Kernighan heuristic runs and constant total CPU time

Because of the nature of MTSPWP, several types of moves were used to
both select appropriate subset of nodes and optimize the route between these
nodes (Jozefowiez et al., 2008):
• ”2-edge exchange move” is the same move as in the case of MTSP.
• ”Node delete move” removes one of the nodes from the current solution.
• ”Node insert move” inserts one of the nodes that is not selected at a
given position in the route.
• ”Node exchange move” exchanges one of the nodes from the current
solution for one of the nodes that is not selected.
The design of the experiments was similar as in the case of MTSP. In the
first phase, instead of the Lin-Kernighan heuristic that cannot be applied in
this case, we used the steepest local search algorithm that was testing all
moves of all types before selecting the best neighbor. In MPLS the type
of the move was drawn at random, and then the specific move was drawn.
The steepest local search was applied to the optimization of the combined
24

Figure 9: Hypervolume indicator for 5-objective MTSP instances with 100 nodes with
various numbers of the Lin-Kernighan heuristic runs and constant total CPU time

scalarizing functions being the weighted sums of the Chebycheff scalarizing
function with weight 1 and the linear scalarizing function with weight 0.5,
which was found the best option in the preliminary experiments. This version
was found to perform better than the weighted sum used in the case of MTSP
and the Lin-Kernighan heuristic. The steepest local search was then run for
each of the randomly generated weight vectors.
We have performed the two experiments analogous like in the case of
MTSP with same numbers of local search runs like the numbers of the LinKernighan heuristic runs. Despite of the different nature of the two problems
the results of the experiments for MTSPWP are very similar to the results
for MTSP. Because of the limited space we present only the results for the
5-objective instances in Figures 11 and 12.
4. Related works
Pareto Local Search algorithm has been proposed by Angel et al. (2004),
Paquete & Stutzle (2006), and Paquete et al. (2007). It has been successfully applied to the bi-objective knapsack (Lust & Teghem, 2012), the bi25

Figure 10: Hypervolume indicator for 5-objective MTSP instances with 200 nodes with
various numbers of the Lin-Kernighan heuristic runs and constant total CPU time

objective traveling salesperson problem (TSP) (Lust & Teghem, 2010; Lust
& Jaszkiewicz, 2010; Liangjun et al., 2014; Jaszkiewicz & Lust, 2017; Cornu
et al., 2017), various bi-objective permutation flowshop problems (DuboisLacoste et al., 2011), the bi-objective set covering problem (Lust & Tuyttens,
2014) and the risk-cost optimization for procurement planning (Mori et al.,
2017). Some recent advancements in PLS involve: Pareto improvement of
some dominated solutions, i.e selection of a dominating solution from the
neighborhood, until such improvements are no longer possible (Inja et al.,
2014); the use of larger perturbations of solutions (Drugan & Thierens, 2012;
Liangjun et al., 2014), the penalization of some features exhibited by many
solutions in the archive (Alsheddy & Tsang, 2010), and the use of the data
perturbations (Cornu et al., 2017). However, none of these proposals focuses
on the many-objective optimization.
One of the main ideas of MPLS is to improve the anytime behavior of
the algorithm, since obtaining the locally optimal Pareto archive is usually
prohibitively time consuming in the many-objective case. An anytime PLS
algorithm has been proposed by Dubois-Lacoste et al. (2011, 2015). Some
similar concepts have been analyzed by Liefooghe et al. (2012). Anytime PLS
26

Figure 11: Hypervolume indicator for 5-objective MTSPWP instances

algorithm is, however, dedicated to the bi-objective case, and the authors
define many-objective optimization as a direction for further research. At a
general level some mechanisms used in MPLS are motivated by these works,
but the specific techniques are very different. For example Dubois-Lacoste et
al. use the optimistic hypervolume to select the promising solutions, which
cannot be directly applied in the many-objective case.
Liangjun et al. (2014) used PLS to solve the multiobjective knapsack
problem instances with up to 4 objectives. Cornu et al. (2017) applied PLS to
the bi- and 3-objective instances of TSP. These papers do not contain, however, information whether any specific mechanisms for the many-objective
case, other than the reduction of the time allocated to PLS, were used.
The idea of using the scalarizing functions with the randomly generated
weight vectors has been proposed in some multiobjective evolutionary algorithms, e.g. by Ishibuchi & Murata (1998), Jaszkiewicz (2002); Jaszkiewicz
& Zielniewicz (2009). The scalarizing functions were, however, used in a
very different way to select solutions for recombination and to optimize the
scalarizing functions with the single objective local search.
The multiobjective traveling salesperson problem is often used as a benchmark problem for the multiobjective metaheuristics (Jaszkiewicz, 2002; Garcia27

Figure 12: Hypervolume indicator for 5-objective MTSPWP instances with various numbers of local search runs and constant total CPU time

Martinez et al., 2007). As it was already mentioned, the state-of-the-art
methods for the bi-objective TSP involve the use of the Lin-Kernighan heuristic and Pareto Local Search (Lust & Teghem, 2010; Lust & Jaszkiewicz, 2010;
Liangjun et al., 2014; Jaszkiewicz & Lust, 2017; Cornu et al., 2017).
The traveling salesperson problem with profits is a well-known combinatorial optimization problem, however, it is usually considered as a single
objective problem with a single cost and a single profit aggregated to one
objective with a weighted sum approach (Feillet et al., 2005). There are
relatively few results for the bi-objective case (Jozefowiez et al., 2008; Zhu
et al., 2011; Labadie et al., 2014; Bérubé et al., 2009). To our knowledge,
multiobjective metaheuristics have not been applied yet to the multiobjective version of the traveling salesperson problem with profits with more than
one cost and/or profit.
5. Conclusions and directions for further research
We have presented a new Many-Objective Pareto Local Search algorithm.
The algorithm has been tested on two different multiobjective combinatorial
28

optimization problems showing its effectiveness. We have also shown that
each of the three new mechanisms used in MPLS significantly contributes
to its effectiveness. Furthermore, the importance of the new mechanisms in
relation to the standard PLS grows with the growing number of objectives.
In particular, in the 4- and 5-objective cases, standard PLS without any of
the new mechanisms was not able to improve the results obtained with the
Lin-Kernighan heuristic (MTSP) or local search (MTSPWP) standalone for
any reduction of the number of runs in the first phase. On the other hand,
MPLS was able to improve these results in almost all cases tested in the
experiment.
Since the standard PLS algorithm proved its high effectiveness in the
bi-objective case, we believe that MPLS could be a very useful element in
the toolbox for the general case of the multiobjective combinatorial optimization, especially when combined with other methods being very effective
in the search towards the Pareto front. In fact, we expect that alike the
standard PLS in the bi-objective case, MPLS could become a typical component of the state-of-the-art algorithms for the many-objective combinatorial
optimization.
The applications of MPLS to various benchmark and real-life problems,
and combination with other multiobjective metaheuristics is a natural direction for further research. In particular MPLS could be combined with such
concepts as the use of larger perturbation of solutions (Liangjun et al., 2014)
or data perturbations (Cornu et al., 2017).
MPLS introduces a new parameter, i.e. the number of the neighborhood
moves. At present we do not have any guidelines for setting this parameter.
Development of a mechanism for automatic adaptation of this parameter is
an interesting direction for further research. In particular, the efficiency of
the partial exploration of the neighborhood may be problem-dependent, and
for some problems full exploration of the neighborhood may be still necessary.
MPLS generates a large number of potentially Pareto-optimal solutions.
The maximum size of the Pareto archive in our experiment exceeded 5 millions of solutions. The final goal of the decision maker is to select the single
solution being the best according to his/her preferences. If no information
about these preferences is available, a multiobjective metaheuristic should
generate a good solution for any possible preferences. However, often some
partial preference information is known in advance or may be gathered during the run of the method. Thus, another interesting direction for further
research is the incorporation of some partial preference information in order
29

to limit the region of the Pareto front searched by MPLS.
Acknowledgment
This research was funded by the Polish National Science Center, grant
no. UMO-2013/11/B/ST6/01075.
References
Aghabeig, M., & Jaszkiewicz, A. (2017). Experimental analysis of design
elements of scalarizing functions-based multiobjective evolutionary algorithms. ArXiv e-prints, abs/1703.09469 . URL: http://arxiv.org/abs/
1703.09469. arXiv:1703.09469.
Alsheddy, A., & Tsang, E. E. P. K. (2010). Guided Pareto Local Search
based frameworks for biobjective optimization. In IEEE Congress on Evolutionary Computation (pp. 1–8). doi:10.1109/CEC.2010.5585983.
Angel, E., Bampis, E., & Gourvès, L. (2004). A Dynasearch Neighborhood
for the Bicriteria Traveling Salesman Problem. In X. Gandibleux, M. Sevaux, K. Sörensen, & V. T’kindt (Eds.), Metaheuristics for Multiobjective
Optimisation (pp. 153–176). Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-642-17144-4_6.
Bérubé, J.-F., Gendreau, M., & Potvin, J.-Y. (2009). An exact e-constraint
method for bi-objective combinatorial optimization problems: Application
to the Traveling Salesman Problem with Profits. European Journal of
Operational Research, 194 , 39 – 50. doi:http://dx.doi.org/10.1016/j.
ejor.2007.12.014.
Chand, S., & Wagner, M. (2015). Evolutionary many-objective optimization:
A quick-start guide. Surveys in Operations Research and Management
Science, 20 , 35 – 42. doi:http://dx.doi.org/10.1016/j.sorms.2015.
08.001.
Cornu, M., Cazenave, T., & Vanderpooten, D. (2017). Perturbed Decomposition Algorithm applied to the multi-objective Traveling Salesman
Problem. Computers & Operations Research, 79 , 314 – 330. doi:http:
//dx.doi.org/10.1016/j.cor.2016.04.025.

30

Drugan, M. M., & Thierens, D. (2012). Stochastic Pareto local search: Pareto
neighbourhood exploration and perturbation strategies. Journal of Heuristics, 18 , 727–766. doi:10.1007/s10732-012-9205-7.
Dubois-Lacoste, J., López-Ibáñez, M., & Stützle, T. (2011). A hybrid
TP+PLS algorithm for bi-objective flow-shop scheduling problems. Computers & Operations Research, 38 , 1219 – 1236. doi:http://dx.doi.org/
10.1016/j.cor.2010.10.008.
Dubois-Lacoste, J., López-Ibáñez, M., & Stützle, T. (2015). Anytime Pareto
local search. European Journal of Operational Research, 243 , 369 – 385.
doi:http://dx.doi.org/10.1016/j.ejor.2014.10.062.
Feillet, D., Dejax, P., & Gendreau, M. (2005). Traveling salesman problems
with profits. Transportation Science, 39 , 188–205. doi:{10.1287/trsc.
1030.0079}.
Ferguson, T. (1967). Mathematical Statistics, a decision theoretic approach.
New-York and London: Academic Press.
Garcia-Martinez, C., Cordon, O., & Herrera, F. (2007). A taxonomy and an
empirical analysis of multiple objective ant colony optimization algorithms
for the bi-criteria TSP. European Journal of Operational Research, 180 ,
116–148. doi:{10.1016/j.ejor.2006.03.041}.
Inja, M., Kooijman, C., de Waard, M., Roijers, D. M., & Whiteson, S.
(2014). Queued Pareto Local Search for Multi-Objective Optimization.
In T. Bartz-Beielstein, J. Branke, B. Filipič, & J. Smith (Eds.), Parallel
Problem Solving from Nature – PPSN XIII: 13th International Conference,
Ljubljana, Slovenia, September 13-17, 2014. Proceedings (pp. 589–599).
Cham: Springer International Publishing. URL: https://doi.org/10.
1007/978-3-319-10762-2_58. doi:10.1007/978-3-319-10762-2_58.
Ishibuchi, H., & Murata, T. (1998). A multi-objective genetic local search
algorithm and its application to flowshop scheduling. IEEE Transactions
on Systems Man and Cybernetics Part C-Applications and Reviews, 28 ,
392–403. doi:{10.1109/5326.704576}.
Jaszkiewicz, A. (2002). Genetic local search for multi-objective combinatorial
optimization. European Journal of Operational Research, 137 , 50 – 71.
doi:http://dx.doi.org/10.1016/S0377-2217(01)00104-7.
31

Jaszkiewicz, A., & Lust, T. (2016). ND-Tree-based update: a Fast Algorithm
for the Dynamic Non-Dominance Problem. ArXiv e-prints, . URL: http:
//arxiv.org/abs/1603.04798. arXiv:1603.04798.
Jaszkiewicz, A., & Lust, T. (2017). Proper balance between search towards
and along Pareto front: biobjective TSP case study. Annals of Operations
Research, (pp. 1–20). doi:10.1007/s10479-017-2415-5.
Jaszkiewicz, A., & Zielniewicz, P. (2009). Pareto memetic algorithm with
path relinking for bi-objective traveling salesperson problem. European
Journal of Operational Research, 193 , 885–890. doi:{10.1016/j.ejor.
2007.10.054}.
Jozefowiez, N., Glover, F., & Laguna, M. (2008). Multi-objective Metaheuristics for the Traveling Salesman Problem with Profits. Journal
of Mathematical Modelling and Algorithms, 7 , 177–195. doi:10.1007/
s10852-008-9080-2.
Labadie, N., Melechovsky, J., & Prins, C. (2014). An Evolutionary Algorithm
with Path Relinking for a Bi-objective Multiple Traveling Salesman Problem with Profits. In Benyoucef, L and Hennet, JC and Tiwari, MK (Ed.),
Applications of Multi-Criteria and Game Theory Approaches: Manufacturing and Logistics Springer Series in Advanced Manufacturing (pp. 195–
223). Springer-Verlag Bberlin. doi:{10.1007/978-1-4471-5295-8\_10}.
Lara, A., Sanchez, G., Coello, C. C., & Schutze, O. (2010). HCS: A new
local search strategy for memetic multiobjective evolutionary algorithms.
Evolutionary Computation, IEEE Transactions on, 14 , 112–132. doi:10.
1109/TEVC.2009.2024143.
Liangjun, K., Qingfu, Z., & Battiti, R. (2014). Hybridization of Decomposition and Local Search for Multiobjective Optimization. Cybernetics, IEEE
Transactions on, 44 , 1808–1820. doi:10.1109/TCYB.2013.2295886.
Liefooghe, A., Humeau, J., Mesmoudi, S., Jourdan, L., & Talbi, E.-G. (2012).
On dominance-based multiobjective local search: design, implementation
and experimental analysis on scheduling and traveling salesman problems.
Journal of Heuristics, 18 , 317–352. URL: https://doi.org/10.1007/
s10732-011-9181-3. doi:10.1007/s10732-011-9181-3.

32

Lin, S., & Kernighan, B. (1973). An effective heuristic algorithm for the
traveling-salesman problem. Operations Research, 21 , 498–516.
Lust, T., & Jaszkiewicz, A. (2010). Speed-up techniques for solving largescale biobjective TSP. Computers & Operations Research, 37 , 521 – 533.
doi:http://dx.doi.org/10.1016/j.cor.2009.01.005.
Lust, T., & Teghem, J. (2010). Two-phase Pareto local search for the biobjective traveling salesman problem. Journal of Heuristics, 16 , 475–510.
doi:10.1007/s10732-009-9103-9.
Lust, T., & Teghem, J. (2012). The multiobjective multidimensional knapsack problem: a survey and a new approach. International Transactions
in Operational Research, 19 , 495–520. doi:10.1111/j.1475-3995.2011.
00840.x.
Lust, T., & Tuyttens, D. (2014). Variable and large neighborhood search to
solve the multiobjective set covering problem. Journal of Heuristics, 20 ,
165–188. doi:10.1007/s10732-013-9236-8.
Mori, M., Kobayashi, R., Samejima, M., & Komoda, N. (2017). Risk-cost optimization for procurement planning in multi-tier supply chain by Pareto
Local Search with relaxed acceptance criterion. European Journal of Operational Research, 261 , 88 – 96. doi:http://dx.doi.org/10.1016/j.
ejor.2017.01.028.
Paquete, L., Schiavinotto, T., & Stuetzle, T. (2007). On local optima in
multiobjective combinatorial optimization problems. Annals of Operations
Research, 156 , 83–97. doi:{10.1007/s10479-007-0230-0}.
Paquete, L., & Stutzle, T. (2006). A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices. European
Journal of Operational Research, 169 , 943–959. doi:{10.1016/j.ejor.
2004.08.024}.
Steuer, R. (1986). Multiple Criteria Optimization: Theory, Computation and
Applications. New-York: John Wiley & Sons.
Talbi, E.-G., Basseur, M., Nebro, A. J., & Alba, E. (2012). Multi-objective
optimization using metaheuristics: non-standard algorithms. International Transactions in Operational Research, 19 , 283–305. doi:{10.1111/
j.1475-3995.2011.00808.x}.
33

Yu, G. (2013). Industrial Applications of Combinatorial Optimization volume 16. Springer Science & Business Media.
Zhu, B., Suzuki, J., & Boonma, P. (2011). Evaluating the alpha-Dominance
Operator in Multiobjective Optimization for the Probabilistic Traveling
Salesman Problem with Profits. In Kita, E (Ed.), Evolutionary Algorithms
(pp. 271–294). Janzeza Trdine99, Rijeka, 51000, Croatia: INTECH Europe.
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C., & da Fonseca, V. (2003).
Performance assessment of multiobjective optimizers: An analysis and
review. IEEE Transactions on Evolutionary Computation, 7 , 117–132.
doi:{10.1109/TEVC.2003.810758}.

34

