On the Traveling Salesman Problem with

Hierarchical Objective Function

Tien Thanh Dam Duy Thinh Nguyen
ORLab, Faculty of Information Technology Department of Computer Science and Operations Research
VNU University of Engineering and Technology Université de Montréal, CIRRELT
Hanoi, Vietnam Montreal, Canada
thanh9810tn1@gmail.com thinhduy@cirrelt.ca

Quoc Trung Bui Trung Kien Do

Daily-Opt Joint Stock Company Department of Computer Science
Hanoi, Vietnam Hanoi National University of Education
trungbui@daily-opt.com Hanoi, Vietnam
kiendt@hnue.edu.vn

Abstract—We address a novel variant of the wellknown Trav- This problem can be applied in several scenarios in real life.
eling Salesman Problem (TSP) called the Traveling Salesman The distribution of relief aid operations after natural disasters
Problem with Hierarchical Objective (TSPHO). In this problem, is an example where priorities represent the urgency of demand
the customers are divided in to several groups with decreasing
priority levels, i.e., the first group is more important than the at each location. A number of applications of the TSPHO can
second one and the second one is more important than the third be found in commercial delivery. Suppose a company provides
one, and so on. The difference between TSPHO and the classical daily delivery service to restock retail stores. The stores which
TSP lies in the objective function. The Hierarchical Objective are out of supplies would be classified as the highest priority
does not minimize the total travel cost, but aims to minimize customers. Others stores might be grouped in clusters of lower
the completion time of the first group then the completion time
of the second group, etc. A transformation of the TSPHO into priorities depending on their stock level. The problem has
an equivalent Asymmetric TSP is first proposed from which one also potential applications in routing service technicians and
can use efficient TSP solvers such as Concorde or Lin-Kernighan- unmanned aerial vehicles [11].
Helsgaun (LKH) to solve the problem. A genetic algorithm is also There are several works in the literature related to the
developed as an alternative solution. Computational results show TSPHO in the sense that the customers are divided in more
the performance of our methods.
Index Terms—TSP, Hierarchical Objective, Graph Transfor- than one group. The Clustered Traveling Salesman Problem
mation, Genetic Algorithm (CTSP) proposed in [4] deals with the situation where a
group of customers (cluster) must be visited contiguously in an
I. I NTRODUCTION optimal, unspecified order. Panchamgam et al. [11] described a
new model for humanitarian relief routing called the Hierarchi-
The well-known Traveling Salesman Problem (TSP) is one cal Traveling Salesman Problem (HTSP). The cluster priority
of most studied problems in the field of operations research indicates the urgency of the demand. Typically, nodes with
[6]. Given a list of customers and the distances between the highest priorities need to be visited before lower priority
each pair of them, the goal of TSP is to find the shortest nodes. The d- relaxed priority rule was also considered to add
possible route that visits each customer and returns to the operational flexibility by allowing the vehicle to visit nodes of
origin location. In the TSP, the customers are supposed to priority π+1, ..., π+d but not priority π+d+l for l ≥ 1 before
have equal urgency and can be serviced in any order as visiting all nodes of priority π. However, the HTSP studies
long as the objective function is minimized. But in many the standard objective function of the TSP which minimizes
practical contexts, customers have different priority levels. the travel cost, not the hierarchical objective. The authors
This research concerns a variant of the TSP that we call made a comparison between the HTSP and the classical TSP
the Traveling Salesman Problem with Hierarchical Objective in term of worst-case behavior and pointed out the trade-off
(TSPHO). The most significant characteristic of the problem is between efficiency (distance) and priority. Recently, Nguyen
that the customers are partitioned into groups with decreasing et al. [9] reformulate the problem and propose a metaheuristic
priority levels, which means that the first group is more urgent based on Iterated Local Search. Cabral et al. [3] presented
than the second one and the second one is more urgent than the undirected Hierarchical Chinese Postman Problem (HCPP)
the third one, etc. We then consider the hierarchical objective where the edges of a graph are partitioned into clusters and
minimizing the completion time of the first group, then that must be serviced while respecting a hierarchy, or precedence
of the second group, so on and so forth. relation, between clusters. The HCPP is similar to the TSPHO
978-1-7281-3003-3/19/$31.00 ©2019 IEEE in terms of objective function; but it is an arc routing problem,
not a node routing problem. better solution with less completion time for group h. This is
The contributions of our research are as follows. We in- impossible because s∗ is the optimal solution of the problem.
troduce the TSPHO, a new variant of the classical TSP and
propose a graph transformation to convert the problem into III. T RANSFORMATION TO THE TSP
the classical TSP. We then solves it with two well-known One of the approaches used for solving the TSPHO is to
TSP solvers: Concorde (for exact solution) and Lin-Kernighan- transform the problem to a classical TSP, thus being able to
Helsgaun (for approximate solution). In addition, we imple- use any algorithm developed for the latter to be used to obtain
ment a genetic algorithm with problem-tailored components a solution to the former. We first show that the problem can be
which can solve instances that cannot be solved by two converted to an asymmetric TSP. The transformation is adapted
transformation graph-based methods. from [3] and operates on a k +1-layered graph G0 = (V 0 , E 0 ).
The rest of the paper will proceed as follows: the follow- The set V 0 is equal to V . Layer 0 contains only one vertex
ing section formally defines the problem and introduces an v00 which is a copy of the depot. Layer h contains the vertices
important characteristic of optimal TSPHO solutions. Section of Gh (h = 1, 2, ..., k). The edges of E 0 their travel time are
III describes how a TSPHO instance can be transformed to defined as follows.
a standard TSP instance from which we can use any TSP 0
• Define an arc from v0 to a vertex vi of the first layer, i.e
solver to solve the TSPHO. A genetic algorithm is described vi ∈ G1 , with travel time equal to 0.
in Section IV while computational results are presented in • For any two vertices vi and vj belonging to the same
Section V. Finally, Section VI concludes our research.
Ph h (h = 1, 2, ..., k), define an arc of travel time
layer
( l=1 Ml )tij . Its value based on the set of M which
II. P ROBLEM DEFINITION
is described in the problem formulation section above.
The problem is defined on an undirected graph G = (V, E), • For any two vertices vi and vj belonging to two consec-
where V is a set of nodes, E is a set of edges. Vertex v0 ∈ V utive layers h − 1 and h, define an arc from vi to vj of
Pk Pk
is a depot. The vertices of V are divided into k disjoint groups travel time ( l=h Ml )tij + tmax l=1 Ml where tmax is
G1 , G2 , ..., Gk with v0 ∈ G1 . Each edge (vi , vj ) is associated the maximum distance in the original matrix.
with a travel time tij satisfying triangle inequality. Let Th be • In addition, define an arc of travel time 2M1 from the
the shortest time required to service all vertices of Gh (h = vertices of Gk to the original depot v0 .
1, 2, ..., k). The TSPHO consists of constructing a tour, starting • The travel time of all remaining arcs is set to a very large
and ending at the depot, in such a way that the completion number to forbid the travel of the vehicle on these arcs
time of nodes in group 1 is minimized, then that of nodes in solutions.
in group 2, etc. This hierarchical objective can be modeled as By this transformation, we can solve the TSPHO with
minimizing the function M1 T1 +...+Mp Tp , where Mi is a very any TSP solvers. In this research, we use two start-of-the-art
large coefficient satisfying M1 >> M2 >> ... >> Mk = 1. algorithms: LKH [7] for approximate solutions and Concorde
The notation ”>>”Pmeans that in any feasible solution the [1] for exact solutions. Because the latter works on symmetric
k
relation Mh Th > j=h+1 Mj Tj must be satisfied for h = graph, we need to transform the problem again into a sym-
1, ..., k − 1. Its value can be estimated by metric TSP by a procedure proposed in [8]. However, the
transformations have a drawback when they create very large
Pk coefficients in the distance matrix which is the input of the
q=h+1 Mq Tq
Mh = TSP solvers. As showed in the experiment section, the TSP
max(thmin |Gh |, thmax )
solvers cannot handle such resulting coefficients, especially
where thmax = maxi∈Gh t0i , thmin = mini,j∈Gh tij and Tq on large instances. In the next section, we develop a genetic
is total time to service all vertices of Gq . In our research, Tq algorithm that solves directly the TSPHO and is capable of
is determined by the objective value of a feasible open-TSP complementing the shortcomings of the transformation-based
solution over the depot and vertices in Gq . methods.
The following property shows an important characteristic of
a TSPHO optimal solution and is the backbone for our solution IV. A GENETIC ALGORITHM FOR THE TSPHO
methods. Genetic algorithm (GA) is a metaheuristic inspired by the
Property 1: The hierarchical objective imposes a constraint process of natural selection. It has been applied widely to
on the order of serviced groups: nodes of the first group must successfully solve a number of routing variants (see [2, 12]
be serviced before nodes of the second group which must be for example). Algorithm 1 describes a general structure of GA
again serviced before nodes of the third group, and so on. for routing applications. Starting from an initial population,
Proof: We prove the property by contradiction. Suppose the algorithm iteratively selects two parents to generate an
that there is some node l of group g appearing between two offspring by the mean of crossover. The new individual is
nodes i and j of group h (g > h) in the optimal solution s∗ . then improved via local search procedure and inserted into
Since the travel times on edges satisfy the triangle inequality, population. This sequence of operations is performed until a
then from i we can go straight to j which will result in a termination condition is met. Whenever the population reaches
a maximum size, a number of individuals is eliminated to • relocate(2): We move one edge (i, i + 1) to another
retain best solutions. position j and therefore, the edges (i − 1, i), (i + 1, i + 2)
and (j − 1, j) are replaced by (i − 1, i + 1), (j − 1, i) and
Algorithm 1 General structure of GA for routing problems
(i + 1, j).
procedure G ENETIC A LGORITHM TSPHO • 2-opt: We take a path from i to j and then, crossover
Initialize population itself and inverse it so that the old path is replaced by the
while Termination condition is not met do new path from j to i.
Select two parents P1 and P2 • relocate(1): We move one vertex i to another position j.
Generate an offspring C by applying the crossover The edges (i − 1, i), (i, i + 1), and (j − 1, j) are replaced
on P1 and P2 by (i − 1, i + 1), (j − 1, i), and (i, j).
Educate C using local search • swap(1,1): This operator exchanges two vertices i and j.
Insert C into population Therefore, the edges (i − 1, i), (i, i + 1), (j − 1, j), and
if maximum population size is reached then select (j, j + 1) are replaced by (i − 1, j), (j, i + 1), (j − 1, i),
survivors and (i, j + 1).
return The best found solution
In our implementation, the first-improvement schema is
used. Moves are examined in the same order as above. The
Initial population: The algorithm starts by generating first
local search phase stops when all possible moves have been
population with Nmin initial solutions; each is initialized by
tried without success.
adding the depot as the first vertex. Then we iterate through
Population management: The population is managed to con-
each group of customers and add one of the Ncv closest
tain at least Nmin and at most Nmax individuals. Whenever
vertices with respect to the last added vertex with equal
the population reaches its maximum size, Nmax − Nmin
probability.
individuals are eliminated to produce the next generation.
Selection and Crossover: In order to generate a new so-
This is performed by either removing clone solutions or the
lution, the algorithm select two parents P1 and P2 in the
worst solutions. After each Nni consecutive iterations with-
population via Roulette Wheel Selection method such that
out improvements, we perform a diversification phase where
better solutions will be selected with higher probability. A new
three fourths of the individuals with lowest fitness score are
offspring is then obtained by crossover of P1 and P2 . Since
removed. After removing, we use initial population procedure
an optimal solution always has to satisfy Property 1, crossover
described above to create new solutions that are then added
operators need to preserve the order of serviced groups. There-
to the population. And finally, the algorithm is stopped after
fore, one can use any classical crossover proposed for TSP to
Nstop iterations.
perform the genetic exchange between two parents in each
group of customers. By experiments, the well-known Order V. E XPERIMENTAL RESULTS
Crossover (OX) operator is selected [5]. Figure 1 illustrates We choose instances of the Vehicle Routing Problem with
our modified crossover. roaming delivery locations proposed in [10] to generate the
instance benchmarks for the TSPHO because they satisfy the
triangle inequality. The number of nodes in the graph varies
from 63 to 238. The number of groups k is set to 2, 3, and 4.
The assignment of a customer to groups is randomly processed
in such a way that the number of customers in each group is
relatively equal.
The methods are tested on a personal computer with Intel(R)
Core(TM) i7-8550U CPU @ 1.80GHz processor, and 8192MB
RAM. By experiments, we select parameter settings for the
GA as follows: Nmin = 50, Nmax = 100, Ncv = 3, Nni =
1000, Nstop = 15, 000.
Figure 1. Crossover The comparison among three methods: Concorde, LKH and
GA under different values of k is reported in Tables I-III.
Local search: To ensure Property 1, the local search pro- In these tables, columns ”Ti ” represent the completion time
cedure is performed within the vertices of the same group of group i while columns ”Time” describe the total running
in a solution. Five local search operators have been used: time (in seconds) of the algorithms. The results in bold show
swap(1,1), swap(2,1), relocate(1), relocate(2) and 2-opt. Here the better solutions provided by the algorithms. Because the
is the schema of these local search operators: Concorde-based method cannot solve any instance with k = 4,
• swap(2,1): This operator performs an exchange of one we remove it results in Table III.
edge (i, i + 1) and one vertex j. The edges (i − 1, i), As can be seen in the result tables, GA performs the best in
(i + 1, i + 2), (j − 1, j) and (j, j + 1) are replaced by term of solution quality. Compared with LKH, it provides 2
(i − 1, j), (j, i + 2), (j − 1, i) and (i + 1, j + 1). better solutions with k = 2 and 7 better solutions with k = 3.
 Concorde LKH GA LKH GA
