# Exact and Heuristic Algorithms for Routing AGV on Path with Precedence Constraints

Authors: Liang Xu; Yao Wang; Lin Liu; Jiaxing Wang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A new problem arises when an automated guided vehicle (AGV) is dispatched to visit a set of customers, which are usually located along a fixed wire transmitting signal to navigate the AGV. An optimal visiting sequence is desired with the objective of minimizing the total travelling distance (or time). When precedence constraints are restricted on customers, the problem is referred to as traveling salesman problem on path with precedence constraints (TSPP-PC). Whether or not it is NP-complete has no answer in the literature. In this paper, we design dynamic programming for the TSPP-PC, which is the first polynomial-time exact algorithm when the number of precedence constraints is a constant. For the problem with number of precedence constraints, part of the input can be arbitrarily large, so we provide an efficient heuristic based on the exact algorithm.


---

## Body

## 1. Introduction

A traveling salesman problem on path (TSPP for short) arises in dispatching an automated guided vehicle (AGV) to visit a set of locations along the wire which transmits signal to navigate the AGV. For the wired AGV, a slot is cut into the floor where a wire is placed, and the slot is cut along the path that the AGV is to follow. A sensor installed on bottom of the AGV detects the radio signal from the wire to navigate the AGV. The areas where AGVs are applied have increased significantly. By survey of Vis [1], typical applications of AGVs include manufacturing, distribution, and transshipment. Other contexts for TSPP can also be found in the applications of other linear service networks, such as laser drill in manufacturing, tracked crane in container terminal, and school bus shuttling in transportation.We then illustrate the TSPP by the example in Figure1.Figure 1
Example to illustrate the TSPP.In this example, the AGV is travelling along the wire (in grey) to shuttle materials between the two conveyors to the four workstations. It has in total four workstations to be visited, where conveyor 1 is the start point of salesman. We denote the start point as 0 and denote the four workstations as 1, 2, 3, and 4, respectively. There are two precedence constraints restricted on the four customers as follows:(1)
P
1
:
0
⟶
3
⟶
1
,
P
2
:
0
⟶
4
⟶
2
,which means that customer 3 should be visited before customer 1 and customer 4 should be visited before customer 2.Imbedded by the special underlying network, TSPP is a special case of the classic traveling salesman problem. Without any constraints, TSPP can be solved trivially. Though there are a deluge of researches contributing to TSP and its varieties, there is no, as far as we know, literature dealing with TSPP-PC directly. Although TSP with precedence constraints, as a special case of TSP, is known to be NP-complete (Garey and Johnson [2]), whether or not TSPP-PC is NP-complete is unknown in literature. In this paper, we design dynamic programming for the TSPP-PC, which is the first polynomial-time exact algorithm when the number of precedence constraints is a constant. For the problem with number of precedence constraints, part of the input can be arbitrarily large, so we provide an efficient heuristic based on the exact algorithm.The exact algorithm is based on dynamic programming, which takes into consideration the last vertices in all precedence constraints visited by the salesman rather than all the vertices visited. Since the number of precedence constraints is a constantk, then the dynamic programming is expected to achieve a polynomial-time running time.This paper is organized as follows: Section2 is the literature review for the related research and Section 3 introduces the formal problem definition. The dynamic programming for TSPP-PC is provided in Section 4, and the dynamic programming can be proved to be the first polynomial-time exact algorithm for TSPP-PC with number of precedence constraints being a constant. In Section 5, we study TSPP-PC with arbitrary large precedence constraints and develop a heuristic based on the exact algorithm. We have a conclusion and give suggestions for the future work in Section 6.


## 2. Literature Review

