Precedence And Time Windows Constrained Travelling Salesman Problem (TSP) In Maritime Surveillance

Introduction

Throughout history, the central problem in maritime warfare has been to locate and identify the enemy. Surveillance, which is defined as the systematic observation of aerospace, surface, sub-surface areas, places and objects by visual, electronic, photographic and other means, therefore, is fundamental to warfare at sea [3]. By conducting surface surveillance operations, Canada is able to enforce its presence/interest in coastal waters and thus protect Canadian sovereignty; furthermore, surveillance operations provide Canada with a means to deter non-state threats such as terrorism or illegal migrants infringing into Canadian coastal waters [4].

In brief, a surveillance operation (in Canada) initially involves the military operational commander deciding on the areas to be searched. Next, a maritime patrol aircraft (MPA) will be deployed to the areas of interest to perform the surveillance function. The aim of the operation might be to detect and classify targets/ships (or classify as many targets as possible) subject to the aircraft’s time-on-station constraint, namely the MPA is restricted to no more than 12 flying hours per day. The latter is imposed to ensure crew safety. The surveillance mission may incorporate no-fly-zones, an area over which an aircraft cannot fly [5]. Missions are often faced with the sequential ordering of searching a set of regions where precedence relations between the regions exist. Time windows or rigid lower and upper bounds on the time the regions have to be searched are also specified.

It has been observed by Marlow et al [1] and Ng and Sancho [5] that the maritime surveillance problem can be modelled as a travelling salesman problem and its variants [6]. The traveling salesman problem TSP is one of the most intensively studied problems in optimization [7,8]. It is very easy to describe but very difficult to solve. The theoretical importance of the TSP is that it belongs in the class of combinatorial optimization problems known as NP-complete. On the other hand, there are also important cases of practical problems that can be formulated as TSP or its generalizations, for example, the drilling of printed circuit boards, the overhauling of gas turbines, the analysis of the structure of crystals (www.tsp.gatech.edu/index.html). The theoretical and practical importance of the TSP has therefore resulted in significant research activities [7,8]. However, the maritime surveillance problem modelled as a TSP has its unique features. After the MPA has commenced its operations and is away from the home base, the time windows and precedence constraints frequently change or are subject to revisions because of continuous intelligence updates. To capitalize on the most recent intelligence, the revised search path subject to conditions change has to be recalculated by flight crew (on board the MPA) who are generally not equipped or knowledgeable enough to understand sophisticated analytical algorithms. Thus the solution procedure should only involve easy implementable algorithms, preferably in an interactive mode. The aim of this paper is to develop an implementable hybrid dynamic programming/heuristic algorithm for surveillance mission planning. Previously, Mingozzi, Bianco and Ricciardelli [9] have discussed the use of dynamic programming strategies for the TSP with time windows and precedence constraints. However, the calculated optimal solution may become infeasible or unacceptable when time windows or precedence relations (conditions) change. Their methodology cannot be easily implemented in an interactive mode for the flight crew. The above mentioned issues are also typical drawbacks when other existing TSP techniques are applied to solve the surveillance problem. To avoid incorporating the difficulty of time windows or precedence constraint changes in the formulation, we adopt the K best solution strategy approach [2]. The essence is to put aside the time windows and/or the precedence constraint and to compute successively more desirable solutions for the TSP until the best solution which does satisfy the change restrictions is found, namely the k^th best solution.

Model formulation

In this paper, we assume only the time windows are subject to changes because of intelligence updates. We formulate the dynamic programming formulation to the precedence constrained travelling salesman problem (PTSP). (The case of both time windows and precedence relations are subject to continuous changes can be dealt with very easily, since the dynamic programming formulation for the TSP is readily available.) We propose a ‘check and confirm’ heuristic to find the best k^th PTSP solution that satisfies the latest time windows updates.

Let N_j = {2,3,…, j–1, j+1, … , N},

P_j = set of all nodes (other than node 1) that must precede node j

and

S = subset of N_j containing i members.

Define the optimal value function:

