icture this. You have just been told to plan for the arrival and departure of 180 container vessels (from small to very large) over the next three days. During this period, about 180,000 containers must be moved - that is, unloaded from and loaded onto vessels. The task requires that you work out exactly when and where the vessels will berth at one of four container terminals in different locations. You also have to coordinate the deployment of various resources that serve the vessels while berthed. These include the cranes to load/unload the containers and the prime movers (the trucks) to transport them. With space and resources just barely adequate for the job, you have to maximise their efficiency.

There is more - every ship wants to berth as soon as possible and experience fast turnaround time. You remind yourself that optimal use of space and resources will have a significant impact on operational cost and level of service. The clock starts to run ... now. You have two hours to accomplish the task.

You get the picture.

The logistics of planning container-vessel berthing described in the scenario above is referred to as a berth-allocation problem and constitutes just one of many complex planning-and-operations problems busy container-transshipment ports encounter. For example, in Singapore, the world's busiest port, PSA Singapore Terminals' 2004 business volume reached about 20 million TEUs - twenty-foot equivalent units. One TEU corresponds to a standard twenty-foot container.

Competition from other ports in the region means that PSA Singapore must provide the best service to maintain its competitive edge. One way to do so is to offer greater port-operations efficiency. Today, PSA Singapore berths an average of 60 vessels a day and handles up to 2,500 containers per hour at the four Singapore terminals.

Even without the complication of scheduling other needed resources, berth allocation planning (BAP) remains a complex problem. In BAP, the port manager has to ensure that (a) the vessel berths as soon as possible after arrival to achieve fast turnaround, (b) the quay cranes unload or load the necessary containers in the shortest time, and (c) the cost of container transshipment is minimised.

Lowering transshipment cost has vital importance because most unloaded containers are going to be transferred to other vessels. If the vessels are berthed far apart, the variable transshipment cost rises in proportion to the increased distance the containers must travel within the terminal. When the port manager berths vessels exchanging many containers near each other, the containers travel shorter distances and the transshipment cost goes down. If the recipient vessel has not yet arrived, these containers will be put into temporary storage in a yard area near their incoming vessel's future berthing location.

The Resource Allocation and Scheduling research group (RAS group) in the School of Computing, National University of Singapore (NUS), has been studying BAP with emphasis on finding practical solutions as opposed to solutions of theoretical or research interest only. Good planning has a positive impact in terms of cost savings achieved via efficient use of resources (time, machines, and labour) and higher levels of customer service.

Unfortunately, BAP constitutes a huge computational challenge - it belongs to a class of difficult problems known in computational-complexity theory as NP-complete problems. To date, no scientist has been able to find a fast algorithm to solve any one of several thousand NP-complete problems.

The fact that the BAP is NP-complete has motivated the team to search for practical solutions - algorithms that are (a) based on rigorous research that gives very good (though not proven optimal) BAP solutions and (b) practical for implementation by competent software developers.

Planning View

The BAP solution can be visualised schematically in the Planning View shown in Figure 1. The vertical axis represents the berthing sections of the port. The height of each section corresponds to the length of the section. The horizontal axis depicts time. A small rectangle depicts each berthing vessel - the height is the vessel length, and the horizontal axis represents berthing duration. The vessels berthed at time t are precisely the rectangles that intersect an imaginary vertical line at time t in the view. Therefore, BAP can also be viewed as the problem of placing a set of small rectangles (representing the berthing vessels) into larger rectangular boxes (representing the berth sections of the port) to achieve (a) no overlap between rectangles, (b) no crossed section boundaries by vessels, and (c) minimised total transshipment cost.

The NUS team proposed a solution to the BAP problem that addresses it in two phases: the section-assignment phase, which decides which section to send each vessel, and the berth-assignment phase, which decides the precise berth location for each vessel within the section. The section-assignment phase focuses on the higher level planning issue of ensuring sufficient resources in each section to minimise global transshipment cost. The local-berth-assignment phase focuses on the detailed berth assignment within the section to make sure that the port can successfully berth all vessels.

The project showed that the problem in the section-assignment phase generalises two well-known problems in logistics - the airport gate-allocation problem and the quadratic-assignment problem . The berth-assignment problem is like an offline version of another well-known computer-science problem called the dynamic-storage-allocation problem - allocating memory space to multiple processes running in a computer.

BAP System

The RAS group has developed a software system called BAPS (Berth Allocation Planning System) that solves the berth-allocation problem (Figures 1-2). The system makes use of in-house RAS group software architecture that enables it seamlessly to integrate different solution engines, which several group members developed to solve different sub-problems. BAPS currently integrates three section-assignment solutions and five different berth-assignment solutions based on different technologies - specialised algorithm technology (graph partitioning, rectangle packing, and approximation algorithms) and artificial intelligence technologies (genetic algorithm, tabu search, and branch-and-bound search).

The group also equipped BAPS with a graphical user interface that allows its use in a decision-support system (DSS) mode. In the DSS mode, the system displays the Planning View of the problem instance being solved, showing successfully scheduled vessels at their berth locations. Those that cannot be scheduled are in the right corner in red (Figure 1). The planner has the option to plan again to obtain a better solution. Two replanning options exist: redoing section assignment and berth assignment, or redoing just berth assignment. The user can do each with a few clicks.

BAPS also comes with a comprehensive evaluation test suite of generated benchmark data for rigorous testing of the performance of various algorithms in the system. To overcome the difficulty in getting real world data, the research team conducted a half-year domain study of port operations, using data from various worldwide sources to help generate the benchmark data for its evaluation test suites.

BAPS can also support exploration of "what if" scenarios during the planning of new ports or in redesign of existing facilities. The planner can provide various parameters in the design of the port - the number of berth sections, the lengths of the sections, their layout and inter-section distances, and so on. BAPS provides a mechanism to generate problem for instances that can be used in exploratory evaluation of berth-operation efficiency during strategic planning exercises.

The RAS group is looking for possible deployment of BAPS in a real-world environment. The system applies directly to any container transshipment port - PSA Singapore and others. Cruise operators such as the Singapore Cruise Centre can also make use of BAPS for their ferries and cruise vessels. Airports can utilise the software (with suitable modification) in airport gate-allocation problems. Another interesting potential use is library-book "transshipment" - returning library books to their home branch in a library network with many branches.

Click here to download the full issue for USD 6.50