Elsevier

Computers & Operations Research

Volume 54, February 2015, Pages 117-128
Computers & Operations Research

A Combinatorial Benders׳ decomposition for the lock scheduling problem

https://doi.org/10.1016/j.cor.2014.09.007Get rights and content

Abstract

The Lock Scheduling Problem (LSP) is a combinatorial optimization problem that represents a real challenge for many harbours and waterway operators. The LSP consists of three strongly interconnected subproblems: scheduling lockages, assigning ships to chambers, and positioning the ships inside the chambers. These should be interpreted respectively as a scheduling, an assignment, and a packing problem. By combining the first two problems into a master problem and using the packing problem as a subproblem, a decomposition is achieved that can be solved efficiently by a Combinatorial Benders׳ approach. The master problem is solved first, thereby sequencing the ships into a number of lockages. Next, for each lockage, a packing subproblem is checked for feasibility, possibly returning a number of combinatorial inequalities (cuts) to the master problem. The result is an exact approach to the LSP. Experiments are conducted on a set of instances that were generated in correspondence with real world data. The results indicate that the decomposition approach significantly outperforms other exact approaches presented in the literature, in terms of solution quality and computation time.

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.

This setup enables experimenting with variations

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)

There are more references available in the full text version of this article.

Cited by (56)

  • The 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 Review
    Citation 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
View all citing articles on Scopus
View full text