On- and Offline Scheduling of Bidirectional Traffic
Elisabeth Lübbecke
Diese Publikation zitieren
Elisabeth Lübbecke, On- and Offline Scheduling of Bidirectional Traffic (2015), Logos Verlag, Berlin, ISBN: 9783832591472
1
Accesses
Accesses
Beschreibung / Abstract
This book provides theoretical and practical insights related to bidirectional traffic on a stretch containing bottleneck segments. On a bottleneck segment concurrent traveling of vehicles in opposite direction is not possible.
The book is motivated by and considers in particular the ship traffic at the Kiel Canal. It connects the North and Baltic Seas and is operated in both directions. In addition, considerations are included that account for the fact that ships register their requests only shortly before their arrival such that scheduling decisions must be adapted online.
The book is motivated by and considers in particular the ship traffic at the Kiel Canal. It connects the North and Baltic Seas and is operated in both directions. In addition, considerations are included that account for the fact that ships register their requests only shortly before their arrival such that scheduling decisions must be adapted online.
Inhaltsverzeichnis
- BEGINN
- 1 Basics
- 1.1 Preliminaries
- 1.2 Background
- 1.3 The ship traffic control problem
- 1.4 Bidirectional scheduling
- 1.5 Related work
- 2 Solving the Ship Traffic Control Problem
- 2.1 Realizing a combinatorial frame via iterated routing
- 2.2 Collision-free routing for a single ship
- 2.3 A heuristic for the STCP
- 2.4 Computational study
- 3 Offline Complexity of Bidirectional Scheduling
- 3.1 Hardness for multiple segments
- 3.2 Hardness of custom compatibilities
- 3.3 Dynamic programs for restricted compatibilities
- 4 Competitive Analysis for Bidirectional Scheduling
- 4.1 The general problem
- 4.2 Identical jobs on a single segment
- 5 Competitive-Ratio Approximation Schemes
- 5.1 General simplifications and techniques
- 5.2 Abstraction of online algorithms
- 5.3 Extension to non-preemptive scheduling
- 6 Approximation Schemes for Bidirectional Scheduling
- 6.1 Polynomial time approximation scheme
- 6.2 Competitive ratio approximation scheme
- Conclusions
- Bibliography