This chapter presents a novel hybrid algorithm for the quay crane scheduling problem (QCSP). QCSP consists of scheduling a sequence of unloading and loading movements for cranes assigned to a vessel, minimizing the total completion time of all the tasks. The proposed algorithm integrates two well-known metaheuristics: Greedy Randomized Adaptive Search Procedure and Ant Colony System; it also incorporates a repositioning strategy of idle cranes to reduce the interference generated by the quay cranes. The experimental results show that the proposed method is able to find quality solutions in short times. In experiments reported in the literature with crafted instances of QCSP, heuristic running time varies from seconds in small instances to hours in instances of medium size. Currently, the industry requirements are up to a maximum of approximately five minutes. The hybrid algorithm presented in this chapter allows addressing these requirements, by finding good quality solutions in significantly shorter time for larger problems, which represents an advantage in real environments.
TopIntroduction
Container terminals are a critical asset to a nation’s economy, infrastructure, and quality of life. They provide the vital link between domestic markets to international customers and vice-versa. Therefore, their efficiencies are critical to the success of the supply chain. Terminals face increasing demand from container shipping customers, and often operate in fierce competition with alternative terminals. It is vital for a terminal to effectively utilize its resources such as the ship berthing areas, container yard, cranes, and manpower, to achieve high productivity and customer satisfaction. The primary objective is to achieve rapid flow of containers at a minimum cost. As such, the time to load/unload a vessel has generally been the terminal’s highest priority; the time spent by a vessel at berth is known as vessel turn time. Many studies have focused on improving the vessel turn time by addressing issues associated with berth scheduling, quay crane scheduling, stowage planning and sequencing, storage activities, and allocation and dispatching of yard cranes and transporters (Kaveshgar et al., 2012; Lu et al., 2012). The study of the operations within container terminals can identify different optimization problems which influence the quality of service of these terminals; metaheuristic algorithms have been widely applied in terminal operation optimization.
The problems identified in the port terminals are classified according to the components involved in them. These components are the containers where merchandise is stored, the terminal areas destined for storage of these containers, the equipment required for transportation and location within the terminal, the vessels where containers will be transported, and quay cranes responsible for loading and unloading containers from vessels.
A key part of the operations carried out in the Port Terminal is the movement of containers. This process starts when a container properly labeled, enters in the installations of the company. Later it is located in a yard, and after that into a vessel. The loading and unloading of containers that are made in the quay, where vessels, cranes and personnel required for these processes are located, are operations that require more attention and care because they have the greatest cost in a port terminal.
A port terminal has mainly five areas (see Figure 1): truck operations area, containers yard, warehousing yard, and the area for vessel operations with empty container. In Figure 1, we can identify three types of operations: (1) ground operation, (2) movements in yard and (3) operation in the quay. The processes addressed in this work are related to operations that take place in yard and quay.
Figure 1. Container flows at a port terminal
The management of the operations required to service a vessel begins with the arrival of the containers to the terminal, this generates a Container Positioning Problem (CPP). The containers do not have an order of arrival and must be stored in such a way that minimizes the operations of gantry cranes. These cranes stow the containers onto trucks that carry them to the quay (Ünlüyurt & Aydın, 2012).
Once the process of accommodation of containers in the yard has been completed, they are waiting for the arrival of the corresponding vessel. Port terminals only have a very limited space to attend vessels simultaneously. When the arrival of more vessels than can be attended a Berth Allocation Problem (BAP) is generated. Solving BAP requires knowledge of certain characteristics of the vessel as well as the distribution of loading and unloading tasks of containers. This is evaluated according to the amount of available quay cranes.
Planning the stowage of a vessel is a two-step process. The first step is executed by the shipping company. In the second step, the containers by category are assigned to specific positions within the boat. This problem is known as Container Ship Stowage Problem (CSSP), and only recently Stowage Planning (Ding & Chou, 2015).