Precedence and time windows constrained Travelling Salesman Problem (TSP) in maritime surveillance
Kevin Y. K. Ng, N. G. F. Sancho · Journal of battlefield technology · 2014
Maritime surveillance initially involves the military operational commander deciding on the areas to be searched. The aim is to detect and classify targets/ships subject to the aircraft's time-on-station constraint, namely the aircraft is restricted to no more than 12 flying hours/day. Very often, a precedence relationship exists between regions to be searched. In addition, time windows or rigid lower and upper bounds on the time the regions have to be searched are also specified. It has recently been shown by Marlow et al and the authors that the surveillance problem can be modelled as a travelling salesman problem (TSP). However, our problem is unique and distinct from the classical TSP. The time windows and precedence constraints are frequently subject to changes or revisions because of continuous intelligence updates. Previously calculated flight path can become infeasible. The solution procedure should only involve easy implementable algorithms so as to allow flight crew to readily recalculate the revised flight path, preferably in an interactive mode. This paper develops an implementable hybrid dynamic programming/heuristic algorithm for surveillance mission planning. To avoid incorporating the difficulty of time windows or precedence constraint changes in the formulation, we adopt the K best solution strategy approach. The essence is to put aside the time windows and/or the precedence constraint and compute successively more desirable solutions for the TSP until the best solution which does satisfy the change restrictions is found, namely the kth best solution.