# Learning Heuristics for Transit Network Design and Improvement with Deep Reinforcement Learning

arXiv: https://arxiv.org/abs/2404.05894 · HTML: https://mlsanity.com/paper/2404.05894/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL for autonomous driving and traffic, one of 15 directions in Deep reinforcement learning methods.
- Builds on 29 of its 96 references that are in the map.
- First posted on arXiv 8 Apr 2024.

## Placed in

- Deep reinforcement learning methods / [RL for autonomous driving and traffic](https://mlsanity.com/deeprl/rl-for-autonomous-driving-and-traffic/)

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Symbolic Regression via Neural-Guided Genetic Programming Population Seeding](https://mlsanity.com/paper/2111.00053/) (2021)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [Multi-Agent Routing Value Iteration Network](https://mlsanity.com/paper/2007.05096/) (2020)
- [A History of Metaheuristics](https://mlsanity.com/paper/1704.00853/) (2017)
- [Deep Reinforcement Learning based Dynamic Optimization of Bus Timetable](https://mlsanity.com/paper/2107.07066/) (2021)
- [A Bibliometric Analysis and Review on Reinforcement Learning for Transportation Applications](https://mlsanity.com/paper/2210.14524/) (2022)

## Built on by (most cited first, 3 of 3)

- [Learning to Design City-scale Transit Routes](https://mlsanity.com/paper/2512.19767/) (2025)
- [AlphaTransit: Learning to Design City-scale Transit Routes](https://mlsanity.com/paper/2605.28730/) (2026)
- [AGORA: Can Deliberation and Governance Gates Absorb Participation Bias in Transit Planning?](https://mlsanity.com/paper/2606.13696/) (2026)

## Abstract (arXiv)

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.