TSP is intensively famous and well-studied in the literature [3], which includes two main streams of varieties: time windows (Foccaci et al. [4]) and precedence constraints (Mingozzi et al. [5]). As we know, it is a NP-hard problem; hence there is no general polynomial-time exact algorithm. However, many exact but not polynomial-time algorithms are developed to solve TSP. One may refer to Lawler et al. [6] to take a glance at general TSP solution approaches.Though TSP is not polynomial-time solvable unless NP =P, there are many special cases which are well solvable. Lawler et al. [6] and Burkard et al. [7] provide complete surveys for the well solvable special cases of TSP. The most important special case of solvable TSP is so-called pyramidally solvable TSPs. The pyramidal tours have two nice properties. First, finding a minimum cost pyramidal tour takes only O
(
n
2
) time, in terms of computation complexity. Second, there exist certain structures of distance matrix which guarantee the existence of a pyramidal optimal tour. Up to now, this distance matrix structure has been found to guarantee the shortest pyramidal tour: Monge matrices, Supnick matrices, Demidenko matrices, Kalmanson matrices, Van der Veen matrices, and generalized distribution matrices. All of these special matrices impose certain conditions on the distance matrices and, therefore, guarantee the existence of pyramidal optimal tour.Though the general Euclidean TSP is still NP-hard (Sanjeev [8]), there are some cases that are well solvable. One of them, which is similar to TSPP, is k-line TSP introduced in Deĭneko and Woeginger [9], where the vertices lie on k parallel (or almost parallel) lines in the Euclidean plane. TSPP is a special case of k-line Euclidean TSP with k
=
1. However, the previous research on this scope does not incorporate the considerations of precedence constraints.The permuted Monge TSP introduced in Burkard et al. [10] also forms an extensive large class of solvable TSPs. A matrix C is called a permuted Monge matrix if there exists a permutation ϕ such that C
ϕ is a Monge matrix. Similar to Euclidean TSP, although the general TSP on permuted Monge matrices is not polynomial solvable, a number of specific forms of matrices provide the possibility of polynomial solving algorithm.For the TSP, some works contribute to the literature by providing approximation algorithms rather than exact algorithms. Based on a tree algorithm which is used to provide an approximated TSP tour, Rathinam et al. [11] have developed a 2-approximation algorithm for multiple traveling salesmen problem. Later, Xu et al. [12] improved this result to (
2
-
1
/
k
) through providing extended Christofides heuristics for this problem. Later, Xu and Rodrigues [13] have developed a 3
/
2-approximation algorithm called Exchange Algorithm for the same problem, which achieves the best approximation ratio unless the 3
/
2 Christofides heuristics for the TSP can be further improved.Mingozzi et al. [5] proposed a dynamic programming strategy for the TSP with time windows and precedence constraints, and a nice bounding function is adopted to reduce the state space graph. In the dynamic programming of Mingozzi et al. [5], its state is defined as (
S
,
τ
,
j
), which can be interpreted as the family of all possible paths from the start point, visiting all customers in the customer subset S, stopping at customer j, and finishing visiting at time τ. Since the set S clearly has an exponential size to the problem scale, the dynamic programming cannot be expected to achieve a polynomial-time running time to return an optimal solution to the TSPP-PC. For TSP with precedence constraints, Moon et al. [14] presented an efficient genetic algorithm, in which a topological sort is utilized, and a new crossover operation is developed for genetic algorithm.Though the TSP with precedence constraints has been studied in the literature, we still need to bridge the gaps for TSPP-PC. The first gap lies in lacking of an answer to the open question of whether or not the problem is NP-complete. The second gap is the absence of an efficient heuristic for the AGV industry.


## 3. Problem Definition

