A bi-objective MILP model for optimal routing in a dynamic network with moving targets (nodes) is developed, where all targets are not necessarily visited. Hence, our problem extends the moving target traveling salesman problem. The two objectives aim to find the sequence of targets visited in a given time horizon by minimizing the total travel distance and maximizing the number of targets visited. Due to a huge number of binary variables, such a problem often becomes intractable in real life. To reduce the computational burden, we introduce a measure of traffic density based on which we propose time horizon splitting heuristics. In a real-world case study of greenhouse gas emissions control, using AIS data related to the locations of ships navigating in the Gulf of Finland, we evaluate the performance of the proposed method. Different splitting scenarios are analyzed numerically. Even in moderate scale cases, the results show that near-efficient values for the two objectives can be obtained by our splitting approach with a drastic decrease in computational time compared to the exact MILP method. A linear value function is introduced to compare the Pareto solutions obtained by different splitting scenarios. Given our results, we expect that the present study is valuable in logistic applications, specifically maritime management services and autonomous navigation.