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

Bin Ji, Dezhi Zhang, Zheng Zhang, Samson S. Yu and Tom Van Woensel

Transportation Research Part E: Logistics and Transportation Review, 2022, vol. 168, issue C

Abstract: 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.

Keywords: Large-scale generalized serial lock scheduling problem; Inland waterway; Discrete optimization; Hybrid heuristic algorithm; Flexible job-shop scheduling; Tabu-based large neighborhood search algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S136655452200312X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:168:y:2022:i:c:s136655452200312x

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2022.102935

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().