Determining how to route vehicles from one location to another and beyond requires the ability to calculate distances and duration between points or indices. Depending on the type of routing problem, there are several ways to go about this.
Do you want a straight-line distance on a flat plane? Use Euclidean distance. Or do you need to account for the curvature of the earth? Haversine distance will get the job done. What if you need to account for real road distances and travel times, or handling objects like bodies of water, mountains, or valleys? Tooling that leverages data providers such as OpenStreetMap (OSM) allows you to accomplish that.
In this post, we'll take a high-level tour of a few common routing-specific distances and how they fit into the Nextmv Decision Stack.
Calculating routes on a flat plane with Euclidean distance
The shortest path between two points is a straight line. When calculating this on a flat plane or grid, you’re using what’s called Euclidean distance. Its formula is the square root of the sum of the squared differences between two vectors — or the Pythagorean theorem. Long live the hypotenuse!
Euclidean distance is useful for calculating routes where the curvature of the earth and street routing don't matter. It’s commonly used in academic vehicle routing problems (VRP), but can be applied to route planning for short-distance flights, open-space hiking, and some simple warehousing scenarios.
Learn more about Euclidean in Nextmv.
Calculating routes on a curved surface with Haversine distance
How do you calculate distance on a curved surface? Conceptually, you want to take those straight Euclidean lines and bend them a bit to be spherical. In practice, Haversine distance (also known as great circle distance or “as the crow flies” distance) makes this possible.
For route optimization problems, Haversine distance is one of the quickest ways to calculate distance on a curved surface. It’s relatively simple to implement and has a lighter computational footprint than approaches that rely on real roads and streets. This makes Haversine an appealing option when dealing with large datasets. While it’s more accurate than Euclidean distance when it comes to curved surfaces, Haversine distance is an approximation and does not take into account requirements that go along with street-based calculations. (More on that in a minute.)
Haversine is still a solid option for quickly calculating reasonable routes in many scenarios, including vehicle routing problems over longer distances, flight paths, and crossing the high seas.
Learn more about Haversine in Nextmv.
Calculating routes using real roads and ways
There are use cases where route planning and optimization requires calculating distances while accounting for real roads, railways, walkways, waterways, and their properties. This can include:
- Routing around valleys, mountains, or bodies of water that do not have available or easily accessible roadways
- Incorporating real-time or historical traffic data
- Accounting for road properties such as speed limits, one-way streets, weight limits, height limits, and accessibility based on different vehicle profiles (e.g., trucks vs. cars vs. bikes vs. pedestrians)
Accomplishing this requires having a map data provider such as OpenStreetMap (OSM) and a route planner built on top of that data provider such as Open Source Routing Machine (OSRM) or RoutingKit.
There are other options to choose from as well. GraphHopper and Valhalla are open source projects built on top of OSM. MapBox is a proprietary solution built on top of OSM. HERE Maps and Google Maps are proprietary route planners with their own map providers.
Which one makes the most sense for your business can depend on a number of factors such as query speed, memory consumption, the scale of your routing problem, the geolocation of your routing problem, and cost. And sometimes it just comes down to preference. We’ve engineered Nextmv to provide that level of flexibility — keep reading!
Learn more about OSRM and RoutingKit in Nextmv.
Calculating route distances with Nextmv using measures
We believe in flexibility and composability at Nextmv. In the same way you can use multiple solving paradigms to optimize for a given problem, we believe it's important for our customers to have access to many distance calculators — or "measures" in Nextmv lingo.
Measures are pre-built ways of implementing various types of distance or duration cost calculations into Nextmv. All you have to do is pick the one that’s right for you. In the routing context, that can mean using an existing OSRM measure or a RoutingKit measure. It can also mean leveraging our more generic matrix measure that allows you to tie into any third-party service that has a matrix endpoint, such as Google Maps, MapBox, and HERE Maps. You can also nest measures (e.g., start with Haversine for durations, and then add an Override measure for specific adjusted distances between some locations) or create a custom measure.
To get familiar with Nextmv’s routing measures and capabilities, create a free Nextmv Cloud account or contact us to discuss our self-hosted offering or additional measures we should consider!
