Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Engineering the modulo network simplex heuristic for the periodic timetabling problem
AU - Goerigk, Marc
AU - Schöbel, Anita
PY - 2011
Y1 - 2011
N2 - The Periodic Event Scheduling Problem (PESP), in which events have to be scheduled repeatedly over a given period, is a complex and well-known discrete problem with numerous real-world applications. One of them is to find periodic timetables which is economically important, but difficult to handle mathematically, since even finding a feasible solution to this problem is known to be NP-hard. On the other hand, there are recent achievements like the computation of the timetable of the Dutch railway system that impressively demonstrate the applicability and practicability of the mathematical model. In this paper we propose different approaches to improve the modulo network simplex algorithm [8], which is a powerful heuristic for the PESP problem, by exploiting improved search methods in the modulo simplex tableau and larger classes of cuts to escape from the many local optima. Numerical experiments on railway instances show that our algorithms are able to handle problems of the size of the German intercity railway network.
AB - The Periodic Event Scheduling Problem (PESP), in which events have to be scheduled repeatedly over a given period, is a complex and well-known discrete problem with numerous real-world applications. One of them is to find periodic timetables which is economically important, but difficult to handle mathematically, since even finding a feasible solution to this problem is known to be NP-hard. On the other hand, there are recent achievements like the computation of the timetable of the Dutch railway system that impressively demonstrate the applicability and practicability of the mathematical model. In this paper we propose different approaches to improve the modulo network simplex algorithm [8], which is a powerful heuristic for the PESP problem, by exploiting improved search methods in the modulo simplex tableau and larger classes of cuts to escape from the many local optima. Numerical experiments on railway instances show that our algorithms are able to handle problems of the size of the German intercity railway network.
U2 - 10.1007/978-3-642-20662-7_16
DO - 10.1007/978-3-642-20662-7_16
M3 - Conference contribution/Paper
AN - SCOPUS:79955797326
SN - 9783642206610
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 181
EP - 192
BT - Experimental Algorithms
A2 - Pardalos, Panos M.
A2 - Rebennack, Steffen
PB - Springer
CY - Berlin
T2 - 10th International Symposium on Experimental Algorithms, SEA 2011
Y2 - 5 May 2011 through 7 May 2011
ER -