Product Code Database
This dissertation, Optimization of Berth Allocations in Container Terminals by Di, Sun, ??, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License
The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author.Abstract:?Efficient and effective berth allocation is essential to guarantee high containerthroughput in a container terminal. Modern mega-terminals are usually comprised ofmultiple disjointed berths. However, this type of Berth Allocation Problem (BAP) hasnot attracted a lot of attention from the academic world due to its great complexity.This research develops new methodologies for solving complex BAPs, in particular,BAPs involving quay crane scheduling in a multiple-berth environment.This research develops a mathematical model and a new Branch and Pricealgorithm (B&P) which hybridizes the column generation approach and the Branchand Bound method (B&B) to generate optimal multiple-berth plans (MBAP) withinacceptable time limits. A new exact algorithm based on the label-correcting concept isdesigned to obtain all potential columns by defining a new label structure anddominance rules. To accelerate the generation of columns, two heuristics are proposedto distribute vessels among berths and to establish the handling sequence of thevessels allocated to each berth. An early termination condition is also developed toavoid the tailing off effect phenomenon during column generation process. Theeffectiveness and robustness of the proposed methodology are demonstrated bysolving a set of randomly generated test problems.Since the Berth Allocation Problem (BAP) and the Quay Crane SchedulingProblem (QCSP) strongly interact, this research also studies the Simultaneous Berth Allocation and Quay Crane Scheduling Problem (BAQCSP). An advancedmathematical model and a new hybrid meta-heuristic GA-TS algorithm which isbased on the concept of Genetic Algorithm (GA) are developed to solve the proposedBAQCSP effectively and efficiently. A new crossover operation inspired by thememory-based strategy of Tabu Search (TS) and the mutation operation areimplemented to avoid premature convergence of the optimization process. The localsearch ability of TS is incorporated into the mutation operation to improve theexploitation of the solution space. Comparative experiments are also conducted toshow the superiority of the performance of the proposed GA-TS Algorithm over theB&B and the canonical GA.Furthermore, this research extends the scope of BAQCSP to consider theSimultaneous Multiple-berth Allocation and Quay Crane Scheduling Problem(MBAQCSP). A MBAQCSP model is developed consisting of various operationalconstraints arising from a wide range of practical applications. Since MBAQCSPcombines the structures of both MBAP and BAQCSP, the exact B&P proposed forsolving MBAP can be modified to optimally solve MBAQCSP. However, thecalculation time of B&P increases significantly as the V/B ratio (i.e., vessel number toberth number) grows. In order to eliminate this shortcoming, this research develops aGA-TS Aided Column Generation Algorithm which hybridizes the GA-TS Algorithmproposed for solving BAQCSP with the Column Generation Algorithm to locate theoptimal or near optimal solutions of MBAQCSP. The computational results show thatthe proposed hybrid algorithm locates excellent near optimal solutions to all testproblems within acceptable time li
|
