PERIODIC NETWORK OPTIMIZATION WITH DIFFERENT ARC FREQUENCIES

For a fixed time interal served railway system we consider the problem to find a timetable such that for a selected class of change possibil ities the arising waiting time is minimal. As a mathematical model to deal with such problems, we introduce ''periodic networks''. The gener al discussion of this concept allows to give formulas for network caus ed waiting times at all junctions. Based on this results we formulate the optimization task to find timetables which minimize a global objec tive depending on all local waiting times. In general, these ''periodi c programs'' are NP-hard. We present a branch and bound approach. As s hown by computational results for the case of a linear objective, the use of the Hermite normal form considerably improves the performance o f the algorithm. For unconstrained problems we give a polynomially wor king method to find the lexicographic best solution.