The ship placement problem constitutes a daily challenge for planners in tide river harbours. In essence, it entails positioning a set of ships into as few lock chambers as possible while satisfying a number of general and specific placement constraints. These constraints make the ship placement problem different from traditional 2D bin packing. A mathematical formulation for the problem is presented. In addition, a decomposition model is developed which allows for computing optimal solutions in a reasonable time. A multi-order best fit heuristic for the ship placement problem is introduced, and its performance is compared with that of the left-right-left-back heuristic. Experiments on simulated and real-life instances show that the multi-order best fit heuristic beats the other heuristics by a landslide, while maintaining comparable calculation times. Finally, the new heuristic’s optimality gap is small, while it clearly outperforms the exact approach with respect to calculation time. set of ships that need to be placed, N ={1,2,…, n} set of lockages (bins) available, M ={1,2,…, m}, where m should be a sufficiently large number, e.g. m = n or equal to an appropriate upper bound set of ships to which ship i ∈ N is allowed to moor width and length of the chamber (integer) width and length of ship i ∈ N (integer) minimal distance between ship i ∈ N and the front/back of the chamber minimal safety distance between ships i ∈ N and j ∈ N when they are adjacent, or laying behind each other represents the left quay of the chamber: x 0 =0, y 0 =0, w 0 =0, l 0 = L represents the right quay of the chamber: x n+1 = W, y n+1 =0, w n+1 =0, l n+1 = L relative cost of the number of lockages integer variables that define the x and y position of ship i ∈ N in the chamber (lower left corner of ship) binary variable that indicates if ship i ∈ N is left to ship j ∈ N (left ij =1⇒ x i + w i ⩽ x j ) binary variable that indicates if ship i ∈ N is behind ship j ∈ N (b ij =1⇒ y i + l i ⩽ y j ) binary variables that indicate if ship i ∈ N is moored to ship j ∈ N’s left, respectively right, side binary variable that indicates whether lockage k ∈ M is used or not binary variable that indicates whether ship i ∈ N is processed in lockage k ∈ M or not binary variable, 0 when ship i ∈ N and j ∈ N are processed in the same lockage, 1 otherwise 
Exact and heuristic methods for placing ships in locks