Learning Heuristics for Transit Network Design and Improvement with Deep Reinforcement Learning
This work addresses the optimization of transit networks for urban planners, offering significant improvements over existing methods, though it is incremental in applying learned heuristics to a known problem.
The paper tackled the problem of designing public transit networks by replacing random heuristics with learned ones using deep reinforcement learning and graph neural networks, achieving new state-of-the-art results on the Mumford benchmark and up to 19% cost savings on a real network in Laval, Canada.
Planning a network of public transit routes is a challenging optimization problem. Metaheuristic algorithms search through the space of possible transit networks by applying heuristics that randomly alter routes in a network. Existing algorithms almost exclusively use heuristics that modify the network in purely random ways. In this work, we explore whether we can obtain better transit networks using more intelligent heuristics, that modify networks according to a learned preference function instead of at random. We use reinforcement learning to train graph neural nets to act as heuristics. These neural heuristics yield improved results on benchmark synthetic cities with 70 nodes or more, and achieve new state-of-the-art results on the challenging Mumford benchmark. They also improve upon a simulation of the real transit network in the city of Laval, Canada, achieving cost savings of up to 19% over the city's existing transit network.