On a rapid calculation of a certain enumeration problem encountered in a public transportation network

Abstract

The article suggests a rapid solution to the apparently simple problem of finding the minimal number of buses that are required to keep up a two way line with prescribed departure and travel times. The buses are assumed to go back and forth and are operated under the convention "the first to arrive at a terminal is the first to leave". The problem dealt with is the most general in the sense that no restrictions are imposed upon either the departure or travel times. The proposed solution has two basic features, namely, it is a functional one and it can be rapidly computed. The distinctiveness of the functional solution, as distinguished from the algorithmic one, is that it can serve as a constraint in a mathematical program where the departure times of buses are taken as control variables. The rapidness is essential when the solution has to be obtained many times as in a dynamic programming optimization procedure with control variables as mentioned above. © 1975.