An adaptive large neighborhood search algorithm for the tugboat scheduling problem

Seaports are important connections between inland and maritime transportation. Tugboats, which can provide enough horsepower and mitigate safety risks when leaving and entering seaports for container ships, are important and limited resources. Therefore, it is essential to schedule tugboats in the management of seaports since most container ships can only enter and leave ports under the assistance of tugboats with reasonable costs. The tugboat scheduling problem considering the multiple service at multiple waypoints pattern which can better utilize the limited tugboats, is studied. In this paper, we develop an efficient adaptive large neighborhood search algorithm with an efficient feasibility check procedure to solve large-scale instances. The computational experiments verify the effectiveness of the proposed algorithm, and some managerial insights are obtained based on the sensitivity analysis.