by Martin Aronsson and Per Kreuger
Software that optimizes stacking of container ports has the potential to significantly improve transhipment efficiency. We have investigated this problem and present some exciting new approaches to solving it.
Large container ports around the world are major hubs in the global cargo transport system. Efficient management of resources in and around a port is essential since investments in port facilities, vessels and support systems are substantial.
SICS has performed a pilot study to investigate how the efficiency of port operations could be improved. The chosen focus was on the container stacks. SICS developed a general model for the handling of the stacks as stores, a simple demonstration that uses and compares two implementations with different properties.
A container stack is a type of temporary store where containers await further transport by truck, train or vessel. The main efficiency problem for an individual stack is to ensure easy access to containers at the expected time of transfer. Since stacks are 'last–in, last–out', and the cranes used to relocate containers within the stack are heavily used, the stacks must be maintained in a state that minimizes on-demand relocations.
Stacking Problem Requirements and Objective
Loading and offloading containers on the stack is performed by stack cranes. In order to access a container which is not at the top of its pile, those above it must be relocated. This reduces the productivity of the cranes. Figure 2 shows a scheme of a port indicating the resources involved.
Maximizing the efficiency of this process leads to several requirements. First, each incoming container should be allocated a place in the stack which should be free and supported at the time of arrival. Second, each outgoing container should be easily accessible, and preferably close to its unloading position, at the time of its departure. In addition, the stability of the stack puts certain limits on, for example, differences in heights in adjacent areas, the placement of empty and 'half' containers and so on.
The objective of this work is therefore to plan the movement of the cranes so as to fulfil these requirements with a minimum number of movements and/or a minimal waiting time for vehicles and vessels.
Methods for Batch Relocation of Containers
Assuming that each outgoing container in the stack has a fixed departure time, a priority can be assigned to each container. This is essentially the duration in days to its departure.
The following two sections describe two models developed in the pilot study. The first is a constraint programming (CP) model that characterizes the desirable properties of a solution to the relocation problem; the second is a heuristic where the properties of desirable states are instead captured by a more sophisticated cost function than that used in the CP model.
The Constraint Model
This model formulates a number of hard constraints which limit the search for an improved goal state. That is, it formulates the properties of a 'sufficiently' desirable goal state and then searches for a sequence of moves that will take the stack in a direction of such a state. These constraints are:
- feasibility - any allocation must be supported, i.e. stand directly on the ground or on top of another container
- consistency - only one container can be allocated to each position at any given time
- priority - all piles should be sorted so those highest priority containers are always on top of lower or equal priority containers.
When searching for sequences of moves to achieve such a state, only containers with the highest priority and containers above them are considered for moving.
With the addition of a simple cost function, priority can be given to moves that tend to take the containers towards the 'right' area of the stack, clear an area where we expect incoming containers, and/or are quick or 'cheap' to perform.
Local Search
The method is a 'greedy' algorithm that could easily be incorporated into a more general local search mechanism but can also, as in the cases considered in the pilot study, be used directly to improve any given stack configuration.
Let the penalty of a single pile be a weighted sum of its 'unsortedness', the distance of each container in the pile from its ideal x,y-position in the stack and, finally, the distance in its z-position from its ideal z-position. Then, in each iteration:
- choose the pile with the worst contribution to the penalty
- compute the best new placement for the top container of that pile
- if this improves the overall penalty, perform the move and iterate
- if not, choose the second worst pile etc
- when no more improving moves can be found, terminate.
The method is quite sensitive to the exact weights assigned to each factor in the penalty function and, especially for stack configurations with close to full allocation, can easily get stuck in local minima.
Results
Using the ideas described above, the study showed that, even using comparatively simple methods from local search and constraint programming, we could reduce the total penalty for typical stacks by 10-50% depending on, for example, the degree of utilisation of the total stack capacity.
Since the allocation of positions to containers is currently done more or less manually, this has convinced us that it should be possible to achieve significant improvements of lead times, storage utilisation and throughput using improved techniques of the type indicated. Even though the pilot study was based on rather simplistic models, which didn't take into account factors such as stack stability or container content, we are confident that improving the management of the container stacks in a more realistic setting would also yield significant improvements in several of the most important measures of transhipment efficiency.
Link:
http://www.sics.se/iam/
Please contact:
Martin Aronsson and Per Kreuger
SICS, Sweden
Tel: +46 8 6331500
E-mail: Martin.Aronsson
sics.se, Per.Kreugersics.se
