Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints

This paper presents new models for multiple depot vehicle scheduling problem (MDVS) and multiple depot vehicle scheduling problem with route time constraints (MDVSRTC). The route time constraints are added to the MDVS problem to account for the real world operational restrictions such as fuel consumption. Compared to existing formulations, this formulation decreases the size of the problem by about 40% without eliminating any feasible solution. It also presents an exact and two heuristic solution procedures for solving the MDVSRTC problem. Although these methods can be used to solve medium size problems in reasonable time, real world applications in large cities require that the MDVSRTC problem size be reduced. Two techniques are proposed to decrease the size of the real world problems. For real-world application, the problem of bus transit vehicle scheduling at the mass transit administration (MTA) in Baltimore is studied. The final results of model implementation are compared to the MTA's schedules in January 1998. The comparison indicates that, the proposed model improves upon the MTA schedules in all respects. The improvements are 7.9% in the number of vehicles, 4.66% in the operational time and 5.77% in the total cost.