Some Studies on the Principles and Mechanisms for Loading and Unloading

Branch and bound algorithms

Branch and bound algorithms are methods for global optimization in non-convex problems. According to Lawler et al. (1966), a branch and bound algorithm searches the complete space of solutions for a given problem for the best solution. The basic concept underlying the branch and bound technique is to divide and conquer. Since a large problem is difficult to solve directly, it is divided into smaller sub-problems until these sub-problems can be conquered. The algorithm is applied recursively to the sub-problems. If an optimal solution is found to a sub-problem, it is a feasible solution to the complete problem, but not necessarily globally optimal. Branch and bound algorithms have been applied successfully in container terminal operations by several researchers. Peterkofsky et al. (1990) formulated the static allocation model with the objective to minimize the weighted amount of time that ships spend at the port. The branch and bound method determines the best possible ship departure schedule. Dominance of infeasible solutions, boundary points, and construction of the branch and bound tree were illustrated. Branching procedures such as node selection, pruning and termination are explained with an example according to the proposed methodology. In order to determine the feasibility, the set of constraints are analyzed one by one. The feasibility of a set of constraints that have a capacitated transportation problem structure is checked through solving a derivative maximum flow problem by labelling algorithm. Computational performance of the method is evaluated by ten problems of different sized ships.

Narasimhan et al. (2002) defined the problem of minimizing the time taken to load and unload the containers from the container stack yard onto the ship as transtrainer routing problem, where transtrainer is the dedicated equipment to load and unload containers from/to trucks to/from container stacking yard blocks respectively. They investigate the theoretical aspects of the problem and prove that the problem is NP-complete. The problem is formulated as an integer program with the given load and bay plans. The overall objective was to minimize the total setup and inter-bay travelling times. A branch and bound based enumerative method was developed to obtain an exact solution to the problem. The properties of optimum solutions and related proofs of lemmas are given. The problem is decomposed into enumerating the degenerate solutions and then arranging the partial sequences in the degenerate solutions to obtain final route for transtrainer. Several lower bounds to prune the size of tree were also developed.

Heuristic models

The other alternatives that can be used for container terminal problems are heuristic techniques. By their nature, heuristic approaches are flexible regarding the nature of the objective function and constraints. As shown inTable ý2., heuristics models covers several techniques including greedy algorithm, simulated annealing algorithms, tabu search, genetic algorithms, etc. Greedy algorithm (GA) has been discussed in details in chapter 3 as it has been applied for optimizing container terminal operations in this research work.

Literature review of container terminal processes:

As mentioned in chapter 1, container terminal operations can be divided over various processes, starting from the arrival of the ship until the departure of the container to its final destination. Container terminals can be classified into two: automated and non-automated.

Figure ý2. View of container terminal.

Automated terminals are preferred in areas where manpower is costly such as the western Europe and the United States. Non-automated terminals operate in Southeast Asia, where labour is less expensive. Figure ý2. represents the basic structure of the container terminals. Steenken et al. (2004), Vis et al. (2003), and Henesey (2006) provide an exhaustive overview of methods for the optimization of container terminal operation operations and logistics. Various decision problems that arise at container terminal can be categorized according to the time horizon involved as i) strategic, ii) tactical, and iii) operational (Hax et al. 1984).

Strategic level includes long-lasting effect decisions on the terminal (covers one to several years) concerning terminal layout, the choice of the handling equipment, and procedures.

Tactical level includes mid-term and short-term decisions (once every week, every month or once every quarter) regarding which types of equipments are used and which layout is chosen.

Operational level involves short-term decisions regarding daily and real-time operations (berth allocation, quay crane scheduling, scheduling routing and loading unloading of trucks, ship stowage), landside operation (transfer operation, yard management), and human resources management.

A review of general classification of various decision problems addressed for container terminal processes are given in the subsequent sections

Arrival of containers

Containers arrive at the ports by different means of transportation such as ships, trucks, and trains. At the strategic level, when ship arrives at the port, it has to moor at the quay side of the port. As there are a number of available berths, a decision has to be made to specify the number of berths that should be allocated to the ship. At the operational level, berth allocation can be done with the objective of maximizing the berth utilization. Logically when ship arrives at the terminal, assigning it to the available berth can be done by first arrived first served rule. However, this strategy may not be good especially when ship's handling time depends on the assigned berth. In Berth Allocating problem, ships are allocated berths closest to the stacking area where most containers for these certain ships are located. In this way, the sum of the waiting and handling time of the ship can be minimized. This problem is equivalent to a machine scheduling problem (e.g. Lawler et al., 1993 and Brucker et al., 2001).

