Shortest Distance Destination, Many Origins

Like any good Geospatial question, the answer to what is the right solution resides in the needs and available tools of the map maker and the data consumer (ie the person who will make use of the answers to the question being asked).

For this particular question, the data consumer needs to know what are the ideal hubs, or meeting cities, between workers that are dispersed across the United States. The solution involves finding the ideal central location for any given subset of team members, as determined by their proximity to each other.

The workflow is to load the set of addresses as lat/long points or georeferenced polygons into the geo-workstation, calculate the distances between all points, and then generate groups based on a threshold of “nearness”. It is likely that some tie-breakers will need to be manually cleaned. Following the establishment of groups of locations based on proximity, the next step is to determine what is the central location to each of these points. Here again, it is likely there will be a need for manual intervention because the insurmountable challenge with routing is that the shortest distance is not always the leading determining factor for route selection. The same is true with location selection. People are often willing to travel a certain distance beyond their shortest path destination if they are likely to receive other benefits from the longer path or further destination. To put in layman’s terms, if Joe and Sally are meeting at a destination, they might opt for a similarly distanced alternate location that has a more scenic drive along the way or has a great restaurant, meeting place or other feature in the alternate destination.

Awesome viz from Germany epidemiology study.

I will start with the solution I would expect as an optimal solution for a GIS Analyst. analysis. The workflow for this scenario is to load the set of addresses as lat/long points or georeferenced polygons into the GIS workstation, from there use the Spatial Analyses tools to calculate the distances between all points, and then generate groups based on a threshold of “nearness” – the actual function is often named “near”.  This GISstackExchange post suggests the OD Cost Matrix is the ideal tool for the solution, and this ESRI tutorial gives step-by-step to the workflow of using it. This ESRI troubleshooting thread provides some great context for solving this problem with GIS Software, but it involves use of GIS software. Even for those that do not have the training to operate GIS software to make this their technical solution, it provides some interesting content on the challenge.

The GIS software may sound like the most advanced solution, but this is the crux of the initial statement on the analyst tools and user needs. For almost all spatial analyses that can be done in GIS Software, there exists an equally efficient method of running the analysis using JavaScript and GDAL/ogr2ogr. For the first step of grouping by a threshold of shortest distance would save you some time, here is a link to the JavaScript code for ‘distance’. Once the sub groups are identified, then all associated polygons within the sub group can be dissolved into a larger polygon, of which the ‘centroid’ can be determined using GDAL/ogr2ogr.

What’s fun is that clearly this is not an uncommon problem that people are faced with. Enough so that someone was motivated to create a GUI for those that don’t have access to the spatial analytical software or the skills to utilize the open source tools. Let’s Meet in the Middle is a web app shows you ‘near’est cities from a selected set of addresses. All things considered, this might actually be the most efficient solution, even if you have a full GIS suite available, but for those looking for identifying multiple centroids then certainly the first step is to identify the sub groupings (based on proximity threshold) for the greater group.

Lastly, check out this Mathematics thread on StackExchange. Also note, the featured image is from a study posted on ResearchGate: Comprehensive Performance Analysis and Comparison of Vehicle Routing Algorithms in Smart Cities.

Margaret Spyker

Leave a Reply Text

Your email address will not be published. Required fields are marked *

Powered by WishList Member - Membership Software