Planning Operations in Public Transport
All large cities have a public transport network that comprises, among others, a bus service. This infrastructure offers to the population the possibility to travel between the various neighbourhoods of the city in an economical and environmentally friendly fashion. Public transport companies are to a large extent subsidized by governments and must therefore offer good-quality service while avoiding excessive operating costs. Consequently, they rely on decision-making software to optimize operational planning.
Given that task complexity (for example, the Société de transport de Montréal offers more than 17,000 bus trips per day, distributed among 225 bus routes), planning for a bus network is typically done by steps. Network planning includes development of: i) bus routes; ii) trip schedules for each route; iii) bus schedules indicating the sequence of trips to perform for each bus; iv) daily work schedules specifying the sequences of trips an anonymous driver must cover; and v) drivers' schedules assigning work duties and days off to each driver for the next month. The problems in steps i) and ii) are at the strategic/tactical level and relate to maximizing the quality of service while respecting some global constraints on resource availability. On the other hand, the problems in steps iii) to v) are operational ones that relate to offering at least cost the service established in the previous steps while taking into account numerous practical constraints such as those stemming from the drivers' collective agreement.
For several decades now, GERAD's researchers have realized research projects on the operational problems of steps iii) to v). Most of these works have been conducted in collaboration with GIRO company, which is the world leader in the commercialization of optimization software for public transport. To solve the driver duty scheduling problem, François Soumis and Jacques Desrosiers have developed at the end of the 1980s, a column generation algorithm, called Gencol, that allows to select the best set of work duties to perform among a huge number of possible duties without having to enumerate them all. This algorithm, which is still in use at GIRO, has been enhanced over the years with new advancements made at the GERAD, namely, the dynamic constraint aggregation technique designed by Issmail El Hallaoui, François Soumis and Guy Desaulniers. More recently, GIRO has decided to also apply column generation for solving the bus scheduling problem in order to handle the recharging constraints of the electric buses. In this regard, a new collaboration with Guy Desaulniers has permitted to study different variants of this problem, including that considering the possibility to slighlty shift the trip start times. Finally, Guy Desaulniers, Andrea Lodi and François Soumis are teaming up to integrate statistical and machine learning methods in the optimization algorithms for public transit.