Evolutionary optimisation approach for the single and multiple-port berth allocations and quay crane assignment problem

Student thesis: Doctoral Thesis


Container terminals play an indispensable role in loading/unloading containers from/to container vessels, since more than 80% of international trade volume in goods is transported by sea. This research aims to improve container terminal operational efficiency, particularly in the seaside area. Three major problems occur in this area during the planning and scheduling of incoming vessels. The first problem is the Berth Allocation Problem (BAP), which is associated with allocating berthing space and time to vessels. The second is the Quay Crane Assignment Problem (QCAP), which is on assigning a number of cranes (QCs) to vessels such that all required transhipments of containers can be fulfilled. The third is the Quay Crane Scheduling Problem (QCSP), which is on scheduling the sequence transhipment operations of the assigned QCs to the appropriate vessels. These problems can be solved independently. However, the first two problems are dependent on one another. The number of available QCs depends on when and where the vessel is berthed, and the berthing handling time varies depending on the number of QCs that can be or are assigned.

This research addresses the integrated Berth Allocation and Quay Crane Assignment Problem (BACAP). The research has developed three models. The first model solves the BACAP with a large-scale benchmark. The second model solves the BACAP with the desired berthing position. These models consider the setting to be a single port with a single terminal. The third model solves the BACAP with desired berthing position by considering there to be multiple ports with multiple terminals. The common objectives are to minimise the total service time for the vessels (waiting time plus handling time), to minimise the total terminal costs and to maximise the utilisation of the quay cranes. The BACAP has been proven to be an NP-hard problem. Consequently, the large-scale instances are difficult to solve using exact methods. Therefore, heuristic methods are essential to solve this type of problem in an acceptable computational time.

This research provides a novel self-adaptive constructive meta-heuristic algorithm using genetic programming (GP) and a genetic algorithm (GA) for solving the continuous dynamic BACAP. The vessel priority rule has a crucial impact on the scheduling processes in order to achieve the vessel operators and terminal operators’ goals. As a result, this research uses GP to evolve effective and robust composite dispatching rules to select the priority of the incoming vessels automatically with regard to the problem’s constraints and berth layout. The outcome will be a solver for the BACAP rather than a solution that can find an optimal or near optimal solution.

The research solves the problem with different constraints and well-known benchmarks for large and small-scale instances. Comparative studies based on extensive computational experiments of the model and the literature were performed to verify its performance. Furthermore, the research extends the current state-of-the-art by innovating a new mathematical model to integrate the operational planning levels and solve the BACAP with multiple ports, in which one terminal operator owns multiple ports with multiple terminals and the incoming vessels have no restriction concerning berthing in any of them.

The computational results of all proposed models show high performance when it comes to solving the BACAP in both single and multiple ports. The results indicate that the frameworks are quite competitive with other techniques and outperform other heuristic-based frameworks on many occasions. Finally, the research presents future work areas and proposes an approach to unify the literature benchmarks and to develop a dataset generator.
Date of AwardApr 2018
Original languageEnglish
SupervisorMohamed Bader-El-Den (Supervisor), Dylan Jones (Supervisor) & Alexander Gegov (Supervisor)

Cite this