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

Weconsider a bi-objective Tramp Ship Routing and Scheduling Problem in which we plan routes for a fleet of tramp shipping vessels using a rich model. The two objective functions are maximizing profit and minimizing greenhouse gas (GHG) emissions. The rich model can handle speed optimization, chartering costs, and bunker planning. The single-objective model is e ciently solved using column generation, where the columns represent the possible routes of a vessel, while the master problem keeps track of the binding constraints. The pricing problems are solved using time-space graphs. The bi-objective model is solved iteratively using the [U+03F5]-constraint method. The mathematical model is mainly composed of perfect matrices. We use this property to design an e cient solution method. We compute the Pareto front for 10 di erent 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 fuelsengine combinations, obtaining emissions reduction of over 40% with less than a 5% profit decrease. For smaller vessels, we tested windassisted and wind-propelled alternatives. Finally, we compare the results with GHG tax levies, showing that these solutions are strongly dominated by the Pareto fronts we compute.