Tree-Deletion Pruning in Label-Correcting
Algorithms for the Multiobjective Shortest Path
Problem

arXiv:1604.08147v1 [] 27 Apr 2016

Fritz Bökler and Petra Mutzel
Department of Computer Science, TU Dortmund, Germany
{fritz.boekler, petra.mutzel}@tu-dortmund.de

Abstract. In this paper, we re-evaluate the basic strategies for label correcting algorithms for the multiobjective shortest path (MOSP) problem,
i.e., node and label selection. In contrast to common believe, we show
that—when carefully implemented—the node-selection strategy usually
beats the label-selection strategy. Moreover, we present a new pruning
method which is easy to implement and performs very well on real-world
road networks. In this study, we test our hypotheses on artificial MOSP
instances from the literature with up to 15 objectives and real-world road
networks with up to almost 160,000 nodes.

1

Introduction

In this paper we are concerned with one of the most famous problems from
multiobjective optimization, the multiobjective shortest path (MOSP) problem.
We are given a directed graph G, consisting of a finite set of nodes V and a set of
directed arcs A ⊆ V × V . We are interested in paths between a given source node
s and a given target node t. Instead of a single-objective cost function, we are
given an objective function c which maps each arc to a vector, i.e., c : A → Qd
for d ∈ N. The set of all directed paths from s to t in a given graph is called Ps,t
and we assume that the objective function c is extended on these paths in the
canonical way.
In contrast to the single-objective case, where there exists only one unique
optimal value, in the multiobjective case there usually does not exist a path minimizing all objectives at once. Thus, we are concerned with finding the Paretofront of all s-t-paths, i.e., the minimal vectors of the set c(Ps,t ) with respect to
the canonical componentwise partial order on vectors ≤. Moreover, we also want
to find for each point y of the Pareto-front one representative path p ∈ Ps,t ,
such that c(p) = y. Each such path is called Pareto-optimal. For more information on multiobjective path and tree problems we refer the reader to the latest
survey [4].
It is long known that the Pareto-front of a MOSP instance can be of exponential size in the input [7]. Moreover, it has been recently shown in [2], that
there does not exist an output-sensitive algorithm for this problem even in the
case of d = 2 unless P = NP.

2

1.1

Previous Work

The techniques used for solving the MOSP problem are based on labeling algorithms. The majority of the literature is concerned with the biobjective case.
The latest computational study for more than 2 objectives is from 2009 [9] and
compares 27 variants of labeling algorithms on 9,050 artificial instances. These
are the instances we also use for our study. In summary, a label correcting version with a label-selection strategy in a FIFO manner is concluded to be the
fastest strategy on the instance classes provided. The authors do not investigate
a node-selection strategy with the argument that it is harder to implement and
is less efficient (cf. also [10]).
In an older study from 2001 [6], also label-selection and node-selection strategies are compared. The authors conclude that, in general, label-selection methods are faster than node-selection methods. However, the test set is rather small,
consisting of only 8 artificial grid-graph instances ranging from 100 to 500 nodes
and 2 to 4 objectives and 18 artificial random-graph instances ranging from 500
to 40,000 nodes and densities of 1.5 to 30 with 2 to 4 objectives.
In the work by Delling and Wagner [5], the authors solve a variant of the
multiobjective shortest path problem where a preprocessing is allowed and we
want to query the Pareto-front of paths between a pair of nodes as fast as
possible. The authors use a variant of SHARC to solve this problem. Though
being a different problem, this study is the first computational study where
an implementation is tested on real-world road networks instead of artificial
instances. The instances have sizes of 30,661, 71,619 and 892,392 nodes and 2
to 4 objectives. Though, the largest instance could only be solved using highly
correlated objective functions resulting in Pareto-front sizes of only at most 2.5
points on average.
1.2

Our Contribution

In this paper, we investigate the efficiency of label correcting methods for the
multiobjective shortest path problem. We focus on label correcting methods,
because the literature (cf. [9, 11]) and our experience shows that label setting
algorithms do not perform well on instances with more than two objectives. We
investigate the question if label-selection or node-selection methods are more
promising and test codes based on the recent literature.
We also perform the first computational study of these algorithms not only
on artificial instances but also on real-world road networks based on the road
network of Western Europe provided by the PTV AG for scientific use. The road
network sizes vary from 23,094 to 159,945 nodes and include three objective
functions. The artificial instances are taken from the latest study on the MOSP
problem.
Moreover, we propose a new pruning technique which performs very well on
the road networks, achieving large speed-ups. We also show the limits of this
technique and reason under which circumstances it works well.

