Neural Bee Colony Optimization: A Case Study in Public Transit Network Design

Andrew Holliday, Gregory DudekarXiv 2023 · DOI · arXiv

Abstract

Designing efficient public transit networks is a computationally intensive task known as the Transit Network Design Problem (NDP). Traditional metaheuristics often struggle with the vast search space of NDP because their exploration moves are largely stochastic and "blind" to underlying spatial demand patterns. This paper explores Neural Bee Colony Optimization (NBCO), a hybrid framework that integrates Graph Neural Networks (GNNs) with the Bee Colony Optimization (BCO) metaheuristic. By replacing random search moves with a learned neural policy, NBCO achieves significant performance gains, outperforming traditional BCO by up to 53% on standard benchmarks. Our results demonstrate that combining the intuitive pattern recognition of deep learning with the global search capabilities of swarm intelligence provides a robust solution for complex urban infrastructure challenges.

Introduction

The Transit Network Design Problem (NDP) is a cornerstone of urban planning. It involves determining a set of bus routes and frequencies that satisfy a city's "many-to-many" demand matrix—where thousands of passengers travel between diverse origins and destinations, often requiring transfers. The objective is to minimize two competing costs: passenger cost (travel, waiting, and transfer times) and operator cost (total route length and fleet requirements).

Because NDP is NP-complete and significantly more complex than the Traveling Salesman Problem (TSP), exact solutions are computationally infeasible for real-world cities. Researchers typically rely on metaheuristics—high-level search strategies like Genetic Algorithms or Bee Colony Optimization. However, these methods often utilize semi-random "moves" to explore the solution space, which may fail to account for the specific geometric and demand-driven nuances of a transit network.

Methodology: The NBCO Framework

Neural Bee Colony Optimization (NBCO) addresses the limitations of traditional search by introducing a learned component into the optimization loop. The architecture consists of two primary modules:

1. The Learned Planner (GNN)

The authors developed a Graph Neural Network (specifically a Graph Attention Network) trained via Reinforcement Learning (REINFORCE). This model is trained to build transit routes incrementally, considering both the physical geometry of the city and the specific passenger demand between nodes. While this GNN can act as a "single-shot" solver to generate networks rapidly, it often hits a performance ceiling when used in isolation.

2. The Metaheuristic Wrapper (BCO)

BCO is inspired by the foraging behavior of honeybees. In a standard BCO setup, "worker bees" explore the solution space by making small, random modifications to existing routes (e.g., swapping a stop), while "recruiter bees" share successful solutions with the rest of the colony.

The Hybrid Innovation: Neural Bees

The core innovation of NBCO is the introduction of "Neural Bees." Instead of performing a random tweak, a Neural Bee utilizes the trained GNN to completely redesign a specific route within the network. This allows the algorithm to take "smarter," more substantial steps through the search space, guided by a policy that understands transit logic rather than mere randomness.

Experimental Setup

To evaluate the efficacy of NBCO, the GNN was first trained on a massive dataset of 32,768 procedurally generated synthetic cities (20 nodes each) featuring various layouts, such as grids and Voronoi diagrams. The hybrid system was then benchmarked against classic NDP datasets:

  • Mandl’s Network: A 15-node synthetic city used as a standard baseline in transit research.
  • Mumford’s Datasets (0-3): Larger, more complex benchmarks ranging from 30 to 127 nodes, designed to simulate the scale of real-world urban environments.

Results and Discussion

The experiments revealed several key insights into the synergy between deep learning and metaheuristics:

  • Superior Scaling: On the largest benchmark (Mumford3, 127 nodes), NBCO outperformed the original BCO algorithm by 33% to 53%, depending on the weighting of passenger versus operator costs. This suggests that the "neural" moves become increasingly valuable as the problem scale grows.
  • Overcoming the Policy Ceiling: While the GNN policy is a powerful heuristic, it is not exhaustive. NBCO outperformed the standalone GNN policy by up to 20%. This proves that the metaheuristic wrapper provides essential global search capabilities that the GNN lacks on its own.
  • Efficient Trade-offs: NBCO successfully identified a superior "Pareto front"—the set of optimal trade-offs between passenger convenience and operator budget. It found more efficient solutions across the entire spectrum of cost distributions than either the GNN or BCO could achieve independently.
  • Complementary Search: The study found that a heterogeneous colony—mixing "Neural Bees" with traditional bees that perform small local tweaks—performed better than a colony of only Neural Bees. This suggests that while neural moves provide high-level intuition, traditional local search is still necessary for fine-tuning solutions.

Conclusion and Future Work

Neural Bee Colony Optimization represents a significant step forward in applying machine learning to infrastructure design. By embedding a learned policy within a swarm intelligence framework, the researchers created a system that is both intuitive and persistent.

Future research will focus on bridging the "synthetic gap" by testing NBCO on massive, real-world datasets from major metropolitan areas. Additionally, there is potential in "end-to-end" training, where the GNN is trained specifically to function as a sub-component of the metaheuristic, potentially leading to even more specialized and efficient search behaviors. Finally, the success of this hybrid approach suggests it could be generalized to other metaheuristics, such as Simulated Annealing or Ant Colony Optimization, across various domains of combinatorial optimization.

Summary updated

Abstract

In this work we explore the combination of metaheuristics and learned neural network solvers for combinatorial optimization. We do this in the context of the transit network design problem, a uniquely challenging combinatorial optimization problem with real-world importance. We train a neural network policy to perform single-shot planning of individual transit routes, and then incorporate it as one of several sub-heuristics in a modified Bee Colony Optimization (BCO) metaheuristic algorithm. Our experimental results demonstrate that this hybrid algorithm outperforms the learned policy alone by up to 20% and the original BCO algorithm by up to 53% on realistic problem instances. We perform a set of ablations to study the impact of each component of the modified algorithm.
BibTeX
@misc{holliday2023neural,
  author = {Andrew Holliday and Gregory Dudek},
  title = {{Neural Bee Colony Optimization: A Case Study in Public Transit Network Design}},
  year = {2023},
  eprint = {2306.00720},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.00720},
}

Loading related content...

Figure