Local solutions of surveillance routing problem by partitioning the objective ships

Surveillance operation is performed, along a given standard route, in order to confirm sea lane security and to detect/counter the suspicious ships. The route is composed of connecting 2-dimensional points on the surface by straight lines sequentially. In our previous paper a model for surveillance routing problem and an efficient algorithm constructing a suboptimal standard route are proposed. Starting from a given initial route, each 2-dimensional point is moved iteratively to maximize locally the expected value of detected ships estimated from total sum of densities of all ships in the whole area. There, some difficulties remained such as overestimation of the objective value by repeating visits in an area where many ships are concentrated locally. In this paper, in order to avoid such conflicts, we first partition the region systematically into line Voronoi regions along the route obtained in each iteration and only use densities derived from each Voronoi region to calculate the local objective values. The improvement brings about the algorithm speeding-up and avoid overestimation caused by repeated visits. Further, taking notice of the symmetric shape of the detective probability function from a standard route, we also propose efficient heuristic methods to obtain a suboptimal route. Finally, numerical examples are given.