Optimizing the routes of a research vessel with an hybrid metaheuristic

In many fisheries surveys sampling operations are carried out at predefined locations called fishing stations. According to predefined time windows, a research vessel performs at most m circuits to visit each fishing station once. Each circuit starts and ends at the home port and should not exceed a maximum duration. Depending on its completion time, a visit to an intermediate port may occur. This article presents a Mixed Integer Linear Programming model with the objective of minimising the sum of the total travelled distance and the total completion time. To solve the problem a hybrid metaheuristic that exploits the structure of the MILP model is developed. The hybrid approach alternates between a genetic algorithm and a perturbation procedure. In each iteration, a genetic algorithm exploits the routing structure of the model to provide feasible solutions for the problem. Then a perturbation algorithm, based on a dual procedure and Benders decomposition, guides the search of the genetic algorithm towards new and diverse solutions. Computational experience with real and benchmark instances show the effectiveness of the hybrid metaheuristic.

Automated summary

This article introduces a Mixed Integer Linear Programming model aiming to minimize the total traveled distance and total completion time. A hybrid metaheuristic approach, combining genetic algorithm and perturbation algorithm, is developed to effectively solve the problem. Computational experiments demonstrate the effectiveness of the hybrid metaheuristic in real and benchmark instances.