Edmond et al. (1978) used a queuing model for decisions on investment in berth construction and cargo handling equipment, and evaluated simple queuing models for container service. The objective of berth planning by evaluation of congestion and cost as suggested by Nicolau (1967) is to arrive at an optimum port capacity while incurring minimum capital cost. Thus, many container terminal managers are keen to minimize turn-around time with the resources that are available to them. According to Imai et al. (1997), Imai et al. (2001) and Nishimura et al. (2001) several versions of BAP are possible. (i) In static BAP, it is assumed that at the beginning of the planning horizon all ships have already arrived in the port. In this case, at a specific berth where the ships are to be handled, there is no idle time between them. The problem can be formulated as two dimensional assignment problem, which can be solved as polynomial time problem see (Ahuja et al. 1993). (ii) In dynamic BAP, it is assumed that more than two ships may arrive during the planning period which makes it difficult for the problem to be solved using polynomial time anymore. Imai et al. (1997) investigated static BAP under multiple objectives. Not only the sum of the waiting and handling times of the ships are minimized, but the ship's dissatisfaction that arises from the berthing order is also investigated. The multiple objectives are handled by using the weighting method, which reduces the multiple objectives into a single one. The set of non-inferior solution is identified by varying the weights. In the dynamic BAP based on a MIP formulation. Imai et al. (2001) developed a Lagrangian relaxation which was solved using the sub-gradient method. An application of genetic algorithm to dynamic berth assignment has been presented by Nishimura et al. (2001) and Cordeau, et al. (2005) considered both static and dynamic BAP. Two tabu search heuristics are presented and tasted on realistically generated instances (up to 35 ships and 10 berths), derived by a statistical analysis of traffic and berth allocation data of the port of Gioia Tauro in Italy. The terminal plans to incorporate the heuristics in its decision support system in the near future.

Loading and unloading of containers

At strategic level, quay cranes are often used to load and unload containers from a ship. Thus the determination of the type of material handling equipments is the decision involved at this level. At the tactical level, the determination of the number of QCs that have to work on a ship is the decision involved here. Such a problem is known as the crane scheduling problem, which can be visualized as a project scheduling problem. In the crane scheduling model, machines (cranes) work to finish independent tasks (holds) but the objective function value varies with the completion time of full job (ships). Daganzo (1989a) provides a description of a static scheduling problem where a number of quay cranes have to serve a number of ships such that the delay costs of the ships are minimized. An MIP is given for this problem, which is only solved for small problems by direct enumeration. Furthermore, a heuristic procedure is designed which is based on following crane scheduling principles:

Principle 1: a crane should not be idle if there is some work it can do.

Principle 2: if cranes work on a ship, at least one of them should work on "maximum hatch" The maximum hatch of the ship corresponds to the hold that requires the most crane time to be finished.

Principles 3: Assume that when the first hold of a ship is about to be assigned, h crane-hours are available before time t (the latest departure time of the ships already assigned).

Daganzo (1989b) studied the effect of crane operations on ship service at port terminals. In the first step, a simple, approximate approach to calculate the maximum berth throughput during periods of congestion was proposed. The approach then examines the effect that two extreme crane operating strategies have on ship delay, when the traffic level does not exceed the maximum throughput. This is done for an idealized situation designed to highlight the impact of crane operations while admitting closed-form solutions. The average ship delay can vary considerably with the crane operating strategy. Peterkofsky et al. (1990) considered the minimization of the total delay of ships as the objective function. The problem is decomposed into two stages, namely finding the best departure schedule for the ship and finding a crane allocation scheme. A branch and bound method was used to solve the static case of crane scheduling problem.

At the operational level, a decision has to be made to prepare the unloading and loading of containers. The unloading plan indicates which containers are to be unloaded and where they are on the ship. Contrary to the unloading process, loading process is hardly flexible. A loading (stowage) plan indicates for each container where it is to be placed on the ship. Containers with same destination, weight, size, content and so on, belong to the same category .Wherein making stowage plan attention has to be made to find out the sequence in which containers have to be unloaded. In general the unloading and stowage plans seek to minimize the number of unnecessary movements to be performed on the ship. According to Shields (1984), the containers, that will be stowed, have to satisfy a variety of constraints, which arise as a result of physical limitations of the ship, the containers and the sequence in which port are visited by ship. The stowage problem is solved with Monte Carlo method (see Metropolis et al. 1949). Many different possible ships loading are generated and the most different one is given such that re-handlings are avoided to a large extent, physical limitations are met and unloading and loading time is minimized. Wilson et al. (2000) presented a very realistic model, taking into account all technical restrictions in order to arrive at a commercially usable decision support system. The approach by Wilson et al. (2000) is based on decomposing the planning process into two sub-processes, namely a tactical and operational process. The first process assigns containers with the same characteristics (size, port, etc.) to blocks of storage space in the ship. The second, assigning a specific container to specific location in the blocks that determined in the first process. Branch and bound is used to assign the containers to the blocks in the ship. In the tactical planning process, packing heuristics together with Tabu Search are used. Avriel et al. (2000) discussed the container ship stowage problem, its complexity, and connection to the coloring of circle graphs. The shifting of containers on board is defined as the temporary removal from and placement back of containers onto a stack of containers. For instance, if a container placed on a vertical stack has a destination of j, while the containers stacked on it have destinations further than j, the latter containers should be shifted. Although shifting cost could be considerable for large ships, container stowage placement decisions are based on port operations efficiency and ship stability, but not enough attention has been given to minimize the number of shifts for a particular route. Avriel et al. (2000) showed that the problem is NP-complete, where a polynomial time algorithm for single column case exists. Also, they derive upper and lower bounds on the number of columns for which a plan can be found in polynomial time that will result in zero shifts. Further, they show that finding the minimum number of columns for which there is a zero shifts stowage plan is equivalent to finding the coloring number of circle graphs. Avriel et al. (1998) proposed a binary linear programming formulation to solve the problem of stowage planning such that the number of unnecessary moves is minimized. It is shown that the stowage planning problem is NP-hard. Therefore, also a heuristic is developed for solving the problem.

