×

zbMATH — the first resource for mathematics

Integral cycle bases for cyclic timetabling. (English) Zbl 1160.90640
Summary: Cyclic railway timetables are typically modeled by a constraint graph \(G\) with a cycle period time \(T\), in which a periodic tension \(x\) in \(G\) corresponds to a cyclic timetable. In this model, the periodic character of the tension \(x\) is guaranteed by requiring periodicity for each cycle in a strictly fundamental cycle basis, that is, the set of cycles generated by the chords of a spanning tree of \(G\).
We introduce the more general concept of integral cycle bases for characterizing periodic tensions. We characterize integral cycle bases using the determinant of a cycle basis, and investigate further properties of integral cycle bases.
The periodicity of a single cycle is modeled by a so-called cycle integer variable. We exploit the wider class of integral cycle bases to find tighter bounds for these cycle integer variables, and provide various examples with tighter bounds. For cyclic railway timetabling in particular, we consider Minimum Cycle Bases for constructing integral cycle bases with tight bounds.

MSC:
90C27 Combinatorial optimization
90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
Software:
PESPLib
PDF BibTeX Cite
Full Text: DOI
References:
[1] Liebchen, Christian, Der berliner U-bahn fahrplan 2005 — realisierung eines mathematisch optimierten angebotskonzeptes, ()
[2] Kroon, Leo G., Mathematics for railway timetabling, ERCIM news, 68, 22-23, (2007)
[3] Liebchen, Christian, The first optimized railway timetable in practice, Transportation science, 42, 4, (2008)
[4] Serafini, P.; Ukovich, W., A mathematical model for periodic event scheduling problems, SIAM journal on discrete mathematics, 2, 4, 550-581, (1989) · Zbl 0676.90030
[5] L. Peeters, Cyclic railway timetable optimization, Ph.D. Thesis, Erasmus University Rotterdam, Rotterdam, The Netherlands, 2003
[6] K. Nachtigall, A branch and cut approach for periodic network programming, Technical Report 29, Hildesheimer Informatik-Berichte, 1994
[7] Liebchen, Christian; Möhring, Rolf H., A case study in periodic timetabling, Electronic notes in theoretical computer science, 66, 6, (2002)
[8] Liebchen, Christian; Proksch, Mark; Wagner, Frank H., Performance of algorithms for periodic timetable optimization, (), 151-180 · Zbl 1169.90315
[9] M. Odijk, Railway timetable generation, Ph.D. Thesis, Delft University of Technology, Delft, The Netherlands, 1997
[10] Liebchen, Christian, Finding short integral cycle bases for cyclic timetabling, (), 715-726 · Zbl 1266.90106
[11] Liebchen, Christian; Möhring, Rolf H., The modeling power of the periodic event scheduling problem: railway timetables — and beyond, (), 3-40 · Zbl 1168.90459
[12] Stockmeyer, L., Planar 3-colorability is polynomial complete, ACM SIGACT news, 5, 19-25, (1973)
[13] Liebchen, Christian, A cut-based heuristic to produce almost feasible periodic railway timetables, (), 354-366 · Zbl 1121.90337
[14] Ahuja, R.; Magnanti, T.; Orlin, J., Network flows: theory, algorithms, and applications, (1993), Prentice Hall Englewood Cliffs
[15] Nachtigall, K., Periodic network optimization with different arc frequencies, Discrete applied mathematics, 69, 1-17, (1996) · Zbl 0856.90118
[16] Odijk, M., A constraint generation algorithm for the construction of periodic railway timetables, Transportation research, 30, 6, 455-464, (1996)
[17] T. Lindner, Train schedule optimization in public transport, Ph.D. Thesis, TU Braunschweig, Braunschweig, Germany, 2000 · Zbl 1048.90114
[18] Deo, N., ()
[19] Bollobás, B., ()
[20] Liebchen, Christian; Rizzi, Romeo, Classes of cycle bases, Discrete applied mathematics, 155, 3, 337-355, (2007) · Zbl 1147.05043
[21] Whitney, H., The abstract properties of linear dependence, American journal on mathematics, 57, 509-533, (1935) · JFM 61.0073.03
[22] Christian Liebchen, Leon W.P. Peeters, On cyclic timetabling and cycles in graphs, Technical Report 761-2002, TU Berlin, Mathematical Institute, 2002 · Zbl 1160.90640
[23] Schrijver, A., Theory of linear and integer programming, (1998), John Wiley & Sons New York · Zbl 0970.90052
[24] J.C. de Pina, Applications of shortest path methods, Ph.D. Thesis, University of Amsterdam, Amsterdam, The Netherlands, 1995
[25] Chickering, D.; Geiger, D.; Heckermann, D., On finding a cycle basis with a shortest maximal cycle, Information processing letters, 54, 55-58, (1995) · Zbl 0875.68685
[26] Horton, J., A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM journal on computing, 16, 2, 358-366, (1987) · Zbl 0632.68064
[27] Golynski, Alexander; Horton, Joseph Douglas, A polynomial time algorithm to find the minimum cycle basis of a regular matroid, (), 200-209 · Zbl 1078.68833
[28] Berger, F.; Gritzmann, P.; de Vries, S., Minimum cycle bases for network graphs, Algorithmica, 40, 1, 51-62, (2004) · Zbl 1082.05083
[29] Kavitha, T.; Mehlhorn, K.; Michail, D.; Paluch, K., A faster algorithm for minimum cycle basis of graphs, (), 846-857 · Zbl 1103.05086
[30] Kurt Mehlhorn, Dimitrios Michail, Minimum cycle bases: Faster and simpler, ACM Transactions on Algorithms (in press) · Zbl 1300.05304
[31] Deo, N.; Prabhu, G.M.; Krishnamoorthy, M.S., Algorithms for generating fundamental cycles in a graph, ACM transactions on mathematical software, 8, 26-42, (1982) · Zbl 0477.68070
[32] Romeo Rizzi, Minimum weakly fundamental cycle bases are hard to find, Algorithmica (2007) online first:doi: doi:10.1007/s00453-007-9112-8
[33] Deo, N.; Kumar, N.; Parsons, J., Minimum length fundamental cycle set: new heuristics and an empirical study, Congressus numerantium, 107, 141-154, (1995) · Zbl 0896.05055
[34] Liebchen, Christian; Rizzi, Romeo, A greedy approach to compute a minimum cycle basis of a directed graph, Information processing letters, 94, 3, 107-112, (2005) · Zbl 1189.68085
[35] Liebchen, Christian; Wünsch, Gregor; Köhler, Ekkehard; Reich, Alexander; Rizzi, Romeo, Benchmarks for strictly fundamental cycle bases, (), 365-378 · Zbl 1203.68126
[36] Elkin, Michael; Emek, Yuval; Spielman, Daniel A.; Teng, Shang-Hua, Lower-stretch spanning trees, SIAM journal of computing, 38, 2, 608-628, (2008) · Zbl 1172.68045
[37] Hartvigsen, D.; Zemel, E., Is every cycle basis fundamental?, Journal of graph theory, 13, 1, 117-137, (1989) · Zbl 0699.05031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.