Home > Research > Publications & Outputs > Exact and heuristic approaches to the robust pe...

Research

Associated organisational units

Links

Text available via DOI:

Keywords

View graph of relations

Exact and heuristic approaches to the robust periodic event scheduling problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Exact and heuristic approaches to the robust periodic event scheduling problem. / Goerigk, Marc.
In: Public Transport, Vol. 7, No. 1, 03.2015, p. 101-119.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Goerigk, M 2015, 'Exact and heuristic approaches to the robust periodic event scheduling problem', Public Transport, vol. 7, no. 1, pp. 101-119. https://doi.org/10.1007/s12469-014-0100-5

APA

Goerigk, M. (2015). Exact and heuristic approaches to the robust periodic event scheduling problem. Public Transport, 7(1), 101-119. https://doi.org/10.1007/s12469-014-0100-5

Vancouver

Goerigk M. Exact and heuristic approaches to the robust periodic event scheduling problem. Public Transport. 2015 Mar;7(1):101-119. Epub 2014 Dec 23. doi: 10.1007/s12469-014-0100-5

Author

Goerigk, Marc. / Exact and heuristic approaches to the robust periodic event scheduling problem. In: Public Transport. 2015 ; Vol. 7, No. 1. pp. 101-119.

Bibtex

@article{b9d52e9a434f4313967aa1f4f152fdd4,
title = "Exact and heuristic approaches to the robust periodic event scheduling problem",
abstract = "In the periodic event scheduling problem, periodically reoccurring events need to be scheduled, subject to constraints on the resulting time differences. A typical application for this type of problem relates to train schedules, which have to repeat every hour for passenger convenience. As external disruptions may occur, robustness considerations need to be included in the scheduling process. In this work, we present a recovery approach for instances where integer programming methods can be applied, and a bi-criteria local search algorithm for large-scale instances. In computational experiments, we compare solutions calculated using the recovery approach to risk-averse and to risk-oblivious solutions. Our results suggest that the solutions generated by our approach have a favorable trade-off between cost and robustness. Furthermore, we compare the local search algorithm to a simplified approach that includes the desired robustness level as a hard constraint. The experiments show that our algorithm finds an improved set of non-dominated solutions within equal computation times.",
keywords = "Periodic event scheduling, Periodic timetabling, Recovery robustness, Robust optimization",
author = "Marc Goerigk",
year = "2015",
month = mar,
doi = "10.1007/s12469-014-0100-5",
language = "English",
volume = "7",
pages = "101--119",
journal = "Public Transport",
issn = "1866-749X",
publisher = "Springer Verlag",
number = "1",

}

RIS

TY - JOUR

T1 - Exact and heuristic approaches to the robust periodic event scheduling problem

AU - Goerigk, Marc

PY - 2015/3

Y1 - 2015/3

N2 - In the periodic event scheduling problem, periodically reoccurring events need to be scheduled, subject to constraints on the resulting time differences. A typical application for this type of problem relates to train schedules, which have to repeat every hour for passenger convenience. As external disruptions may occur, robustness considerations need to be included in the scheduling process. In this work, we present a recovery approach for instances where integer programming methods can be applied, and a bi-criteria local search algorithm for large-scale instances. In computational experiments, we compare solutions calculated using the recovery approach to risk-averse and to risk-oblivious solutions. Our results suggest that the solutions generated by our approach have a favorable trade-off between cost and robustness. Furthermore, we compare the local search algorithm to a simplified approach that includes the desired robustness level as a hard constraint. The experiments show that our algorithm finds an improved set of non-dominated solutions within equal computation times.

AB - In the periodic event scheduling problem, periodically reoccurring events need to be scheduled, subject to constraints on the resulting time differences. A typical application for this type of problem relates to train schedules, which have to repeat every hour for passenger convenience. As external disruptions may occur, robustness considerations need to be included in the scheduling process. In this work, we present a recovery approach for instances where integer programming methods can be applied, and a bi-criteria local search algorithm for large-scale instances. In computational experiments, we compare solutions calculated using the recovery approach to risk-averse and to risk-oblivious solutions. Our results suggest that the solutions generated by our approach have a favorable trade-off between cost and robustness. Furthermore, we compare the local search algorithm to a simplified approach that includes the desired robustness level as a hard constraint. The experiments show that our algorithm finds an improved set of non-dominated solutions within equal computation times.

KW - Periodic event scheduling

KW - Periodic timetabling

KW - Recovery robustness

KW - Robust optimization

U2 - 10.1007/s12469-014-0100-5

DO - 10.1007/s12469-014-0100-5

M3 - Journal article

AN - SCOPUS:84921351073

VL - 7

SP - 101

EP - 119

JO - Public Transport

JF - Public Transport

SN - 1866-749X

IS - 1

ER -