DISCRETE OPTIMIZATION IN PUBLIC RAIL TRANSPORT

Many problems arising in traffic planning can be modelled and solved u sing discrete optimization. We will focus on recent developments which were applied to large scale real world instances. Most railroad compa nies apply a hierarchically structured planning process. Starting with the definition of the underlying network used for transport one has t o decide which infrastructural improvements are necessary. Usually, th e rail system is periodically scheduled. A fundamental base of the sch edule are the lines connecting several stations with a fixed frequency . Possible objectives for the construction of the line plan may be the minimization of the total cost or the maximization of the passengers' s comfort satisfying certain regulations. After the lines of the syste m are fixed, the train schedule can be determined. A criterion for the quality of a schedule is the total transit time of the passengers inc luding the waiting time which should be minimized satisfying some oper ational constraints. For each trip of the schedule a train consisting of a locomotive and some carriages is needed for service. The assignme nt of rolling stock to schedule trips has to satisfy operational requi rements. A comprehensible objective is to minimize the total cost. Aft er all strategic and tactical planning the schedule has to be realized , Several external influences, for example delayed trains, force the d ispatcher to recompute parts of the schedule on-line. (C) 1997 The Mat hematical Programming Society, Inc. Published by Elsevier Science B.V.