A Combinatorial Benders׳ decomposition for the lock scheduling problem
Introduction
The Port of Antwerp (Belgium), one of the largest harbours in Europe, processed more than 180 MTE (Million Tonnes Equivalent) of cargo and 70 000 ships in 2012, with an average of almost 200 ships a day [8]. It is a major hub for both inland and intercontinental cargo traffic. The harbour is situated at the river Scheldt with tidal differences averaging five meters. In order to ensure a persistent water level within the harbour, locks separate the docks from the main water way. These locks entail a complex optimization problem: the vast number of ships entering and leaving the harbour every day has to be assigned to lock chambers, their exact position inside the locks need to be determined, and the lockages have to be scheduled. Improving the efficiency of the lock operations could reduce the expensive waiting time of ships, and make the port more attractive for business and economy.
The Albertkanaal is an important inland waterway connecting the Port of Antwerp with the Port of Liège. Over the years, numerous industrial activities have emerged on its banks, leading to over 37 MTE of cargo processed in 2012 [7]. Six locks are used to overcome the height difference of 56 m between Antwerp and Liège. The increase of barge traffic and recent periods of drought make it of paramount importance to reduce the number of lockage operations (i.e. water usage) and the waiting times of ships.
The present contribution is a new, fast exact approach to the lock scheduling problem (LSP) based on a Combinatorial Benders׳ decomposition approach. The LSP is decomposed into a master problem and a subproblem. The master problem (MP) first assigns the ships to lock chambers, after which it attempts to schedule lockages. The subproblem (SP) takes care of positioning the ships inside the lock chambers. Whenever the subproblem identifies an infeasible lockage, i.e. a set of ships that cannot be transferred simultaneously due to the chamber׳s capacity or safety constraints, combinatorial inequalities (cuts) are generated and added to the master problem. The master problem and the subproblem are solved iteratively, until a provable optimal schedule is obtained.
The main focus of this paper is on the decomposition approach and its application to LSP, thereby omitting detailed discussions on the subproblems as they exhibit a large number of application specific constraints. Section 2 describes the LSP. Section 3 provides a literature review. Section 4 presents Benders׳ decomposition approach, defining the master problem and the subproblem in detail, as well as their interaction. Particular attention goes to the generation of feasibility cuts for the master problem, as they largely determine the efficiency of the algorithm. Experiments are conducted on a large number of instances based on data obtained from different Belgian locks. The results are presented in Section 5. Section 6 offers the conclusions.
Section snippets
Problem outline
The Lock Scheduling Problem consists of three interconnected subproblems: an assignment, a packing and a scheduling problem. Each problem comes with a large number of constraints, mainly resulting from safety and nautical regulations. The problem has been described in detail by Verstichel et al. [12]; here we only sketch the general outline. The main lock scheduling specific terms used throughout this paper are elucidated in Fig. 1, which shows a lock with two identical parallel chambers.
Literature review
LSP was first introduced in an inland setting by Verstichel and Vanden Berghe [14], who presented a heuristic approach. Although it is capable of efficiently solving large instances, the heuristic does not provide any insights as to the quality of the solutions. An in depth analysis of the ship placement subproblem of the LSP was made by Verstichel et al. [13], who presented several exact and heuristic solution approaches and a decomposition method for this variant of two dimensional
A Combinatorial Benders׳ decomposition
Verstichel et al. [12] attempted to solve the LSP via a single, large, Mixed Integer Linear Programming problem. The present paper introduces a Benders׳ decomposition which splits the LSP in a master problem and a subproblem. The advantage of this decomposition is that part of the complexity of the problem is shifted to a separate subproblem, thereby obtaining two simpler problems. In addition, efficient dedicated algorithms can be employed to solve the master problem and the subproblem,
Experiments
To assess the quality of the Combinatorial Bender׳s approach, a number of experiments have been conducted on instances based on real-world data originating from the Albertkanaal in Belgium [11]. A problem instance consists of two parts:
- 1.
traffic data:
exact arrival times of the ships,
the directions of the ships,
the dimensions of the ships; safety distances have been accounted for in the reported dimensions.
- 2.
lock data: the characteristics of the locks.
Conclusion
An exact Combinatorial Benders׳ decomposition to the lock scheduling problem was proposed. The LSP, encompassing a scheduling, assignment and packing problem, is decomposed into a master problem and a subproblem. The master problem handles resp. the scheduling and assignment problems, whereas the packing problem is dealt with in the subproblem. When compared to Verstichel et al. [12], where LSP is solved as single integrated ‘monolithic’ MIP problem, the Benders׳ decomposition has two
Acknowledgments
Research funded by Ph.D. Grants SB091152 and SB093152 of the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen).
We would like to thank the Scheepvaartmanagement of the Port of Antwerp for sharing their experience and real-life data on the ship placement problem. The real-life data provided by IT-Bizz and nv De Scheepvaart was also greatly appreciated.
References (14)
- et al.
A benders approach for the constrained minimum break problem
Eur J Oper Res
(2007) - et al.
The generalized lock scheduling probleman exact approach
Transp Res Part E: Logist Transp Rev
(2014) - et al.
Exact and heuristic methods for placing ships in locks
Eur J Oper Res
(2014) - et al.
Combinatorial Benders cuts for the minimum tollbooth problem
Oper Res
(2009) Partitioning procedures for solving mixed-variables programming problems
Numer Math
(1962)- et al.
Combinatorial benders׳ cuts for mixed-integer linear programming
Oper Res
(2006) - Côté JF, Dell׳Amico M, Iori M. Combinatorial Benders׳ cuts for the strip packing problem. Technical report...
Cited by (56)
Solving energy-efficient lock group co-scheduling problem with ship lift and approach channel using a collaborative adaptive multi-objective algorithm
2024, Expert Systems with ApplicationsCombinatorial Benders decomposition for the operational aircraft maintenance routing problem
2024, Computers and Operations ResearchDiscrete multi-objective artificial bee colony algorithm for green co-scheduling problem of ship lift and ship lock
2023, Advanced Engineering InformaticsThe generalized serial-lock scheduling problem on inland waterway: A novel decomposition-based solution framework and efficient heuristic approach
2022, Transportation Research Part E: Logistics and Transportation ReviewCitation Excerpt :The more generalized single-lock scheduling problem with ship placement is also investigated in the literature. Verstichel et al. (2014a, 2015) focused on scheduling a single lock with multiple chambers, which was regarded as a combinatorial problem consisting of a chamber assignment problem, a lockage operation scheduling problem, and a ship placement problem. A MILP model and a logic-based Bender’s decomposition approach were proposed in the two studies to obtain the optimal solution, respectively.
Heterogeneous multi-depot collaborative vehicle routing problem
2022, Transportation Research Part B: Methodological