Optimizing Bus Driver Scheduling: A Set Covering Approach for Reducing Transportation Costs

Cutting operational costs is a critical component for transportation agencies. To reduce these costs, agencies must optimize their scheduling. Typically, the total operating costs of transport include vehicle expenses and driver wages. Solving such tasks is complex, and optimal planning is usually broken down into multiple stages. These stages can include vehicle scheduling, driver shift planning, and driver assignment. This paper focuses specifically on developing a near-optimal driver schedule for a specified set of vehicle schedules. It shows how to efficiently assign drivers to predetermined optimal vehicle routes while ensuring compliance with regulatory constraints on driving hours. We address this challenge using a mathematical model based on the set covering problem, building on a framework established perviously. The set covering problem is typically formulated as an integer programming problem, solvable through column generation techniques. Our algorithm combines this method with heuristics, taking into account the practical aspects of the problem. The article also presents a computational analysis of the method using benchmark and real data.