Efficient Duty Scheduling: Technical Report on Dynamic Network Column Generation

Abstract

Efficient crew scheduling is essential for cost-effective and reliable public transportation operations. This paper presents a mathematical model for an extensive duty network and introduces an advanced scheduling approach that integrates column generation and dynamic network generation to iteratively construct and refine duty schedules. The column generation method is used to compute an upper bound and generate an initial duty schedule, while dynamic network generation iteratively improves the schedule, ensuring feasibility and enabling cost reductions. The proposed approach balances computational efficiency with solution quality, allowing for early termination with near-optimal results.

Both the extensive and dynamic approaches face challenges in computing optimal solutions within a practical runtime. The extensive duty network model benefits significantly from preprocessing, which reduces the complexity of the problem and improves solvability. However, its applicability remains limited for medium to large-scale instances. The dynamic network generation approach, in contrast, efficiently computes high-quality duty schedules in comparably short computational time. It can be used flexibly—either to generate initial feasible solutions, refine existing schedules, or continue iterating until optimality is proven if required.

Despite the challenges in proving optimality, the structured nature of the dynamic network generation approach makes it highly promising for integration with other planning steps, such as timetabling and vehicle scheduling. Future research should further evaluate the integration of dynamic network generation into broader transportation planning frameworks and explore enhancements to improve convergence speed. Overall, while not necessarily the most efficient standalone method for optimizing crew schedules, the dynamic network generation approach offers a powerful and flexible tool for integrated public transportation planning, enabling both efficiency gains and operational adaptability.