Constructing an Optimal Fleet for a Transportation Schedule.

A schedule is a set of passages; is a 4-tuple p = (p1, p2, p3, p4) where p1, p2 denote departure and arrival terminals, p3, p4 departure and arrival times. A fleet is a partition of the schedule into chains; each chain is a finite or infinite sequence of passages p1, p2, … having the property pn² = pn+i¹ and pn4 ≤ pn+i³. The fleet-size is the minimal possible dimension (i.e., the number of chains) of the fleets. The deficit function d(t, a) for a terminal a is the difference between the number of departures and arrivals occuring at a during the interval [O, t]. It is proved that the fleet-size is equal to ∑o max≥0 d(t, a). A general method for constructing all optimal fleets is described. A special case of periodic schedules is studied and it is proved that a periodic schedule can ba decomposed into an optical periodic fleet. Applications of the deficit function technique to practical scheduling when passages have tolerances for departure times are discussed. [ABSTRACT FROM AUTHOR]