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

• URL: http://arxiv.org/abs/2404.05894v4
• Date: Sat, 22 Feb 2025 15:55:18 GMT
• Title: Learning Heuristics for Transit Network Design and Improvement with Deep Reinforcement Learning
• Authors: Andrew Holliday, Ahmed El-Geneidy, Gregory Dudek,
• Abstract summary: We use deep reinforcement learning with graph neural nets to learn low-levels for an evolutionary algorithm.<n>These learneds improve the algorithm's results on benchmark synthetic cities with 70 nodes or more, and achieve new state-of-the-art results.<n>They also improve upon a simulation of the real transit network in the city of Laval, Canada, by as much as 52% and 25% on two key metrics.
• Score: 7.660968783738993
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transit agencies world-wide face tightening budgets and declining ridership. To maintain quality of service while cutting costs, efficient transit network design is essential. But planning a network of public transit routes is a challenging optimization problem. The most successful approaches to date use metaheuristic algorithms to search through the space of possible transit networks by applying low-level heuristics that randomly alter routes in a network. The design of these low-level heuristics has a major impact on the quality of the result. In this paper we use deep reinforcement learning with graph neural nets to learn low-level heuristics for an evolutionary algorithm, instead of designing them manually. These learned heuristics improve the algorithm's results on benchmark synthetic cities with 70 nodes or more, and achieve new state-of-the-art results the challenging Mumford benchmark. They also improve upon a simulation of the real transit network in the city of Laval, Canada, by as much as 52% and 25% on two key metrics, and offer cost savings of up to 19% over the city's existing transit network.

Related papers

• 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)
• Advanced Artificial Intelligence Strategy for Optimizing Urban Rail Network Design using Nature-Inspired Algorithms [0.0]
  This study introduces an innovative methodology for the planning of metro network routes within the urban environment of Chennai, Tamil Nadu, India. A comparative analysis of the modified Ant Colony Optimization (ACO) method with recent breakthroughs in nature-inspired algorithms demonstrates the modified ACO's superiority over modern techniques.
  arXiv  Detail & Related papers  (2024-07-04T17:57:39Z)
• 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 Neural-Evolutionary Algorithm for Autonomous Transit Network Design [8.610161169928796]
  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.
  arXiv  Detail & Related papers  (2024-02-27T15:59:15Z)
• Solving Large-scale Spatial Problems with Convolutional Neural Networks [88.31876586547848]
  We employ transfer learning to improve training efficiency for large-scale spatial problems. We propose that a convolutional neural network (CNN) can be trained on small windows of signals, but evaluated on arbitrarily large signals with little to no performance degradation.
  arXiv  Detail & Related papers  (2023-06-14T01:24:42Z)
• A sequential transit network design algorithm with optimal learning under correlated beliefs [4.8951183832371]
  This study proposes an artificial intelligence-driven algorithm that combines sequential transit network design with optimal learning to address the operation under limited data. An operator gradually expands its route system to avoid risks from inconsistency between designed routes and actual travel demand. For validation, a new route system is designed on an artificial network based on public use microdata areas in New York City.
  arXiv  Detail & Related papers  (2023-05-16T14:14:51Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• HARL: Hierarchical Adaptive Reinforcement Learning Based Auto Scheduler for Neural Networks [51.71682428015139]
  We propose HARL, a reinforcement learning-based auto-scheduler for efficient tensor program exploration. HarL improves the tensor operator performance by 22% and the search speed by 4.3x compared to the state-of-the-art auto-scheduler. Inference performance and search speed are also significantly improved on end-to-end neural networks.
  arXiv  Detail & Related papers  (2022-11-21T04:15:27Z)
• Optimal service station design for traffic mitigation via genetic algorithm and neural network [3.7597202216941783]
  We focus on the problem of optimally designing a service station to achieve beneficial effects in terms of total traffic congestion and peak traffic reduction. We propose a genetic algorithm based on the recently proposed CTMs, that efficiently describes the dynamics of a service station. We leverage the algorithm to train a neural network capable of solving the same problem, avoiding implementing the CTMs.
  arXiv  Detail & Related papers  (2022-11-18T11:11:07Z)
• Accelerating Deep Reinforcement Learning for Digital Twin Network Optimization with Evolutionary Strategies [0.0]
  The community proposed the Digital Twin Networks (DTN) as a key enabler of efficient network management. Deep Reinforcement Learning (DRL) showed a high performance when applied to solve network optimization problems. In this paper, we explore the use of Evolutionary Strategies (ES) to train DRL agents for solving a routing optimization problem.
  arXiv  Detail & Related papers  (2022-02-01T11:56:55Z)
• Optimal transport in multilayer networks [68.8204255655161]
  We propose a model where optimal flows on different layers contribute differently to the total cost to be minimized. As an application, we consider transportation networks, where each layer is associated to a different transportation system. We show an example of this result on the real 2-layer network of the city of Bordeaux with bus and tram, where in certain regimes the presence of the tram network significantly unburdens the traffic on the road network.
  arXiv  Detail & Related papers  (2021-06-14T07:33:09Z)
• A Deep Value-network Based Approach for Multi-Driver Order Dispatching [55.36656442934531]
  We propose a deep reinforcement learning based solution for order dispatching. We conduct large scale online A/B tests on DiDi's ride-dispatching platform. Results show that CVNet consistently outperforms other recently proposed dispatching methods.
  arXiv  Detail & Related papers  (2021-06-08T16:27:04Z)
• Cream of the Crop: Distilling Prioritized Paths For One-Shot Neural Architecture Search [60.965024145243596]
  One-shot weight sharing methods have recently drawn great attention in neural architecture search due to high efficiency and competitive performance. To alleviate this problem, we present a simple yet effective architecture distillation method. We introduce the concept of prioritized path, which refers to the architecture candidates exhibiting superior performance during training. Since the prioritized paths are changed on the fly depending on their performance and complexity, the final obtained paths are the cream of the crop.
  arXiv  Detail & Related papers  (2020-10-29T17:55:05Z)
• Decentralized Optimization of Vehicle Route Planning -- A Cross-City Comparative Study [7.74034002629298]
  We conduct a study to compare different levels of agent altruism and the resulting effect on the network-level traffic performance. The main finding is that, with increased vehicle altruism, it is possible to balance traffic flow among the links of the network.
  arXiv  Detail & Related papers  (2020-01-10T11:02:51Z)

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.