Menu ▾ ▴

Home

Martin Luy

The Lock Scheduling Problem

Locks are intended to lift ships between different water levels. Ships arriving at both sides of a lock should be assigned to lock chambers such that primarily all ships will wait as short as possible. As this problem is NP-hard (proof by reduction to 3-Partition), advanced algorithms are necessary when you have more than a few ships.

Research project

This software was initially developed within a project of TU Berlin regarding the Kiel Canal (see http://www.wsa-kiel.wsv.de/ and http://www.wsd-nord.wsv.de/Schiff-WaStr/Schifffahrt/NOK/index.html). More information about that project can be found on the website of the Combinatorial Optimization & Graph Algorithms group.

Documentation

The code has been extensively documented by Javadoc. Besides, the workflows of the implemented algorithms have been described in detail in the paper of my diploma thesis, see http://martin-luy.de/diploma_thesis.html.

Applicability

The software can be applied to locks at inland waterways as well as at river mouths, however the following conditions should be met:

Lock chambers:

  • The lock chambers are situated in parallel, not one after another.
  • They perform lockages independently from each other.
  • The time intervals for filling and dumping as well as for opening and closing the doors of the lock chambers only depend on the properties of the lock chambers and not e.g. on the tides. I.e. for lockages at water mouths, tides will not be considered at the moment.

Ships:

  • Ships are individual and won't be separated.
  • Offline problem: The arrival times of the ships must be known at the beginning. (Otherwise a superior algorithm has to ensure that. That will e.g. be necessary if there are interactions of lockages between several lock locations. One could solve that by iteratively calculating the lockages for consecutive overlapping time horizons.)

Prioritization of ships:

  • By default there is no prioritization. That causes large ships waiting while some smaller ships will be placed together in some lock chamber first. That can be changed by simple modifications, e.g. by weighting the waiting times of large ships in the objective function or by multiplying the waiting times of all ships by their volume or surface area.
  • The FCFS (“first come first serve”) rule can be selected to be active or inactive. It says that per lock chamber and direction, ships will be passed through in the order of their arrivals.

Positions of ships in lock chambers:

  • Ships will be placed at the left and right side of the chambers. (For other requirements, only the packing algorithm has to be changed in general.)
  • The safety distances in front of / behind and left / right of the ships are assumed to be constant. (Otherwise, only modifications to the packing should be necessary, too.)

Entrances and leavings of ships into / out of the lock chambers:

  • The entrance and leaving times from the waiting rooms into the lock chambers and vice versa only depend on the direction and the lock location.
  • The safety times before and between the entrances and leavings only depend on the direction and the lock chamber.
  • In case there are at least two lock chambers, ship routes might cross each other. That's not considered at the moment and will have to be handled externally.
  • Ships will leave their lock chamber in the order of their entrance.

Get started

In a few steps you will have it running:

  • Download the Code.
  • Be sure you have JDK 7 installed and your path and classpath variables configured properly.
  • Create a new project in your development environment.
  • Import the content of the 'trunk' directory of the software from your file system.
  • Add the 'JUnit4' library.
  • Modify the input data contained in XML files in the 'trunk/data' directory according to your problem instance. Units of the parameter values are meters and seconds.
  • Run workflow.Controller.java. You will see some output of the calculation on your console, and some windows with graphical results will open after a short time.

Graphics

(Click on the pictures to enlarge)

Screenshot thumbnail
Local search display
Screenshot thumbnail
Solution display

Solution display

The first table in the display shows the data of the found solution. The second table contains the input data and solution data regarding the lock chambers.

Below, the solution is displayed graphically. The vertical axis shows the time elapsed since some initial point in time. Vertical black lines separate all activities happening at specific lock chambers.

Light blue bars represent the time intervals that are relevant for the ships, i.e. from the arrival at the waiting area until leaving the lock chamber (horizontal pink line). The displayed numbers are the IDs of the ships. The yellow segments illustrate the entrance of the ships into their chamber. Potentially displayed red segments represent the latest time interval for the ship to enter the chamber without delaying the execution of the lockage.

In the middle of each illustration of a chamber there is a vertical bar which shows the activities of the chambers themselves. Light and dark gray segments represent lockages of both directions. The enclosed ships are drawn left or right of the bar accordingly. Ship entrances and leavings will happen in the order from outer to inner.

Dark blue segments represent executions of lockages, i.e. closing the entrance gate, adjusting the water level, and opening the exit gate. These time intervals are separated by two white lines. The green segments (hiding parts of the gray lockage bars) illustrate safety times that must be ensured for a lock chamber before a ship enters or leaves it.

When you click on some of these graphic components, detailed information will be shown. E.g. for the light blue bars of the ships, the entrances of the ships, and the lockage executions. For the gray segments of the lockages, the tooltips will show the positions of the enclosed ships in the lock chamber from top view and from left and right.

Local search display

This graphic illustrates the local search that was performed by the algorithm for some problem instance. Each node represents some solution. The cost is shown on the vertical axis, and the number of search steps on the horizontal axis. Nodes of neighbor solutions are connected by an edge.

Clicking on a node will open a solution display for that solution. Hovering over some node will show a tooltip with information about that solution.

Project Admins: