Timetable Nodes for Public Transport Network

• URL: http://arxiv.org/abs/2410.15715v2
• Date: Wed, 23 Oct 2024 05:02:39 GMT
• Title: Timetable Nodes for Public Transport Network
• Abstract summary: Faster pathfinding in time-dependent transport networks is an important and challenging problem in navigation systems. We propose a method that advances graph-based approaches by using different optimization techniques from computational geometry. Our solution suits any other time-dependent networks and can be integrated into other pathfinding algorithms.
• Score: 31.793066412010468
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Faster pathfinding in time-dependent transport networks is an important and challenging problem in navigation systems. There are two main types of transport networks: road networks for car driving and public transport route network. The solutions that work well in road networks, such as Time-dependent Contraction Hierarchies and other graph-based approaches, do not usually apply in transport networks. In transport networks, non-graph solutions such as CSA and RAPTOR show the best results compared to graph-based techniques. In our work, we propose a method that advances graph-based approaches by using different optimization techniques from computational geometry to speed up the search process in transport networks. We apply a new pre-computation step, which we call timetable nodes (TTN). Our inspiration comes from an iterative search problem in computational geometry. We implement two versions of the TTN: one uses a Combined Search Tree (TTN-CST), and the second uses Fractional Cascading (TTN-FC). Both of these approaches decrease the asymptotic complexity of reaching new nodes from $O(k\times \log|C|)$ to $O(k + \log(k) + \log(|C|))$, where $k$ is the number of outgoing edges from a node and $|C|$ is the size of the timetable information (total outgoing edges). Our solution suits any other time-dependent networks and can be integrated into other pathfinding algorithms. Our experiments indicate that this pre-computation significantly enhances the performance on high-density graphs. This study showcases how leveraging computational geometry can enhance pathfinding in transport networks, enabling faster pathfinding in scenarios involving large numbers of outgoing edges.

Related papers

• AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network [50.69521065962045]
  We present the Anisotropic Graph Diffusion Network (AGDN), a new Graph Neural Network framework designed to solve the Traveling Salesman Problem (TSP)<n>Our method tackles two central difficulties: (1) the lack of informative topological prior in fully connected TSP graphs, and (2) losing connected nodes in the optimal solution after the commonly used graph sparsification techniques.<n>AGDN consistently outperforms existing methods while keeping time competitive.
  arXiv  Detail & Related papers  (2026-06-17T15:24:37Z)
• Routing in Non-Isotonic Quantum Networks [0.0]
  Optimal routing in quantum-repeater networks requires finding the best path that connects a pair of end nodes.<n>We show that utility functions that take into account both the rate and quality of the entanglement generation are often non-isotonic.<n>We present two best-first-search algorithms that use destination-aware merit functions for faster convergence.
  arXiv  Detail & Related papers  (2025-11-25T18:48:49Z)
• Knowledge-Guided Machine Learning for Stabilizing Near-Shortest Path Routing [3.595536209220219]
  We propose a simple algorithm that needs only a few data samples from a single graph for learning local routing policies.<n>We learn a new policy, which we call GreedyTensile routing, that almost always outperforms greedy forwarding.<n>We demonstrate the explainability and ultra-low latency run-time operation of Greedy Tensile routing.
  arXiv  Detail & Related papers  (2025-09-08T12:56:42Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Learning Graph Search Heuristics [48.83557172525969]
  We present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigations from data. Our function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5% on average.
  arXiv  Detail & Related papers  (2022-12-07T22:28:00Z)
• Universal Neural Optimal Transport [0.0]
  UNOT (Universal Neural Optimal Transport) is a novel framework capable of accurately predicting (entropic) OT distances and plans between discrete measures for a given cost function.<n>We show that our network can be used as a state-of-the-art initialization for the Sinkhorn algorithm with speedups of up to $7.4times$.
  arXiv  Detail & Related papers  (2022-11-30T21:56:09Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• RNGDet++: Road Network Graph Detection by Transformer with Instance Segmentation and Multi-scale Features Enhancement [19.263691277963368]
  The graph structure of road networks is critical for downstream tasks of autonomous driving systems, such as global planning, motion prediction and control. In the past, the road network graph is usually manually annotated by human experts, which is time-consuming and labor-intensive. Previous works either post-process semantic segmentation maps or propose graph-based algorithms to directly predict the road network graph. Previous works suffer from hard-coded processing algorithms and inferior final performance. Since the new proposed approach is improved from RNGDet, it is named RNGDet++.
  arXiv  Detail & Related papers  (2022-09-21T07:06:46Z)
• tBDFS: Temporal Graph Neural Network Leveraging DFS [33.762062743040495]
  We propose tBDFS -- a novel temporal GNN architecture. tBDFS applies a layer that efficiently aggregates information from temporal paths to a given (target) node in the graph. Overall, our goal is not to add new information to a node, but rather observe the same exact information in a new perspective.
  arXiv  Detail & Related papers  (2022-06-12T08:38:06Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  We propose a learnable network to approximate geodesic paths on 3D surfaces. The proposed method provides efficient approximations of the shortest paths and geodesic distances estimations.
  arXiv  Detail & Related papers  (2022-05-30T16:22:53Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  We show that network simplex and augmenting path based algorithms can consistently outperform numerical matrix-scaling based methods. We present a new algorithm that improves upon the classical Kuhn-Munkres algorithm.
  arXiv  Detail & Related papers  (2020-05-03T20:37:05Z)

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.