3

1.3

Organization

In Sec. 2, we describe the basic techniques of labeling algorithms in multiobjective optimization. The tree-deletion pruning is the concern of Sec. 3. Because
the implementation of the algorithms is crucial for this computational study, we
give details in Sec. 4. The computational study and results then follow in Sec. 5.

2

Multiobjective Labeling Algorithms

In general, a labeling algorithm for enumerating the Pareto-front of paths in a
graph maintains a set of labels Lu at each node u ∈ V . A label is a tuple which
holds its cost vector, the associated node and, for retrieving the actual path, a
reference to the predecessor label. The algorithm is initialized by setting each
label-set to ∅ and adding the label (0, s, nil) to Ls .
These algorithms can be divided into two groups, depending if they select
either a label or a node in each iteration. These strategies are called label or
ˆ at a
node selection strategies, respectively. When we select a label ` = (v, u, `)
node u, this label is pushed along all out-arcs a = (u, w) of u, meaning that a
new label at the head of the arc is created with cost v + c(a), predecessor label
` and associated node w. This strategy is due to [12] for d > 2. If we follow a
node-selection strategy, all labels in Lu will be pushed along the out-arcs of a
selected node u. This strategy was first proposed in [3] for the biobjective case.
Nodes or labels which are ready to be selected are called open.
After pushing a set of labels, the label sets at the head of each considered
arc are cleaned, i.e. all dominated labels are removed from the modified label
ˆ dominates a label `0 = (v0 , u0 , `ˆ0 , ) if v ≤ v0 and
sets. We say a label ` = (v, u, `)
0
v 6= v .
There are many ways in which a label or node can be selected. A comparative study was conducted by Paixao and Santos [10]. For example, a pure FIFO
strategy seems to work best in the aforementioned study. But also other strategies
P are possible: For example, we can sort the labels by their average cost, i.e.,
i∈{1,...,d} vi /d and always select the smallest one. A less expensive variant is
ˆ in a FIFO
due to [1, 9], where we decide depending on the top label ` = (v, u, `)
0
0
0 ˆ0
0
queue Q where to place a new label ` = (v , u , ` ): If v is lexicographic smaller
than v, then it is placed in the front of Q, otherwise it is placed at the back of
Q.
Both available computational studies on labeling algorithms for the multiobjective shortest path problem with more than 2 criteria suggest that labelselection strategies are far superior compared to node-selection strategies [6, 9].
2.1

Label Setting vs. Label Correcting Algorithms

In the paper by Martins [8], the author describes an algorithm using a labelselection strategy. The algorithm selects the next
S label by choosing the lexicographic smallest label among all labels in L := u∈V Lu . In general, whenever

4

ˆ in L, this label represents a nondomwe select a nondominated label ` = (v, u, `)
inated path from s to u. Labeling algorithms having the property that whenever
we select a label we know that the represented path is a Pareto-optimal path,
are called label setting algorithms. Labeling algorithms which do not have this
property, and thus sometimes delete or correct a label, are called label correcting
algorithms. On the plus side, in label setting algorithms, we never select a label
which will be deleted in the process of the algorithm. But selecting these labels
is not trivial. For example selecting a lexicographic smallest label requires a priority queue data structure, whereas the simplest label-selection strategy requires
only a simple FIFO queue.
In many studies the label correcting algorithms are superior to the label
setting variants. See for example [6, 9, 11]. It is not clear why this is the case.
One possible reason is, that the cost of the data structure can not make up for
the advantage of not pushing too many unneeded labels. Since the case is clear
for the comparison of label setting and label correcting algorithms, we do not
evaluate label setting algorithms in our study.

3

Tree-Deletion Pruning

c
a

v

s
b
Fig. 1: Illustration of the tree-deletion pruning

The main difficulty which is faced by label correcting algorithms is that we
can push labels which will later be dominated by a new label. To address this
issue, let us take a label-selection algorithm into consideration which selects the
next label in a FIFO manner. In Fig. 1, we see the situation where a label `
at node v, which encodes a path a from s to v, is dominated by a label `0 ,
which encodes a different path b from s to v. Based on the label `, we might
already have built a tree of descendand labels c. If we proceed with the usual
label correcting algorithm, first the descendant labels of ` will be pushed and
later be dominated by the descandants of `0 . To avoid the unnecessary pushes
of descendants of `, we can delete the whole tree c after the label ` is deleted.
This pruning method will be called tree-deletion pruning (TD). We can employ

5

Algorithm 1 Abstract version of the LS algorithm
Require: Graph G = (V, A), nodes s, t ∈ V and objective function c : A → Qd
Ensure: List R of pairs (p, y) for all y ∈ c(Ps,t ) and some p ∈ Ps,t such that c(p) = y
1: Lu ← ∅ for all u ∈ V \{s}
2: ` ← (0, s, nil)
3: Ls ← {`}
4: Q.push(`)
5: while not Q.empty do
ˆ ← Q.pop
6:
` = (v, u, `)
7:
for (u, w) ∈ A do
8:
Push ` along (u, w) and add the new label `0 to Lw
9:
Clean Lw
. Tree-deletion for every deleted label in Lw
10:
if `0 is nondominated in Lw then
11:
Q.push(`0 )
12: Reconstruct paths for each label in Lt and output path/vector pairs

Algorithm 2 Abstract version of the NS algorithm
Require: Graph G = (V, A), nodes s, t ∈ V and objective function c : A → Qd
Ensure: List R of pairs (p, y) for all y ∈ c(Ps,t ) and some p ∈ Ps,t such that c(p) = y
1: Lu = ∅ for all u ∈ V \{s}
2: Ls = {(0, s, nil)}
3: Q.push(s)
4: while not Q.empty do
5:
u ← Q.pop
6:
for (u, w) ∈ A do
7:
for not yet pushed label ` in Lu do
8:
Push ` along (u, w) and add the new label to Lw
9:
Clean Lw
. Tree-deletion for every deleted label in Lw
10:
if at least one new label survived the cleaning process and w ∈
/ Q then
11:
Q.push(w)
12: Reconstruct paths for each label in Lt and output path/vector pairs

this method in label correcting algorithms using both, the label-selection and
node-selection strategies.

4

Implementation Details

We implemented both label-correcting algorithms, a version of the FIFO labelselection (LS) and FIFO node-selection (NS) algorithms in C++11. The reason
for choosing these variants is that the LS-algorithm is the fastest method in the
latest comparative study [9]. Both alternatives are also implemented using treedeletion pruning (LS-TD and NS-TD, respectively). Pseudocode can be found
in Algorithms 1 and 2.

6

We use the OGDF1 for the representation of graphs. Wherever possible, we
try to use std::vector for collections of data.
Label Selection In the label-selection variant we use a std::deque to implement
the queue of open labels.
Node Selection In the node-selection variants we use our own implementation of
a ring-buffer to implement the queue of open nodes. Also, only those labels of a
node are pushed, which have not been pushed before.
Tree-Deletion Pruning The successors of each label are stored in an std::list.
The reason for this is that the sucessor-lists are constructed empty and most
of them remain empty for the whole process of the algorithm. Construction of
empty std::lists is the cheapest operation among the creation of all other
relevant data structures.
Cleaning Step While there is a considerable literature on finding the subset of
minimal vectors in a set of vectors, it is not clear which method to use in practice. In the node-selection algorithm, we could use the fact that we try to find
the nondominated vectors of two sets of nondominated vectors, which has been
successfully exploited for the biobjective problem in [3]. To make the comparison between label-selection and node-selection strategies more focused on the
strategies itself, we use a simple pairwaise comparison between all pushed labels
and all labels at the head of the arc. A more sophisticated method would make
the node-selection strategy only faster. Moreover, the studies on multiobjective
labeling algorithms also employ this method.

5

Computational Study

The experiments were performed on an Intel Core i7-3770, 3.4 GHz and 16 GB
of memory running Ubuntu Linux 12.04. We compiled the code using LLVM 3.4
with compiler flag -O3.
In the computational study, we are concerned with the following questions:
1. Is label selection really faster than node selection?
2. In which circumstances is tree-deletion pruning useful?
We will answer these questions in the following subsections.
5.1

Instances

We used two sets of instances. First, we took the instances of [9] and tested our
implementations on them. The aforementioned study is the latest study which
tested implementations of labelling algorithms for MOSP. For each problem type,
1

http://ogdf.net/

7
Name
n
d Name
n
d
CompleteN-medium 10–200
3 CompleteN-large 10–140
6
CompleteK-medium
50
2–15 CompleteK-large
100
2–9
GridN-medium
441–1225 3 GridN-large
25–289
6
GridK-medium
81
2–15 GridK-large
100
2–9
RandomN-medium 500–10000 3 RandomN-large 1000–20000 6
RandomK-medium
2500
2–15 RandomK-large
5000
2–9

Fig. 2: Overview on the artificial test instances

there are 50 randomly drawn instances. In summary they make up a set of 9,050
test problems.
The properties of these instances can be seen in Fig. 2. The random graph
instances are based on a hamiltonian cycle where arcs are randomly added to
the graph. In the complete graph, arcs are added between each pair of nodes
in both directions. The grid graphs are all square. The arc costs were choosen
uniformly random in [1, 1000] ∩ N. The instances are available online, see [9] for
details.
The second set of instances is similar to the instances from [5]. They are
based on the road network of Western Europe provided by PTV AG for scientific
use. We conducted our experiments on the road network of the Czech Republic
(CZE, 23,094 nodes, 53,412 edges), Luxembourg (LUX, 30,661 nodes, 71,619
edges), Ireland (IRL, 32,868 nodes, 71,655 edges) and Portugal (PRT, 159,945
nodes, 372,129 edges, only for the tree-deletion experiments). As metrics we
used similar metrics as in [5]: travel distance, cost based on fuel consumption
and travel time. The median Pareto-front sizes are 13.0, 30.5, 12.5 and 133.5,
respectively and thus comparable or larger than those in [5]. For each of the
instances we drew 50 pairs of source and target nodes.
5.2

Running Times Node Selection vs. Label Selection

In Fig. 3 we see a selection of the results on the RandomN-large, RandomK-large,
GridK-large as well as the real-world road network instance sets.
To evaluate the results we decided to show box plots, because the deviation
of the running times is very large and it is easier to recognize trends. The box
plots give a direct overview on the quartiles (box dimension), median (horizontal
line inside the box), deviation from the mean (whiskers: lines above and below
the box) and outliers (points above and below the whiskers).
We see that the node-selection strategy performs better on all these instances
than the label-selection strategy. The node-selection strategy is up to a factor of
3 faster on both test sets. This is also true for the other large and medium sized
instances where the maximum factors range from 1.4 to 3.17. Detailed box plots
can be found in the appendix.
Also on the real-world road networks the results are positive. The nodeselection strategy is up to factor of 3.16 faster than the label-selection strategy.

8

2

3

4

5

6

7

8

9

CZE

IRL

LUX

12
100

10

8
Method
LS

6

Method
LS

10

NS

NS

4

2

1

0
2

3

4

5

6

7

8

9

CZE

IRL

LUX

Number of Objectives

(a) RandomK-large
1

2

3

4

5

6

7

8

(b) Real-world road networks

9 10 11 12 13 14 15 16 17 18 19 20

2

3

4

5

6

7

8

9

10
20
8
15

Method
LS

10

NS

5

Method
6

LS
NS

4

2

0

0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

Number of Nodes (in thousands)

(c) RandomN-large

2

3

4

5

6

7

8

9

Number of Objectives

(d) GridK-large

Fig. 3: Comparison of the running times (in seconds) of the label-selection (LS)
and node-selection (NS) strategies

A partial explanation can be attributed to memory management: In the nodeselection strategy a consecutive chunk of memory which contains the values of the
labels pushed along an arc can be accessed in one cache access. While in the labelselection strategy only one label is picked in each iteration, producing potentially
many cache misses when the next label—potentially at a very different location—
is accessed.
5.3

Tree-Deletion Pruning

The results concerning TD are ambiguous. First, to see how well TD might
work, we performed a set of experiments showing how many labels are touched
by the label correcting algorithms which could have been deleted when using
tree-deletion pruning. In Fig. 4, we see the results of this experiment on the
CompleteN-large, CompleteK-large, GridK-large and RandomK-large test
sets.
We observe that on these instances, especially the node-selection strategy
tends to produce larger obsolete trees than the label-selection strategy. We also

9

10

20

30

40

50

60

70

80

90 100 110 120 130 140

2

3

4

5

6

7

8

9

80000

150000
60000
Method
100000

LS

Method
LS

40000

NS
50000

NS
20000

0

0
10

20

30

40

50

60

70

80

90 100 110 120 130 140

2

3

Number of Nodes

3

4

5

6

7

8

5

6

7

8

9

Number of Objectives

(a) CompleteN-large
2

4

(b) CompleteK-large

9 10 11 12 13 14 15 16 17 18 19 20

2

3

4

5

6

7

8

9

20000

1000
15000
Method

Method

LS

LS
10000

NS

500

NS

5000

0

0
2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

Number of Objectives

(c) GridK-large

2

3

4

5

6

7

8

9

Number of Objectives

(d) RandomK-large

Fig. 4: Measuring how many nodes have been touched which could have been
deleted by tree-deletion pruning in the label-selection (LS) and node-selection
(NS) strategies

observe this behavior on the complete-graph instances of medium and large size.
The situation is different on the grid-graph instances, where both algorithms
have a similar tendency to produce obsolete trees.
Another observation is that when increasing the number of objectives, the
number of obsolete trees which could have been deleted decreases in the grid and
random graph instances (see Figs. 4 b and c). This happens because when looking
at instances with a large number of objectives and totally random objective
values, most labels remain nondominated in the cleaning step. The completegraph instances are an exception here, because the number and kind of labels
pushed to each node are very diverse und so still many labels are dominated.
Hence, what we expect is that on instances where a large number of labels
is dominated in the cleaning step the tree-deletion pruning is very useful. The
results of the comparison of the running times can be seen in Fig. 5. It can
be seen on the real-world road networks that the tree-deletion pruning works

10

2

3

4

5

6

7

8

9

10

11

12

13

14

15

CZE

IRL

LUX

PRT

1.00
1000
Method

Method

NS

NS

NS-TD

NS-TD
10

0.01

2

3

4

5

6

7

8

9

10

11

12

13

14

15

CZE

IRL

LUX

PRT

Number of Objectives

(a) GridK-medium
1

2

3

4

5

6

7

8

(b) Real-world road networks

9 10 11 12 13 14 15 16 17 18 19 20

10

20

30

40

50

60

70

80

90 100 110 120 130 140

8
10

8

6
Method
NS

4

NS-TD

Method
6

NS
NS-TD

4

2
2

0

0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

NumberDofDNodesD(inDthousands)

(c) RandomN-large

10

20

30

40

50

60

70

80

90 100 110 120 130 140

Number of Nodes

(d) CompleteN-large

Fig. 5: Comparison of the running times (in seconds) of the node-selection strategy with (NS-TD) and without (NS) tree-deletion pruning

very well and we can achieve a speed-up of up to 3.5 in comparison to the pure
node-selection strategy.
On the artificial benchmark instances however, the results are not so clear.
TD works well on medium sized grid graphs with a small number of objectives
and also on complete graphs of any size. On the other instances of the artificial
benchmark set, TD performs slightly worse than the pure node-selection strategy,
especially on the large instances.
This behavior can be explained by the large number of labels which are
dominated in the road network instances. The size of the Pareto-fronts are small
compared to the instances of the artificial test set. So, we hypothesize that the
pruning strategy is especially useful if many labels are dominated in the cleaning
step and large obsolete trees can be deleted in this process. TD seems also to
work better on denser networks.
To test this hypothesis, we created a new set of random graphs. To make the
graphs more dense than in the previous instances, we drew 0.3 times the possible
number of edges and to match the small sized Pareto-fronts of the instances

11

251

501

751

1001

10

Method
LS
LS-TD
1

251

501

751

1001

Number of Nodes

Fig. 6: Comparison of the running times (in seconds) of the node-selection strategy with and without TD on the corrolated random networks
from [5] with a high correlation of the objective functions, i.e., we used a Gauss
copula distribution with a fixed correlation of 0.7. If the hypothesis is false, TD
should run slower than the pure node-selection strategy on these instances.
But the results in Fig. 6 show that TD beats the pure node-selection strategy
on these graphs. TD achieves a speed-up of up to 1.14. Using a wilcoxon signed
rank test we can also see that the hypothesis that TD is slower than the pure
node-selection strategy on these instances can be refused with a p-value of less
than 0.001.

6

Conclusion

To conclude, we showed in this paper that node-selection strategies in labeling algorithms for the MOSP problem can be advantageous, especially if implemented
carefully. So node-selection strategies should not be neglected as an option for
certain instance classes.
We showed that the tree-deletion pruning we introduced in this paper, works
well on the real-world road networks. On the artificial instances it does not seem
to work to well, which we can explain by the very low densities and unrealistic
objective functions used in these instances. To show that TD works well when
having larger correlations as in the real-world road networks and higher densities,
we also created instances which had the potential to refute this hypothesis. But
the hypothesis passed the test.

References
1. Bertsekas, D.P., Guerriero, F., Musmanno, R.: Parallel asynchronous labelcorrecting methods for shortest paths. Journal of Optimization Theory and Applications 88(2) (1996) 297–320
2. Bökler, F., Ehrgott, M., Morris, C., Mutzel, P.: Output-sensitive complexity
for multiobjective combinatorial optimization. Journal of Multi-Criteria Decision
Analysis (submitted) (2016)

12
3. Brumbaugh-Smith, J., Shier, D.: An empirical investigation of some bicriterion
shortest path algorithms. European Journal of Operational Research 43(2) (1989)
216–224
4. Clímaco, J.C.N., Pascoal, M.M.B.: Multicriteria path and tree problems: Discussion on exact algorithms and applications. International Transactions in Operational Research 19(1–2) (2012) 63–98
5. Delling, D., Wagner, D.: Pareto paths with sharc. In Vahrenhold, J., ed.: SEA
2009. Volume 5526 of Lecture Notes in Computer Science., Springer-Verlag Berlin
Heidelberg (2009) 125–136
6. Guerriero, F., Musmanno, R.: Label correcting methods to solve multicriteria
shortest path problems. Journal of Optimization Theory and Applications 111(3)
(December 2001) 589–613
7. Hansen, P.: Bicriterion path problems. In Fandel, G., Gal, T., eds.: Multiple
Criteria Decision Making Theory and Application. Volume 177 of Lecture Notes
in Economics and Mathematical Systems. Springer Berlin Heidelberg New York
(1979) 109–127
8. Martins, E.Q.V.: On a multicriteria shortest path problem. European Journal of
Operational Research 16 (1984) 236–245
9. Paixao, J., Santos, J.: Labelling methods for the general case of the multiobjective
shortest path problem: a computational study. In: Computational Intelligence
and Decision Making. Intelligent Systems, Control and Automation: Science and
Engineering. Springer Netherlands (2009) 489–502
10. Paixao, J.M., Santos, J.L.: Labelling methods for the general case of the multiobjective shortest path problem - a computational study. Technical Report 07-42,
Universidade de Coimbra (2007)
11. Raith, A., Ehrgott, M.: A comparison of solution strategies for biobjective shortest
path problems. Computers & OR 36(4) (2009) 1299–1331
12. Tung, C.T., Chew, K.L.: A multicriteria Pareto-optimal path algorithm. European
Journal of Operational Research 62 (1992) 203–209

13

Appendix
We provide all boxplots for all experiments in this appendix. Figs. 7 and 8 show
all the running times on all large and medium sized instances of the artificial
instance sets. Figs. 9 and 10 show the comparison of the node-selection strategy
with and without TD. And in Figs. 11 and 12 we can see the number of labels
which could have been delete when we had used TD. The figures are oversized
for better readability and will be removed in a final version of the paper.

14

10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

2

4

5

6

7

8

9

10

11

12

13

14

15

15

1.0

Method
LS
NS

Running]Time][s]

1.5

Running Time [s]

3

10
Method
LS
NS
5

0.5

0.0

0
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

2

3

4

5

6

Number of Nodes

7

8

9

10

11

12

13

14

15

13

14

15

Number]of]Objectives

(a) CompleteN-medium

(b) CompleteK-medium

441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225

2

3

4

5

6

7

8

9

10

11

12

6

5

Method

100

LS
NS

Running]Time][s]

Running Time [s]

150

4
Method
LS

3

NS
2

50
1

0

0
441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225

2

3

4

5

6

Number of Nodes

(c) GridN-medium
0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

5.5

6

6.5

7

8

9

10

11

12

13

14

15

13

14

15

Number]of]Objectives

7

7.5

(d) GridK-medium
8

8.5

9

9.5 10

2

3

4

5

6

7

8

9

10

11

12

25

20

Method
LS
NS
0.5

Running]Time][s]

RunningTTimeT[s]

1.0
Method

15

LS
NS
10

5

0

0.0
0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

5.5

6

6.5

7

7.5

NumberTofTNodesT(inTthousands)

(e) RandomN-medium

8

8.5

9

9.5 10

2

3

4

5

6

7

8

9

10

11

12

Number]of]Objectives

(f) RandomK-medium

Fig. 7: Comparison of the running times of the label-selection (LS) and nodeselection (NS) strategies

13

14

15

15

10

20

30

40

50

60

70

80

90

100

110

120

130

140

2

3

4

5

6

7

8

9

40
15

10

Method
LS
NS

Running]Time][s]

Running Time [s]

30

Method
LS

20

NS

5
10

0

0
10

20

30

40

50

60

70

80

90

100

110

120

130

140

2

3

4

Number of Nodes

(a) CompleteN-large
100

121

144

6

7

8

9

(b) CompleteK-large
169

2
80

Running Time [s]

5

Number]of]Objectives

3

4

5

6

7

8

9

10

8

60
Method
LS

Method
6

LS

NS

40

NS

4
20

2

0

0
100

121

144

2

169

3

4

(c) GridN-large

1

2

3

4

5

6

7

8

5

6

7

8

9

8

9

Number of Objectives

Number of Nodes

(d) GridK-large

9 10 11 12 13 14 15 16 17 18 19 20

2

3

4

5

6

7

12
20

10

8

15

Method
LS

10

Method
LS

6

NS

NS
4

5
2
0

0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

Number of Nodes (in thousands)

(e) RandomN-large

2

3

4

5

6

7

Number of Objectives

(f) RandomK-large

Fig. 8: Comparison of the running times of the label-selection (LS) and nodeselection (NS) strategies

8

9

16

10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

2

3

4

5

6

7

8

9

10

11

12

13

14

15

10.0

0.6
Method
NS
NS-TD

0.4

Running[Time[[s]

RunningDTimeD[s]

0.8

Method
NS
NS-TD
0.1

0.2

0.0
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

2

3

4

5

6

NumberDofDNodes

7

8

9

10

11

12

13

14

15

Number[of[Objectives

(a) CompleteN-medium

(b) CompleteK-medium

441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225

2

3

4

5

6

7

8

9

10

11

12

13

14

15

100

1.00

Running Time [s]

80

Method
60

Method

NS

NS

NS-TD

NS-TD

40

0.01
20

0

2

441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225

3

4

5

6

7

8

9

10

11

12

13

14

15

Number of Objectives

Number of Nodes

(c) GridN-medium

(d) GridK-medium

0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10

2

3

4

5

6

7

8

9

10

11

12

13

14

15

10.0
0.8

Method
NS
0.4

NS-TD

Running[Time[[s]

RunningTTimeT[s]

0.6
1.0

Method
NS
NS-TD

0.2
0.1

0.0
0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10

NumberTofTNodesT(inTthousands)

(e) RandomN-medium

2

3

4

5

6

7

8

9

10

11

12

Number[of[Objectives

(f) RandomK-medium

Fig. 9: Comparison of the running times of the node-selection strategy with (NSTD) and without (NS) tree-deletion pruning

13

14

15

17

2

10

20

30

40

50

60

70

80

3

4

5

6

7

8

9

90 100 110 120 130 140

10

8
Method
6

NS
NS-TD

4

Running[Time[[s]

10.0

2

Method
NS

1.0

NS-TD

0.1

0
10

20

30

40

50

60

70

80

90 100 110 120 130 140

2

Number of Nodes

3

4

(a) CompleteN-large
100

121

144

5

6

7

8

9

Number[of[Objectives

(b) CompleteK-large
169

2

3

4

5

6

7

8

9

Method
40

NS
NS-TD

Running[Time[[s]

Running Time [s]

60

1.0

Method
NS
NS-TD

20

0

0.1
100

121

144

169

2

3

4

Number of Nodes

(c) GridN-large

2

3

4

5

6

7

8

6

7

8

9

8

9

(d) GridK-large
2

1

5

Number[of[Objectives

3

4

5

6

7

9 10 11 12 13 14 15 16 17 18 19 20

6
Method
NS

4

NS-TD

Running[Time[[s]

8

1.0

Method
NS
NS-TD

2

0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

NumberDofDNodesD(inDthousands)

(e) RandomN-large

0.1
2

3

4

5

6

7

Number[of[Objectives

(f) RandomK-large

Fig. 10: Comparison of the running times of the node-selection strategy with
(NS-TD) and without (NS) tree-deletion pruning

8

9

18

10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

2

3

4

5

6

7

8

9

10

11

12

13

14

15

150000

Method

100000

LS
NS

50000

TouchedyRecursivelyyDeletedyLabels

TouchedLRecursivelyLDeletedLLabels

8000

6000

Method
LS

4000

NS

2000

0

0
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

2

3

4

5

6

NumberLofLNodes

7

8

9

10

11

12

13

14

15

13

14

15

NumberyofyObjectives

(a) CompleteN-medium

(b) CompleteK-medium

441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225

2

3

4

5

6

7

8

9

10

11

12

1000000
Method
LS
NS
500000

TouchedyRecursivelyyDeletedyLabels

TouchedaRecursivelyaDeletedaLabels

1500000
600

Method

400

LS
NS

200

0

0
441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225

2

3

4

5

6

7

NumberaofaNodes

(c) GridN-medium

9

10

11

12

13

14

15

12

13

14

15

(d) GridK-medium

0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10

2

3

4

5

6

7

8

9

10

11

12000

40000

Method

30000

LS
NS
20000

10000

TouchedyRecursivelyyDeletedyLabels

50000

TouchedRRecursivelyRDeletedRLabels

8

NumberyofyObjectives

10000

8000
Method
LS

6000

NS
4000

2000

0

0
0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10

NumberRofRNodesR(inRthousands)

(e) RandomN-medium

2

3

4

5

6

7

8

9

10

11

12

NumberyofyObjectives

(f) RandomK-medium

Fig. 11: Measuring how many nodes have been touched which could have been
deleted by tree-deletion pruning in the label-selection (LS) and node-selection
(NS) strategies

13

14

15

19

10

20

30

40

50

60

70

80

90 100 110 120 130 140

2

3

4

5

6

7

8

9

80000

150000
60000
Method
100000

LS

Method
LS

40000

NS
50000

NS
20000

0

0
10

20

30

40

50

60

70

80

90 100 110 120 130 140

2

3

4

Number of Nodes

(a) CompleteN-large
100

121

144

169

196

TouchedSRecursivelySDeletedSLabels

6

7

8

9

225

(b) CompleteK-large
256

289

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

80000

1000

60000
Method

Method

LS
40000

LS

NS

NS

500
20000

0

0
100

121

144

169

196

225

256

2

289

3

4

5

6

7

8

(c) GridN-large
1

2

3

4

5

6

7

8

9

9 10 11 12 13 14 15 16 17 18 19 20

Number of Objectives

NumberSofSNodes

(d) GridK-large

10 11 12 13 14 15 16 17 18 19 20

2

TouchedvRecursivelyvDeletedvLabels

5

Number of Objectives

3

4

5

6

7

8

9

80000

20000

60000
Method

15000
Method

LS
40000

NS

LS
10000
NS

20000

5000

0

0
1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19 20

NumbervofvNodesv(invthousands)

(e) RandomN-large

2

3

4

5

6

7

Number of Objectives

(f) RandomK-large

Fig. 12: Measuring how many nodes have been touched which could have been
deleted by tree-deletion pruning in the label-selection (LS) and node-selection
(NS) strategies

8

9

