Some Studies on the Principles and Mechanisms for Loading and Unloading

Overhead grid rail technology

A concept known as Overhead Grid rail technology for optimizing the use of space and improving the productivity of container terminals (OHGR) has been proposed by Sea-Land and August Design, Inc (Design, 2005). The OHGR consists of an overhead rail, passive switches, shuttles, container buffers and a computer control system. The container handling devices (shuttles) can access any part of the container yard, eliminating the need for ground vehicles in the terminal and, as a result, the need for unproductive road areas (Dougherty, 2008). The shuttles could access the gate area to transfer containers, access a rail spur to transfer to and from trains, and the shuttles could deliver cargo directly to quay cranes in order to improve productivity. Alternatively the shuttles could be isolated to operations within the OHGR and yard vehicles can be used to transfer containers between the OHGR and the gate, ship, and train buffers (Ioannou et al. 2000). The key advantages of OHGR are that it provides high density of stacked containers,, near random access to densely stacked containers, reduction in crane “dancing”, reduction of in-hoisting time, elimination of crane waiting time, valuable combination of high density and high productivity, and ability to be modified or moved from port to port (Khoshnevis et al., 2000).

Automated storage/retrieval system

Automated Storage/Retrieval Systems (AS/RS) are a storage system that uses fixed-path storage and a retrieval machine running on one or more rails between fixed arrays of storage racks. AS/RS are used to efficiently store cargo awaiting shipment or awaiting pickup by a customer, also used to increase the packing density of cargo and containers, and for storage and retrieval with minimal human effort (Asef-Vaziri et al. 2000) and (Khoshnevis et al. 2000). Physical handling systems are used to move cargo or containers within a terminal, to or from a ship, or to or from a storage location. AS/RS can also interface directly with an AGV system, further reducing labour content. These benefits offer more efficient utilization of available space, and quicker and less labour-intensive storage and retrieval (Liu et al. 2002). AS/RS is most often used in distribution centres, which stock large number of items, instead of trans-shipment terminals (such as ports). Like AGV systems, AS/RS require significant capital investment and skilled labour for operation and maintenance. Naturally, the benefits of an AS/RS would be greatest in ports where land and labour costs are especially high or where the space is constrained.

Assisting systems

Besides cranes and transport vehicles, assisting systems play an important role for the organization and optimization of work flow at container terminals. This is valid especially for communication and positioning systems. The electronic communication is based on international standards (EDIFACT; Electronic Data Interchange For Administration, Commerce and Transport). Every change of container status is communicated between the respective parties. From the point of view of the terminal operator the most important messages are: the container loading and unloading lists which specify every container to be loaded or unloaded to/from a ship with specific data; the ‘bay plan’ which contains all containers of a ship with their precise data and position within the ship (it is communicated before arrival in the port); the ‘stowage instruction’ which describes the positions where export containers have to be located in a ship and which is the base for the stowage plan of the terminal; container pre-advices for delivery by train and truck, and the schedule and loading instruction for trains only to name a few. Although only some of these messages specially the stowage instruction for ships and trains interfere directly with the operational activities of the terminal, they are very important because they help to maintain completeness and correctness of container data which is necessary to optimize the work flow. Besides the communication with external partners, the internal communication systems play a major role in optimizing the terminal operation.

Participants at container terminals

There are 6 principal participants at a terminal: 1) the shipper that loads the container and sends it to the terminal, 2) the inland carrier that transports the container to and from the terminal, 3) the terminal operator that oversees the terminal operations, 4) the stevedore who loads and unloads the containerized vessels, 5) the steamship line, and 6) the consignee or recipient of import cargo. The shipper could be the owner of the cargo, freight forwarder, or broker. The inland carrier could be a truck or rail company. The terminal operator might be a public port authority that operates a facility open to any vessel that makes arrangement to call there, or a steamship line operating the terminal as a dedicated facility, serving only its own vessels and customers. The stevedore could be the terminal operator itself or an independent contractor hired by the steamship line. The steamship line is the one who owns the vessel and is a key player in the process. It interacts with the shipper, terminal operator, consignees, and government officials. Lastly, the consignee could be a retailer who bought the cargo or a subsidiary of the shipper.

Problem statement

The main functions of the terminals are delivering containers to consignees and receiving containers from shippers, loading containers onto and unloading containers from vessels, trains, trucks, and storing containers temporarily. The productivity of container terminals is often measured in terms of the time necessary to load and unload containers by cranes and trucks, which are the most important and expensive equipment used in ports. The truck scheduling problem consists of determining a sequence of unloading and loading movements for trucks assigned to cranes in order to minimize completion time as well as the crane idle times. The efficiency of a container terminal is also measured by the degree of utilization of human resources, equipment, yard area, and cost of the operations.

