Homogeneous Optimal Fleet

The structure of chains in the optimal chain decomposition of a periodic schedule S is investigated. A finite oriented graph termed the Linis Graph (LG) is defined which serves as the key for this investigation. The edges of the LG are trip-types of S and the vertices of the LG represent terminals. It is proved that there is an Euler cycle for a connected LG satisfying natural precedence relations between arrival and departure times. Expansion of this cycle in a real time gives a “master-chain” of trips which, being repeated periodically, gives an infinite periodic chain. Time-shifted periodic replication of this chain allows obtaining a group of twin-type periodic chains forming an optimal fleet over S. It is proved that if the LG has m connected components then there is an optimal fleet consisting of m groups of similar periodic chains. It is shown that if the graph of terminals is connected and the LG is disconnected then it is possible to obtain a twin-type fleet over S by adding to S “dummy” trip-types. A general approach to constructing a twin-type fleet of minimal size for this case is described. The relation of the theory developed to the so-called center problem is discussed.