The Lock Scheduling Problem

The present thesis introduces the lock scheduling problem and promising decompositions into sub problems. Several combinatorial optimization methods have been developed for the lock scheduling problem. Single and parallel chamber locks and lock operations in both an inland and mixed-traffic setting are considered, and a mathematical model precisely describing the problem is presented.Three interrelated sub problems can be discerned: ship placement, chamber assignment and lockage operation scheduling. These are closely related to the two dimensional bin packing problem, the assignment problem and the (parallel) machine scheduling problem respectively.After an in-depth analysis the ship placement sub problem is decomposed by exploiting its sequence constraints, and both an exact and a heuristic approach are developed and tested on a large and diverse test set.A decision support tool for lock masters is presented and evaluated during live-tests at mixed-traffic locks in a major port and on an important waterway. These tests reveal that the introduction of fast and high-quality optimization software in the lock master's tool suite can increase lock efficiency by enabling a faster reaction to last-minute changes, quickly producing good solutions during peak traffic and increasing the lock's planning horizon.The lock scheduling problem is solved through Combinatorial Benders' decomposition by combining the assignment and scheduling problems into a master problem and considering ship placement as a sub problem. Efficient cut separation methods are introduced and tested and the performance of an exact and of a heuristic solution method for the packing sub problem are evaluated. Experiments show that the decomposition method outperforms a monolithic branch-and-bound approach, and that the slow convergence of the master problem is currently the decomposition method's limiting factor.nrpages: 160status: publishe