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

• URL: http://arxiv.org/abs/2404.05894v5
• Date: Wed, 21 May 2025 15:44:53 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 to train a graph net to provide neurals for an evolutionary algorithm.<n>These neurals improve the algorithm's results on benchmark synthetic cities with 70 nodes or more, and achieve state new-of-the-art results on the challenging Mumford benchmark.<n>They also improve upon a simulation of the real transit network in the city of Laval, Canada, by 52% and 25% on two key metrics, and offer cost savings of up to 19% over the city's existing transit network.
• Score: 7.660968783738993
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. The design of these heuristics has a major impact on the quality of the result. In this paper, we use deep reinforcement learning to train a graph neural net to provide heuristics for an evolutionary algorithm. These neural heuristics improve the algorithm's 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, by 52% and 25% on two key metrics, and offer cost savings of up to 19% over the city's existing transit network.

Related papers

• Network Sparsity Unlocks the Scaling Potential of Deep Reinforcement Learning [57.3885832382455]
  We show that introducing static network sparsity alone can unlock further scaling potential beyond dense counterparts with state-of-the-art architectures.<n>Our analysis reveals that, in contrast to naively scaling up dense DRL networks, such sparse networks achieve both higher parameter efficiency for network expressivity.
  arXiv  Detail & Related papers  (2025-06-20T17:54:24Z)
• 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)
• Deep Heuristic Learning for Real-Time Urban Pathfinding [0.0]
  This paper introduces a novel approach to urban pathfinding by transforming traditional algorithms into deep learning models that leverage real-time contextual data, such as traffic and weather conditions. We propose two methods: an enhanced A* algorithm that dynamically adjusts routes based on current environmental conditions, and a neural network model that predicts the next optimal path segment using historical and live data.
  arXiv  Detail & Related papers  (2024-11-07T00:22:04Z)
• 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)
• 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)
• 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)
• Binary Neural Networks: A Survey [126.67799882857656]
  The binary neural network serves as a promising technique for deploying deep models on resource-limited devices. The binarization inevitably causes severe information loss, and even worse, its discontinuity brings difficulty to the optimization of the deep network. We present a survey of these algorithms, mainly categorized into the native solutions directly conducting binarization, and the optimized ones using techniques like minimizing the quantization error, improving the network loss function, and reducing the gradient error.
  arXiv  Detail & Related papers  (2020-03-31T16:47:20Z)
• 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.