International Council for the Exploration of the Sea CM 1996/D:17 Optimizing the Sailing Route for Fixed Groundfish Survey Stations

Groundfish surveys usually cover relatively large areas. The stations are numerous and often widespread. Determining the best sailing route between stations is not always obvious. An optimization of the sailing routes could reduce cost and research time. The exact sailing path is usually decided during the tour, since it may depend on factors such as weather and other vessels working the stations. Any means of assisting the captain in deciding which route to take should be valuable. The Groundfish Survey Problem (GSP) can be regarded as a variant of the Travel-ling Salesman Problem (TSP). The TSP is a combinatorial optimization which attempts to minimize the total distance travelled between cities. Unlike the TSP where the cities are entered and exited at the same location, the vessels may enter a station from either end of the towing path and so the number of possible solutions is significantly greater for the GSP. Over the last years Genetic Algorithms (GAs) have been used with some success to solve large TSPs where traditional methods fail or are too slow. Genetic Algorithms work with the coding of the problem rather than the problem itself. Here the GA approach is extended to include a new type of coding. The coding used borrows an idea from nature known as diploidy. Furthermore, the GA performance is enhanced using local search heuristics. A software solution utilizing the global optimization power of GAs, combined with local search has been implemented and tested