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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 73 citations exist upstream.