Optimization Of Berth-Quay Crane Scheduling Under Uncertainty Environments In Container Terminals

Berths and quay cranes are important resources in Mulit-user container terminals. Thus, the berth and quay crane scheduling problem is one of the basic and hot spots in terminal operations. There are lots of studies focusing on this problem. However, the main works are limited within static environment, and lack of relative researches in uncertainty environment. With a detailed analysis of the production system in front of the container terminals, this dissertation systematically studies the berth and quay crane scheduling problem under uncertainty environments. The berth and quay crane scheduling approach, the rescheduling policies, the generative rescheduling approach, and the repair-based rescheduling approach are discussed in order. Considered that the layout of a container terminal has strong effects on berth and quay scheduling problem, thus, all the researches mentioned before are discussed in both discrete layout and continuous layout. To be more specific, the main work is as follows:Firstly, at the stage of berth and quay crane original schedule generation, a multi-objective optimization model is established to minimize both the stay time of ships and the production costs in container terminals. To solve the model, a multi-objective genetic algorithm is proposed, in which, genome structure, genetic operators, and the selected strategy are improved. Both the optimization model and the algorithm are discussed in discrete layout and continuous layout, respectively. Experiments are given to verify the proposed approach. And results show that a satisfied berth and quay crane schedule with maximum benefits can be obtained quickly.Secondly, at the stage of the execution of the berth and quay crane original schedule, an improved rescheduling policy is presented to deal with the rescheduling problem caused by uncertainties which may cause the original schedule infeasible. The rescheduling policy is to define the occurring time and the depth of the rescheduling. At first, based on the source, the uncertainties in container terminals are classified further by the style of disturbance, the degree of disturbance and predication. Considered the predication of some uncertainties, a new event-driven rescheduling policy combined with pre-driven for predicate event and driven for un-predicate event rescheduling policies is given based on the traditional event-driven rescheduling policy. Then, by introducing a minimum-time interval condition, the event-driven rescheduling policy is mixed with periodic rescheduling policy. Moreover, a changed-rescheduling depth system is given to deal with the problem caused by fixed rescheduling depth, such as low quality of rescheduling even infeasible. Experiments are given to validity the proposed rescheduling policy.Thirdly, a generative rescheduling approach is presented to solve the berth and quay crane rescheduling problem caused by event-driven rescheduling policy. This approach is discussed both in discrete layout and continuous layout for extensive applicability. For each layout, a recovery model is established to minimize the number of skipping over ships. A Memetic algorithm is proved by introduced a local search system for search quality and efficiency. The validity of this approach is proved by experiments.At last, a repair-based rescheduling approach is given to solve the berth and quay crane rescheduling problem caused by periodic rescheduling policy. For both discrete layout and continuous layout, the objective function of the recovery model includes two parts:one is to minimize the deviation between the update berth and quay crane schedule and the original one for all the scheduled ships, and the other is to minimize the waiting time of the unscheduled ships. Based on the feature of the discrete layout, a solution algorithm is proposed by combined the Particle Swarm Optimization with the crossover operator. Moreover, a human-computer interaction-based neighborhood search heuristic was presented to solve the rescheduling problem in continuous layout. In this heuristic, the original schedule, the type, and the degree of the disturbance are considered. Experiments are given to show the efficiency and quality of the proposed approach.