Column generation for the multi-port berth allocation problem with port cooperation stability

Abstract

This paper proposes a multi-port berth allocation problem (MPBAP) under a cooperative environment, which aims to determine berthing times and berthing positions for all considered vessels arriving at multiple neighboring ports. The previous studies on the MPBAP (or the BAP with multiple ports) consider that multiple ports have established stable cooperation, while the port cooperation stability problem (PCSP) has not been addressed. This paper investigates the PCSP with the MPBAP, where our MPBAP further integrates the vessel diverting issue that vessels with excessive waiting times can be diverted to neighboring ports. For the PCSP, we investigate how to group multiple neighboring ports into different stable port groups, and then determine optimal port groups. For all possible port groups, we propose a mixed integer programming model for the MPBAP, and a column generation approach is devised to solve it. Based on optimal solutions of the MPBAP for various port groups, cooperative game theory is utilized to obtain stable port groups, and then the PCSP can be formulated as a binary programming model for determining optimal port groups. Numerical experiments are carried out to account for the efficiency and effectiveness of the proposed models and solution method.