zbMATH — the first resource for mathematics

The berth planning problem. (English) Zbl 0911.90283
Summary: Singapore has one of the busiest ports in the world. Berth planning is one of the problems faced by planners. This paper studies the berth planning problem. We first formulate the problem and show that it is NP-complete. We transform the berthing problem to a restricted form of the two-dimensional packing problem, use a graph theoretical representation to capture the problem succinctly, and propose an effective heuristic for the problem. Experimental results show that our heuristic performs well on historical test data.

90C27 Combinatorial optimization
90C90 Applications of mathematical programming
90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
Full Text: DOI
[1] M. Garey, D. Johnson, Computers and Intractability, Freeman, 1979. · Zbl 0411.68039
[2] Port of Singapore Authority, Annual Report 1994. PSA Corporate Communications Department, 1979.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.