Hence, in a container seaport, normally trains, trucks, large container ships and feeders meet, while in an airport, planes, cars and trains arrive and depart. The other types of ports are subsets. In principle both freight and persons use those means of transportation but to different degrees. In airports, persons are usually the dominant factor, while in seaports it is freight. This leads to different key problems: In sea ports, loading and unloading of containers on and from ships, the control of various types of vehicles and cranes and the optimal stacking of containers is vital; in airports, it is the control of all moving vehicles on the ground, the optimal positioning of planes, the management of personnel, the optimal use of all terminal resources and the maximization of the comfort of the passengers. Nevertheless, many problems in seaports and airports have a very similar mathematical structure, and solution procedures might be applicable to both types of ports.

Planning and control is the basis for running ports efficiently. Strategic planning is certainly needed when building new ports or when extending the facilities considerably. Operations research can also be used for this purpose (simulation, for example), but we want to focus on tactical planning and control. Both are necessary because actions have to be prepared ahead of time (i.e., personnel and space has to be provided, mobile resources maintained and fueled, etc.), and when an event happens ( i.e., a ship or a plane arrives), one has to act and react quickly and optimally. The planning environment is, however, different from the control environment, and the methods applied differ as well. Two of the main differences are uncertainty is higher in planning than in control, and reaction time is much shorter in control, which generally has to be done "online." Hence, computation in planning is not a very strict constraint and uncertainty models and calculi can be used. By contrast, in control computations have to be very fast, which can either be achieved by very fast algorithms or by only modifying planning results according to realizations (wait-and-see approach).

We shall illustrate this by looking in more detail at the most complex types of ports, namely large sea harbors (container ports) on the one hand and large international airports on the other hand.

Seaports: Moving and Stacking Containers


After a rather slow start more than 50 years ago, containers have revolutionized the transportation of cargo around the world. Containers have greatly reduced port handling times and costs, leading to lower freight rates, and, in turn, increasing trade flows.

Today, approximately 90 percent of all non-bulk sea cargo is transported in containers. Roughly 18 million containers make more than 200 million trips per year on ships that can load the equivalent of up to 14,500 standard 20-foot containers, or TEU (20-foot equivalent units), more than four times the capacity of the largest container ship of 25 years ago [2].

Container terminals are under strong pressure to cope with the increasing traffic. For example, the Container Terminal Burchardkai (CTB), the largest terminal at the port of Hamburg, Germany, and one of the largest individual container handling facilities world wide, is re-designing its terminal layout and handling processes in order to double its throughput capacity from 2.6 million TEU per year to 5.2 million TEU (Figure 1). The transition takes place in parallel to the ongoing terminal operations on a restricted area roughly the size of the country of Monaco. The increase in capacity is made possible through the use of highly automated handling equipment controlled by O.R.-based planning and real-time optimization algorithms jointly developed by INFORM and Hamburg Port Consulting.

Figure 1: Progress in terminal operations: The Burchardkai, Hamburg, in 1968; straddle carrier based operation in 2005; and the future layout in 2014 with automated six-high storage blocks served by triple rail mounted gantry cranes (in red).
Source: INFORM

For almost 10 years, INFORM has developed the modular terminal logistics operating and optimization system TerminalStar that is today used for handling tens of thousands of containers at maritime and inland ports as well as road/rail terminals.

Figure 2 shows the transportation flow through a port container terminal. Import containers arriving by ship move from the quay side on the left through the central intermediate storage area to the railhead and truck interface on the land side at the right. Export containers move in the opposite direction.

Figure 2: Transportation flow through a port container terminal.
Source: INFORM

Generally, the main objective at a container terminal is to minimize vessel turnaround times, corresponding to the maximization of quay crane throughput. The different areas where optimization methods are applied can be roughly classified as: (1) ship planning, (2) storage and stacking logistics and (3) transport optimization. A recent survey lists more than 200 references for these topics [5].

Ship planning begins with the allocation of ships to berths several weeks before a ship's arrival, so that export containers arriving by train and truck can be stored close to the future berthing place. The central part of ship planning is the stowage planning that selects specific stowage positions for all containers to be loaded. The objective is to maximize the utilization of the ship and to minimize the number of container rehandles. Usually, an initial stowage plan listing the required container attributes such as size, weight and the port of destination for every on-board stowage position is created by the shipping line. This plan is transferred to the terminal operator, who then assigns individual containers satisfying the required attributes such that the number of container rehandles in the storage yard is minimized. The final step of ship planning consists of scheduling the allocation of quay cranes over time to the storage bays of the ships that run perpendicular to a ship's main axis.

Storage and stacking logistics within the terminal is an area of rapidly increasing importance because the yard space to stock the growing number of containers has become a critical resource. Usually containers are placed one above the other in stacks. Picking one of the underneath container requires additional moves (rehandles) necessary to clear the containers on its top. To maximize the throughput of the system, these unproductive moves should be avoided.

