Optimizing the routes of a research vessel with an hybrid metaheuristic. Issue 1 (2nd January 2021)

• Record Type: Journal Article
• Authors: Mesquita, Marta; Paias, Ana; Wise, Laura
• Is Part Of: International journal of management science and engineering management. Volume 16:Issue 1(2021)
• Page Start: 58
• Page End: 71
• Publication Date: 2021-01-02
• Subjects: Hybrid metaheuristic -- genetic algorithm -- mixed Integer Linear Programming -- routing -- time windows; Management science -- Periodicals; Engineering -- Management -- Periodicals; Engineering -- Management; Management science; Periodicals; 658.005
• DOI: 10.1080/17509653.2020.1864673
• Languages: English
• ISSNs: 1750-9661

Abstract

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.