Most terminals are now taking measures to increase their throughput and capacity by introducing new technologies, reducing equipment dwell times through increasing demurrage fees and/or limiting the advance delivery of export cargo, and increasing storage density by stacking containers four or five levels. However, there are four major problem faced by container terminal managers.

How to manage the flow of containers to and from the terminal

How to track the highly dynamic movement of containers in the yard area

How to allocate resources to perform loading and loading operations in the terminal optimally

How to schedule loading and unloading operations in an optimal manner

This major objective of this research is to develop generic models that can be used to schedule loading and unloading operations at container terminals in an optimal manner. This objective can be achieved through optimizing the makespan for loading and unloading containers in the container terminal using greedy search algorithm and mixed integer programming. The intent behind optimizing the makespan is (1) to reduce the waiting time of the trucks, (2) to cut down the operation costs, (3) to find the optimal number of trucks to be used for loading unloading containers to /from trains and (4) to contribute towards improvement in the national economy. Specific objectives of the thesis include

To carry out a literature review of application of optimization techniques to container terminal operations

To carry out literature review of container handling processes in container terminals

To collect data pertaining to container laoding-unloading in Inland Container Depot in Tughlakabad

To develop and evaluate the performance mixed integer programming based mathematical model

To develop and evaluate the performance of scheduling mechanisms based on different principles using greedy and reverse greedy algorithms

To identify and recommend models for improving container terminal operations

The remainder of this thesis is organized as follows. Chapter two presents the literature review of research related to this work. Chapter three presents characteristics of container terminal at ICD, Tughlakabad, New Delhi owned by Container Corporation of India (CONCOR), which is the terminal selected as a case study for this research work. Chapter four discusses the development of mathematical model of truck dispatching problem using mixed integer programming which has been developed using AMPL software.

Chapter five presents heuristic model based on different scheduling mechanisms to address the problem of this research work.

Chapter six presents application of models based on different scheduling algorithms to solve four real-world problems. The analysis of results obtained by using the developed models is also presented in this chapter.

Lastly, chapter seven summarizes key findings from this thesis work, highlights its contribution, and discusses potential areas for future research.

LITERATURE REVIEW

General

The demand on container terminals has increased due to high growth rates on major seaborne container routes. Terminals are faced with the problem of handling an increasing number of containers in short time and at low cost. Therefore, container terminals are forced to increase handling capacities and to achieve gains in productivity. The problem of dispatching and scheduling of the trucks at the container terminal has been extensively studied by many researchers. But unfortunately; most of this research is not directly applicable to container terminals due to their unique characteristics. This, in turn, requires the development of algorithm that take into account the special characteristics and constraint associated with container terminals. Since throughput is the most important objective for a container terminal thus it is important to minimize the total throughput that is the handling time of unloading / loading of all containers from / to the ship. In the following sections, a literature review of terminal operations and logistics has been presented. The review is broadly divided into two parts. In the first part, literature related to applications of optimization techniques to container terminals is presented. The second part presents a review of container terminal processes.

Optimization techniques

Optimization models are used to obtain best solution of a given problem under given circumstances. Most optimisation models are based on some type of mathematical programming technique. Some successful applications of these techniques to container terminal operation have been reported in the literature. Application of various optimization models to container terminal problems has been reviewed by Sirikijpanichkul et al. (2005); Taniguchi et al. (2001); and Russell et al (2003). Basically, these techniques fall into two categories; namely, classical and heuristic. A categorization of optimization techniques has been presented in Table ý2.. A brief review of applications of traditional and heuristic techniques to container terminal operations has been presented in this chapter.

Table ý2. Categorization of optimization techniques

Technique & ApplicationAdvantagesDisadvantagesMathematical programming:

Branch and bound algorithms,

Lagrangian relaxation,

- Branch and cut methodsProvides exact SolutionLimited to small scale simplified problems.

Require many simplified

assumptions

High computation

CostGreedy algorithm,

Simulated annealing search,

Local beam search,

Tabu search,

Genetic algorithms,

Expert system

Neural network

Multi-agent system, Etc.Practical for complex model formulations.

Flexible regarding the nature of the objective function and constraints.

Reasonable computation cost.May not sometimes achieve global optimum solutionsMathematical model

A mathematical model of a system describes system behavior using equations and logical relationships. Types of mathematical models include probabilistic models, mathematical programming models, and simulation models. In addition to the functional and logical relationships that describe system behavior, mathematical models include several other components.

