Research On Quay Crane Scheduling Problem In Container Terminal

With the rapid growth of the maritime container transportation,container terminals need more scientificxue we and economical management and operation methods.The goal of the Quay Crane Scheduling Problem（QCSP）is to assign the tasks to each quay crane under the safety clearance and non-crossing constraints,such that the completion time is minimized.The QCSP is one of the key factors impacting the efficiency of quay cranes and the time container vessels spend in port,which are key indicators of the overall service quality and competitiveness of a container terminal.In addition,some vessels have mixed-stacking of 40-foot containers and 20-foot containers.Moreover,due to equipment maintenance,shift change,the priority between vessels and other reasons,the quay cranes may not always be available.In this paper,we study the QCSP in the general case which considers the safety clearance and non-crossing constraints.Based on this,we study the case of the QCSP with mixed-stacking and the case of the QCSP under time window constraints,which are more realistic.In Chapter 1,we give basic concepts and literature review of the QCSP.In Chapter 2,we study the QCSP in general cases.A heuristic algorithm based on the key-bay and the lower bound of the completion time is designed.In Chapter 3,we study the case of the QCSP with mix-stacking and the case of the QCSP under time window constraints.We give the integer programming model and heuristic algorithm for these two cases,respectively.For the case of the QCSP with mix-stacking,a more detailed description of the task configuration and safety clearance is given.In Chapter 4,we present the numerical experimental results for those three cases mentioned above.The results reveal that in those cases,the heuristics designed in this paper can obtain feasible solutions for the QCSP of various scales in millisecond-level time.On average,the completion time of the heuristic solutions is about 110%of the optimal solutions obtained by Gurobi,a commercial programming solver.In addition,using the heuristic solution as the initial feasible solution can speed up the solving of the programming models by at least 5 times.