Routing problem in surveillance operation at sea

We consider an airplane routing problem when it flies for surveillance operation at sea. The surveillance operation is done by the following procedure. First, an airplane surveys the given area along a given standard route (piecewise linear) by its own sensor (radar, visual apparatus etc.) and detects a ship. The range of the sensor is limited, so the plane cannot grasp the information of all ships within the mission area at once. Then the plane approaches the objective and discriminates what it is. The plane must go back to the base before its fuel is used up. We intend to give a standard route to accomplish the mission more efficiently. The precise information on the ships (position and speed) cannot be grasped before takeoff, so we cannot utilize the combinational techniques, which are often used in vehicle routing problems. We formulate the problem as a non-linear optimization problem with a constraint for flight distance. The objective is to maximize the expected value of the detected ships within an operation, that is calculated as integration, along a given route, of product value of the detecting probability from the plane and the density of the ships in the area. As the surveillance operation is carried out periodically, and the positions of the ships (such as fishing boats, ocean ships) is expectable to some degree, we assume that we can draw the density map of ships of the area. We also suppose that the detecting probability obeys the inverse cube law of the distance. The density of the ships is given as a sum of 2-dimensional normal density functions, centered at expected positions of individual ships. We use Augmented Lagrangean Function Method to construct the algorithm of the problem. Numerical experiments show that the method proposed in the paper gives a good standard route in reasonable computation time.