Deficit Function Bus Scheduling with Deadheading Trip Insertions for Fleet Size Reduction

This paper begins with a brief review of the operational aspects of bus scheduling at Egged (The Israel National Bus Carrier), and their experience with an optimal bus scheduling algorithm. Due to the limitations of this algorithm, Egged Management has decided it is still not justified to replace the manually and currently used planning procedures (comprised of 60 schedulers using Gantt charts). Consequently, an approximate procedure incorporating a man/computer interface was requested which would allow the inclusion of practical considerations that experienced schedulers may wish to introduce in the schedule. Due to its visual nature, the deficit function was selected as a natural tool to form the basis of such a man-machine interactive scheduling procedure. A deficit function defines the net number of departures required at each terminal up to and including time t . According to the well-known fleet size formula, the minimum number of vehicles required to service a multiterminal fixed schedule of trips is equal to the sum of the maximal deficits at all terminals. As deficit function theory stops at a fixed schedule of trips, it was necessary to develop procedures to (1) primarily determine when and where to insert deadheading trips, and (2) secondarily include such considerations as garage limitations, inclusion of refueling trips, and driver limitations. The final algorithm is capable of generating schedules automatically in a purely computer mode. In an interactive mode it allows the user to select one of several computer suggested improvements or to interject his own suggestions and immediately see the effects on the final schedule through observation of the deficit functions on a CRT or computer generated output.