A Hybrid Iterated Greedy Algorithm for Hydrographic Survey Routing Problem

Abstract

Hydrographic surveying is a necessary task in the maritime community, which can contribute to maritime security, economic development, scientific research, and environmental protection. Hydrographic surveying is a regular and costly activity; hence, careful hydrographic survey planning is required. Hydrographic survey routing is one of the main tasks in hydrographic survey planning, in which we not only need to find the most interesting maritime area(s) (usually evaluated through a risk measure, aggregating navigation risk, environmental impact, and/or data obsolescence), but also the shortest route to do the hydrographic surveying. In this article, first, we attempt to formulate the hydrographic survey routing problem and then develop an efficient hybrid iterated greedy algorithm to solve the problem. The proposed algorithm consists of three stages, that is, Stage 1 with a memetic algorithm to find a good starting point, Stage 2 with a global greedy algorithm to explore the global search space, and Stage 3 with a local greedy algorithm to exploit the local search space. Five real case studies in France are conducted to validate the performance of the developed algorithm.

Keywords:

• Hydrographic survey routing
• hybrid iterated greedy metaheuristic
• maritime risk map

Acknowledgement

The authors would thank the Brittany Region (France) for their support under the grant number SAD18023.

Data availability statement

Due to the nature of this research, participants of this study did not agree for their data to be shared publicly, so supporting data is not available. Some data and source codes can be shared upon a reasonable request.