Tugboat scheduling for container ports

Container ports play an important role in global logistics and supply chains by providing container handling services for container ships. In a port, container ships usually need the assistance of tugboats in order to undergo berthing, shifting, and unberthing movements. Effective scheduling of the tugboats for serving the ships is thus of great importance for ensuring safe and efficient container ship movements in a port. However, research on tugboat scheduling is scarce in the literature. We contribute to the literature by studying a real-life tugboat scheduling problem (Tug-SP). We formulate the Tug-SP using a mixed-integer linear programming (MILP) model taking into consideration various practical constraints. In view of the specific problem structure, we further develop six families of valid inequalities to strengthen the MILP model. To efficiently solve the Tug-SP, we develop a tailored branch-and-cut algorithm by incorporating these valid inequalities into a standard branch-and-bound solution framework. We evaluate the computational performance of the proposed branch-and-cut algorithm using a set of test instances generated from real-life ship traffic data collected from the Port of Singapore. The computational results validate the effectiveness of the proposed valid inequalities, and show that the branch-and-cut algorithm can optimally solve instances of realistic sizes with a reasonable amount of computation time.