n n
T1 T2 Time T1 T2 Time T1 T2 Time T1 T2 T3 T4 Time T1 T2 T3 T4 Time
63 1075 2083 0.72 1075 2083 0.23 1075 2083 21.41 63 784 1506 2164 3039 0.18 784 1506 2164 3039 7.96
66 1137 2240 1.5 1139 2321 0.22 1137 2240 22.27 66 807 1651 2342 3229 0.31 807 1651 2342 3229 8.33
68 1061 2131 0.87 1061 2131 0.43 1061 2131 20.74 68 619 1433 2240 3042 0.19 619 1433 2240 3042 8.18
75 1172 2283 0.45 1172 2283 0.29 1172 2283 60.07 75 648 1609 2411 3124 0.19 648 1609 2411 3124 11.49
76 1321 2267 1.02 1321 2267 0.51 1321 2267 30.42 76 828 1732 2592 3165 0.17 828 1732 2592 3165 11.38
80 1096 2369 0.50 1096 2369 0.31 1096 2369 32.11 80 831 1592 2552 3237 0.19 831 1592 2552 3237 12.06
98 1549 2994 3.37 1549 2994 0.49 1549 2994 6.00 98 1122 2286 3188 4271 0.6 1091 2255 3157 4240 20.18
103 1436 2780 3.21 1436 2780 0.0.96 1436 2780 62.11 103 1070 2070 2971 3931 1.06 1026 2094 2958 3931 21.56
106 1227 2863 5.74 1227 2863 1.03 1227 2863 59.56 106 895 1834 3006 4222 1.1 895 1834 3006 4222 23.84
107 1313 2634 1.21 1313 2634 0.99 1313 2634 71.12 107 1020 1972 3013 3963 0.34 1020 1972 3013 3963 22.86
113 1287 2641 1.90 1287 2641 1.10 1287 2641 81.81 113 961 1939 2756 3821 0.75 961 1939 2756 3821 31.42
118 1409 2854 4.77 1409 2854 0.84 1409 2854 102.12 118 1011 2012 3128 4063 0.78 1011 2012 3128 4063 30.37
119 1280 2781 2.68 1280 2781 0.71 1280 2781 84.55 119 870 1919 2976 4143 0.94 870 1919 2976 4143 29.31
124 1530 2892 5.79 1530 2892 1.52 1530 2892 96.92 124 1070 2180 3099 4349 0.93 1070 2180 3099 4349 32.55
130 1723 3279 1.12 1723 3279 1.19 1723 3279 97.31 130 1257 2536 3718 4856 1.05 1257 2536 3718 4856 35.47
208 2155 4313 8.89 2155 4334 1.56 2155 4313 329.25 208 1808 3279 5054 6846 2.17 1641 3239 4756 6392 106.13
213 2104 4120 12.47 2104 4121 2.08 2104 4120 359.58 213 1577 3054 4541 5994 2.38 1577 3054 4541 5978 113.2
219 2244 4216 57.33 2244 4216 1.87 2244 4216 368.25 219 1661 3124 4640 6124 2.46 1654 3117 4633 6117 121.02
225 2370 4746 5.57 2370 4746 1.85 2370 4746 409.29 225 - - - - - 1576 3318 4996 6842 135.02
226 2230 4559 24.72 2230 4559 1.97 2230 4559 510.83 226 1808 3279 5054 6846 2.73 1808 3279 5054 6846 131
229 2257 4456 26.56 2257 4456 2.18 2257 4456 436.25 229 - - - - - 1621 3291 4739 6507 129.02
234 2143 4161 13.70 2144 4162 2.18 2144 4162 442.59 234 1576 3073 4589 5971 4.06 1560 3057 4573 5955 142.04
235 2123 4307 8.17 2123 4307 2.84 2123 4307 447.64 235 - - - - - 1566 3136 4716 6213 137.7
238 2166 4568 22.17 2166 4568 2.13 2166 4568 481.08 238 - - - - - 1720 3394 5155 6800 157.37
Table I Table III
R ESULTS WITH k = 2 R ESULTS WITH k = 4

