The lockmaster's problem

Ward Passchyn, Sofie Coene, Dirk Briskorn, Johann L. Hurink, Frits C.R. Spieksma, Greet Vanden Berghe

Research output: Contribution to journalArticleAcademicpeer-review

27 Citations (Scopus)

Abstract

Inland waterways form a natural network infrastructure with capacity for more traffic. Transportation by ship is widely promoted as it is a reliable, efficient and environmental friendly way of transport. Nevertheless, locks managing the water level on waterways and within harbors sometimes constitute bottlenecks for transportation over water. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of upstream-bound ships and another set of ships traveling in the opposite direction. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper, a dynamic programming algorithm is proposed that solves the lockmaster's problem in polynomial time. This algorithm can also be used to solve a single batching machine scheduling problem more efficiently than the current algorithms from the literature do. We extend the algorithm such that it can be applied in realistic settings, taking into account capacity, ship-dependent handling times, weights and water usage. In addition, we compare the performance of this new exact algorithm with the performance of some (straightforward) heuristics in a computational study.
Original languageUndefined
Pages (from-to)432-441
Number of pages10
JournalEuropean journal of operational research
Volume251
Issue number2
DOIs
Publication statusPublished - 1 Jun 2016

Keywords

  • EWI-26990
  • Lock scheduling
  • Transportation
  • METIS-316914
  • Batch Scheduling
  • Complexity
  • Dynamic Programming
  • IR-100322

Cite this