Constructing an Optimal Fleet for a Transportation Schedule

A schedule is a set of passages; a passage 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 p₁, p₂, … having the property p_n2 = p_n+11 and p_n4 ≤ p_n+13. 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 occurring at a during the interval [0, t]. It is proved that the fleet-aim is equal to ∑_amax_t≥0d(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 be decomposed into an optimal periodic fleet. Applications of the deficit function technique to practical scheduling when passages have tolerances for departure times are discussed.