Figure ý2. (a) Single cycling unloading (b) Double cycling unloading and loading.

Goodchild et al. (2004) described the double cycling technique that can be used to improve the efficiency of quay cranes by eliminating some empty moves instead of using the current method, where often all relevant containers are unloaded from the ship before any are loaded (single cycling). In double cycling, containers are loaded and unloaded simultaneously (see Figure ý2.). A solution for this problem has been presented through simple formulae to determine reductions in the number of operations and the operating time.

Ambrosino et al. (2006) proposed a model for the Master Bay Plan Problem (MBPP) where the main goal is the minimization of the loading time of all containers, given that all other ship movements have fixed and known duration. The authors propose a three phase algorithm based on partitioning procedure of the ship, an assignment phase of containers to ship portions and heuristic algorithm. They also propose methods to check and validate the ship stability of the overall stowage plan. Imai et al. (2004) presented a multi-criteria optimization method to the ship stowage problem which takes into account two contrasting objectives: the ship stability and the number of container re-handles. The authors propose a multi-objective integer programming model and they implement a weighting method to come up to a single objective function. Computational experiments for instances with up to 504 containers are provided. Sciomachen et al. (2006) formulate the MBPP as a three-dimensional bin packing problem and present a heuristic solution method which is based on this relation. Objectives are to minimize the total loading time as well as to efficiently use the quay equipment. The approach is validated by using real test cases from the port of Genova (Italy).

Transport of containers from quayside to stack and vice versa

At strategic level, several types of equipment could be used (e.g. truck, straddle carrier, AGV) to transport containers from quayside to stack and vice versa. One of the decisions here concerns with the type of material handling equipment, which take care of the transport of containers. According to Baker (1998) the use of straddle carriers instead of non-lifting trucks improves QC productivity. For the transport of multiple containers, multi-trailer systems can be used (see Error: Reference source not found). This system, in this figure, uses a truck that pulls five trailers, each capable of carrying 2 TEU.

After deciding which system will be used tactical decision entails determining the necessary number of material handling equipment needed to carry out day to day operations. Steenken (1992) developed an optimization system to determine the number of straddle carriers and their route. Because of the fact that the system had to be implemented into a radio data transmission system, it had to fulfil the conditions of a real-time application. The problem is solved as a linear assignment problem.Vis et al. (2001) presented a model and an algorithm to determine the necessary number of AGVs at an automated container terminal. To solve the problem a network formulation was presented.

At the operational level it should be decided which vehicle transports which container and which route is chosen. The objectives are to minimize empty travel distances, delay of ships, or total travel time of the vehicles. A complete review of the routing and scheduling of vehicles in general is given by Bodin et al., 1983 and by Steenken (1992). Steenken et al. (1993) described the more specific problem of the routing of straddle carriers at the container terminal. The objective is to minimize empty-travel distances by combining unloading and loading jobs. Routing and scheduling systems are tested and integrated into a radio data transmission system of a real terminal. Steenken (1992) obtained savings of 13% in empty drives compared with the previously existing situation at the terminal, by solving the problem as a linear assignment problem. Steenken et al. (1993) solve the problem by formulating it as a network problem with minimum costs. Savings of 20¨C35% in empty-travel distances can be obtained within acceptable computation times.

Bish et al. (2001) considered the truck dispatching problem in a container terminal. They model both the loading and unloading of the ship by a quay crane which is serviced by a fleet of identical trucks. Their model attempts to minimize the makespan to complete the entire loading and unloading operation. It was shown that the problem was NP-hard. Bish (2003) extended this study to examine the problem of determining a storage location for each discharging container, dispatching vehicles to containers, and scheduling the discharging and loading operations of quay cranes to minimize the maximum time needed to serve a given set of ships. The problem also was shown to be NP-hard and they proposed heuristic algorithms to solve it.