f_i (j, S) = length of the shortest path from city 1 to city j via the set of i intermediate cities S, and satisfies the given precedence relations. (i indicates the number of cities in S).

The dynamic programming formulation is:

f_i (j, S) = min_kЄS [ f_i–1(k, S – {k}) + d_k,j ] if P_j$\subseteq$S or if P_j =Ø

= ∞ if P_j$\not\subset$ S

where d_k,j is the distance from city k to city j; i = 1,2,…,N–2; j ≠ 1; S$\subseteq$N_j,

with boundary conditions:

f₀ (j, -) = d_1j if P_j=Ø

= ∞ otherwise

The solution is given by:

Rank min_j=2,…,N {f_N–2(j,N_j) + d_j,1} values in ascending order w₁, w₂,……. The smallest and best solution is w₁ and the second-smallest value is w₂. (However, there is no guarantee that it is the second-best solution to the PTSP.) There might exist a value (or values) which is (are) larger than w₁ but less than w₂. We propose the following ‘check and confirm’ heuristic to find the in-between values and compute the K best solutions. The essence of the heuristic is based on the observation (Principle of Optimality) f_N–3(k, N_k – {j}) is the optimal policy at node k, stage N–3. It therefore suffices only to examine whether there exists a value (or values), (obtained by combining the distance from node k to the previously identified node j and f_N–3(k, N_k – {j})), between w₁, w₂. That is, we search for any ‘k’ such that:

If no ‘k’ exists, w₂ is the second-best solution. If one ‘k’ exists, then f_N–3(k, N_k–{j}) + d_k,j + d_j,1 is the second-best solution and w₂ is the third-best solution.

Suppose two ‘k’ values exist between w₁, w₂ (denoted by k₁, k₂) and let:

We investigate whether other values exist between x₁, x₂. Using the same reasoning as provided in the above, namely f_N–4(m, N_m – {k} – {j}) is the optimal policy at node m, stage N–4. We search for any ‘m’ such that:

f_N–4(m, N_m – {k} – {j}) + d_m,k + d_k,j + d_j,1 lies between x₁, x₂.

Suppose two ‘m’ values exist between x₁, x₂ (denoted by m₁, m₂).

Let:

Again we examine whether other values exist between y₁ and y₂. We search for any ‘p’ such that:

f_N–5(p, N_p – {m} - {k} - {j}) + d_p,m + d_m,k + d_k,j + d_j,1

lies between y₁, y₂. Suppose two ‘p’ values exist between y₁, y₂ (denoted by p₁, p₂) and let:

z1 = f_N–5(p₁, N_p – {m} – {k} – {j}) + d_p1,m1 + d_m1,k1 + d_k1,j + d_j,1

z2 = f_N–5(p₂, N_p – {m} – {k} - {j}) + d_p2,m1 + d_m1,k1 + d_k1,j + d_j,1

We then explore values that might exist between z₁ and z₂ using the same logic as outlined previously.

The case of having three or more values, say x₁, x₂, x₃, … lying between w₁, w₂ are dealt with in a sequential manner. First, we consider x₁, x₂ and determine whether values exist between x₁, x₂. Repeat the process for x₂, x₃; then for x₃, x₄; etc. Cases for three or more z values lying between y₁, y₂ or y₂, y₃ are evaluated in a like manner. After the ‘check and confirm’ heuristic application to w₁, w₂; we proceed to apply the same heuristic to interval w₂, w₃ ….. and so forth.

We summarize the K best solutions found using the simple ‘check and confirm’ heuristic. We define vector (w₁, w₂, X_x, Y_y, Z_z) where w₁, w₂ denotes the smallest and 2^nd smallest min_j=2,…,N {f_N-2(j, N_j) + d_j,1} value respectively; X_x denotes the number of values (given by equation (2)) that exist between w₁, w₂, for example X_x = 1 indicates there exists one value greater than w₁ but less than w₂. Similarly Y_y, Z_z denotes the number of values existing between x₁, x₂ and y₁, y₂ respectively. The definitions of x₁, x₂, y₁, y₂ are defined in equations (3) and equation (4). We list the K best solutions found by the heuristic:

