Scheduling Multi-Vessel Placement in Multi-Chamber Inland Waterway Locks Using Switching Max-Plus Algebra

Abstract

Inland waterway transport is a low CO2 emission alternative to road transport. A shift towards more inland waterway transport could also help reduce road congestion and noise pollution. Infrastructure bottlenecking, particularly at locks, is part of the reasons preventing this shift. Congestion is leading to delays. Locks can be physically improved, or the passage of the vessels through the locks can be optimized through scheduling. Recent work introduced a novel switching-max-plus-linear system approach to scheduling vessels passing through networks of waterways and locks, also introducing a novel routing component to the scheduling problem. Switching max-plus-linear systems are a convenient way to model scheduling systems using max-plus-linear algebra. The switching-max-plus-linear model only considered locks with a single chamber that can only process one vessel at a time. Additionally, it only considered four specific waterway network configurations, rather than any arbitrary network configuration. Real locks can have multiple chambers, and they can process multiple vessels at the same time if they are placed according to regulations in the two-dimensional space of the chamber. The scope of this report was then to build upon this switching max-plus-linear model by adding support for arbitrary network configurations, and multi-chamber, multi-vessel locks with proper twodimensional ship placement, to answer the main research question: How can multi-vessel, multichamber locks with ship placement be integrated into the SMPL IWT scheduling model? Three mathematical scheduling models formulated as SMPL systems were introduced, each subsequent model building on the previous one. The first introduced support for arbitrary network configurations. The second introduced support for multi-chamber locks and allowed vessels to pass through lock chambers at the same time, provided that their assigned one-dimensional sizes fit into the assigned one-dimensional capacity of the chamber. The third introduced support for twodimensional ship placement through a Tetris-like placement sequence also modeled as a switching max-plus-linear system. The models were translated to mixed integer linear programming models, and arrival time and arrival time offset objectives were added, so they could be used as the rules by which a scheduler would build and solve offline scheduling optimization models on a case-by-case basis. Auxiliary objectives to promote vessels slowing down, rather than waiting stationary in the waiting areas, were also added. The models were all found to be working as intended and implemented correctly through the use of a number of verification cases and tests. Complexity tests showed that the solution times for all three models already became larger than a practical limit of 15-20 minutes for simple scenarios with 10-15 vessels. A heuristic model that mimics how vessels are assigned to lockages in practice was built. Comparisons to the scheduling models on the verification cases showed negligible differences for the models in single-lock cases, but it indicated that the multi-vessel, multi-chamber models may outperform practice in multi-lock cases. Future research is recommended to focus on online optimization to account for disturbances, distributed optimization to reduce calculation times, and validation of the model’s performance with real data.