Bi-objective routing in a dynamic network: An application to maritime logistics

A bi-objectiveMILP 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 travelling salesman problem. The two objectives aim at finding 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 the real life cases. To reduce the computational burden, we introduce a measure of traffic density, based on which we propose a time horizon splitting heuristics. In a real-world case study of greenhouse gas emissions control, using Automatic Identification System 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 analysed numerically. Even in the cases of a moderate scale, 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.