The stacking problem consists of finding an optimal location for each incoming container. The container is characterized by a set of attributes (geometrical, operational and logistical). Only boxes with the same length can be stacked, and the maximal stack height depends on the type of equipment employed. It is good practice to place containers with similar attributes one on top of the other. In this way, each container in a stack can be considered equivalent, avoiding rehandles. One of the most used stacking strategies involves placing export containers with the same departing ship and same destination on top of each other. Alternatively, it is possible to stack according to the estimated time of departure so that containers with an earlier departure time will be placed on top of others that will be picked up later.

In automated storage blocks, automatic re-stacking during times where the handling equipment would otherwise be idle, can be used to re-optimize the storage area, resulting in a reduction of one-tenth of container loading operations.

In the vast majority of cases, information is uncertain at the moment of the decision. Often it changes over time (for example, time of departure). The fast turnover of containers implies that the available time window for each decision is usually very limited (order of seconds). For these reasons, the stacking problem can be classified as a real-time optimization problem. This means that, in practical applications, one of the most employed optimization techniques are heuristics, mainly rule-based systems or ranking systems.

Other alternative approaches are based on the use of the "soft computing" area of research. A key element of the system is an inference engine formed by a set of rules "if... then..." that operates on fuzzy variables. The use of fuzzy technology allows to model uncertain and qualitative data through the use of linguistic variables, simplifying the mathematical model and reducing the number of variables. The resulting inferential engine uses its tolerance towards imprecision and uncertainty to represent adequately the complex relationships between the variables of the system, making it more understandable and transparent to the user.

In many cases, different algorithms or mathematical models are evaluated and validated through simulation tools. Often the system is a mathematical model of the full logistic process understandable only to few specialists due to the complex structure of the problem and the large number of variables. Testing the performance of the stacking module is also particularly important because the results of the optimization heavily depend on the quality and quantity of the available data. The use of a standard modeling language or rule engine is promising even if difficult due to the extreme variability in logistics solutions employed in modern terminals.

Transport optimization deals with the horizontal transportation of containers. An import container is initially transported from the quay side to the storage area, most frequently by straddle carriers or internal trucks and on some modern facilities by automated guided vehicles. This leads to challenging online vehicle routing optimization problems. At CTB, for example, 104 straddle carriers are controlled. Compared to current practice, the efficiency can often be improved by pooling vehicles. Similar vehicle routing problems arise on the land side, where containers are transported between the storage blocks and the railhead and where external trucks must be scheduled and routed through the terminal.

The intermediate storage area is organized in rectangular blocks that are either served directly by the straddle carriers, which can stack containers up to three or sometimes four high, or by rubber tired or rail mounted gantry cranes (RTMG and RMG) that can typically stack up to five or six high. For example, an RMG block at the CTB can hold more than 2,000 standard containers. At newer facilities the operation of the RMG cranes is fully automatic with two or even three cranes per storage block. Crane scheduling is concerned with the online optimization of the stacking cranes. The objective is to minimize the travel times of the cranes and delays and waiting times at the interfaces of the storage blocks. Online crane scheduling is also needed at the rail interface to unload and load rail cars.

Staff Planning at Airports


At most airports, passenger transportation clearly dominates cargo handling, generating approximately 87 percent of total worldwide revenues in commercial aviation [4]. In general, the aviation industry has been a classical application domain of operations research techniques [1]. INFORM has been active in this field since 1989, offering the GroundStar suite of applications. With installations at 140 airports worldwide, GroundStar is a success story in applying operations research to airport and ground handling operations. Increasing traffic volumes and additional cost pressure imposed by low-cost carriers stress the importance of efficient resource utilization.

The GroundStar suite comprises systems for planning, rostering and real-time control of ground handling staff and equipment. Furthermore, gates and terminal resources like check-in counters and baggage belts can be planned and dispatched. Mobile communication systems (e.g. WLAN or cell phone technology) are integrated for staff dispatching, and interfaces to flight information and display systems ensure seamless integration with other airport and airline systems. Additional components include airport operational databases, billing and contract management as well as data analysis tools.

When airports are involved in ground handling activities, staff costs are an essential cost factor, representing 50 percent or more of total costs [3]. Optimizing staff scheduling — making available sufficient staff with sufficient qualifications at the right times and locations — is therefore of utmost importance. This is true for passenger-related services in the terminal (like check-in, security, boarding) as well as ramp handling services on the apron (e.g., baggage transportation and loading; see Figure 3).

Figure 3: Different application areas of staff planning and dispatching including passenger and ramp handling services.
Source: INFORM

Staff scheduling typically proceeds in three phases. In demand planning, staffing requirements are calculated for a given staff group (e.g., loading/unloading department). To this end, the schedule of all relevant flight events is determined for the given planning period. In short-term operative planning (e.g., one month in advance), scheduled arrival and departure times are available for scheduled as well as charter flights. Typical passenger and baggage figures can be forecasted to a reasonable accuracy from historical data. Engagement standards then define how many people are required for which times for a given flight. As an example, the unloading of a medium-size aircraft may require one supervisor and three loaders for a time of 30 minutes after arrival. Using a rule-based system, the engagement standards are matched to the flight schedule.

