Program > By author > Wise Laura

Every autumn, a research vessel carries out a sampling survey tour to estimate the abundance of several demersal species of the Portuguese continental waters. The sampling operations are made at predefined geographical locations, the fishing stations, within predefined multiple time windows.The vessel route starts and ends at the port of Lisbon and must visit all fishing stations. According to a predefined periodicity, the vessel must enter a port to supply food, refuel and/or change crew. Given the geographical locations of the fishing stations/ports and the current weather conditions, the objective is to minimize the total traveled distance and the completion time.

We present a MILP model that highlights three combinatorial subproblems, namely a clustering subproblem dividing the set of fishing stations into two subsets, a routing subproblem defining the spatial movement of the vessel, and a scheduling subproblem establishing the times at which each location is visited. The size of the real instances addressed in this paper make the exact resolution of the model impractical. Despite the existence of a high dependency among the referred three subproblems, one may devise a hierarchic ordering of the decisions that are involved in the resolution of the model, which suggests the use of sequential approaches. Therefore, we propose two sequential heuristic approaches that combine genetic algorithms and ALNS to obtain feasible solutions. Computational experience with real data shows that the heuristics are suitable tools to solve the problem, obtaining good feasible solutions in short CPU time.