(w₁, w₂, X_x, Y_y, Z_z) k number of best solutions found, solutions presented in ascending order

(w₁, w₂, 0, 0, 0) k = 2, w₁ < w₂

(w₁, w₂, 1, 0, 0) k = 3, w₁ < f_N-3(k, N_k - {j}) + d_k,j + d_j,1 < w₂

(w₁, w₂, 2, 0, 0) k = 4, w₁ < x₁ < x₂ < w₂

(w₁, w₂, 2, 1, 0) k = 5,

w₁ < x₁ < f_N-4(m, N_m - {k} - {j}) + d_m,k + d_k,j + d_j,1 < x₂ < w₂

(w₁, w₂, 2, 2, 0) k = 6, w₁ < x₁ < y₁ < y₂ < x₂ < w₂

(w₁, w₂, 2, 2, 1) k = 7,

w₁ < x₁ < y₁ < f_N-5(p, N_p – {m} - {k} – {j}) + d_p,m + d_m,k + d_k,j + d_j,1 < y₂ < x₂ < w₂

(w₁, w₂, 2, 2, 2) k = 8, w₁ < x₁ < y₁ < z₁ < z₂ < y₂ < x₂ < w₂

The five-component vector (w₁, w₂, X_x, Y_y, Z_z) can be extended to include six or seven components and so on if the above branching and tracking procedure warrants. Once the dynamic programming functional values min _j=2,…,N {f_N-2(j, N_j) + d_j,1} have been evaluated, the heuristic only involves simple comparison of values to determine the K best solutions. It is intuitively easy to understand and can be readily implemented in an interactive mode.

On the other hand, unless the number of regions to be searched is relatively small, we concede that the ‘dynamic programming/check and confirm’ heuristic approach for maritime surveillance can be quite tedious and cumbersome. In surveillance applications, the time-on-station constraint (less than 12 flying hours because of crew safety concern) severely restricts the number of regions that can be searched. In view of this physical limitation, the size of the surveillance problem is normally restricted to less than ten regions [3]. Albeit the hybrid ‘dynamic programming/check and confirm’ heuristic involves mundane calculations, it provides a viable solution approach for finding the K best solutions to the TSP with precedence constraint. Next, the k^th best solution which satisfies the latest time window restrictions solves the surveillance problem.

Example

It is required to start in node 1 visit all the nodes and return back to node 1. Also node 2 must be visited before nodes 3 and 5, node 3 must be visited before node 7, node 5 must be visited before node 6, and node 4 must be visited before node 9. Table 1 summarizes the asymmetric distance matrix d_ij between nodes i and j. (The aircraft velocity decreases with head wind and increases with tail wind. To highlight this fact, an alternative is to keep the aircraft velocity constant and increase the distance d_ij for flights subject to head wind and decrease d_ij for flights with tail wind.)

In addition, node 2 is to be visited in the time window [4, 10] and node 5 in the time window [15, 20]. For illustrative purposes, we have assumed that one unit of time is equivalent to one unit of distance. Following our approach in the previous section, we put aside the time windows constraint (since they are subject to changes). Next, we compute successively more desirable solutions for the PTSP until the best solution which does satisfy the updated time windows restriction is found, namely the k^th best solution.

The following values are found using the dynamic programming formulation for the PTSP (equation 1):

f₀(2,–)=d_1,2=4; f₀(3,–)=∞; f₀(4,–)=d_1,4=3; f₀(5,–)=∞; f₀(6,–)=∞; f₀(7,–)=∞; f₀(8,–)=5; f₀(9,–)=∞. The value ∞ means that the precedence constraint has been violated.

Also:

f₁(3,{2})=4+d_2,3=9; f₁(4,{2})=4+d_2,4=10; f₁(5,{2})=4+d_2,5=11; f₁(6,{2})=∞; f₁(7,{2})=∞; f₁(8,{2})=4+d_2,8=8; f₁(9,{2})=∞.

Continuing on we find using equation (1), the solution to the PTSP is:

