On- and offline scheduling of bidirectional traffic / vorgelegt von Dipl. Math. Elisabeth Lübbecke Prenzlau.

Format:

Book

Author/Creator:

Lübbecke, Elisabeth, author.

Language:

English

Subjects (All):

Traffic flow.

Physical Description:

1 online resource (ii, 139 pages) : illustrations

Edition:

1st ed.

Place of Publication:

Berlin : Logos Verlag Berlin GmbH, [2015]

Summary:

Long description: 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.

Contents:

Intro

1 Basics

1.1 Preliminaries

1.2 Background

1.3 The ship traffic control problem

1.3.1 A precise geometric model

1.3.2 Scheduling on transit segments

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.2.1 Graph for collision-free routing

2.2.2 Forbidden time windows

2.2.3 Routing details for the canal

2.2.4 Running time

2.3 A heuristic for the STCP

2.3.1 Construction of solutions by sequential routing

2.3.2 Improving schedules by local search on the combinatorics

2.3.3 Rolling horizon

2.4 Computational study

2.4.1 Algorithmic components

2.4.2 Combinatorial relaxation

2.4.3 GPS data realized

3 Offline Complexity of Bidirectional Scheduling

3.1 Hardness for multiple segments

3.2 Hardness of custom compatibilities

3.2.1 Makespan minimization

3.2.2 Minimization of total completion time

3.3 Dynamic programs for restricted compatibilities

4 Competitive Analysis for Bidirectional Scheduling

4.1 The general problem

4.1.1 Lower bound

4.1.2 Upper bound

4.1.3 Polynomial running time

4.2 Identical jobs on a single segment

4.2.1 Lower bound

4.2.2 Upper bound

5 Competitive-Ratio Approximation Schemes

5.1 General simplifications and techniques

5.1.1 Simplification within intervals

5.1.2 Irrelevant history

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.

Notes:

Description based on print version record.

Includes bibliographical references (pages 125-133).

PublicationDate: 20151030

ISBN:

3-8325-9147-8