Whilst considering some physical conditions defining the possible berthing of a container vessel in port, like LOA of vessel, free space between vessels, vessel ETA & ETD, draught and tide, temporary unavailable berthing zones (non-working crane or quay under repair) vessels can be planned for berthing at a container terminal.
Combining these restrictions with knowledge about the physical characteristics of the yard (geometry, dimensions, yard driving rules), the actual location of containers ready for loading and assigned blocks for discharge containers, the assigned vessel berth can be optimized with the result of saved mileage of the yard equipment.
This optimization algorytm belongs to the NP-hard complexity class. This means that there is no exact effective algorithm known. Brute force algorithm, that finds all vessels' permutations (only relative vessel position, no exact coordinates, no traffic optimization) requires about 1018 combinations to be considered for moderately busy terminals with 20 calls per week. Such direct approach may take hours and even days just to find a feasible berthing scenario.
Wikipedia:
NP-hard (nondeterministic polynomial-time hard), in computational complexity theory, is a class of problems informally "at least as hard as the hardest problems in NP." A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H, i.e. . In other words, L can be solved in polynomial time by an oracle machine with an oracle for H.
The famous simplex method that successfully solves many real world problems cannot be applied to berthing optimization as it contains non-linear both constraints and target function, due to the yard equipment mileage calculation.
The solution was to build an effective approximation algorithm by incorporating algorithms from graphs theory and an inhouse developed algorithm for solving system of inequalities, that describes parameters of the task. It finds near to optimal solution in seconds:
The proposed algorithm starts with finding a feasible solution by solving a system of inequalities. This system reflects physical limitations such as total berth length, vessel length, minimal allowable distance between vessels, location of unavailable zones, etc. The solver not only places vessels to berth to meet all constraints, but also find vessel position among available positions resulting in minimal yard equipment mileage. The algorithm also uses vessel priority based on total amount of move operations to guarantee that "heavy" vessels get the best positions. Output of this stage is a feasible berthing scenario with reasonably good total mileage.
Next phase operates with graph representation of the berth scenario. It checks if small shift of vessel and all dependent vessels (that do not change order of vessels) give total mileage decrease. If mileage can be decreased by the vessel shift, the algorithm executes accordingly.
Then a set of heuristics is applied to the scenario. These heuristics defines rules of vessel permutations, that cannot break the scenario feasibility, but can result in mileage decrease. This phase completes final scenario tuning.
An important advantage of the approach is that it allows adjusting almost any parameter manually and letting others to be found by the algorithm. Additionally, the structure of the algorithm allows adaption to new business requirements. This results in flexibility in practical applications.
