Pilotage planning in seaports

Lingxiao Wu, Shuai Jia, Shuaian Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)90–105
Number of pages16
JournalEuropean Journal of Operational Research
Volume287
Issue number1
DOIs
Publication statusPublished - 16 Nov 2020

Keywords

  • Branch-and-price
  • Column generation
  • Pilotage planning
  • Port operations
  • Scheduling
  • Sea pilot

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this