Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
A Bicriteria Approach for Robust Timetabling
verfasst von : Anita Schöbel, Albrecht Kratz
Erschienen in: Robust and Online Large-Scale Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Finding robust solutions of an optimization problem is an important issue in practice. Various concepts on how to define the robustness of an algorithm or of a solution have been suggested. However, there is always a trade-off between the best possible solution and a robust solution, called the price of robustness. In this paper, we analyze this trade-off using the following bicriteria approach. We treat an optimization problem as a bicriteria problem adding the robustness of its solution as an additional objective function. We demonstrate this approach at the aperiodic timetabling problem in which a timetable which is robust under delays is sought. We are able to derive necessary conditions for the resulting Pareto-optimal timetables. For the case in which the robustness is defined as the largest delay for which all connections are maintained we show the bicriteria problem can be solved with the same time complexity as the original single-criteria problem.