Vehicle and crew scheduling for urban bus lines

A solution to the urban transportation problem is given by vehicle and crew schedules. These schedules must meet the passenger demand and satisfy technical and contractual restrictions stemming from the daily operation of the lines, while optimizing some measure of operational cost. This work describes a computational tool developed to solve the urban transportation problem in the large metropolitan area of São Paulo, Brazil. The techniques used are based on integer programming models coupled with heuristics. The former produces good feasible solutions, and the latter improves the quality of the final solutions. While the operational and labor restrictions are specific to the city of São Paulo, the same ideas can inspire similar approaches for solving the urban transportation problem arising in other metropolitan areas.