zbMATH — the first resource for mathematics

Periodic network optimization with different arc frequencies. (English) Zbl 0856.90118
Summary: For a fixed time interval served railway system, we consider the problem to find a timetable such that for a selected class of change possibilities the arising waiting time is minimal. As a mathematical model to deal with such problems, we introduce “periodic networks”. The general discussion of this concept allows to give formulas for network caused waiting times at all junctions. Based on this results we formulate the optimization task to find timetables which minimize a global objective depending on all local waiting times. In general, these “periodic programs” are NP-hard. We present a branch-and-bound approach. As shown by computational results for the case of a linear objective, the use of the Hermite normal form considerably improves the performance of the algorithm. For unconstrained problems we give a polynomially working method to find the lexicographic best solution.

90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
Full Text: DOI
[1] Brucker, P.; Burkard, R.; Hurink, J., Cyclic schedules for r irregularly occuring events, J. comput. appl. math., 30, 173-189, (1990) · Zbl 0718.90043
[2] Brucker, P.; Hurink, J., A railway scheduling problem, Zeitschrift für oper. res., A 223-A 227, (1986) · Zbl 0617.90046
[3] Burkard, R.E., Optimal schedules for periodically recurring events, Discrete appl. math., 15, 167-180, (1986) · Zbl 0614.90050
[4] Cuninghame-Green, R., Minimax-algebra, () · Zbl 0399.90052
[5] Edmonds, J., Matroids and the greedy algorithm, Math. programming, 127-136, (1971) · Zbl 0253.90027
[6] Elmaghraby, S., Activity networks: project planning and control by network models, (1977), Wiley New York · Zbl 0385.90076
[7] Gondran, M.; Minoux, M., Graphs and algorithms, (1984), Wiley New York · Zbl 1117.06010
[8] Lawler, E., Optimal cycles in a doubly weighted linear graph, (), 209-213
[9] Nachtigall, K., Exact solution methods for periodic programs, Hildesheimer informatik-berichte., 14/93, (1993)
[10] Schrijver, A., Theory of linear and integer programming, (1986), Wiley Chichester · Zbl 0665.90063
[11] Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM J. discrete math., 2, 550-581, (1989) · Zbl 0676.90030
[12] Serafini, P.; Ukovich, W., A mathematical model for the fixed-time traffic control problem, European J. oper. res., 42, 152-165, (1989)
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.