Author:

Abstract:

Ships have increasingly become an essential component within international trade. When arriving at terminals, goods (such as containers) are processed for further transportation to inland locations. Port terminals compete to offer the best service to customers while guaranteeing the least ship waiting time possible. One of the most prevalent problems terminals face when managing their daily operations is the Berth Allocation Problem (BAP). This problem concerns the assignment of vessels to a specific berth and timeslot, while minimizing objectives such as total stay time or assignment cost. The berth characteristics, vessel dimensions and estimated arrival times restrict the number of eligible berths for each vessel. The BAP has been proven NP-hard [1], posing challenges when handling large instances. Academic work has focused primarily on the BAP in container terminals, with the ship handling times being fixed or dependent on the quay cranes assigned to process the cargo. Furthermore, the BAP may be classified as discrete, continuous or hybrid depending on the particular berthing layout. The discrete variant considers the quay as consisting of a finite set of berths or sections such that only a single ship may moor at each berth for any period of time. No quay partitioning exists within the continuous version and therefore vessels may berth anywhere along the quay. Finally, the hybrid variant considers the quay to be partitioned into a number of berths, with vessels capable of occupying more than one of these sections under certain conditions. Generally, terminal layouts considered in the literature consist of linear quays, implying the capability of this problem being modelled as a 2D bin-packing problem and presented in two-dimensional space. One dimension is spatial, i.e. the quay length, while the other is a temporal decision horizon. While significant research has been conducted regarding the BAP in container terminals, little attention has been afforded to the BAP when concerning complex terminal layouts. The present work considers the discrete BAP in a tank terminal which consists of irregular quays. Adjacent, opposite and indented berths impose mooring and sailing restrictions to vessels in the terminal as a safety measure. Furthermore, the ship handling times depend on the levels of the tanks in the terminal and the setup time to start loading and unloading. The aim of this work is to successfully address the BAP in terminals with irregular quays. An exact approach based on a Mixed Integer Linear Program- ming (MILP) model is introduced to tackle small instances and a heuristic ap- proach based on the Multi-Depot Vehicle Routing Problem with Time Windows (MD-VRPTW) is employed when facing larger ones. Ships are represented as customers, while berths are considered depots. Experiments are conducted on benchmark instances derived from a real-world case. The exact method proves capable of providing optimal solutions for small to medium-sized instances, whereas the heuristic delivers high-quality results in reasonable computational time. Future work includes extending the exact model to cope with additional real-world problem characteristics, such as the selection of the most beneficial tank regarding throughput to minimize total service time.