In TSPP-PC, a salesman is supposed to visit a set of vertices, which are located along a path. The distance between two vertices is measured by the Euclidean distance on the path. The objective of the TSPP-PC is to determine the optimal sequence of the vertices to be visited with the total traveling distance minimized and without violating the given precedence constraints.Formally, we can represent the TSPP-PC as follows. Suppose the salesman is located at0, so-called start point, originally, and he is expected to visit a set of vertices along a path, denoted by V
=
{
1,2
,
…
,
n
}. For i
=
1,2
,
…
,
n, we use x
i to denote the coordinate of vertex i and use X to denote {
x
1
,
x
2
,
…
,
x
n
}. Hence, the distance between i and j, denoted by d
i
j, is determined by (2)
d
i
j
=
x
i
-
x
j
. The objective of the problem is to determine a sequence (
i
1
,
i
2
,
…
,
i
n
) of vertices, such that the total travel distance D where (3)
D
=
d
0
,
i
1
+
d
i
1
,
i
2
+
⋯
+
d
i
n
-
1
,
i
n
+
d
i
n
,
0 is minimized, without violating the precedence constraints imposed. That is, the salesman starts from the start point, visits all the vertices one by one as the sequence, and finally returns to the start point, subject to the precedence constraints. Let P denote the collection of all the k precedence constraints, P
i for i
=
1,2
,
…
,
k. Strictly, (4)
P
=
P
1
,
P
2
,
…
,
P
k
, where P
i is denoted as (5)
v
e
r
t
e
x
v
i
,
0
v
i
,
1
v
i
,
2
⋯
v
i
,
l
i
p
r
i
o
r
i
t
y
0
1
2
⋯
l
i
.We have v
i
,
0
=
0 for i
=
1,2
,
…
,
k, which means that each precedence constraint must begin from vertex 0. For any single precedence P
i with l
i
+
1 vertices, it is noted that v
i
,
j has the jth priority. The vertex v
i
,
j can be visited if all vertices v
i
,
t with higher priority (t
<
j) have been visited. For simplicity of notation, we denote the precedence P
i as (
v
i
,
0
,
v
i
,
1
,
…
,
v
i
,
l
i
). Taking P
2 in the first section as an example, P
2
=
(
v
2,0
,
v
2,1
,
v
2,2
)
=
(
0,4
,
2
), where l
2
=
2 and vertex 0 must be visited before vertex 4 and vertex 2 can be visited unless vertex 4 has been visited. Thus, any instance of TSPP-PC can be described as (
V
,
X
,
P
).One can notice that, for instance(
V
,
X
,
P
) to the TSPP-PC, in a single precedence constraint, a vertex v appears exactly once; otherwise, multiple v in a single precedence constraint leads to a contradiction because any vertex u in between consecutive v’s should be visited both after v and before v. Furthermore, if more than one precedence constraint shares a common vertex v, the instance (
V
,
X
,
P
) may have no feasible solution because two precedence constraints share common vertices that may be contradictive. For example, the two precedence constraints P
1
=
(
0,2
,
1,3
) and P
2
=
(
0,1
,
4,5
,
2
) share two vertices 1 and 2, and the two constraints are contradictive because 2 should be visited before 1 in P
1 and 2 should be visited after 1 in P
2, which implies there exists no feasible solution for this instance. To guarantee existence of feasible solution, we consider only those instances that all precedence constraints in P share no common vertex, which implies that each vertex appears in all precedence constraints in P at most once. For precedence P
i where i
=
1,2
,
…
,
k, any vertex v can be visited if and only if all vertices in P
i before v have been visited.In this paper, we first consider the number of precedence constraints,k, is independent of the instance input and design the polynomial-time exact algorithm with time complexity O
(
k
n
k
+
1
) based on dynamic programming. Since the exact algorithm has an exponential running time when k is part of the problem instance and can be arbitrarily large, we design a heuristic algorithm based on the exact algorithm for the TSPP-PC with two precedence constraints.Next, we show as follows that, for any instance of the TSPP-PC, finding an optimal visiting sequence inP suffices an optimal visiting sequence in V. Let x
R denote the coordinate which is the biggest among all the vertices in P. That is, x
R
=
arg
⁡
max
⁡
{
x
i
∣
i
∈
P
}. We further define the set of vertices that are on the right-hand side of vertex x
R as R; that is, R
=
{
i
∈
V
∣
x
i
>
x
R
}.Furthermore, we define the setL
=
{
i
∈
V
∖
P
∣
x
i
≤
x
R
}. Clearly, the set of V is decomposed as P, R, and L; that is, V
=
P
∪
R
∪
L.We are now in position to present the first property of TSPP-PC to remove the consideration of vertices inR and L.Property 1.
For any instance of TSPP-PC, an optimal solution must be in the form of(
…
,
x
R
,
R
,
…
) where the solution visits vertices in R one by one after it visits the vertex x
R.This is true because there is no precedence constraint imposed on the vertices inR and finally to reach the vertex n, the distance of trip from x
R to x
n and from x
n back to x
R could not be shortened.Due to Property1, we can remove the consideration of the vertices in R. After we obtain the optimal visiting sequence in the vertex set which excludes R from V, we insert the vertices in R to establish the final sequence.Furthermore, we are even able to remove the consideration of vertices inL. That is because when we schedule the vertices in P, to reach the vertex x
R, the salesman would pass by all the vertices in L as the continuity of the traveling. Because the vertices in L have no precedence constraint, the salesman could visit these vertices when passing by them.Based on the fact above, we can simplify this problem by removing the consideration of the vertices inL and R. After an optimal visiting sequence in P is obtained, we can solve the problem with L and R as shown in Algorithm 1:Algorithm 1 (transformation of optimal sequence inP to optimal sequence in V).
⁡⁡
Input. An optimal visiting sequence in P is denoted as S
P.
Output. An optimal visiting sequence in V is denoted as S
V.(1)
SetS
V
=
〈
0
〉.
(2)
Find the setsP, L, and R, and x
R
=
arg
⁡
max
⁡
{
x
i
∣
i
∈
P
}.
(3)
Insert the vertices inL into S
P when the salesman passes by them. Afterwards, we obtain a new sequence S
R.
(4)
Insert the vertices inR into S
R after x
R in a nondecreasing order to obtain S
V.The following theorem states the correctness for Algorithm1.Theorem 2.
Given any optimal visiting sequenceS
P for P, Algorithm 1 returns an optimal visiting sequence S
V for V
=
P
∪
L
∪
R.Proof.
We prove the correctness for Theorem2 by contradiction. Suppose there exists a visiting sequence S
V
′ with total distance d, whose travel distance is shorter than S
V. We can construct as follows a shorter visiting sequence S
P
′. Since the distance from x
R to the farthest vertex in R is a constant, denoted as d
1, then shortcutting all vertices in R from S
V
′ leads to a visiting sequence S
R
′ with distance d
-
d
1. Note that S
R
′ has a shorter distance than the visiting sequence S
R obtained in Algorithm 1 because S
R has a distance d
1 shorter than S
V. Finally, notice that shortcutting vertices in L from S
R
′ obtains S
P
′ with the same travel distance and shortcutting vertices in L from S
R obtains S
P with the same travel distance. One can conclude that the travel distance for S
P
′ is less than S
P, which contradicts the assumption that S
P is the optimal visiting sequence in P.