f₇(9,{2,3,4,5,6,7,8})+d₉₁=30=w₁ with f₇(9,{2,3,4,5,6,7,8})=26, d₉₁=4 and the path is d₁₂+d₂₃+d₃₇+d₇₅+d₅₆+d₆₄+d₄₈+d₈₉+d₉₁.

We also find that the second smallest value in equation (1) is:

f₇(8,{2,3,4,5,6,7,9})+d₈₁=35=w₁

With f₇(8,{2,3,4,5,6,7,9})=30, d₈₁=5 and the path is d₁₂+d₂₃+d₃₇+d₇₅+d₅₆+d₆₄+d₄₉+d₉₈+d₈₁.

Next we use equation (2) to find any value of the PTSP that lies between w₁ and w₂. We obtain the value:

f₆(4,{2,3,4,5,6,7,8})+d₄₉+d₉₁=33=x₁

With f₆(4,{2,3,4,5,6,7,8})=24, d₄₉=5 and d₉₁=4 the path is d₁₂+d₂₃+d₃₇+d₇₅+d₅₆+d₆₈+d₈₄+d₄₉+d₉₁.

There is no other value found using equation (3). However, we still have to find other values, if possible, using equation (4) between x₁=33 and w₂=35. Only one value, f₅(6,{2,3,5,7,8})+d₆₄+d₄₉+d₉₁=34=y₁ is found, with f₅(6,{2,3,5,7,8})=24, d₆₄=1, d₄₉=5, and d₉₁=4 and the path is d₁₂+d₂₃+d₃₇+d₇₅+d₅₈+d₈₆+d₆₄+d₄₉+d₉₁. Thus the first-, second-, third-, and fourth- best solutions to the PTSP are given by 30, 33, 34 and 35 respectively with the paths specified in the above. It can be easily verified that all the four solutions satisfies the time window constraints, namely node 2 is to be visited in the time window [4, 10] and node 5 in the time window [15, 20]. The best solution is 30.

However, recent intelligence updates specify that aside from the given time windows constraints for nodes 2 and 5, node 6 can only be visited in the time window [23, 25]. It is found that only the third-best solution (= 34) can satisfy the time windows constraints for nodes 2, 5 and 6. The optimal path is given by d₁₂+d₂₃+d₃₇+d₇₅+d₅₈+d₈₆+d₆₄+d₄₉+d₉₁.

Conclusion

In this paper, we have modelled the maritime surveillance as a TSP with precedence and time windows constraints. However our problem is unique in that the constraints are subject to continuous updates and changes. Previously calculated flight path can become infeasible. In addition, technical difficulties on board the aircraft restrict the implementation of well-established analytical TSP solution algorithms. In view of this, we have adopted the K best solution strategy [2]. All conditions that are the subject of updates or changes are put aside; more desirable solutions for the TSP are then computed successively until the best solution which does satisfy the change restrictions is found, namely the k^th best solution. Based on the Principle of Optimality, we have developed a heuristic approach to compute the K best solutions, thus providing a viable solution alternative to a class of TSP variants.

Our dynamic programming heuristic approach to calculate the flight path of maritime surveillance has recently been introduced to the military operational commander. The intent is to have the said approach implemented as one of the standard operating procedures for surveillance. Final implementation cannot commence until approval is received from upper military echelons.

References

Author

Kevin Y.K. Ng received his PhD from McGill University. He is a Senior Operational Research Scientist with the Defence R&D Canada. Prior to joining DRDC, he was a NSERC Postdoctoral Fellow at the Canada Center for Remote Sensing. His research interest includes C4ISR and networked operations. He was an associate editor with the Canadian Journal of Operational Research and Information Systems and is currently an associate editor with the Military Operations Research Journal. Dr Ng’s publications in military operations research have earned him honorable mentions at the INFORMS Koopman Prize and the Canadian OR Society Practice Prize competitions.

N.G.F. Sancho is a professor in the Department of Mathematics & Statistics, McGill University, Canada. His interests are in dynamic programming, in particular travelling salesman problems and their applications, Markovian and Semi-Markovian decision processes.