The paper addresses the synergies from combining a heuristic method with a predictive technique to solve the Dynamic Traveling Salesman Problem (DTSP). Particularly, we build a genetic algorithm that feeds on Newton׳s motion equation to show how route optimization can be improved when targets are constantly moving. Our empirical evidence stems from the recovery of fish aggregating devices (FADs) by tuna vessels. Based on historical real data provided by GPS buoys attached to the FADs, we first estimate their trajectories to feed a genetic algorithm that searches for the best route considering their future locations. Our solution, which we name Genetic Algorithm based on Trajectory Prediction (GATP), shows that the distance traveled is significantly shorter than implementing other commonly used methods.