A Joint Berth Allocation and Quay Crane Assignment Problem: Lagrangian Relaxation Approach

Abstract

Continuous growth in containers transportation worldwide stresses the importance of optimizing seaside operations, which are considered to be a bottleneck in most container terminals. In this thesis, we formulate a mixed integer program for the joint berth allocation and quay crane assignment problem. In the literature, most papers have dealt with these problems separately. The berth allocation problem (BAP) is concerned with assigning ships to berths/quay positions, while the quay crane assignment problem (QCAP) decides on the assignment of cranes to ships. However, the handling time of ships heavily depends on the number of containers to be handled and the assignment of quay cranes, thus presenting a real-life application of the problem. Moreover, our new formulation takes into account different types of cranes that differ in productivity due to variation in age profile and technology. In addition, the formulation takes into consideration priorities in serving the ships, their preferred berthing position, due time and the operational cost of using different types of cranes. Due to the complexity of the problem, it cannot be solved within a polynomial time. Thus, an efficient Lagrangian Relaxation based-heuristic is required to solve the problem within an acceptable computational time. Testing and sensitivity analysis are conducted to assess the effectiveness of the algorithm. The algorithm achieves near-to-optimal solution within a reasonable computational time, and the sensitivity analysis explains the effect of the total number of quay cranes on the cost of the schedule and the handling time of ships.

Date of Award	2014
Original language	American English
Supervisor	Ali Diabat (Supervisor)