Optimization Online


Ship Traffic Optimization for the Kiel Canal

Elisabeth Lübbecke (elisabeth.luebbecke***at***inform-software.com)
Marco Lübbecke (marco.luebbecke***at***rwth-aachen.de)
Rolf Möhring (Rolf.Moehring***at***tu-berlin.de)

Abstract: We introduce, discuss, and solve a hard practical optimization problem which we call the ship traffic control problem (STCP). Since we plan bi-directional traffic, STCP relates to, and in fact generalizes train timetabling on single-track networks. The objective of finding quickest routes motivates the integration of recent algorithmic ideas from dynamic collision-free routing of automated guided vehicles. We offer a unified view of routing and scheduling which blends simultaneous (global) and sequential (local) solution approaches to allot scarce network resources to a fleet of vehicles in a collision-free manner. This leads us to construct a fast online heuristic. The STCP originates from the Kiel Canal which is the basis for the trade between the countries of the baltic area and the rest of the world. As traffic is projected to significantly increase, the canal is planned to be enlarged in a billion Euro project. Our work forms the mathematical and algorithmic basis for a tool to evaluate the different enlargement options. In view of computational experiments on real traffic data expert planners approved that our combinatorial algorithm is well-suited for this decision support. With the help of instance-dependent lower bounds we assess the quality of our solutions which significantly improves upon manual plans. We are confident that our ideas can be extended to other application areas like train timetabling and collision-free routing, also in more general networks.

Keywords: dynamic routing, conflict-free routing, job-shop scheduling, local search, rolling horizon

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Network Optimization

Citation: TU Berlin, Inst. Math.; and RWTH Aachen, Operations Research.

Download: [PDF]

Entry Submitted: 12/01/2014
Entry Accepted: 12/01/2014
Entry Last Modified: 06/10/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society