Abstract
Transit agencies world-wide face tightening budgets. To maintain quality ofservice while cutting costs, efficient transit network design is essential. Butplanning a network of public transit routes is a challenging optimizationproblem. The most successful approaches to date use metaheuristic algorithms tosearch through the space of possible transit networks by applying low-levelheuristics that randomly alter routes in a network. The design of theselow-level heuristics has a major impact on the quality of the result. In thispaper we use deep reinforcement learning with graph neural nets to learnlow-level heuristics for an evolutionary algorithm, instead of designing themmanually. These learned heuristics improve the algorithm's results on benchmarksynthetic cities with 70 nodes or more, and obtain state-of-the-art resultswhen optimizing operating costs. They also improve upon a simulation of thereal transit network in the city of Laval, Canada, by as much as 54% and 18% ontwo key metrics, and offer cost savings of up to 12% over the city's existingtransit network.