Demand planning yields a set of work tasks to be carried out by the staff. Most tasks will have to take place at fixed points in time while for other tasks, the ground time for an aircraft will induce a time window. As an example, cabin cleaning and fueling can typically be carried out within some well-defined part of the ground time. Further task properties include the duration, a location (e.g., the gate) and qualification requirements (e.g., language skills for check-in staff). Depending on the size of operations and the organization structure (e.g., decentralized planning of staff groups by terminal), we will typically have to cover several hundreds to several thousand tasks per day.

Shift scheduling then aims at covering the workload most efficiently by shift duties. Depending on the staff mix as well as legal, union and corporate regulations, shifts will have durations that are fixed or flexible within given limits. Furthermore, there may be limits on admissible starting times. Within given time intervals within the shifts, employees have to be granted lunch and relief breaks of specified durations. Shifts entailing special allowances (e.g., night shifts) are usually penalized. When task assignment is integrated in shift scheduling, employees will be assigned tours of tasks at different locations, introducing vehicle routing aspects into the shift-scheduling model.

In the rostering phase, shifts are assigned to the employees, respecting legal, union and corporate regulations (e.g., minimum rest times between consecutive shifts). Especially for full-time staff, rosters often incorporate repeating structures that either make reference to families of shift duties (e.g., general morning shifts) or specify the concrete shift duties in each position. In this case, shift scheduling and rostering will be strongly interdependent, and both tasks should be integrated into a single-solution approach. While the solution of such integrated formulations is challenging, it is often the only way to make the overall staff scheduling process amenable to a fully automated solution approach. Resulting schedules are typically efficient and at the same time more ergonomic than schedules obtained by a sequential approach and manual interactions. The use of automated scheduling techniques typically saves planners up to 30 percent of their time to create rosters. Additionally, advanced operations research techniques can lead to staff schedules that require 2 percent to 5 percent less working time compared to manually generated solutions.

Obviously, the scale of airport operations makes scheduling systems essential tools in the day-to-day work at airports. In comparison to paper-and-pencil approaches, the mere transparency introduced by scheduling systems can lead to work-time savings of 8 percent and more. On a tactical and strategic level, the impact can even be higher. Flexible O.R. solution techniques enable evaluating alternative staff planning practices, e.g., by revising patterned rosters and shift duties or by cross-utilizing staff groups. GroundStar has also been very successfully employed for evaluating alternative regulations and concessions in corporate bargain negotiations and for optimizing the staff mix. Such procedural changes can lead to savings of up to 12 percent in staff costs.

Making operational data available to the management is a further important benefit of advanced scheduling solutions. Planning and rostering data, as well as time and attendance information, are an important building block of management information systems. Integrated business intelligence solutions help in providing managers with essential information for steering purposes.

On a real-time level, hub control systems integrate information from the different handling services. This allows for tracking and monitoring of the different handling processes, displaying interdependencies and analyzing critical chains. Additionally, interdependencies between the flights (e.g., transfer passengers) can be displayed. Providing an aggregate view on handling activities, hub control provides decision support that is essential in avoiding flight delays and increasing service quality.

Synergies


Even though the visual appearance of container terminals and airports is very different, the mathematical structures of some of their components are pretty similar. For instance, berth planning in terminals and gate planning at airports, quay crane scheduling and scheduling of loading/unloading of aircraft, horizontal container transport by straddle carriers or trucks in terminals, and cargo, baggage and passenger transport on the apron are very similar operations. Demand planning, shift scheduling and rostering are all based on flight or ship timetables. Given the large number of O.R. approaches that are available for solving these problems, such as many kinds of integer programming, chance constraint methods, rule-based systems, approximate reasoning, heuristics, etc., it makes a lot of sense to use synergies of the development of problem solutions for container terminals and airports. This not only improves the solutions, but also makes the development more efficient.



Ulrich Dorndorf is the chief technical officer of INFORM.

Jörg Herbers is consultant for airports, airlines and ground handling companies in the Airport Systems Division of INFORM.

Enrico Panascia is responsible for the development of the storage logistics module for container terminals in the Logistics Systems Division of INFORM.

Hans-Jürgen Zimmermann is founder of INFORM and chairman of the board and scientific adviser. Headquartered in Aachen, Germany, with offices in Frankfurt, London and Chicago, INFORM (www.inform-ac.com) specializes in IT systems for the optimized planning and control of business processes.

References

1. C. Barnhart, P. Belobaba and A.R. Odoni, 2003, "Applications of Operations Research in the Air Transport Industry," Transportation Science, Vol. 37, No. 4, pp. 368-391.
2. Brian J. Cudahy, 2006, "Box Boats — How Container Ships Changed the World," Fordham University Press.
3. A. Graham, 2001, "Managing Airports — an International Perspective," Elsevier.
4. International Air Transport Association (IATA), "New Financial Forecast," December 2006.
5. Dirk Steenken, Stefan Voß and Robert Stahlbock, 2004, "Container Terminal Operation and Operations Research — a classification and literature overview," OR Spectrum, Vol. 26, pp. 3-49.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2007 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com


Web Site © Copyright 2007 by Lionheart Publishing, Inc. All rights reserved.