The AFSA-GA Algorithm for the Quay Crane Scheduling Problem of the Loading and Unloading Operations

Introduction

As the production operation of the container terminal, the efficiency of the container loading and unloading operation by the QCs is the key point to influence the waiting-time of the ship’s stay in port and the transportation efficiency of the terminal. The container terminal operation includes the series of interrelated operations, such as, the quay cranes(QCs)begin to load and unload containers, the internal container trucks transport containers between ship and yard, when the container ship arrives at the pier. The import and export containers are stored in the yard temporary, the quay cranes(QCs) complete the containers’ loading an unloading in the yard, the external container trucks complete the transport between the yard and ship. Quay cranes are the most important equipment of container terminal, and they are the bottleneck of container terminal system. The operation efficiency of quay cranes directly determines the whole container terminal’s production efficiency.

Based on synchronized loading and unloading technology, and combined with actual scheduling method in terminals, quay crane collaborative scheduling among vessels is proposed. Mathematical models are established to minimize the maximum delay time of all ships. Then quay crane scheduling method based on synchronized loading and unloading for single ship is proposed.

At present, the container quay crane scheduling problem of container terminal can separate to the scheduling problem of multi-container cranes of single container ship and the base bay of the container crane allocation problem. Daganzo (1900) studied more than one ships’ static and dynamic container quay crane scheduling problem for the first time, and divided the container ships into multiple areas, requiring that at most one quay crane work for one area at any time, the objective function is to minimize the cumulative delay cost of all container ships. Kim and Park (2004) used the branch and bound algorithm and the greedy random heuristic algorithm to solve the quay crane scheduling problem of the single container ship by considered the constrains such as the non-cross-crossing of container quay crane, which take the minimum time-span of container ship and the total completion time of container quay cranes as objective function. Chen, Nishimura et al. (2008) proposed the multi-user container terminal berth and container quay cranes’ allocation model, used the heuristic-genetic algorithm to get the optimal solution of the problem. Lee, Wang and Miao (2008) established the non-interference constraint model of the container quay crane scheduling problem, and used the GA to obtain the approximate optimal solution of the problem. Canonaco, Legato, Mazza et al. (2008) used queuing theory to study the quay crane scheduling problem of container terminal, but ignored the influence of the non-interference of the container quay cranes and the operation’s sequence on the dock front loading and unloading operation. Tavakkoli-Moghaddam, Makui, Salahi et al. (2009) used the rolling decision method to study container quay crane scheduling problem, but simplified the ship berth distribution and ignored the influence of ship superstructure to the quay crane operation.

The integrated loading and unloading quay crane collaborative scheduling problem is the NP-Hard problem and difficult solved by the exact algorithm. Nishimura, Imai, and Papadimitriou (2001), Goodchild, Daganzo (2007) and Lee and Chen (2009) used heuristic algorithm, genetic algorithm and global search evolution algorithm to solve the problem. The former mostly relies on the heuristic developed by practical experience and its calculation speed is fast, but it easily falls into the local optimal result and difficultly get the global optimal result. The latter is mainly genetic algorithm, the advantage is to be able to search for the theoretical optimal result, the disadvantage is that the huge calculation of the model will be occurred with the increase in the number of ships and berths, which the search space will rapidly expand and the combined explosion problem will happen.