A Neural-Evolutionary Algorithm for Autonomous Transit Network Design

• URL: http://arxiv.org/abs/2403.07917v3
• Date: Mon, 07 Oct 2024 15:45:38 GMT
• Title: A Neural-Evolutionary Algorithm for Autonomous Transit Network Design
• Authors: Andrew Holliday, Gregory Dudek,
• Abstract summary: We use a graph neural net model as a policy for constructing route networks, and then use the policy as one of several mutation operators in a evolutionary algorithm. We evaluate this algorithm on a standard set of benchmarks for transit network design, and find that it outperforms the learned policy alone by up to 20% and a plain evolutionary algorithm approach by up to 53% on realistic benchmark instances.
• Score: 8.610161169928796
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Planning a public transit network is a challenging optimization problem, but essential in order to realize the benefits of autonomous buses. We propose a novel algorithm for planning networks of routes for autonomous buses. We first train a graph neural net model as a policy for constructing route networks, and then use the policy as one of several mutation operators in a evolutionary algorithm. We evaluate this algorithm on a standard set of benchmarks for transit network design, and find that it outperforms the learned policy alone by up to 20% and a plain evolutionary algorithm approach by up to 53% on realistic benchmark instances.

Related papers

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in Evolutionary optimization. We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms. For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Applications of deep reinforcement learning to urban transit network design [0.0]
  This thesis concerns the use of reinforcement learning to train neural networks to aid in the design of public transit networks. The Transit Network Design Problem (TNDP) is an optimization problem of considerable practical importance.
  arXiv  Detail & Related papers  (2025-02-25T01:24:20Z)
• Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratch [72.26822499434446]
  Auto-Train-Once (ATO) is an innovative network pruning algorithm designed to automatically reduce the computational and storage costs of DNNs. We provide a comprehensive convergence analysis as well as extensive experiments, and the results show that our approach achieves state-of-the-art performance across various model architectures.
  arXiv  Detail & Related papers  (2024-03-21T02:33:37Z)
• A Deep Reinforcement Learning Approach for Adaptive Traffic Routing in Next-gen Networks [1.1586742546971471]
  Next-gen networks require automation and adaptively adjust network configuration based on traffic dynamics. Traditional techniques that decide traffic policies are usually based on hand-crafted programming optimization and algorithms. We develop a deep reinforcement learning (DRL) approach for adaptive traffic routing.
  arXiv  Detail & Related papers  (2024-02-07T01:48:29Z)
• Eco-Driving Control of Connected and Automated Vehicles using Neural Network based Rollout [0.0]
  Connected and autonomous vehicles have the potential to minimize energy consumption. Existing deterministic and methods created to solve the eco-driving problem generally suffer from high computational and memory requirements. This work proposes a hierarchical multi-horizon optimization framework implemented via a neural network.
  arXiv  Detail & Related papers  (2023-10-16T23:13:51Z)
• Neural Bee Colony Optimization: A Case Study in Public Transit Network Design [11.490474551585217]
  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.
  arXiv  Detail & Related papers  (2023-05-18T17:48:46Z)
• Multi-agent Reinforcement Learning with Graph Q-Networks for Antenna Tuning [60.94661435297309]
  The scale of mobile networks makes it challenging to optimize antenna parameters using manual intervention or hand-engineered strategies. We propose a new multi-agent reinforcement learning algorithm to optimize mobile network configurations globally. We empirically demonstrate the performance of the algorithm on an antenna tilt tuning problem and a joint tilt and power control problem in a simulated environment.
  arXiv  Detail & Related papers  (2023-01-20T17:06:34Z)
• Fast and computationally efficient generative adversarial network algorithm for unmanned aerial vehicle-based network coverage optimization [1.2853186701496802]
  The challenge of dynamic traffic demand in mobile networks is tackled by moving cells based on unmanned aerial vehicles. Considering the tremendous potential of unmanned aerial vehicles in the future, we propose a new algorithm for coverage optimization. The proposed algorithm is implemented based on a conditional generative adversarial neural network, with a unique multilayer sum-pooling loss function.
  arXiv  Detail & Related papers  (2022-03-25T12:13:21Z)
• Cooperative Behavioral Planning for Automated Driving using Graph Neural Networks [0.5801044612920815]
  This work proposes to leverage machine learning algorithms to optimize traffic flow at urban intersections by jointly planning for multiple vehicles. Learning-based behavior planning poses several challenges, demanding for a suited input and output representation as well as large amounts of ground-truth data. We train and evaluate the proposed method in an open-source simulation environment for decision making in automated driving.
  arXiv  Detail & Related papers  (2022-02-23T09:36:15Z)
• Neural Optimal Transport [82.2689844201373]
  We present a novel neural-networks-based algorithm to compute optimal transport maps and plans for strong and weak transport costs. We prove that neural networks are universal approximators of transport plans between probability distributions.
  arXiv  Detail & Related papers  (2022-01-28T16:24:13Z)
• Learning Optimal Antenna Tilt Control Policies: A Contextual Linear Bandit Approach [65.27783264330711]
  Controlling antenna tilts in cellular networks is imperative to reach an efficient trade-off between network coverage and capacity. We devise algorithms learning optimal tilt control policies from existing data. We show that they can produce optimal tilt update policy using much fewer data samples than naive or existing rule-based learning algorithms.
  arXiv  Detail & Related papers  (2022-01-06T18:24:30Z)
• Model-based Decision Making with Imagination for Autonomous Parking [50.41076449007115]
  The proposed algorithm consists of three parts: an imaginative model for anticipating results before parking, an improved rapid-exploring random tree (RRT) and a path smoothing module. Our algorithm is based on a real kinematic vehicle model; which makes it more suitable for algorithm application on real autonomous cars. In order to evaluate the algorithm's effectiveness, we have compared our algorithm with traditional RRT, within three different parking scenarios.
  arXiv  Detail & Related papers  (2021-08-25T18:24:34Z)
• Meta-Reinforcement Learning for Trajectory Design in Wireless UAV Networks [151.65541208130995]
  A drone base station (DBS) is dispatched to provide uplink connectivity to ground users whose demand is dynamic and unpredictable. In this case, the DBS's trajectory must be adaptively adjusted to satisfy the dynamic user access requests. A meta-learning algorithm is proposed in order to adapt the DBS's trajectory when it encounters novel environments.
  arXiv  Detail & Related papers  (2020-05-25T20:43:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.