Every autumn, a research vessel carries out a sampling survey tour to estimate the abundance of groundfish species of the Portuguese continental waters. The sampling operations are carried out 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 current weather conditions, the objective is to minimize the total traveled distance and completion time. We present a mixed integer linear program to describe the problem and propose two sequential heuristic approaches that combine genetic algorithms and adaptive large neighborhood search to solve it. Computational experience with real data shows that the proposed heuristics are suitable tools to solve the problem.