Stories with Tag shortest path

• Show HN: US Routing – Python library for fast local routing in the US

  permalink

  Posted: 2025-05-07 23:51:32

  Verbose tl;dr

  US Routing is a Python library designed for fast route calculations within the United States. It utilizes a pre-built graph of US roads, stored efficiently in memory, allowing for rapid queries without external dependencies or API calls. This offline capability makes it suitable for applications needing quick routing solutions, such as logistics or mapping tools, where network latency or cost is a concern. The project is open-source and available on GitHub.

  A new Python library, named "US Routing," has been introduced with a focus on providing rapid and efficient routing calculations within the United States. This library leverages pre-calculated routing data specifically optimized for the US road network, enabling significantly faster query responses compared to traditional online routing services or general-purpose routing engines. Instead of relying on external APIs or computationally intensive on-the-fly calculations, US Routing utilizes a local dataset, minimizing latency and dependencies.

  The project is open-source and hosted on GitHub, offering users the flexibility to integrate it directly into their Python applications. The core functionality revolves around providing driving routes and associated information, such as travel time and distance, between specified locations within the United States. This is achieved by leveraging a pre-built graph representation of the US road network, stored locally, allowing for rapid traversal and route computation. While the exact details of the underlying data and algorithms aren't fully elaborated in the announcement, the emphasis is on speed and efficiency for US-centric routing needs. This makes it potentially suitable for applications requiring numerous routing queries or scenarios where low latency is crucial, such as logistics, delivery optimization, or interactive mapping applications. The project aims to offer a practical alternative to relying on external routing services, particularly for applications focused specifically on the US geography.

  • Python
  • Routing
  • Library
  • US
  • USA
  • United States
  • Navigation
  • GIS
  • geographic information systems
  • Graph Algorithms
  • shortest path
  • local routing
  • fast routing
  • travel
  • maps
  • Open Source
  • Transportation
  • logistics

  Summary of Comments ( 26 )
  https://news.ycombinator.com/item?id=43921653

  Verbose tl;dr

  HN users generally praised the project for its speed, simplicity, and use of OpenStreetMap data. Several commenters appreciated the clear documentation and the straightforward Python interface. Some questioned the licensing implications of using Valhalla's routing engine, specifically whether the non-commercial clause of the Valhalla license affects the US Routing library. Others suggested alternative approaches like GraphHopper or OSRM, and discussed the tradeoffs between local routing engines and cloud-based solutions. A few users mentioned potential use cases like delivery route optimization and logistics planning. The performance comparison with other routing libraries generated considerable interest, with some expressing skepticism and asking for more detailed benchmarks.

  The Hacker News post for "Show HN: US Routing – Python library for fast local routing in the US" has several comments discussing the project and related topics.

  Some users expressed interest in the project and its potential applications. One commenter questioned the licensing implications of using OpenStreetMap data, specifically mentioning the requirement to credit OpenStreetMap and its contributors. They further inquired about how this credit is displayed within the library's usage.

  Another user highlighted the importance of the Valhalla project, suggesting that it's often overlooked despite its significant contributions to routing solutions. They posit that Valhalla's prominence is somewhat overshadowed by other more widely recognized projects like OSRM and GraphHopper. This commenter seems to imply the project being showcased might benefit from learning from or integrating aspects of Valhalla.

  One commenter pointed out that the project uses a pre-calculated grid for routing, raising a concern about how this grid handles areas with varying road densities. They suggested that a uniform grid might be inefficient or inaccurate in areas with vastly different road network complexities, advocating for a more adaptive approach.

  A different user mentioned their personal use of pgRouting, a PostgreSQL extension for geospatial routing, on a custom dataset of US roads. They didn't elaborate on the specifics of their application but implied satisfaction with this setup.

  Another commenter asked a clarifying question about whether the library handles routing for all vehicle types or focuses specifically on cars. This suggests an interest in the library's versatility and potential application to different transportation modes.

  Finally, a comment discussed the challenges inherent in routing, especially considering real-world scenarios like traffic, road closures, and turn restrictions. This brought a practical perspective to the discussion, highlighting that static routing solutions, while valuable, often need to be coupled with dynamic data for real-time applications.

