A Matching Based Heuristic for Scheduling Mass Transit Crews and Vehicles

In this paper, we describe a computerized procedure for scheduling mass transit crews and vehicles. The procedure differs from previous methods in that rather than first scheduling vehicles and then crews, it schedules vehicles and crews simultaneously. Several of the subproblems are solved as matching problems on graphs. A computational test of this procedure using a database from the Baltimore Metropolitan Transit Authority has produced solutions of lower cost than those used by the transit authority.