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

2023/05/18 by Holliday, Andrew, Dudek, Gregory
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Neural and Evolutionary Computing (cs.NE)

paper · doi:10.48550/arxiv.2306.00720

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.

Related

• A Neural-Evolutionary Algorithm for Autonomous Transit Network Design
• Applications of deep reinforcement learning to urban transit network design
• Learning Heuristics for Transit Network Design and Improvement with Deep Reinforcement Learning
• Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives
• Neural Combinatorial Optimization with Reinforcement Learning