Multiple depot transit vehicle scheduling problem with time restriction constraints

This research presents an innovative formulation for the "Multiple Depot Vehicle Scheduling" (MDVS) problem. Compared to previous formulations, that decreases the size of the problem significantly without eliminating any feasible solution (it decreases the number of variables by about 40%). A new formulation of the problem considering the "Time Restriction Constraints" (TRCs) is also presented. These constraints are added to the problem considering real world operational restrictions, such as fuel consumption restrictions.; CPLEX software is used as the optimization code in this research. The MDVS problem, is dealt with by relaxing the integrality constraints, and solving the resulting linear program. If the solution is non-integer, the list of the non-integer variables is added to the problem and the problem is solved in Mixed Integer Programming module. For solving the "Multiple Depot Vehicle Scheduling with Time Restriction Constraints" (MDVSTRC) problem an "Exact Solution Procedure" is proposed. This procedure is a constraint generation approach. Several heuristic approaches are also proposed for solving the MDVSTRC problem. The characteristics of a real world problem, the operation problem of the MTA of Baltimore City, are studied and a simulation code is developed to generate test problems based on these characteristics. All of the approaches are tested on test problems, and the results are discussed and compared.; Three techniques are established for decreasing the size of the real world problems into manageable and solvable size. Three strategies are developed based on different possible uses of the "reduction techniques", and "heuristic solution procedures", as tools. A study is conducted on the MTA operation problem that is modeled using the proposed formulation. In this case study the problem of the weekday schedule of the MTA is developed based on 5650 daily trips. The model is quite applicable to real world problems. The results are compared to the MTA schedule in January 1998. The comparison indicates that the proposed model improves upon the MTA schedules in all aspects, i.e., 8.1% in the number of vehicles, 3.8% in the operational time, and 5.25% in the total cost.