Bus schedule optimization
Operations research (OR) and transportation
In the field of transportation and logistics, route/schedule planning is critical to guarantee a service’s reliability while keeping operating costs down. Whether it’s to transport goods, send mail, provide public transit or maintain roads, companies must determine the best route for dozens or hundreds of vehicles (trucks, cars, buses, trains, planes, etc.). Operations research contributes tools to help decision-makers plan these routes at the lowest cost, while taking into account the company’s operational constraints.
OR and public transit
Bus companies, for instance, must solve problems like these: What schedule should each bus line follow? How many vehicles are needed so that all trips are covered? Which driver should do what trip? To answer such questions, the company must follow a number of rules, such as maintaining a regular frequency of trips on a given line, giving drivers regular breaks and minimizing the number of “empty” trips. These conditions make the problem highly complex, especially when thousands of bus trips per day are involved.
Challenges in OR
Operations research has made it possible to develop efficient algorithms that are now being used by transportation companies the world over. But many areas for improvement are currently being explored:
- Better tailoring of trips to meet users’ needs: For instance by collecting data to understand more precisely what the desired trips are
- Improving schedule reliability: By better taking into account the variability of travel times
- Improving network flexibility: By quickly re-optimizing a solution when an incident occurs (mechanical failure, unusual traffic slow-down, etc.)
- Decreasing costs: For instance by incorporating trip timetabling and bus scheduling into a single problem
Some technical details
Planning bus schedules can be modeled with a connection graph: A node represents a trip that’s required. We add an arc between Nodes 1 and 2 if a vehicle can execute Trip 1 followed immediately by Trip 2. Thus, a path in this graph gives a feasible sequence of trips for a given vehicle. We must then choose, among all these possible paths, an option that minimizes costs and covers all the requested trips. To do this, we use integer programming and, more specifically, a column generation algorithm.