Optimizing the routes of a research vessel with an hybrid metaheuristic

ABSTRACT

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.

KEYWORDS:

• Hybrid metaheuristic
• genetic algorithm
• mixed Integer Linear Programming
• routing
• time windows

Acknowledgments

This research was partially supported by the Portuguese national funding agency for science, FCT Fundação para a Ciência e Tecnologia, within projects UID/MAT/04561/2019 and PTDC/MATNAN/2196/2014.

Disclosure statement

No potential conflict of interest was reported by the authors.