Branch-and-Cut-and-Price Strategy for the Port-Scheduling Problem

Port operations are essential logistics problems within Liner Shipping. Among them, we can find problems such as Stowage Planning, Quay Crane Scheduling or Berth Allocation. Normally, these problems are solved independently after the services in Liner Shipping have been determined. In this talk we present a less studied problem that we will denote the Port-Scheduling Problem.

The motivation of this problem arises from large ports, such as the Port of Rotterdam, which are divided into several terminals. Vessels and in particular feeder vessels need to move between the terminals to pick-up and deliver containers while respecting capacity constraints in each terminal. In this paper, we propose a mathematical model, inspired by the Job-Shop Scheduling Problems, to design the routing and scheduling of vessels in the port during a given time horizon.

The solution method is based on column-generation, where the vessel routes are handled in the Sub-Problem, and the master problem selects the routes respecting the precedence constraints in terminals. Overlap of vessels in terminals is controlled afterwards, by adding valid cuts (as new precedence parameters) imposing an ordering in which the vessels should visit the (previously overlapped) terminals.