Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Improving the modulo simplex algorithm for large-scale periodic timetabling
AU - Goerigk, Marc
AU - Schöbel, Anita
PY - 2013/5
Y1 - 2013/5
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. The most prominent of them is to find periodic timetables in public transport. Although even finding a feasible solution to the PESP is NP-hard, recent achievements demonstrate the applicability and practicability of the periodic event scheduling model. In this paper we propose different approaches to improve the modulo network simplex algorithm (Nachtigall and Opitz, 2008 [17]), 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 large-scale railway instances show that our algorithms not only perform better than the original method, but even outperform a state-of-the-art commercial MIP solver.
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. The most prominent of them is to find periodic timetables in public transport. Although even finding a feasible solution to the PESP is NP-hard, recent achievements demonstrate the applicability and practicability of the periodic event scheduling model. In this paper we propose different approaches to improve the modulo network simplex algorithm (Nachtigall and Opitz, 2008 [17]), 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 large-scale railway instances show that our algorithms not only perform better than the original method, but even outperform a state-of-the-art commercial MIP solver.
KW - Combinatorial optimization
KW - Large-scale optimization
KW - Periodic event scheduling problem
KW - Periodic timetabling
U2 - 10.1016/j.cor.2012.08.018
DO - 10.1016/j.cor.2012.08.018
M3 - Journal article
AN - SCOPUS:84875221719
VL - 40
SP - 1363
EP - 1370
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
IS - 5
ER -