• Shortest-possible walking tour to 81,998 bars in South Korea

  permalink

  Posted: 2025-04-24 00:20:40

  Verbose tl;dr

  A researcher has calculated the shortest possible walking tour visiting all 81,998 bars in South Korea, a journey spanning approximately 115,116 kilometers. This massive traveling salesman problem (TSP) solution, while theoretically interesting, is practically infeasible. The route was computed using Concorde, a specialized TSP solver, and relies on road network data and bar locations extracted from OpenStreetMap. The resulting tour, visualized on the linked webpage, demonstrates the power of sophisticated algorithms to tackle complex optimization challenges, even if the application itself is whimsical.

  This webpage meticulously documents the computational journey undertaken to devise a remarkably efficient walking tour encompassing a staggering 81,998 bars located across the entirety of South Korea. The central challenge, framed as a Traveling Salesperson Problem (TSP), involves determining the shortest possible route that visits each bar precisely once and returns to the starting point. Given the immense scale of this particular problem, with nearly 82,000 distinct locations to consider, arriving at an optimal solution presents a formidable computational hurdle.

  The author employs sophisticated optimization techniques, specifically a refined implementation of the Lin-Kernighan heuristic, to tackle this complex task. The Lin-Kernighan heuristic is an iterative algorithm that systematically improves an initial tour by identifying and swapping segments to progressively reduce the overall distance. Due to the sheer magnitude of the problem, the computations were distributed across a network of computers, leveraging their combined processing power to gradually refine the solution over an extended period.

  The resulting tour, meticulously detailed on the webpage, represents an exceptionally efficient traversal of these numerous establishments. The author provides various visualizations of the tour, including interactive maps and downloadable data files, allowing for in-depth exploration of the generated route. Furthermore, the webpage offers insights into the computational methodology employed, highlighting the challenges encountered and the strategies adopted to overcome them. The magnitude of the problem and the impressive optimization achieved underscore the power and applicability of advanced algorithmic techniques in tackling real-world logistical challenges, albeit in this instance, applied to a rather unconventional, yet fascinating, scenario. While the practical implications of visiting nearly 82,000 bars are perhaps debatable, the project serves as a compelling demonstration of the capabilities of modern optimization algorithms when applied to exceptionally large datasets.

  • traveling salesman problem
  • TSP
  • optimization
  • Graph Theory
  • algorithms
  • South Korea
  • walking tour
  • bars
  • route planning
  • shortest path
  • combinatorial optimization
  • mathematics
  • Geography
  • travel

  Summary of Comments ( 122 )
  https://news.ycombinator.com/item?id=43778105

  Verbose tl;dr

  HN commenters were impressed by the scale of the traveling salesman problem solved, with one noting it's the largest road network TSP solution ever found. Several discussed the practical applications, questioning the real-world usefulness given factors like bar opening/closing times and the impracticality of actually completing such a tour. The algorithm used, Concorde, was also a topic of discussion, with some explaining its workings and limitations. Some users highlighted potential issues with the data, specifically questioning whether all locations were truly accessible by road, particularly those on islands. Finally, a few users humorously imagined actually attempting the tour, calculating the time required, and referencing other enormous computational problems.

  The Hacker News post titled "Shortest-possible walking tour to 81,998 bars in South Korea" sparked a discussion with a moderate number of comments, primarily focusing on the computational aspects of solving the Traveling Salesperson Problem (TSP) at such a large scale. Several commenters expressed fascination with the scale of the problem and the optimization techniques employed.

  One commenter highlighted the use of Concorde, a specialized TSP solver known for its efficiency, and questioned whether the solution found was truly optimal or just a very good approximation. They also raised the practical considerations of such a tour, noting the impracticality of actually undertaking it. This sparked a small side discussion about the definition of "optimal" in the context of TSP solvers and the computational resources required to guarantee true optimality for very large datasets.

  Another commenter delved into the specifics of the algorithm used, mentioning the Lin-Kernighan heuristic as a key component of Concorde's approach. They explained how this heuristic iteratively improves a tour by swapping edges to find shorter paths. The discussion then touched upon the concept of "tour length," distinguishing between Euclidean distance and actual travel distance, with an acknowledgement that the solution likely focuses on abstract distance rather than real-world walkability.

  There was also a brief exchange about the data source for the bar locations, with speculation about the use of OpenStreetMap (OSM) or similar databases. This led to a comment about the potential issues with data accuracy and completeness, particularly in densely populated areas.

  A few comments offered humorous takes on the premise, imagining the physical challenges of completing such a tour and the potential toll on one's liver.

  Overall, the comments section reflects a mix of technical appreciation for the computational feat, practical considerations about the real-world implications, and lighthearted amusement at the absurdity of the concept. No one seemed to be planning an 82,000-bar pub crawl anytime soon, but the problem clearly captured the imagination of several commenters.