## 4. Exact Algorithm for TSPP-PC

In this section, we focus on the TSPP-PC with constant precedence constraints. As mentioned before, our task is to find the first polynomial-time exact algorithm for this problem.Before introducing our dynamic programming for finding the optimal sequence inP, we need to state a new property for an optimal solution which is a basis of our dynamic programming.Property 2.
For any instance of the TSPP-PC, an optimal sequence must visit a new vertex (the vertex that has not been visited in the existing sequence) at each step of the salesman. Thus, an optimal sequence contains each vertex inP exactly once.This property holds by the fact that, supposing the salesman visits a vertexi more than once in a sequence, we can always shortcut duplicated i to obtain a new sequence with equal or shorter total length.We uses
i to denote the last vertex that salesman has just visited in the ith precedence, and so we can use S
=
(
s
1
,
s
2
,
…
,
s
k
) to denote the set of vertices that the salesman has just visited in the k precedence constraints.Recall that thek precedence constraints are imposed by(6)
P
1
=
0
,
v
1,1
,
v
1,2
,
…
,
v
1
,
l
1
,
P
2
=
0
,
v
2,1
,
v
2,2
,
…
,
v
2
,
l
2
,
⋮
P
k
=
0
,
v
k
,
1
,
v
k
,
2
,
…
,
v
k
,
l
k
.By definition ofS
=
(
s
1
,
s
2
,
…
,
s
k
), we can conclude that if the salesman has visited s
i in P
i for i
=
1,2
,
…
,
k, then all the vertices in P
i before s
i have been visited and all the vertices in P
i after s
i have not been visited.Let(
t
,
S
) denote the state that the salesman has just visited S
=
(
s
1
,
s
2
,
…
,
s
k
) in all the precedence constraints and stops at the vertex s
t, where 1
≤
t
≤
k.Letf
∗
(
t
,
S
) denote the minimum travel time taken by the salesman who starts from the start point and ends up with state (
t
,
S
). We use Γ
(
t
,
S
) to denote all those states (
t
′
,
S
′
) that can reach state (
t
,
S
) by exact one step of the salesman. For any vertex v in P with v
≥
0, let σ
-
1
(
v
) denote the immediately previous vertex before v in the precedence that contains v. Let σ
t
-
1
(
S
) denote the vector obtained by replacing s
t in S by σ
-
1
(
s
t
). It is noted that, for the state (
t
,
S
), since the salesman has visited all the vertices in S and stops at s
t, then before salesman’s last step, he must have visited all the vertices in σ
t
-
1
(
S
) and can start from any vertex of σ
t
-
1
(
S
) to reach s
t in the last step. Hence, by definition of Γ
(
t
,
S
) and above analysis, we can see that (7)
Γ
-
1
t
,
S
=
t
′
,
S
′
∣
S
′
=
σ
t
-
1
S
,
1
≤
t
′
≤
k
.With the current state being(
t
,
S
), if s
t
≥
0 (the vertex s
t has a previous vertex in P
t), before the step which arrives at the state (
t
,
S
), the salesman must start with a state t
′
,
S
′
∈
Γ
(
t
,
S
) and arrives s
t via the edge (
s
t
′
,
s
t
). Meanwhile, with the current state being (
t
,
S
), if s
t
=
0, since vertex 0 has been visited initially, according to Property 2, we do not need to consider this state as a potential for optimal solution, and thus we let f
∗
(
t
,
S
)
=
+
∞ if s
t
=
0. Then, the recursion function can be(8)
f
∗
t
,
S
=
m
i
n
t
′
,
S
′
∈
Γ
-
1
t
,
S
f
∗
t
′
,
S
′
+
d
s
t
′
,
s
t
,
s
t
>
0
;
+
∞
,
s
t
=
0
.To facilitate the dynamic programming, we define boundary conditions as follows:(9)
f
∗
t
,
S
_
=
0
,
∀
t
=
1,2
,
…
,
k
,where S
_
=
(
0,0
,
…
,
0
) in which the k coordinates are all equal to zero.Based on the recursion equation, the optimal travel time could be written as(10)
min
1
≤
t
≤
k
⁡
f
∗
t
,
S
¯
+
d
s
¯
t
,
0
,where S
¯
=
(
s
¯
1
,
s
¯
2
,
…
,
s
¯
k
) and s
¯
t denotes the last vertex in P
t for t
=
1,2
,
…
,
k.In summary, based on the dynamic programming, we describe the exact algorithm as in Algorithm3. The exact algorithm is based on Property 2. Since the salesman visits a new vertex at each step, then it takes |
V
| steps for the salesman to visit all the vertices (without the step to return to the start point). Meanwhile, it is observed that if it takes i steps (
i
>
0
) for the salesman to reach a state (
t
,
S
), then the salesman must start from a state in Γ
-
1
(
t
,
S
) which takes exact i
-
1 steps. Hence, we can iteratively calculate the state values for all states which take the salesman i steps with i
=
1,2
,
…
,
|
V
|.Algorithm 3 (exact algorithm for the TSPP-PC).
⁡⁡
Input. It is an instance (
V
,
X
,
P
) to the TSPP-PC.
Output. It is an optimal objective value to (
V
,
X
,
P
).(1)
Fort
=
1,2
,
…
,
k, calculate f
∗
(
t
,
S
_
) by boundary conditions (9).
(2)
Fori
=
1,2
,
…
,
|
V
|, do the following:
(a)
Find all the solutions for∑
j
=
1
k
‍
y
j
=
i with y
j
∈
{
0,1
,
…
,
l
j
} and denote the set of all solutions as Y
i.
(b)
For each element(
y
1
,
y
2
,
…
,
y
k
)
∈
Y
i, calculate f
∗
(
t
,
(
v
1
,
y
1
,
v
2
,
y
2
,
…
,
v
k
,
y
k
) with 1
≤
t
≤
k by recursion equation (8), where v
j
,
y
j denote the y
jth vertex (excluding vertex 0) in P
j.
(3)
Calculate the optimal objective value to(
V
,
X
,
P
) by (10).Next, we state the correctness and time complexity of Algorithm3 in the following theorem.Theorem 4.
Algorithm3 returns an optimal solution to the TSPP-PC with a time complexity in O
(
k
n
k
+
1
).Proof.
Based on the dynamic programming, to prove the correctness of Algorithm3, it suffices to prove that, for any state that can be reached by the salesman, Algorithm 3 returns its state value, that is, for t
=
1,2
,
…
,
k and any S
=
(
s
1
,
s
2
,
…
,
s
k
) with s
i
∈
P
i for i
=
1,2
,
…
,
k, Algorithm 3 returns f
∗
(
t
,
S
).
We prove the correctness by induction. First, for those states that can be reached by 0 step, that is, fort
=
1,2
,
…
,
k and S
_
=
(
0,0
,
…
,
0
), we have f
∗
(
t
,
S
_
)
=
0. For any state that can be reached by the salesman with i
-
1 steps, suppose the state values have been returned by Step (2) of Algorithm 3 when it is repeated for i
-
1. We prove as follows, for any state that can be reached by the salesman with i steps, the state values are returned by Step (2) of Algorithm 3 when it is repeated for i. For any state (
t
,
S
) that can be reached with i steps, by definition of Y
i, since the salesman visits one new customer in each step and the total number of customers that have been visited is i, it can be seen that there exists (
y
1
,
y
2
,
…
,
y
k
)
∈
Y
i such that S
=
(
v
1
,
y
1
,
v
2
,
y
2
,
…
,
v
k
,
y
k
).
According to definition ofY
i
-
1, we know that there exists (
y
1
′
,
y
2
′
,
…
,
y
k
′
)
∈
Y
i
-
1 such that ∑
j
=
1
k
|
y
j
′
-
y
j
|
=
1. By assumption of the induction, all the state values for (
t
′
,
S
′
) with 1
≤
t
′
≤
k and S
′
=
(
v
1
,
y
1
′
,
v
2
,
y
2
′
,
…
,
v
k
,
y
k
′
) have been returned, which implies that Γ
-
1
(
t
,
S
) have been returned. Thus, by recursion equation (8), the state value f
∗
(
t
,
S
) can be returned.
We analyze the computation complexity of this exact algorithm as follows. The number of precedence constraints isk. In Algorithm 3, each iteration of Step (2) needs to calculate state value f
∗
(
t
,
S
) with t
=
1,2
,
…
,
k and S
=
(
s
1
,
s
2
,
…
,
s
k
) where s
i
∈
P
i for i
=
1,2
,
…
,
k, which has a running time in O
(
k
n
k
) (l
i
≤
n for i
=
1,2
,
…
,
k). Then, totally, the computation effort of Algorithm 3 is in O
(
k
n
k
+
1
), which has a polynomial running time only when k is a constant independent of the input size.Example 5.
Let us use the example in Section1 to illustrate the exact algorithm for TSPP-PC.
First, by boundary conditions in (9), in Step (1) Algorithm 3, when t
=
1 and t
=
2 we have (11)
f
∗
1
,
0,0
=
0
,
f
∗
2
,
0,0
=
0
.
Then, in Step (2)(a), wheni
=
1, we have (12)
Y
1
=
0,1
,
1,0
. For (
y
1
,
y
2
)
=
(
0,1
)
∈
Y
1 and t
=
1, we have v
1
,
y
1
=
0 and v
2
,
y
2
=
4. Then, by recursion equation (8) with S
=
(
s
1
,
s
2
)
=
(
0,4
) and t
=
1, since s
1
=
0, we have (13)
f
∗
1
,
0,4
=
+
∞
. For (
y
1
,
y
2
)
=
(
0,1
)
∈
Y
1 and t
=
2, we have v
1
,
y
1
=
0 and v
2
,
y
2
=
4. Then, by recursion equation (8) with S
=
(
s
1
,
s
2
)
=
(
0,4
) and t
=
2, since s
2
>
0, we have (14)
f
∗
2
,
0,4
=
min
⁡
f
∗
1
,
0,0
+
d
0,4
,
f
∗
2
,
0,0
+
d
0,4
=
4
.
Similarly, for(
y
1
,
y
2
)
=
(
1,0
)
∈
Y
1, we have (15)
f
∗
1
,
3,0
=
3
,
f
∗
2
,
3,0
=
+
∞
.
When Step (2) is repeated fori
=
2, we have (16)
Y
2
=
0,2
,
1,1
,
2,0
.
For(
y
1
,
y
2
)
=
(
0,2
), we can obtain that (17)
f
∗
1
,
0,2
=
+
∞
,
f
∗
2
,
0,2
=
6
.
For(
y
1
,
y
2
)
=
(
1,1
), we can obtain that (18)
f
∗
1
,
3,4
=
5
,
f
∗
2
,
3,4
=
4
.
For(
y
1
,
y
2
)
=
(
2,0
), we can obtain that (19)
f
∗
1
,
1,0
=
5
,
f
∗
2
,
1,0
=
+
∞
.
When Step (2) is repeated fori
=
3, we have (20)
Y
3
=
1,2
,
2,1
.
For(
y
1
,
y
2
)
=
(
1,2
), we can obtain that (21)
f
∗
1
,
3,2
=
7
,
f
∗
2
,
3,2
=
6
.
For(
y
1
,
y
2
)
=
(
2,1
), we can obtain that (22)
f
∗
1
,
1,4
=
7
,
f
∗
2
,
1,4
=
8
.
When Step (2) is repeated fori
=
4, we have (23)
Y
4
=
2,2
.
For(
y
1
,
y
2
)
=
(
2,2
), we can obtain that (24)
f
∗
1
,
1,2
=
7
,
f
∗
2
,
1,2
=
8
.
Thus, in Step (3), according to (10), we have that the optimal objective value equals (25)
min
⁡
f
∗
1
,
1,2
+
d
1,0
,
f
∗
2
,
1,2
+
d
2,0
=
8
.


## 5. Heuristic Algorithm for the TSPP-PC

Based on the dynamic programming for the TSPP-PC, we can develop the first exact algorithm for this problem. As shown in Theorem4, the dynamic programming has a time complexity of O
(
k
n
k
+
1
), which is a polynomial running time when k is a constant independent of the problem instance. The constant k precedence number commonly applies to the case when the AGV has k loading positions. For instance, when an AGV has k loading positions, it has a capacity of loading at most k items simultaneously, and thus it only needs to consider k precedence constraints where k is a constant.In comparison, for this AGV with no fixed loading positions, its loading capacity depends on the sizes of different objects, and thus the number of precedence constraints is part of the instance input. Whenk is part of the problem instance and can be arbitrarily large, the dynamic programming has an exponential running time. Hence, we need to develop an efficient heuristic for the TSPP-PC with arbitrarily large k.Although the dynamic programming has an exponentialO
(
k
n
k
+
1
) running time when k is part of the problem instance, it is still quite efficient when applied to the instance with k
=
2 (with a running time of O
(
n
3
)). Based on this observation, our heuristic for the TSPP-PC is based on an iterative insertion of vertices in one precedence constraint and applies the dynamic programming for TSPP-PC with k
=
2 to the current visiting sequence for the salesman (which can be taken as the first precedence) and the precedence that is to be inserted (which is the second precedence) to find an optimal visiting sequence for the TSPP-PC with two precedence constraints. The details of the heuristic algorithm can be described in Algorithm 6.Algorithm 6 (heuristic algorithm for the TSPP-PC).
⁡⁡
Input. It is an instance (
V
,
X
,
P
) to the TSPP-PC.
Output. It is a feasible solution S to (
V
,
X
,
P
).(1)
Let a visiting sequenceS
=
〈
0
〉. Do the following until P
=
∅.
(a)
SupposeP currently has m precedence constraints, denoted as P
1
,
P
2
,
…
,
P
m. Find the precedence P
j
∗ in P such that the first vertex in P
j
∗ has a closest distance with last vertex in V
(
S
).
(b)
Apply Algorithm3 to obtain an optimal solution S
′ to the TSPP-PC with two precedence constraints S and P
j
∗.
(c)
LetS
=
S
′ and P
=
P
∖
P
j
∗.
(2)
ReturnS.To test the efficiency of the heuristic algorithm for the TSPP-PC, we conduct several numerical experiments for different scale of problem instances. In the first set of numerical experiments, we focus on testing the average performance of the heuristic over the greedy insertion algorithm that is usually applied by the industry.In the subsequent numerical experiments, we use the following settings. In total 100 problem instances of different scales are generated. The problem instances contain only customers in the precedence constraints. Meanwhile, as mentioned before, we consider in the problem instances only those precedence constraints sharing no common customers. The 100 problem instances are divided into 10 groups with theith group having i precedence constraints for i
=
1,2
,
…
,
10. The biggest problem instance has in total 50 customers with 10 precedence constraints. Each customer is randomly generated with the coordination from {
1,2
,
…
,
200
}.In the following, we briefly introduce the greedy insertion algorithm that is usually applied in the industry. In the greedy insertion algorithm, it starts with the visiting sequence containing only the start point. In each iteration of the greedy insertion algorithm, from the current standing point of the salesman, it finds out the closest available customer that has not been visited in all precedence constraints, adds the customer to the visiting sequence, and removes the customer from the precedence. The greedy insertion algorithm repeatedly inserts customer into visiting sequence until all the customers have been inserted.Next, we compare the average objective value and running time for each group of the problem instances. In Table1(a), the second column and third column indicate the objective value and the running time for greedy insertion algorithm, the fourth and fifth column indicate the objective value and the running time for the heuristic algorithm, and the final column indicates the improvement of the objective of the heuristic versus the objective of the greedy insertion algorithm.Table 1
Average performance: Algorithm6 versus greedy insertion.
(a)
Group
Obj_GRE
Time_GRE (s)
Obj_HEU
Time_HEU (s)
Improvement (%)
1
677
0.04
640
0.035
5.7
2
816
0.019
739
0.15
10.5
3
1030
0.02
744
0.61
38.3
4
1363
0.02
926
7.2
47.2
5
1374
0.18
853
10.4
61.1
6
1564
0.25
885
31.3
76.6
7
1715
0.26
957
47
79.1
8
1915
0.28
889
55.4
115.5
9
2228
0.32
947
135
135.9
10
2309
0.48
976
215
136.5
(b)
Group
Obj_GRE
Time_GRE (s)
Obj_HEU
Time_HEU (s)
Improvement (%)
1
677
0.04
640
0.04
5.7
2
816
0.019
732
0.16
11.5
3
1030
0.02
749
0.62
37.5
4
1363
0.02
910
6.34
49.7
5
1374
0.18
862
8.85
59.4
6
1564
0.25
862
21
81.4
7
1715
0.26
924
42
85.4
8
1915
0.28
905
91
111.5
9
2228
0.32
977
122
127.9
10
2309
0.48
993
142
132.5From Table1(a), one can see that, with growth of scale of the problem instance, the heuristic algorithm has a much better average performance than the greedy insertion algorithm. For the problem instances with two precedence constraints, the objective value of the heuristic algorithm and greedy insertion algorithm is relatively close. For the problem instance with 5 precedence constraints (Group 5), the improvement ratio can be seen to be 61.1%. For the problem instance with at most 10 precedence constraints (Group 10), the improvement ratio has been raised up to 136.5%. From the perspective of the running time, when precedence constraints in each problem instance are no more than five, running times of the heuristic algorithm and the greedy insertion algorithm are comparable. With increasing of number of precedence constraints, the running time of the heuristic algorithm rises for two reasons. The first reason is that the iterations of the heuristics go up with the number of precedence constraints and the second reason is that the running time for each iteration goes up with number of the total vertices in the two precedence constraints.To test the robustness of the heuristic, we also run the 100 problem instances in a different manner which revises Step (1)(a) of Algorithm6 as inserting the precedence in P with minimum index. We also compare the average performance and running time of revised Algorithm 6 to the greedy insertion algorithm. In the following table, the second and third column indicate the average objective value and running time for the greedy insertion algorithm, the fourth and fifth column indicate the average objective value and running time for Algorithm 6, and the final column indicates the improvement of the objective of the greedy insertion algorithm versus the objective of the revised algorithm.From Table1(b), we can see that, firstly, the running times of Algorithm 6 and revised Algorithm 6 for each group are very close. Moreover, revised Algorithm 6 has a relatively close improvement ratio over the heuristic when compared to the greedy insertion algorithm. In conclusion, the heuristic algorithm based on the exact algorithm is robust with the polices that determines the precedence to be inserted in Step (1)(a) of Algorithm 6.


## 6. Conclusion

In this note, we considered the TSPP-PC, which is a variety of TSPs. Though TSP is widely studied, whether or not TSPP-PC is polynomial-time solvable remains an open question in the literature. We provide a positive answer to this problem when number of precedence constraintsk is part of the input size and develop efficient heuristic for the problem with arbitrarily large k.Future work is supposed to be taken on these directions. First, we are expecting to prove the NP-hardness for the TSPP-PC withk part of the input size. Second, for the case that different precedence constraints share common vertices, it remains to develop an exact algorithm or to prove its NP-hardness. Third, developing heuristic algorithm with searching part of the state space in the dynamic programming is supposed to be another interesting research direction.



---

*Source: 5040513-2016-07-31.xml*