Research On Blocks Relocation Problem In Container Terminal

The handling technologies and strategies of container has always been a critical factor to measure the efficiency of a container terminal,and the Post-stacking Problem is one of the most important issues.The main content of the Post-stacking Problem research is: given the structure of the bay which is considered,the initial positions of the containers and the retrieval sequence of the containers,the objective is to find the optimal relocation sequence of the containers,so as to minimize the number of relocations.this dissertation deal with a kind of post-stacking problem—Block Relocation Problem(BRP).In the first chapter,this dissertation introduces the basic terminologies of container terminal which is related to the post-stacking problem.Then,according to the basic classification of the post-stacking problem,the classification of main algorithms and the computational complexity,the relative literatures are reviewed.In the second chapter,the mathematical model of the Blocks Relocation Problem is established,and the concept of the Worst Bay State of the containers is proposed.The algorithm of the Blocks Relocation Problem and the Worst Bay State are studied when the width of a bay is 2.Then,the conjecture of the Worst Bay State is given when the height of a bay is unlimited and the width of a bay is 3.We get some interesting properties during the research.Kim et al.proposed a kind of heuristic algorithm based on probability method for BRP in 2006,but the assumption of randomness is impractical.In the third chapter,this dissertation revises the kind of heuristic algorithm proposed by Kim by embedding the theory of discrete time Markov chain into the model,the randomness assumption in the algorithm is improved theoretically,and the improved recursive formula is given.Caserta et al.proposed the integer programming model of BRP in 2012.In the fourth chapter,inspired by the original model of Caserta,this dissertation presents a more detailed 0-1 integer linear programming model for the Blocks Relocation Problem.Then,induced in previous research,a heuristic algorithm based on rules of relocation is proposed and the effectiveness of the algorithm is verified by simulation experiments.