Original Advances in Column Generation Methods for Integrated Crew and Vehicle Scheduling in Nigerian Mass Transit Systems

Integrated crew and vehicle scheduling in urban mass transit represents one of the most computationally challenging classes of combinatorial optimization problems in operations research, and its solution for the large, operationally complex transit systems emerging in Nigerian cities such as Lagos, Kano, and Abuja has received virtually no attention in the academic literature. This dissertation develops original advances in column generation methods for integrated crew and vehicle scheduling in Nigerian mass transit systems, making algorithmic and theoretical contributions of broad applicability. A formal integer programming formulation of the integrated crew and vehicle scheduling problem tailored to the operational characteristics of Nigerian Bus Rapid Transit and conventional bus transit systems is developed, incorporating driver rest regulations, vehicle depot constraints, multi-depot operations, and the non-standard break patterns characteristic of Nigerian urban transit schedules. Original algorithmic contributions include: a novel bi-level column generation scheme that coordinates vehicle and crew subproblems through an original arc-price communication mechanism; a dynamic constraint aggregation technique that reduces degeneracy in the master problem; and a primal recovery heuristic based on diving with reduced costs that reliably generates high-quality integer solutions. Theoretical convergence results for the bi-level column generation procedure are established under mild assumptions. Computational experiments on instances derived from the Lagos Bus Rapid Transit operational data demonstrate solution of instances with 280 vehicles and 850 crew members within three hours, generating schedules 11 percent less costly than separately optimized vehicle and crew schedules. The framework is directly applicable to transit planning authorities across Nigeria. Keywords: column generation, crew scheduling, vehicle scheduling, mass transit, Lagos