Constructing an Optimal Fleet for a Transportation Schedule

Abstract

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 1 , p 2 , … having the property p n 2 = p n+1 1 and p n 4 ≤ p n+1 3. 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 ∑ a max t≥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 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.