container-terminal

How it is built

Architecture overview

A container terminal operating system (TOS) keeps the one true picture of where every container is and decides what every crane, truck and automated vehicle does next. Containers arrive by ship, truck and train, wait in the yard in stacks, and leave by another mode. Money is made or lost in three places: how long a ship waits at the berth, how many times a container is moved without need (a relocation, because the one you want is under others), and how long trucks queue at the gate. The system is layered by time scale. Slow planning (days to hours) fixes the berth plan, the crane plan and the yard layout with optimisation. Fast dispatch (seconds) turns the plan into work instructions for machines with simple rules and small matching problems. Under both lies a log of container events, from which yard inventory, billing and audit are derived. The one idea that makes it work: optimise slowly where a wrong answer is cheap to revise, dispatch quickly with rules that cannot deadlock, and simulate every rule change before it touches a live terminal. Navis N4 is the commercial example in the graph; the open code around it is mostly solvers and simulators.

Parts:

• Event ledger — the record of where each container is and what happened to it — Event sourcing, Optimistic concurrency control
• Berth and crane planning — when and where ships dock, which cranes work them, in what order — Mixed-integer programming (branch and bound), Job-shop scheduling, simulated-annealing (no page yet)
• Yard planning — which block and stack receives which container — Bin packing, Large neighbourhood search (ruin and recreate), Constraint propagation (constraint programming)
• Equipment dispatch — which machine takes which move next, and which route — Assignment problem (Hungarian / Jonker–Volgenant), multi-agent-path-finding (no page yet), Deadlock detection
• Gate — identify the truck and the container, match to a booking — Optical character recognition (text recognition)
• Positioning — where machines and containers physically are — Kalman filter, multilateration-tdoa (no page yet)
• Emulation — try plans and rules on a model before use — discrete-event-simulation (no page yet)

 shipping line ── booking, BAPLIE ─►┌───────────────────────── planning (slow: days → hours) ──────────────────┐
 vessel schedule ─────────────────► │ berth plan (MIP) ─► crane plan (job shop) ─► yard plan (bin packing, LNS)│
                                    └──────────────┬─────────────────────────────────────────────────────────┬─┘
                                                   ▼ work instructions (move, from, to, due)                 │
 gate ─ OCR ─ booking check ──► work queue ──► dispatch (assignment, path finding, deadlock guard) ──► machines
   │                                  ▲                              ▲ positions (GNSS + Kalman, RTLS)       │ done
   └────────── events ────────────────┴────────────── event ledger (append-only) ◄─────────────────────────────┘
                                                   │ fold: yard inventory, dwell time, billing, audit
                                         emulation (discrete-event model) replays the same event stream with new rules

How the parts fit together

Event ledger

Every physical change becomes an event on a container: gate-in, discharged from ship, placed in slot, relocated, loaded, gate-out. Event sourcing keeps these as an append-only stream per container; the yard map is a fold over them. Three reasons fit a terminal specifically: storage billing needs the exact time a container entered and left; disputes (who dropped it, when did the customs hold start) are settled from the history; and the emulation part replays the same stream. Planning and dispatch run at the same time against the same containers, so two decisions can target one slot or one container. The append carries the version the decision was based on, the check of Optimistic concurrency control: the later decision fails and re-reads. Locks would be the alternative; they would hold up a crane for a database wait, while conflicts are rare (most containers are touched by one plan at a time), so retry is cheaper than waiting. Contract: events are facts about the real world, so a "move done" event comes from the machine or the operator, never from the plan; a plan is only an intent and may be overruled.

Berth and crane planning

A vessel call has an arrival window, a length, a number of containers to discharge and load, and a berth section it can use. The berth allocation problem picks start time and quay position per vessel so that the sum of waiting and delay is small and no two ships overlap in space and time. This is a small, well-structured integer problem, and Mixed-integer programming fits it: a call list of a week is small enough to solve to a proven bound, with the formulation tightened by Cutting planes and Presolve reductions inside the solver (the surveys by Steenken et al. and Stahlbock and Voss describe the berth, quay-crane and yard problems in this form). When the call list is too large or the rules too irregular, the same plan is searched with simulated-annealing (no page yet): swap two ships' order, re-time, accept worse moves early.

Once ships are placed, cranes work them. The quay crane schedule is a Job-shop scheduling problem: tasks (bay sections) with precedence, a machine (the crane) that does one at a time, cranes that cannot cross on one rail, and the makespan as the cost, which is the time the ship stays. Dispatching rules build a plan, a swap of critical neighbours or a constraint model improves it. Contract with the next stage: the plan is a sequence of container moves per crane with target times; stowage of the ship itself (the bay plan) arrives from the line as a BAPLIE message, a standard that SMDG maintains, and returns as a plan to confirm.

Yard planning

The yard is blocks of stacks, and a stack is last-in, first-out: reach the third container and the two above must be moved. Yard planning decides where a container goes so that later moves are few. Bin packing is the capacity layer: groups of containers (by size, weight class, destination vessel, hazardous or reefer) go to blocks until each block's slots are used, with the load spread so that no block becomes the crane bottleneck; sort-descending first fit is the simple, fast start. Within a block, the rule is to stack by expected departure so that the next to leave sits on top, and to keep gaps for what arrives next. A plan is then improved with Large neighbourhood search: clear a group of containers from the plan, reinsert with a cost that counts expected relocations. Side rules (segregation of dangerous goods, reefer plugs, 20 versus 40 foot positions) are constraints, and Constraint propagation prunes impossible slots from the domain of a container before the search sees them. The alternative to a planned yard is an on-arrival rule (put it in the nearest free slot), which is faster, needs no forecasts and costs more relocations when the forecast of departure order is good. Contract: the yard plan is a table from container (or group) to the allowed blocks; the exact slot is chosen when the container arrives, against the live state.

