The “Traveling Salesman Problem” refers to an optimization problem originating from the plight of salespeople struggling to plan a route between all of their door-to-door stops for the day. In the world of computer science, computational time for solving problems can vary vastly depending on the complexity of the problem. For a traveling salesman making upwards of 50 stops per day, it can be tough to calculate the fastest possible route among every single possible option. Thankfully, GIS can often provide the best practical solution in a world where everyone is always on the move.
ArcGIS Online has several built-in tools that can be used for drive-time analysis. The Use Proximity suite of tools available directly in Map Viewer can be a great resource for planning routes and determining the best location for new facilities. There’s a wide range of implications and use cases for these tools too. Drivers in the parcel delivery industry come to mind as the “modern” traveling salespeople but even emergency response and aid delivery can have strict deadlines. Simply click on the “Analysis” icon on the right side of Map Viewer, and then choose “Tools” and “Use proximity” to get started. Please note that these tools will consume ArcGIS Online credits.
Plan out the route
The Plan Routes tool is ideal for situations where a driver needs to hit multiple stops, perhaps even alongside multiple drivers traveling simultaneously. Input your starting and stopping points, any time restraints or barriers you might have and Esri’s algorithm does the rest. These can include the time spent at each stop and the overall maximum time allowed for travel.
The output of this tool is always in lines, representing the most efficient Routes calculated by the algorithm. This tool will also generate the Assigned Stops and any Unassigned Stops if the parameters are too strict to allow for any of the vehicles to reach their destinations. Each Assigned Stop, as well as the starting point, will be numbered in the output to indicate the order in which each stop should be made.
The Plan Routes tool can draw optimized routes for every starting and stopping point.
Check the directions
One of the available options in the Plan Routes tool is to “Include route layers.” This setting will additionally generate a Route Layer, which can be used for navigation. Once a Route Layer is pulled into Map Viewer, the option to “Launch Directions” becomes available, providing users with turn-by-turn directions to each of the stops in the generated route.
Generating a Route Layer when running proximity tools can provide users with turn-by-turn directions along their route.
Get those areas covered
When conducting site suitability analyses for future infrastructure, many factors are often considered. One of the most important for facilities where travel to and from the facility is integral to the facility’s primary function – like a shipment processing facility – is the distance that can be traveled within a certain amount of time. These “coverage areas” or “drive-time areas” can be generated using the Generate Travel Areas tool.
This tool outputs polygons representing the distance traveled within a certain time frame either toward or away from the input layer’s features. For example, with the input of a fire station feature layer, one could calculate polygons representing the maximum distance traveled by fire engines within a 4-minute drive time in any direction away from that fire station. Such an output would have implications for the overall availability of fire stations and their ability to cover regions within a municipality.
Travel Areas can illustrate how far away from or toward a vehicle can travel within a specified timeframe.
Barriers
Both the Plan Routes and Generate Travel Areas tools have the option to include barriers as part of the algorithm used to calculate the travel route or area. Points, lines, and polygons can be valid barrier inputs representing any number of real-world scenarios. During a natural disaster or other emergency situation, roadways may be shut down and this can drastically change what the quickest and most efficient route is between locations.
Barriers can be enabled in the Proximity Tools suite by first opening the “Optional barrier layers” section in the individual tool and selecting the desired feature layers to serve as barriers for the route-solving process. New routes or travel areas will be generated as though the pathways blocked by these barriers are no longer accessible, creating outputs that are more true to the current conditions of the world.
Don’t get lost
The world has never been more interconnected. It’s easy to see how such analyses can be conducted at a global scale and have much broader implications for how people and items move throughout the world. For a problem thought to be so computationally intensive to solve, GIS makes it look easy.
Contact us for help implementing these tools for your organization!