ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Separation of cycle inequalities in periodic timetabling (2019)

Borndörfer, Ralf ; Hoppmann, Heide ; Karbstein, Marika ; [et al.]

add to mindlist on the mindlist

Details

Publication Date: 2021-04-14

Description: Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.

Language: English

Type: article , doc-type:article

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

Overview

hit 1 - 1 | 1 hit