Decision variables are the variables that affect the performance of a given system. Examples of decision variables are the number of cranes to be installed at a container berth, or the number of parking spaces at container terminal.

Parameters are values over which the decision-maker has no control. Examples of parameters are the service rate of an agent at a ticket counter, or the arrival rate of trucks to a container terminal. Identifying the decision-maker for a system is an important step in the modeling activity. If the president of a distribution company is the decision-maker, the location of a warehouse might be a decision variable. If the decision-maker is the warehouse manager, then the location of the facility is a parameter.

Constraints are any limitations that may be placed on the decision variables. Examples of constraints are area limitations for dockside cranes at a container terminal, budget limitations for operating container terminal, and towing capacity limitations of the trucks used in an intermodal system. A constraint may limit a single decision variable or it may involve two or more decision variables.

Performance measures are quantities that capture the level to which the system is operating. Examples of performance measures are throughput, waiting times, equipment utilization, operating costs, and inventory levels.

An objective function identifies an important performance measure and the optimization goal (maximize or minimize) for the measure. For example, an objective function may maximize utilization of yard tractors, minimize operating costs of a container terminal, or maximize profit generated from a container terminal. In a mathematical model, decision variables, parameters, constraints, performance measures, and objective functions are all captured using equations and/or logical relationships.

According to Liu (2002), some of techniques being commonly used by the researchers can be broadly classified as follows:

Linear programming (LP)

Non-linear programming (NLP)

Mixed integer programming(MIP)

Linear programming

Linear programming (LP) is a most widely used mathematical programming technique. LP is an optimization problem with a linear objective function, a set of linear constraints, and nonnegative restrictions imposed upon the underlying decision variable. LP has been used in the optimization of container terminal operations, and the optimization model is of the form

Minimize or Maximizeµ §Eq ý2.Subject to µ §=B(i) for all i=1,...pEq ý2.Xj ¡Ý 0 for all j=1,...qEq ý2.Where µ § is a q dimensional vector of decision variables, C is a q dimensional vector of objective function coefficients; B is a p dimensional vector of right hand side o A is a p q matrix of constraint coefficients; and T represents the matrix transpose operation.

An integer programming model is the one in which all the decision variables assume integer values. Rajotia et al. (2002) applied a mixed integer linear programming model to study the deterministic case for finding out the minimum number of vehicles for loading and unloading a given number of containers. The objective of the model is to minimize empty trips made by the vehicles by taking into account the load handling time, empty travel time, and waiting and congestion time. The result of the model is compared with the result of a simulation study. They conclude that the vehicle fleet size is underestimated using the analytical methods. Holguin et al. (1998) presented a linear programming model of an intermodal container terminal. The model estimates storage charges to maximize a “pricing” function subject to the storage capacity for containers. They classify containers according to marginal operating costs, space requirements, and price elasticity of dwell times. The objective function is evaluated according to the storage charges placed on each container classification. This price function may maximize profit, or profit subject to a breakeven constraint. The model is constrained by a function of the average stack height, dwell time, and input rate for each container classification.

Kim et al. (1999a) studied dispatching of containers to AGVs in a container terminal. The authors proposed a mixed integer linear programming model (MIP) and heuristics to dispatch containers to AGVs such that the delay of the ship is minimised Kim et al. (2004) presented a study that tried to synchronize ship operations with vehicle dispatching using both MIP model and a look ahead heuristic. In a numerical investigation, their heuristics were shown to outperform conventional dispatching rules. Ambrosino et al. (2006) studied the impact of yard organization on the stowage of containers in terms of unproductive export containers movement in the port. They tackled the problem using a heuristic approach based on a 0-1 linear programming model. Alessandri et al. (2007b) proposed a linear discrete-time model and a linear cost function in order to model the flows of containers through an intermodal container terminal and to optimize problems related to the strategic planning of maritime terminals. The objective of the proposed optimal control problem is the minimization of the transfer delays of containers in the terminal. The entire terminal is decomposed into three sub-terminals for ships, for trucks and trailers, and for block trains. Handshaking queues are used for describing delays in transferring containers from one resource to another one. A receding-horizon strategy is adopted in order to seek a solution of the optimization problem. The effectiveness of the proposed control scheme is evaluated by numerical experiments using data from a Mediterranean port in the Northern part of Italy.

Non-linear programming

NLP technique can be applied where some of the constraints or the objective function is nonlinear. NLP can effectively handle a non-separable objective function and non-linear constraints. A general NLP problem can be expressed in the form

