In-port multi-ship routing and scheduling problem with draft limits

This paper addresses an in-port multi-ship routing and scheduling problem in maritime transportation. The key objective is to find an optimal routing and schedule for multiple ships that are planned to pick up or deliver cargos located in the various terminals of a port with different draft limits. Using the multiple traveling salesman problem (mTSP) as a base, we formulate a multi-ship routing and scheduling model with draft limits and time windows constraints. To solve the developed model, a two-stage solution method based on dynamic programming and branch-and-bound algorithms is developed. The solution approach is applied to 41 real-sized problem instances. Our experiments revealed that the proposed method outperforms CPLEX by accurately solving the problem instances in a reasonable time. The formulated problem and presented solution can be implemented in fleet operations of autonomous ships in smart maritime transportation systems of the future.

Automated summary

This paper addresses an in-port multi-ship routing and scheduling problem in maritime transportation, proposing a solution method based on dynamic programming and branch-and-bound algorithms. The experiments showed that the proposed method outperforms CPLEX algorithm in solving the problem instances accurately within a reasonable time.