The lock scheduling problem: Connecting chamber scheduling and ship placement through Combinatorial Benders' Decomposition

hips must often pass one or more locks when entering or leaving a tide independent port. So do barges travelling on a network of waterways. These locks control the flow and the level of inland waterways, or provide a constant water level for ships while loading or unloading at the docks. We consider locks with a single chamber or several (possibly different) parallel chambers, that can transfer one or more ships in a single operation. The resulting lock scheduling problem consists of three strongly interconnected subproblems: scheduling the lockages, assigning ships to chambers, and positioning the ships inside the chambers. By combining the first two problems into a master problem and using the packing problem as a sub problem, a decomposition is achieved for which an efficient Combinatorial Benders approach has been developed. The master problem is solved first, thereby sequencing the ships into a number of lockages. Next, the feasibility of each lockage is verfified by solving the corresponding packing subproblem, possibly returning a number of combinatorial inequalities (cuts) to the master problem. The main focus of the talk will be on the packing sub problem and on how it interacts with the master problem through combinatorial Bender's cuts. A decision support tool that allows lock masters to compute and compare several solutions for a set of arriving and departing ships will also be presented. Live tests have shown that this tool's flexibility and high solution quality may help the lock masters in making quick and informed decisions.status: publishe