Minimise µ §Eq ý2.subject to µ § i = 1........., pEq ý2.where µ § j = 1,....... qEq ý2.in which F is to be minimised subject to m constraints expressed by function g(x), n is the number of decision variables, and Eq ý2. is a bound constraint for the jth decision variable xj with µ § and µ § being the lower and upper bounds, respectively.

Alessandri et al. (2007a) generalized the results of Alessandri et al.( 2007b) by proposing a nonlinear predictive control approach for the allocation of the available handling resources in a maritime intermodal terminal. A mixed integer nonlinear problem is formulated for modelling the container flows within the terminal. The solution techniques developed by them treats decisions expressed by binary variables as non-differentiable functions. However, NLP requires that both the objective function and constraints are differentiable functions.

Mixed integer programming

A mixed integer programming (MIP) problem results when some of the variables in the model are real valued (can take on fractional values) and some of the variables are integer valued the model is therefore “mixed”. When the objective function and constraints are all linear in form, then it is a mixed integer linear program (MILP). In common parlance, MIP is often taken to mean MILP, though mixed- integer nonlinear programs (MINLP) also accrue, and are much harder to solve.

Zhang et al. (2005) presented three mixed binary integer programming models for dispatching vehicles such as AGVs or yard trucks at the quayside. The models consider the unloading phase of a vessel in one berth without taking physical settings such as buffers for vehicles into account. Furthermore, congestion free vehicle traffic is assumed, and continuous operations of quay cranes are not guaranteed since the number of vehicles is limited. The models determine the starting times of the unloading operations as well as the order of vehicles for carrying out the jobs. The objective is the minimization of the overall waiting time of the quay crane (or container jobs) which is equivalent to minimizing the job ready time of the last job. Nguyen et al.( 2009) discussed how to dispatch ALVs by utilizing information about pickup and delivery locations and time in future delivery tasks. A mixed-integer programming model is provided for assigning optimal delivery tasks to ALVs. A procedure for converting buffer constraints into time window constraints and a heuristic algorithm for overcoming the excessive computational time required for solving the mathematical model are suggested

Simulation

Simulation is a modelling technique used to approximate the behaviour of a system on a computer, representing all the characteristics of the system largely by a mathematical or algebraic description. Simulation models provide the response of the system to certain inputs, which include decision rules that allow the decision makers to test the performance of existing systems or a new system without actually building it. Optimization models aim to identify optimum decisions for system operation that maximises certain given objectives while satisfying the system constraints. On the other hand, simulation models are used to explore only a finite number of decision alternatives so that the optimum solution may not necessarily be achieved. However, many simulation models now involve a certain degree of optimisation and the difference between the optimisation and simulation models is becoming less distinct.

Simulation models have been routinely applied for many years by several researchers. Legato et al. (2001) and Canonaco et al. (2007) have proposed methods for integrated berth planning via simulation. Ludwik (1990) simulated a ship-to-rail intermodal freight terminal using a knowledge base and a set of algorithms. The knowledge base consisted of the physical elements of the terminal and the terminal operations processes¨Cspecifics about the loading and unloading of equipment, the type of ships arriving to the terminal, the storage facilities, the type of cargo being handled, and the interactions among these elements. Ludwik (1990), defined the vehicle, its arrival frequency and time of first arrival, its economic cost, and its required operations. He described processes by the type of cargo transfer (storage to vehicle, vehicle to vehicle, etc), the type of cargo, a process efficiency measure, and the terminal elements required to carry out the process. A microscopic simulation model based on Automated Container Terminal (ACT) has been proposed by Ioannou et al. (2001). Data was collected from a conventional terminal and simulation was carried for the ACT system for the same operational scenario in order to compare and evaluate their performances. The performance of the model was assessed by throughput, ship turn-around time, truck turn-around time, gate utilization, container dwell time, idle rate of equipment.

Liu et al. (2002) and Liu et al. (2004) investigated the impact of two commonly used terminal layouts and automation using AGVs on the terminal performance. One layout is characterized by container stacks that are placed in parallel with the berth. In the second layout, the stacks are arranged perpendicular to the berth. A multi attribute decision-making method is applied in order to evaluate the terminal performance and determine the optimal number of deployed AGVs. Three operational scenarios are considered and compared for both automated yard layouts: (1) loading, (2) unloading, and (3) combined loading and unloading operations. Simulation experiments based upon real-life yard operational data from Norfolk in the United States of America. Results of simulation showed that the performance of a non automated terminal can be substantially improved by automation using AGVs. An additional finding was that the yard layout influences the terminal performance as well as the number of AGVs. It is indicated that the combined operation can increase the terminal throughput as well as the utilization of equipment in the yard.