A bi-objective tramp ship routing and scheduling problem to accelerate shipping sustainability transition

The transition to sustainable shipping entails a combination of short-term and long-term measures to minimize environmental impact. In this work, we study a bi-objective Tramp Ship Routing and Scheduling Problem (TSRSP) in which we plan routes for a fleet of tramp shipping vessels using a feature-rich model to mitigate emissions in the short term. The two objective functions are the maximization of profit and the minimization of greenhouse gas (GHG) emissions. This feature-rich model can handle speed optimization, chartering costs, and bunker planning. This tactical/operational model has many similar solutions, only differing slightly in operational choices, resulting in marginally different profits and emissions. This way, emissions can be effectively reduced by optimizing operations using an emission-aware model without waiting for technological advancement. Its single-objective counterpart is efficiently solved using column generation, where the columns represent the possible routes of a vessel, while the master problem controls route selection. New columns are generated using dynamic programming on a time-space graph. The bi-objective model is solved iteratively using an enhanced ϵ-constraint method. Lagrangian relaxation is used to improve the solutions bounds by leveraging the constrain matrix integrality properties, and a dicotomic search procedure is used to accelerate the search. The algorithm determines the Pareto front, which describes the optimal compromise between profit and emission. We compute the Pareto front for 10 different historical scenarios between 2021 and 2023, showing that emissions can be reduced on average by more than 10% with less than a 2% profit decrease and by 20% with a 5% profit decrease. Then, we compute the Pareto front with alternative fuels-engine combinations, obtaining average emissions reduction of over 40% with less than a 5% profit decrease. We integrate these results with insights to explain the positive results. Finally, we compare the results with GHG tax levies, showing that these solutions are strongly dominated by the Pareto fronts we compute.