Modeling and Solution Algorithm for Green Lock Scheduling Problem on Inland Waterways

Abstract

Inland navigation serves as a vital component of transportation, boasting benefits such as ample capacity and minimal energy consumption. However, it also poses challenges related to achieving navigation efficiency and environmental friendliness. Locks, which are essential for inland waterways, often cause ship passage bottlenecks. This paper focuses on a green lock scheduling problem (GLSP), aiming to minimize fuel emissions and maximize navigation efficiency. Considering the realistic constraints, a mixed-integer linear programming model and a large neighborhood search solution algorithm are proposed. From a job shop scheduling perspective, the problem is decomposed into three main components: ship-lockage assignment, ship placement subproblem, and lockage scheduling subproblem coupled with ship speed optimization. A large neighborhood search algorithm based on a decomposition framework (LNSDF) is proposed to tackle the GLSP. In this, the complex lockage scheduling problem is addressed efficiently by mapping it to a network planning problem and applying the critical path method. Numerical experiments substantiate the effectiveness of our proposed model and a heuristic approach was used in solving the GLSPs. In the sensitivity analysis, under three different objective weight assignments, the resulting solutions achieved average effective ship fuel savings of 4.51%, 8.86%, and 2.46%, respectively. This indicates that our green lock scheduling problem considering ship speed optimization can enhance ship passage efficiency while reducing carbon emissions.

Keywords

• sustainable navigation
• green lock scheduling
• mixed-integer linear programming
• speed optimization
• discrete optimization