Pilotage planning in seaports

Vessel pilotage is compulsory in most seaports around the world. When traveling into or out of the terminal of a seaport, vessels should be navigated by sea pilots in order to follow correct and safe waterways. This paper studies a pilotage planning problem that involves decisions of scheduling the vessel traffic in a seaport, assigning work shifts to pilots, and scheduling the pilots in each work shift for vessel navigation. We formulate the problem as a linear mixed-integer programming (MIP) model that aims at minimizing the cost incurred by the pilotage operations, and show that the problem is strongly NP-hard. For solving the problem, we develop a branch-and-price (B&P) algorithm in which the pricing problem is solved by a novel dynamic programming algorithm. We further propose several acceleration techniques to improve the efficiency of the B&P algorithm. The computational performance of the B&P algorithm is evaluated in extensive numerical experiments. Computational results demonstrate that the B&P algorithm is able to solve problem instances of practical sizes, and that the algorithm outperforms a standard MIP solver and a solution method commonly used in practice.