Concorde LKH GA
n
T1 T2 T3 Time T1 T2 T3 Time T1 T2 T3 Time
63 894 1621 2609 0.25 894 1621 2610 0.15 894 1621 2609 12.52
by the the fact that the double graph transformations (one from
66 933 1858 2858 0.55 933 1858 2858 0.19 933 1858 2858 13.04 TSPHO to asymmetric TSP and one from asymmetric TSP to
68 927 1795 2681 0.22 927 1795 2681 0.11 927 1795 2681 14.85 symmetric TSP) create very large coefficients in the distance
75 946 1920 2746 0.44 946 1920 2746 0.2 946 1920 2746 15.76 matrix that cannot be handled by Concorde. The performance
76 1165 2147 2749 0.41 11652147 2749 0.14 1165 2147 2749 16.27
80 945 2059 2846 0.78 945 2059 2846 0.26 945 2059 2846 16.16 of the LKH-based method is relatively good. It is the fastest
98 1286 2464 3692 3.40 12862464 3709 0.43 1286 2464 3692 32.84 algorithm but when compared to other approaches, it provides
103 1138 2226 3369 1.00 11382226 3369 0.42 1138 2226 3369 33.73 worse solutions in several cases. Moreover, it returns the
106 1009 2238 3600 5.66 10092238 3600 0.4 1009 2238 3600 32.82
message error due to large edge weight on four instances with
107 1079 2296 3408 0.62 10792296 3408 0.45 1079 2296 3408 35.97
113 1073 2169 3228 1.04 10742130 3189 0.34 1073 2169 3228 40.78 k = 4.
118 1105 2311 3556 2.64 11052311 3556 0.76 1105 2311 3556 47.60
119 1058 2304 3590 0.72 10662312 3598 0.38 1058 2304 3590 44.25
124 1226 2397 3630 1.94 12262397 3630 0.71 1226 2397 3630 53.03 VI. C ONCLUSIONS
130 1390 2798 4146 8.18 13922800 4148 0.70 1390 2798 4146 56.87
208 - - - - 1838 3612 5372 1.99 1838 3612 5372 167.43
213 - - - - 1808 3507 5211 2.41 1805 3504 5208 171.58 In this paper, we study a new variant of the TSP problem
219 - - - - 1906 3670 5385 2.37 1906 3670 5385 190.84 that called Traveling Salesman Problem with Hierarchical
225 - - - - 1806 3919 5853 2.13 1806 3919 5853 199.98 Objective (TSPHO). The problem has a number of routing
226 - - - - 1906 3866 5840 1.99 1906 3866 5826 190.97
229 - - - - 1905 3669 5584 2.94 1905 3669 5584 225.93
applications in which the demand of customers with higher
234 - - - - 1708 3429 5126 2.56 1708 3429 5126 217.03 urgency level must be strictly taken into account. We propose
235 - - - - 1786 3649 5467 2.33 1786 3649 5467 214.98 graph transformations to convert TSPHO to a standard TSP
238 - - - - 1843 3694 5682 2.95 1830 3681 5669 219.90 and use Concorde and LKH to solve the problem. A genetic
Table II
R ESULTS WITH k = 3 algorithm with problem-tailored components: population initi-
ation, crossovers, local search, and population management
is developed. The experimental results show that our GA
can provide better solutions than two transformation-based
Remarkably, it absolutely outperforms LKH-based algorithm algorithms can. However, the speed of our GA is quite slow. If
on instances with k = 4. The running time of GA is the longest fast solution process is more important, we recommend Con-
but it never excesses 500 seconds for medium-sized instances corde and LKH-based algorithms when the size of instances
with around 200 customers, thus still acceptable. Concorde- and the number of customer groups are small. If these two
based method can solve to optimality all instances with k = 2 algorithm cannot solve the problem, GA is a good alternative.
in very small amount of time but fails to provide any solution In the future, we will adapt the proposed methods to tackle
on instances with more than 130 nodes and k = 3. It also the capacitated version of the problem: the vehicle routing
cannot handle any instance with k = 4. These can be explained problem with hierarchical objective function.
 ACKNOWLEDGMENT
