How Routing Engines Find the Fastest Route
How a routing engine works: the road graph built from map data, costing per mode, hierarchies for long trips, transit timetables, and why routes fail.
How a routing engine works: the road graph built from map data, costing per mode, hierarchies for long trips, transit timetables, and why routes fail.
ow to get your website indexed: how crawlers find pages, why a page is crawled but not indexed, sitemaps, IndexNow, and a checklist to work through.
Carpathian Maps gives your site a world map and your backend walk, bike, drive and transit directions, all from Carpathian's own map server.
Carpathian's threat intelligence feeds list hostile IPs, domains, and URLs at a fixed address, so your firewall can fetch them on a schedule and block them.
Debugging is a loop: paste the error, try the fix, paste the next error. A message cap ends that loop before the bug does. Carpathian AI helps with it all.
A routing engine finds the fastest route by turning a map into a graph, where intersections are points and road segments are the lines between them, giving every segment a cost in seconds, and searching for the cheapest chain of segments from your start to your destination. The cost depends on how you travel. A footpath is free for a walker and closed to a car, and a highway is the reverse.
Two ideas keep that search fast across a whole country. The engine expands outward from the start in order of cost, so it never revisits a point it already reached more cheaply. And it keeps highways in a separate, smaller layer, so a long trip climbs onto the highway network instead of searching every side street between two cities. Transit adds a timetable: a bus route is only usable when a bus is running.
For the related question of how far someone can get in a set time, see What Is an Isochrone Map, and How Do You Make One?.
A routing graph is the road network stored as points and connections. Each point (a node) is an intersection or the end of a road, and each connection (an edge) is a stretch of road between two nodes, carrying what the engine needs to know: length, speed, one-way rules, surface, and who may use it. Every route is a path through this graph.
The graph is built from map data, and for most open routing engines that data is OpenStreetMap, the volunteer-built world map. Its data is under the Open Database License, which requires you to "provide credit to OpenStreetMap" wherever you use it, which is why the credit appears in the corner of maps built on it.
Building the graph is the slow part. The engine reads every road, path and turn restriction in the source data, splits roads at intersections, works out speeds from road types and tags, and writes the result in a compact form it can load quickly. For a city that takes minutes. For the whole planet it's a job measured in hours to days on a large server, which is one reason most teams call a hosted directions API rather than run their own.
Engines also cut the graph into pieces so they don't need it all in memory. Valhalla, a widely used open-source routing engine, stores the world as square tiles in three levels: highways (motorway, trunk and primary roads) in 4-degree tiles, arterial roads in 1-degree tiles, and local roads in quarter-degree tiles.
If your signup code or password reset never showed up, your email provider most likely stopped it. School and work addresses are the usual cause.
Costing is how a routing engine prices each road for a given way of traveling. It turns length and speed into seconds, then adds penalties for things the traveler would avoid, like a steep hill on a bike or an unprotected left turn in a car. The same graph gives different routes for walking, cycling and driving because each mode prices the roads differently.
A few examples of what costing decides:
When a route looks odd, costing is usually the reason. The engine chose what was cheapest by its prices, and those prices may not match what a local driver knows.
The classic method is Dijkstra's algorithm: start at your origin, repeatedly take the cheapest point not yet settled, and update the cost of reaching its neighbors. When the destination is settled, the path to it is the fastest one. Modern engines speed this up by searching toward the destination and by moving long trips onto a smaller highway layer.
Edsger Dijkstra published the method in 1959, in a three-page paper titled "A note on two problems in connexion with graphs" in Numerische Mathematik. It still underpins most routing. Picture dropping ink at your starting point on a map where the ink spreads faster along fast roads: the first time the ink reaches your destination, it has traced the fastest route.
Plain Dijkstra spreads in every direction, which wastes time on the side of town you're not headed toward. Engines add three refinements:
Once the path is found, the engine walks along it and writes the instructions: "Turn left onto Grand Avenue," "Continue for 2 kilometers," "Take the exit." Each instruction is called a maneuver, and it's built from the street names and angles stored on the edges.
Transit routing searches a timetable as well as a map. A bus line only connects two stops when a bus is scheduled, so the planner needs a departure time, walks you to a stop, rides the trips that run after you arrive, and walks you from the last stop. The fastest trip at 8 a.m. can be a different trip, or no trip, at 8 p.m.
Timetables come from agencies in GTFS (General Transit Feed Specification), the standard format for transit schedules. A GTFS feed is a set of text files, and the specification requires agency.txt, routes.txt, trips.txt and stop_times.txt, plus stops and service dates. The calendar files say which days each schedule runs, so a feed has a start and end date, and an expired feed returns no trips at all.
Transit planners combine the feed with street data for the walking parts. OpenTripPlanner, an open-source planner, describes itself as "an open source multi-modal trip planner, focusing on travel by scheduled public transportation" that builds its network "primarily" from GTFS and OpenStreetMap. OpenTripPlanner 2 plans with a method called multi-criteria range-RAPTOR, which works in rounds (each round allows one more transfer) rather than settling points one at a time, and it considers "every minute in a window" of departures rather than one instant.
The time dependence produces answers that look like failures and aren't. In a test from downtown Des Moines, a bus search at 6:45 on a Sunday evening returned no trip, while the same search for 9:00 on a Tuesday morning came back with a route 5 bus. The timetable had no service in the first window.
Most routing failures come from the data or the request, not from the search. A point too far from any road, a place outside the engine's coverage, a missing path in the map, or a timetable with no trip in the search window all produce no route. Wrong-looking routes usually trace back to the map's tags or the mode's costing.
The common causes, roughly in order of how often they show up:
Choose a directions API by where it routes, which modes it covers, how fresh its data is, and what happens to the locations you send it. Price and speed matter, but a cheap API that can't route where your users are, or that keeps a record of their trips, is the wrong one.
Work through these questions:
Carpathian Maps is a directions and map API built on Valhalla, OpenTripPlanner and OpenStreetMap, run on Carpathian's own servers. Your backend sends two points and a mode (walk, bike, drive or transit) and gets back the time, the distance, the path and step-by-step instructions. The coordinates in a request are never written to a log. The launch article covers keys, pricing and limits.
It routes coordinates, not addresses, so you'll need a geocoder if your users type addresses. Transit covers the agencies listed in the coverage table, which today is DART in the Des Moines metro, and walk, bike and drive routing works where that same table says. If your users need worldwide transit today, this isn't the API for that. If the coverage fits, create an account and follow the Connect guide.
