  Transit agencies world-wide face tightening budgets. To maintain quality of
service while cutting costs, efficient transit network design is essential. But
planning a network of public transit routes is a challenging optimization
problem. The most successful approaches to date use metaheuristic algorithms to
search through the space of possible transit networks by applying low-level
heuristics that randomly alter routes in a network. The design of these
low-level heuristics has a major impact on the quality of the result. In this
paper we use deep reinforcement learning with graph neural nets to learn
low-level heuristics for an evolutionary algorithm, instead of designing them
manually. These learned heuristics improve the algorithm's results on benchmark
synthetic cities with 70 nodes or more, and obtain state-of-the-art results
when optimizing operating costs. They also improve upon a simulation of the
real transit network in the city of Laval, Canada, by as much as 54% and 18% on
two key metrics, and offer cost savings of up to 12% over the city's existing
transit network.
