An adaptive large neighborhood search algorithm for the tugboat scheduling problem. (March 2023) - Wang, Xin; Liang, Yijing; Wei, Xiaoyang; Chew, Ek Peng
Abstract: 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. Highlights: Schedule tugboats under the service pattern of multiple service at multiple points. An efficient adaptive large neighborhood search algorithm is presented. A tailored feasibility check method embedded in the presented algorithm is devised. Computational experiments are conducted to obtain some managerial insights.