Minimum Cost Schedules for a Public Transportation Route—I. Theory

A fleet of vehicles carries passengers in one direction on a public transit route, then returns empty to the dispatch point after a round trip travel time T. The arrival rate of passengers is a known, deterministic, continuous, function of time and the objective is to devise a schedule that minimizes the total cost for passenger waiting time and vehicle operation. It is shown that the optimal dispatch rate at any time t is either equal to the arrival rate at t + kT where k is some integer (not necessarily positive) or proportional to the square root of the average of the passenger arrival rates at t − mT, t − (m − 1)T, …, t, …, t + nT where m and n are nonnegative integers (sometimes both zero). Furthermore, the optimal dispatch rate, expressed as a function of time, can be discontinuous only at t_q + jT and at t_d, where t_q is a time when a queue of waiting passengers forms, t_d is a time when a queue disappears, and j is an integer.