Equipment dispatch

Every second or so, the system has idle machines and pending moves, and must pair them. The pairing is an Assignment problem: cost is empty travel plus lateness, one machine per job, solved in O(n³) by the Hungarian or Jonker-Volgenant method. For n of tens to a few hundred this fits the time budget; the min-cost-flow view (min-cost-flow, no page yet) is the alternative when jobs can be chained. Re-solving the whole matrix on every change makes assignments flip; the usual guard is to freeze a pair once a machine has started towards the job.

For automated vehicles in a fenced area, paths must not collide. multi-agent-path-finding (no page yet), as conflict-based search, plans collision-free paths for many robots on a grid: plan each alone, find the first conflict, branch on constraints that forbid it. It is accurate, but a plan is only as good as the timing: a vehicle that runs late makes the plan wrong, and a few late vehicles can lock each other in a loop at a crossing. Deadlock detection is the guard at run time: vehicles waiting for a zone held by another form a wait-for graph, a cycle in it is a deadlock, and one vehicle backs out or is rerouted. The same idea protects the database layer when two operations wait for each other's slot. Contract: dispatch only hands out moves from the work queue, only reads positions, and writes events when a move completes; it never edits the yard plan.

Gate

A truck arriving must be identified (the truck, the driver, the booking) and the container on it read and checked, in a lane, in seconds, or the queue spills onto the public road. Optical character recognition reads the container number from camera images: find the text region, recognise the characters, then correct with a lexicon and score confidence. The container number is not free text: ISO 6346 defines three owner letters, an equipment category letter, a six-digit serial number and a check digit (source: ISO 6346, Wikipedia summary). That check digit is the free validator of the OCR: a read that fails the check is retried or sent to a human, and a read that passes and matches the booking is accepted. Low-confidence reads go to a remote operator instead of the lane staff. Contract: the gate emits either a verified container and booking pair or an exception with the images; it never guesses.

Positioning

Yard planning is only as good as the position data. Machines carry satellite receivers whose noisy fixes are fused with wheel and gyro data by a Kalman filter, giving a smooth position and an uncertainty that dispatch can use (a vehicle whose uncertainty grows is slowed). Where the sky is blocked by stacks and cranes, tags and fixed receivers locate a transmitter from differences in arrival time (multilateration-tdoa, no page yet), whose output feeds the same filter as another measurement. The physical position of a container (which slot it is really in) still comes mostly from the operator's confirmation at the moment of the move, since a wrong slot in the ledger is worse than a noisy machine position.

Emulation

discrete-event-simulation (no page yet) runs a model of the terminal on a time-ordered event queue, with seeded random numbers, so the same arrival stream can be replayed under two dispatch rules or two yard policies and compared. Every planning and dispatch change goes through it first. The ledger helps, since real history is a stream the model can replay. ConFlowGen (see below) generates synthetic container flows when no history exists.

Data and control flow

One vessel call, from schedule to departure:

1. The line announces the call with its stowage plan (BAPLIE); the berth planner places the vessel on the quay and fixes the window.
2. The crane planner sequences the discharge and load moves per crane and sets target times.
3. The yard planner assigns the incoming containers to blocks and reserves space for the containers to be loaded.
4. The plan is cut into work instructions (container, from, to, due time) and put into the work queue; nothing is executed yet.
5. When the ship is alongside, dispatch repeatedly pairs idle trucks and automated vehicles with the next moves of each crane (assignment), plans their paths and watches for deadlock.
6. Each completed move writes an event; the fold updates the yard inventory; the planners read the new state on their next pass.
7. If the ship is late, or a crane breaks, the plans are recomputed from the current state: the berth plan, then the crane plan, then the yard plan, because each depends on the one before.

One truck at the gate:

1. The truck's booking or appointment is looked up; the camera reads the container number.
2. The check digit and the booking are matched; success creates a gate-in event, failure creates an exception for a human.
3. The yard planner picks the allowed block, the live state picks the slot, and a move instruction goes to a yard crane.
4. The crane reports done; the event is written and storage billing starts from it.

Scaling

1. Gate throughput limits first in many terminals, since it is the interface to the public road: more lanes, faster OCR with a human fall-back, appointments to flatten arrival peaks.
2. Dispatch latency is next: assignment is cubic, so keep n small by restricting each job to the machines of its area, and freeze pairs once started. Decompose by block or by crane.
3. Yard efficiency (relocations per move) is a quality limit, not a speed limit: better forecasts of departure, more search time for LNS on the big groups, tighter segregation of cranes between blocks.
4. Planning time grows with the call list and the number of cranes: solve the berth problem by MIP with a time limit and a bound, then hand a good-enough plan to the heuristics.
5. Ledger size grows with every move; read paths use folded views and snapshots, and old events go to cold storage.

Failure modes

Real implementations

I found no open-source production container TOS. The open pieces are solvers and simulators, which is the reason the planning and emulation parts above point to them. SMDG publishes the BAPLIE/MOVINS ship-planning messages used between lines and terminals (smdg.org).

Sources

• D. Steenken, S. Voss, R. Stahlbock, Container terminal operation and operations research - a classification and literature review, OR Spectrum 26, 2004. DOI
• R. Stahlbock, S. Voss, Operations research at container terminals: a literature update, OR Spectrum 30, 2008. DOI
• ISO 6346, Freight containers: coding, identification and marking (summary: Wikipedia).
• SMDG, ship-planning messages BAPLIE and MOVINS. smdg.org
• ConFlowGen documentation. docs
• READMEs of the repositories in the table above.