Algorithms used by the ArcGIS Network Analyst extension
The routing solvers within the ArcGIS Network Analyst extension—namely the Route, Closest Facility, and OD Cost Matrix solvers—are based on the well-known Dijkstra's algorithm for finding shortest paths. Each of these three solvers implements two types of path-finding algorithms. The first type is the exact shortest path, and the second is a hierarchical path solver for faster performance. The classic Dijkstra's algorithm solves a shortest-path problem on an undirected, nonnegative, weighted graph. To use it within the context of real-world transportation data, this algorithm is modified to respect user settings such as one-way restrictions, turn restrictions, junction impedance, barriers, and side-of-street constraints while minimizing a user-specified cost attribute. The performance of Dijkstra's algorithm is further improved by using better data structures such as d-heaps. In addition, the algorithm needs to be able to model the locations anywhere along an edge, not just on junctions.
Dijkstra's algorithm
The classic Dijkstra's algorithm solves the single-source, shortest-path problem on a weighted graph. To find a shortest path from a starting location s to a destination location d, Dijkstra's algorithm maintains a set of junctions, S, whose final shortest path from s has already been computed. The algorithm repeatedly finds a junction in the set of junctions that has the minimum shortest-path estimate, adds it to the set of junctions S, and updates the shortest-path estimates of all neighbors of this junction that are not in S. The algorithm continues until the destination junction is added to S.
Route
This uses the well-known Dijkstra's algorithm, which is described above.
Closest facility
This uses a multiple-origin, multiple-destination algorithm based on Dijkstra's algorithm. It has options to only compute the shortest paths if they are within a specified cutoff or to solve for a fixed number of closest facilities.
OD cost matrix
This uses a multiple-origin, multiple-destination algorithm based on Dijkstra's algorithm. It has options to only compute the shortest paths if they are within a specified cutoff or to solve for a fixed number of closest destinations. The OD Cost Matrix solver is similar to the Closest Facility solver but differs in that it does not compute the shape of the resulting shortest path for less overhead and faster performance.
Hierarchical routing
Finding the exact shortest path on a nationwide network dataset is time-consuming due to the large number of edges that need to be searched. To improve performance, network datasets can model the natural hierarchy in a transportation system where driving on an interstate highway is preferable to driving on local roads. Once a hierarchical network has been created, a modification of the bidirectional Dijkstra is used to compute a route between an origin and a destination.
The overall objective here is to minimize the impedance while favoring the higher-order hierarchies present in the network. It does this by simultaneously searching from both origin and destination locations, as well as connection or entry points into higher-level roads, then searching the higher-level roads until segments from both origin and destination meet. As the search is restricted to the upper hierarchy, a smaller number of edges are searched, resulting in faster performance. Note that this is a heuristic algorithm; its goal is fast performance and good solutions, but it does not guarantee that the shortest path will be found. For this heuristic to be successful, the top-level hierarchy must be connected, as it will not descend to a lower level if a dead end is reached.
Generally, it makes sense to use this solver on a hierarchical network where the edge weights are based on travel time. This mimics the way people normally drive on a highway network.
Traveling salesman problem option for the Route solver
The Route solver has the option to generate the optimal sequence of visiting the stop locations. This is the traveling salesman problem, or TSP. The TSP is a combinatorial problem, meaning there is no straightforward way to find the best sequence. Heuristics are used to find good solutions to these types of problems in a short amount of time. The TSP implementation within Network Analyst also handles time windows on the stops; that is, it finds the optimal sequence to visit the stops with a minimum amount of lateness.
The traveling salesman solver starts by generating an origin-destination cost matrix between all the stops to be sequenced and uses a tabu search-based algorithm to find the best sequence of visiting the stops. Tabu search is a metaheuristic algorithm for solving combinatorial problems. It falls in the realm of local search algorithms. The exact implementation of the tabu search is proprietary, but it has been researched and developed extensively in-house at Esri to quickly yield good results.
Vehicle routing problem with time windows
The vehicle routing problem (VRP) is a superset of the traveling salesman problem. In a TSP, one set of stops is sequenced in an optimal fashion. In a VRP, a set of orders needs to be assigned to a set of routes or vehicles such that the overall path cost is minimized. It also needs to honor real-world constraints including vehicle capacities, delivery time windows, and driver specialties. The VRP produces a solution that honors those constraints while minimizing an objective function composed of operating costs and user preferences, such as the importance of meeting time windows.
The VRP solver starts by generating an origin-destination matrix of shortest-path costs between all order and depot locations along the network. Using this cost matrix, it constructs an initial solution by inserting the orders one at a time onto the most appropriate route. The initial solution is then improved upon by resequencing the orders on each route, as well as moving orders from one route to another, and exchanging orders between routes. The heuristics used in this process are based on a tabu search metaheuristic and are proprietary, but these have been under continual research and development in-house at Esri for many years and quickly yield good results.
Service area
The Service Area solver is also based on Dijkstra's algorithm to traverse the network. Its goal is to return a subset of connected edge features such that they are within the specified network distance or cost cutoff; in addition, it can return the lines categorized by a set of break values that an edge may fall within. The service area solver can generate lines, polygons surrounding these lines, or both.
The polygons are generated by putting the geometry of the lines traversed by the Service Area solver into a triangulated irregular network (TIN) data structure. The network distance along the lines serves as the height of the locations inside the TIN. Locations not traversed by the service area are put in with a much larger height value. A polygon generation routine is used with this TIN to carve out regions encompassing areas in between the specified break values. The polygon generation algorithm has additional logic to produce the generalized or detailed polygons and to deal with the many special cases that can be encountered.
Location-allocation
Location-allocation is a solver for the facility location problem. That is, given N candidate facilities and M demand points with a weight, choose a subset of the facilities, P, such that the sum of the weighted distances from each M to the closest P is minimized. This is a combinatorial problem of the type N Choose P, and the solution space grows extremely large. Optimal solutions cannot be obtained by examining all the combinations. For example, even a small problem like 100 choose 10 contains over 17 trillion combinations. In addition, the location-allocation solver has options to solve a variety of location problems such as to minimize weighted impedance, maximize coverage, or achieve a target market share. Heuristics are used to solve the location-allocation problems.
The location-allocation solver starts by generating an origin-destination matrix of shortest-path costs between all the facilities and demand point locations along the network. It then constructs an edited version of the cost matrix by a process known as Hillsman editing. This editing process enables the same overall solver heuristic to solve a variety of different problem types. The location-allocation solver then generates a set of semirandomized solutions and applies a vertex substitution heuristic (Teitz and Bart) to refine these solutions creating a group of good solutions. A metaheuristic then combines this group of good solutions to create better solutions. When no additional improvement is possible, the metaheuristic returns the best solution found. The combination of an edited matrix, semirandomized initial solutions, a vertex substitution heuristic, and a refining metaheuristic quickly yields near-optimal results.