This research is funded by Vietnam National Foundation for
Science and Technology Development (NAFOSTED) under
grant number 102.99-2016.21.
R EFERENCES
[1] Applegate, D., Bixby, R., Chvatal, V., and Cook,
W. (2006). Concorde TSP Solver. Available at.
http://www.math.uwaterloo.ca/tsp/concorde/index.html.
[2] Bulhões, T., Hà, M. H., Martinelli, R., and Vidal, T.
(2018). The vehicle routing problem with service level
constraints. European Journal of Operational Research,
265(2):544–558.
[3] Cabral, E. A., Gendreau, M., Ghiani, G., and Laporte, G.
(2004). Solving the hierarchical chinese postman problem
as a rural postman problem. European Journal of Opera-
tional Research, 155(1):44–50.
[4] Chisman, J. A. (1975). The clustered traveling salesman
problem. Computers & Operations Research, 2(2):115–119.
[5] David, L. (1985). Applying adaptive algorithms to
epistatic domains. IJCAI, 85:162–164.
[6] Gutin G, P. A., editor (2002). Traveling salesman problem
and its variations. Kluwer Academic Publishers.
[7] Helsgaun, K. (2000). An effective implementation of
the lin-kernighan traveling salesman heuristic. European
Journal of Operational Research, 126(1):106–130.
[8] Jonker and Volgenant (1983). Transforming asymmetric
into symmetric traveling salesman problems. Operations
Research Letters, 2:161–163.
[9] Nguyen, P.-H., Tran, N.-N.-H., Hà, M.-H., Langevin, A.,
and Trépanier, M. (2018). Solving the clustered traveling
salesman problem with d-relaxed priority rule. arXiv
preprint arXiv:1810.03981.
[10] Ozbaygin, G., Karasan, O. E., Savelsbergh, M., and
Yaman, H. (2017). A branch-and-price algorithm for the
vehicle routing problem with roaming delivery locations.
Transportation Research Part B: Methodological, 100:115–
137.
[11] Panchamgam, K., Xiong, Y., Golden, B. L., Dussault,
B., and Wasil, E. A. (2013). The hierarchical traveling
salesman problem. Optimization Letters, 7(7):1517–1524.
[12] Pham, T. A., Hà, M. H., and Nguyen, X. H. (2017).
Solving the multi-vehicle multi-covering tour problem.
Computers & OR, 88:258–278.