File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Optimization of Berth allocations in container terminals

TitleOptimization of Berth allocations in container terminals
Authors
Issue Date2012
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Sun, D. [孙镝]. (2012). Optimization of Berth allocations in container terminals. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4819956
AbstractEfficient and effective berth allocation is essential to guarantee high container throughput in a container terminal. Modern mega-terminals are usually comprised of multiple disjointed berths. However, this type of Berth Allocation Problem (BAP) has not 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 Price algorithm (B&P) which hybridizes the column generation approach and the Branch and Bound method (B&B) to generate optimal multiple-berth plans (MBAP) within acceptable time limits. A new exact algorithm based on the label-correcting concept is designed to obtain all potential columns by defining a new label structure and dominance rules. To accelerate the generation of columns, two heuristics are proposed to distribute vessels among berths and to establish the handling sequence of the vessels allocated to each berth. An early termination condition is also developed to avoid the “tailing off effect” phenomenon during column generation process. The effectiveness and robustness of the proposed methodology are demonstrated by solving a set of randomly generated test problems. Since the Berth Allocation Problem (BAP) and the Quay Crane Scheduling Problem (QCSP) strongly interact, this research also studies the Simultaneous Berth Allocation and Quay Crane Scheduling Problem (BAQCSP). An advanced mathematical model and a new hybrid meta-heuristic GA-TS algorithm which is based on the concept of Genetic Algorithm (GA) are developed to solve the proposed BAQCSP effectively and efficiently. A new crossover operation inspired by the memory-based strategy of Tabu Search (TS) and the mutation operation are implemented to avoid premature convergence of the optimization process. The local search ability of TS is incorporated into the mutation operation to improve the exploitation of the solution space. Comparative experiments are also conducted to show the superiority of the performance of the proposed GA-TS Algorithm over the B&B and the canonical GA. Furthermore, this research extends the scope of BAQCSP to consider the Simultaneous Multiple-berth Allocation and Quay Crane Scheduling Problem (MBAQCSP). A MBAQCSP model is developed consisting of various operational constraints arising from a wide range of practical applications. Since MBAQCSP combines the structures of both MBAP and BAQCSP, the exact B&P proposed for solving MBAP can be modified to optimally solve MBAQCSP. However, the calculation time of B&P increases significantly as the V/B ratio (i.e., vessel number to berth number) grows. In order to eliminate this shortcoming, this research develops a GA-TS Aided Column Generation Algorithm which hybridizes the GA-TS Algorithm proposed for solving BAQCSP with the Column Generation Algorithm to locate the optimal or near optimal solutions of MBAQCSP. The computational results show that the proposed hybrid algorithm locates excellent near optimal solutions to all test problems within acceptable time limits, even problems with high V/B ratios. Finally, this research also shows that the proposed GA-TS Aided Column Generation Algorithm can be easily modified to solve MBAP efficiently.
DegreeDoctor of Philosophy
SubjectContainer terminals - Management - Mathematical models.
Dept/ProgramIndustrial and Manufacturing Systems Engineering

 

DC FieldValueLanguage
dc.contributor.authorSun, Di-
dc.contributor.author孙镝-
dc.date.issued2012-
dc.identifier.citationSun, D. [孙镝]. (2012). Optimization of Berth allocations in container terminals. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4819956-
dc.description.abstractEfficient and effective berth allocation is essential to guarantee high container throughput in a container terminal. Modern mega-terminals are usually comprised of multiple disjointed berths. However, this type of Berth Allocation Problem (BAP) has not 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 Price algorithm (B&P) which hybridizes the column generation approach and the Branch and Bound method (B&B) to generate optimal multiple-berth plans (MBAP) within acceptable time limits. A new exact algorithm based on the label-correcting concept is designed to obtain all potential columns by defining a new label structure and dominance rules. To accelerate the generation of columns, two heuristics are proposed to distribute vessels among berths and to establish the handling sequence of the vessels allocated to each berth. An early termination condition is also developed to avoid the “tailing off effect” phenomenon during column generation process. The effectiveness and robustness of the proposed methodology are demonstrated by solving a set of randomly generated test problems. Since the Berth Allocation Problem (BAP) and the Quay Crane Scheduling Problem (QCSP) strongly interact, this research also studies the Simultaneous Berth Allocation and Quay Crane Scheduling Problem (BAQCSP). An advanced mathematical model and a new hybrid meta-heuristic GA-TS algorithm which is based on the concept of Genetic Algorithm (GA) are developed to solve the proposed BAQCSP effectively and efficiently. A new crossover operation inspired by the memory-based strategy of Tabu Search (TS) and the mutation operation are implemented to avoid premature convergence of the optimization process. The local search ability of TS is incorporated into the mutation operation to improve the exploitation of the solution space. Comparative experiments are also conducted to show the superiority of the performance of the proposed GA-TS Algorithm over the B&B and the canonical GA. Furthermore, this research extends the scope of BAQCSP to consider the Simultaneous Multiple-berth Allocation and Quay Crane Scheduling Problem (MBAQCSP). A MBAQCSP model is developed consisting of various operational constraints arising from a wide range of practical applications. Since MBAQCSP combines the structures of both MBAP and BAQCSP, the exact B&P proposed for solving MBAP can be modified to optimally solve MBAQCSP. However, the calculation time of B&P increases significantly as the V/B ratio (i.e., vessel number to berth number) grows. In order to eliminate this shortcoming, this research develops a GA-TS Aided Column Generation Algorithm which hybridizes the GA-TS Algorithm proposed for solving BAQCSP with the Column Generation Algorithm to locate the optimal or near optimal solutions of MBAQCSP. The computational results show that the proposed hybrid algorithm locates excellent near optimal solutions to all test problems within acceptable time limits, even problems with high V/B ratios. Finally, this research also shows that the proposed GA-TS Aided Column Generation Algorithm can be easily modified to solve MBAP efficiently.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.source.urihttp://hub.hku.hk/bib/B48199564-
dc.subject.lcshContainer terminals - Management - Mathematical models.-
dc.titleOptimization of Berth allocations in container terminals-
dc.typePG_Thesis-
dc.identifier.hkulb4819956-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineIndustrial and Manufacturing Systems Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b4819956-
dc.date.hkucongregation2012-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats