Modelling traffic dependent lock capacity with combinatorial Benders' decomposition

Waterborne multimodal transportation is becoming an increasingly important part of the logistics chain given its comparatively low pollution levels when compared to other transportation methods. Analysis of the increased traffic flows on rivers and canals indicates, however, that locks will soon become a major bottleneck for inland waterway transportation. Inland waterway operators are thus facing the significant challenge of scheduling their waterway's series of locks in such a way that the transit time of ships traversing the waterway is minimized. The serial Lock Scheduling Problem (sLSP) is the combinatorial optimization problem corresponding to this increasingly difficult challenge for inland waterway operators. A combinatorial Benders' decomposition for the single-chamber serial lock scheduling problem is presented. This approach enables a straightforward transition from fixed/infinite capacity models to those with traffic-dependent lock capacity at little to no additional computational cost. The presented decomposition approach considers the original fixed/infinite capacity model as the Master Problem and evaluates the traffic dependent capacity constraints in a sub problem. By adding combinatorial Benders' cuts to the Master Problem before and during the solution process, it quickly converges to a feasible and optimal traffic dependent capacity sLSP solution. The method's performance is evaluated on a large set of small to medium sized instances, analysing the influence of traffic dependent lock capacities on both the ship waiting time and total computation time. The results demonstrate how the total required computation time of both models are within the same interval, thus highlighting the efficiency of the presented decomposition approach. For larger lock capacities, the decomposition approach is consistently faster than its fixed capacity counterpart. Furthermore, the results reveal significant differences in ship waiting times between fixed/infinite and traffic dependent models on the instances with real-life ship sizes. These results indicate that traffic dependent lock capacity is a prerequisite for an accurate prediction of ship waiting times in realistic scenarios where ships of different sizes are handled by the lock.status: publishe