The generalized serial-lock scheduling problem on inland waterway: A novel decomposition-based solution framework and efficient heuristic approach

Serial locks with multiple chambers are common on major inland waterways worldwide. For the first time, this study designs a novel heuristic algorithmic structure for the generalized serial lock scheduling problem (GSLSP) from a batch-processing-based flexible job-shop scheduling perspective, which converts the GSLSP into a discrete optimization problem. Subsequently, the overall discrete optimization problem is decomposed into an assignment problem and two subproblems (a two-dimensional packing problem and the shortest path problem). They are solved by a tabu-based adaptive large neighborhood search algorithm (TALNS), a multi-order best-fit algorithm, and the Bellman–Ford algorithm, respectively. Additionally, a solution-space cutting strategy is proposed to accelerate the TALNS, which occupies most of the computational burden. Case studies are implemented based on practical historical data from the two-lock system in Yangtze River and the six-lock system along the Albertkanaal canal. Numerical results demonstrate that high-quality solutions can be obtained for large-scale GSLSPs within a reasonable time by the proposed hybrid algorithmic structure. After that, GSLSPs with simplified settings are solved with the proposed framework, and the computational results are compared with those obtained by state-of-the-art methods in the literature. Extensive numerical experiments and comparisons infer the effectiveness and versatility of the proposed approach for solving different variants of GSLSP and its superiority over existing methods. Furthermore, experimental results on GSLSPs with varying lock configurations show that the throughput capacity of locks in the middle of a serial-lock system has a more significant impact on the overall transportation efficiency of the serial lock system.