Stochastic quay partitioning problem

In this paper we consider the problem of dividing a quay of a container terminal into berth segments so that the quality of service for future ship arrivals is as good as possible. Since future arrivals are unknown, the alternative solutions are evaluated on various arrival scenarios generated for certain arrival intensity from a stochastic model referred to as a ship traffic model (STM). This problem will be referred to as a stochastic quay partitioning problem (SQPP). SQPP is defined by an STM, arrival intensity, quay length and a set of admissible berth lengths. Evaluation of an SQPP solution on one scenario is a problem of scheduling the arriving vessels on the berths, which is a classic berth allocation problem (BAP). In SQPP the sizes of BAP instances that must be solved by far exceed capabilities of the methods presented in the existing literature. Therefore, a novel approach to solving BAP is applied. Tailored portfolios of algorithms capable of solving very large BAP instances under limited runtime are used. Features of SQPP solutions are studied experimentally: patterns in selected berth lengths, dispersion of solutions quality and solutions similarity. We demonstrate, that partitioning a quay into equal-length berths is not the best approach. The largest vessel traffic is dominating in defining best quay partitions, but dedicating quays for shorter vessels give lower dispersion of solution quality. A set of algorithms to partition a quay is proposed and evaluated: methods based on integer linear programming (ILP) to match vessel classes arrival intensities with berth availability, hill climber, tabu search and a greedy approach. Only under high arrival intensity can these methods show their prowess. ILP methods have an advantage of low solution evaluation cost. Tabu is most flexible, but at high evaluation costs. To the best of our knowledge, SQPP is posed and solved for the first time in the operations research.