Kim et al. (1999a) discussed dispatching containers to AGVs so as to minimize the delay of the ship and the total travel time of the AGVs. MIP formulations and a heuristic method for such a problem is given with numerical experiments. Kim et al. (1999b) investigated the single transfer crane routing problem. They focus on the minimization of total handling time of transfer crane at the container storage yard by determining the optimal number of containers to be picked up at each yard bay as well as the optimal route of the transfer crane. Their modelling approach and optimal algorithm is applied without major changes to the straddle carrier routing problems for single and multiple carrier cases as illustrated below. Kim et al. (1999c) discussed the optimal routing of single straddle carrier, which is the frequently used transhipment equipment in port container terminals. They propose a MIP model with the objective of minimizing the total travel time of the straddle carrier and investigate the properties of optimal solutions to devise a solution procedure. The solution procedure is decomposed into two stages. In the first stage, the number of containers to be picked up during a sub tour is determined. In the second stage, the visiting sequence of yard bays by the straddle carrier is found. Their solution procedure could be summarized as follows. First, with respect to a set of transportation model constraints involved in MIP model all basic feasible solutions are generated. Then the set of basic feasible solutions subject to the whole constraints is constructed by enumerating the solutions found in the first step. Next, the routing problem is solved by dynamic programming according to the solution set found in the second step and the least cost route is selected.

Stacking of containers

As already mentioned in chapter 1, there are two ways of storing containers can be seen in the container terminal, storing on the ground and stacking on chassis. The stack as shown in Figure ý2. is an area in the terminal where import and export containers can be stored for a certain period. The stack covers the major part of the terminal and it is used for temporary storage of containers, it can be divided into blocks, each consisting of number of rows, as per terminal the stack's height varies between two to eight storey high (Cools, 2005). A transfer point at end of each lane is situated; at this point the crane unloads - loads the container off/on the truck that transports the container. Empty containers are usually stored in separate area.

Figure ý2. Yard crane and a container block

To stack and retrieve containers, several types of equipment could be used (e.g. gantry yard crane, reach stacker, top loader, etc). At strategic level one decision is how to choose the material handling equipment which is best suited for the stack layout. Another strategic decision which affects greatly the efficiency of stacking is the stack layout itself. The stack height and strategies for storage and retrieval of export and import containers are the factors involved in determining the stack layout. Chen, (1999) described various storage strategies. At the stack, reaching to demanded container it is necessary to move the containers that are placed on the top of it. Reshuffling and removing the containers at the idle time, leads to minimize the delay. Chen (1999) presented a systematic approach to the terminal system which provides a cornerstone for the empirical study of the terminal operations. Using the approach presented by Chen (1999) several factors such as terminal management strategy, shortage of storage capacity, poor quality of container information received, operational rules, higher container storage which influence operational efficiency and cause `unproductive container movements’ can be taken into account. Chen (1999) concluded that improvement of all surrounding conditions has to be carried out to achieve higher stacking.

Chung et al. (1988) proposed the idea of using a buffer area where the number of empty chassis is available to store export containers temporarily. They developed and tested strategies that can reduce the unproductive movements of the stack crane during the loading process and as result reduce the total container loading time. They developed a simulation model to investigate the effect of buffer area on the port operation. A reduction of 4% in the loading time can be obtained by utilizing the buffer area. De Castilho et al. (1993) concluded that for a good configuration of the stack area, the amount of handling effort required to retrieve a container from the stacks depends on stack heights and on the operation strategy used. As a result, it is possible to trade off extra handling effort for higher stacking against space requirements. Moreover, the best operating strategy can be selected for the chosen configuration.

Kim et al. (1999d) examined the storage space allocation problem with stack height and allocation space as the decision variables. The objective was to minimise the number of reshuffles under the condition that the space requirements are met. First, the case in which import containers arrive with a constant arrival rate is observed. The stack height and the amount of space are decision variables. It was concluded that the optimal height of the stack equals the total number of import containers during the length of the planning horizon divided by the total number of available locations in the stack. Secondly, it is assumed that the arrival rate of import containers follows a cyclic pattern with the period of one week. Thirdly, the case in which the arrival rate of containers varies in an irregular way on a rolling horizon is observed. Both problems can be solved by formulating a linear program model. The solution can be obtained by solving the dual problem and related sub-problems by applying the sub-gradient optimization technique. The problem is solved for different cases by determining firstly a formula representing the relationship between the stack height and number of re-handles and secondly by determining methodologies based on Lagrangian relaxation.