Network Analyst and ArcPy: finding k-alternate path

Using ArcGIS Network Analyst extension, it is possible to find out the best route between a pair of points (best is defined in terms of the impedance — it can the shortest or the fastest route, for instance). However, you might like having multiple alternatives to the best route which one usually refers to as the K shortest paths.

The K shortest path routing algorithm is

an extension algorithm of the shortest path routing algorithm in a given network.

When solving a route between a pair of points, Network Analyst finds only a single route that is considered to be the best. That is, one cannot get a number of routes while solving a Route layer. However, this is something many of you have seen when routing using Google Maps or HERE, for instance.

I got curious and have started searching for this algorithm implementation using ArcGIS Network Analyst. I’ve found a very useful Esri forums post by a former Esri Network Analyst product engineer Michael Rice who wrote that

At the ArcGIS 10 release, you can approximate a k-shortest paths solver using the enhanced barrier features. Additionally, for line and polygon barriers, instead of just restricting the parts of the network that are covered by their geometry, you can opt to simply scale the costs of the parts of the network covered by the geometry.

Therefore, to approximate k-shortest paths, you can do the following:

1. Solve the route to get the best path
2. Take the current best path and load it as a polyline barrier with a scale factor of x
3. Repeat

Note that by scaling the polyline barrier instead of restricting it, this will allow
the next path to reuse some of the same edges along the previous path if necessary, but at a higher cost than in previous paths. Also note that when multiple line barriers apply to the same edge, the final scale factor for the cost of that edge becomes the product of their individual scale factors. For example, if there are two line barriers applied to some edge with scale factors x and y, respectively, the scaled cost of traversing that edge will be x*y*originalEdgeCost.

This means that the more an edge is reused across different paths, the less likely it will be to be used in any subsequent paths as the process discussed above continues to iterate.

This approach will technically not guarantee a true k-shortest path solve, so we must
be careful not to incorrectly label it as such. As I said previously, it is merely an
approximation for this concept. A more appropriate name might be to call this a
k-alternate path approach (as opposed to shortest). The alternate paths you get will
ultimately depend on the scale factors you use.

I’ve written a Python add-in that given a number of alternative routes to find, will generate a new feature layer with a number of routes solved. I have used the workflow Michael described loading a solved route as a polyline barrier for all subsequent solve operations. You can use this code when you want to generate multiple alternate routes. This is how it looks in ArcMap.

2017-04-27 15_12_00-Routing.mxd - ArcMap

The Python code to be used to make the add-in:

Arcpy: Get route distance and travel time between stops in an ArcMap Network Analysis layer

If you are a user of ArcGIS Network Analyst extension, this post is for you. I am pretty sure many analysts solving routes between multiple stops would like to get some additional information about the solved stops. The route feature created after the solve does contain the information on the total route travel time as well as its distance. However, there is no information about the distance between individual stops in the route.

In other words, if your route has 10 stops, what if you would like to quickly get the distance value from the stop2 to stop7? If you have set up the accumulators in the Route solver properties, you will get those accumulators attributes in the Stops sub layer. This means you will be able to do the calculation manually because you would know that from the route start point, it took 5 minutes to get to stop2 and 18 minutes to get to stop7, so the travel time between the stop2 and stop7 is 13 minutes (18 min minus 5 min).

To avoid doing those tedious calculations, I’ve written a tiny code snippet with arcpy that you can wrap into an ArcGIS Python add-in. After installing the add-in, you will be able to select two arbitrary route stops and after calling the code, a message window will show you the distance and travel time between the stops. This code is supposed to be wrapped into a Python add-in, but can also be executed as a standalone script tool with minor modifications. This code assumes that the route has been already solved and there are accumulators associated with the route solver.

If you would like to customize this tool making it more flexible by reading the accumulators and getting their types and units, take a look at the RouteSolverProperties arcpy object as well as the network dataset Describe object properties.

This is how this code runs in ArcMap with the Python add-in installed:

distance_between_route_stops

The code:

Build ArcGIS network dataset from OpenStreetMap

I have blogged previously on how you can get street data for use in the ArcGIS Network Analyst. If you have obtained TomTom or Nokia (Navstreets) data, you can easily build a network dataset (further ND) by using the Esri SDP toolbox which I have blogged about earlier.

If you don’t have any other sources for the data, consider using the OpenStreetMap (OSM) data if it is applicable in your business case. I have blogged earlier on how to get OSM data into ArcGIS network dataset, but this approach is outdated and I recommend another way to build the network. The overall workflow is fairly straightforward:

Download OSM data

Go to the OSM home page tab and choose area to download. You can either draw a rectangle or specify the bounding box coordinates. If the area you choose will be too large, you will have to use one of the sources listed at the left panel for bulk data downloads. Clicking the Overpass API link will trigger downloading the map file with no extension. Rename it by adding the .osm extension.

2015-02-20 15_46_54-OpenStreetMap _ ExportInstall ArcGIS Editor for OSM

Now you have to download the ArcGIS Editor for OSM, either 10.0, 10.1 or 10.2.x Desktop version. The installation file will install the libraries required as well as a geoprocessing (further GP) toolbox tools of which you will access later on. Read through the documentation on how to build a ND from OSM data on the ArcGIS OSM Editor home page. After installing, you should find the OpenStreetMap Toolbox in your ArcToolbox folder in ArcGIS.

Load OSM file into geodatabase

Start by running the Load OSM File GP tool. Please activate the Conserve Memory option if you have a large OSM file (larger than the amount of RAM), because during this process all nodes are going to be fetched. If you fail to do so, the process might crash. I’ve hard time to process some large files on a 8GB virtual machine partly because of the Windows paging 2GB limit. Running the processing from the 64bit Python might help, but this is something I have not tested yet. I remember that some of network data processing algorithms I have developed failed on building adjacency matrix for a network with 15 million edges when running with 32bit Python, but completed with no problems when running under 64bit Python taking almost 10GB of RAM on my machine.

Build a network dataset

When the data will be loaded into a feature dataset, you are ready to build a network dataset. You will need the Create OSM Network Dataset GP tool for that. You will need to provide a Network Configuration File which you can find in the C:\Program Files (x86)\ArcGIS\Desktop10.1\ArcToolbox\Toolboxes\ND_ConfigFiles provided. This is an XML file which provides parameters for interpreting your road types data into edge cost evaluators. The DriveGeneric.xml is for a generic motorcar routing network, but there is another one which can be used for cycling networks. There is one more file there – DriveMeters.xml. This configuration offers faster runtime performance (less Script evaluators), but will only work with coordinate systems that have a linear unit of meters. Let the tool to run as it might take a lot of time if you have a large dataset. After the ND is built, feel free to modify its properties and test how it works.

OSM_serviceareasI suggest start by downloading a small area to verify the tools are working as expected. The map.osm file you download should not be larger than 20MB. After you have verified the workflow, feel free to try larger datasets. There are some other useful tools in the ArcGIS OSM Editor toolbox which you might want to explore. There are some for designing maps based on the OSM data and loading data into PostgreSQL database.

Street data processing toolbox from Esri

Recently I was doing quite a lot of work with street data processing so that one could get network dataset in ArcGIS based on raw data coming as Navstreets shapefiles from HERE (known also as Nokia and previously Navteq).

Just for some years ago, there was no other way to compile those shapefiles into network dataset except from doing a lot of operations manually and use ArcObjects/Python. Fortunately, Esri has published a Street data processing toolbox which would do just that. It is free and supports both Navteq Navstreets data as well as TomTom Multinet.

I was worrying a bit first because I was not sure whether the SDP toolbox is capable of compiling really large datasets covering a bigger part of Europe and North America. However, it went really well and huge datasets were compiled within a week. I have been using some machines I had at my disposal, but I have run out of RAM quite soon. I had to use Amazon EC2 running a rather powerful instance. As a best practice, in addition to running on a 64-bit OS and having lots of RAM, you should also be sure that you have plenty of temporary disk space on the system drive (the temp folder is used heavily for the temp data storage). Note that the temporary space is not the same as the destination for the output file geodatabase where the network dataset will be created, and is often located at C:\Users\%username%\AppData\Local\Temp\. The USA+Canada network dataset was compiled in 70 hours (Amazon EC2 m2.2xlarge instance was used).

Be aware that SDP tools cannot be run with background processing enabled, so you should author and run a tool via a model or Python script tool if you want to run some custom data processing operations first. Remember to switch off the background processing in ArcGIS Desktop application (Geoprocessing > Geoprocessing Options). You can run Dissolve Network GP tool to get a more compiled network dataset which will be faster in operation (remember to build a network dataset after dissolving) and then compress file geodatabase with Compress Geodatabase GP tool to make it smaller, perform faster and be read-only. The network dataset in this format (dissolved network and compressed geodatabase) performs as good as SDC.

 

OpenStreetMap to ArcGIS Network Analyst

Over some years, I have seen that many people are looking for ways to get started with the network analysis in ArcGIS. However, some may not have access to a properly prepared routing dataset, which can be used directly in ArcGIS by using the Network Analyst extension. I have blogged a bit on various street data sources before, so, by now, you should have a good idea about where to look for street data.

A couple of days ago, I found a very interesting resource on how to process the OpenStreetMap data in order to get a routable network dataset which can be used for network analysis purposes directly in ArcMap. The tools are available at the 52° North web site, the open source software initiative, and were written by Eva Peters.

After using the tools for some time and testing them extensively during some evenings (I’ve compiled some nice network datasets over Swedish metropolitan areas), I’ve decided to summarize how to use them to help those who want to get their hands on a properly configured ArcGIS network dataset for their geographic area, in order to learn how various Network Analyst solvers work.

Prerequisites:

  • ArcGIS 9.3.1 or 10.0 installed (either license would work – ArcView, ArcEditor or ArcInfo. You can even use your ArcGIS Engine license, if you have one). If you don’t have ArcGIS installed yet plan to install one, check the Esri system requirements page.
  • ArcObjects .SDK for Java 9.3.1 or 10.0 installed. If you don’t have SDK installed yet plan to install one check the Esri system requirements page. Since you are not going to develop anything with the ArcObjects SDK for Java for now, you don’t really need to install JDK (Java Development Kit). In fact, you can install JRE (Java Runtime Environment).
  • JRE is required. This can be downloaded from the Oracle web site. The version JRE6 has been tested by Eva, so why not download the jre-6u31-windows-i586.exe package there. I’ve used this one, too.

This is pretty much it.

After you’ve installed the software we need, just do a couple of checks to see that everything is alright.

  1. Start ArcMap to see that the installation went well.
  2. Check that the Java installation is OK: open the cmd and enter “java –version” to check if Java works fine. You should get a message like this:

C:\Documents and Settings\Administrator>java -version
java version “1.6.0_31”
Java(TM) SE Runtime Environment (build 1.6.0_31-b05)
Java HotSpot(TM) Client VM (build 20.6-b01, mixed mode, sharing)

  1. Download the tool from the 52 North web site. The tool itself is a .jar file (Java ARchive) which you can think of as a kind of .exe file in Windows. You will run this .jar file much like you would do with the .exe file. The easiest way to run the tool is to use a batch file (with the .bat extension), which will refer to the ArcObjects Java libraries we need and Java itself.
  2. Create a .bat file by using any text editor like Notepad (I like Notepad2). Enter this text into the .bat file:

“C:\Program Files\Java\jre6\bin\java” -cp “C:\Program Files\ArcGIS\java\lib\arcobjects.jar”;”C:\Program Files\osm2nds\osm2nds_ArcGIS_10.0_gui_1.1.jar” org.n52.osm2nds.core.userinterface.gui.Main

PAUSE

Where:

  • “C:\Program Files\Java\jre6\bin\java” is the default path to the Java installation folder
  • If using ArcGIS 9.3.1 – “C:\Program Files\ArcGIS\java\lib\arcobjects.jar” or
  • If using ArcGIS 10.0 – “C:\Program Files\ArcGIS\Desktop10.0\java\lib\arcobjects.jar” is the default path to the ArcObjects for Java installation folder
  • C:\Program Files\osm2nds\osm2nds_ArcGIS_10.0_gui_1.1.jar” is the path to the folder where you saved your tool downloaded from the 52North page.

Don’t forget that the path may vary depending on the Windows version used (in 64-bit Windows you would get ArcObjects installed in the “Program Files (x86)” folder).

You can find more notes on the installation and running the tool at the 52 North web page, if needed, since this post is just a brief overview. Let me know what you think about the tools and whether this is something useful!

Street data for Network Analyst

Through talking with customers and being personally involved in several projects which require having street data for routing purposes, I have learnt some valuable lessons which I want to share with the GIS community.

First of all, to get started working with street data is not as easy as it seems. One may need to contact a local agency for any street data in the public domain. At the same time, quite often there are no street data available, which implies spending quite a large amount of money on data acquisition. Technically, to get started performing network analysis using ESRI Network Analyst extension is relatively easy, yet to get the data for the work is much harder.

Secondly, there is a lack of awareness of street data sources available in the ESRI community. Obviously, there are much fewer people working with Network Analyst extension compared to the users of Spatial Analyst or 3D Analyst extensions. So, a person involved in solving routing tasks is forced to get to know the software on his/her own by using limited help system and other resources available. The number of white papers and magazine articles related to the ESRI tools for network analysis is limited as well, yet there is a great deal of interest in this particular area.

Finally, vendors’ street data is shipped in a raw format and obviously not in ArcGIS network dataset format! Navteq Navstreets and TeleAtlas Multinet products are delivered among others in ESRI Shape format. This implies that users may need to dive into the hundreds of pages which comprise the reference manual, in order to figure out many things – such as how to convert turns tables into ArcGIS turn feature class, import signposts, and set the directions parameters properly, to name a few. It is a time consuming process which is likely to involve contacting vendor’s support and extensive trial by error tests.

To give a thorough overview of the network analysis in ArcGIS would take too much time, so let’s just focus on the acquisition of street data in this post. Options available are as below/follows:

1) TIGER (Topologically Integrated Geographic Encoding and Referencing system) data from the U.S. Census Bureau is a good option to get the street data. Visit U.S. Census Bureau for more information or proceed to the ESRI ArcData Web interface for direct downloading available data. Street data do have a lot of attributive information, but one will still need to perform a lot of manual data editing. The data coverage includes only the USA.

2) ESRI has a separate product – ESRI StreetMap Premium, which provides access to the street data in SDC format both for North America and Europe. This product can be used in the Network Analyst directly and no data processing is required. Be aware that these network data are for read-only use and no edits to data can be applied. This data product provides the best performance as well as robust functionality, yet the least customization flexibility, because one can only use the street data as it is.

3) Navteq Navstreets and TeleAtlas Multinet are one of the most often used products for network analysis purposes. The data is delivered in MapInfo or ESRI Shape format and need to be processed in order to be used with the Network Analyst extension. Navteq does provide Navstreets data in the compiled ESRI File Geodatabase from the Q1 2011 yet some data processing still will be required. Depending on how much information you want to include into your network dataset, you will need to perform some joins and geometry processing operations as well as use ArcGIS geoprocessing tools or scripting language, for instance, Python. The data coverage includes the whole world.

4) OpenStreetMap – a collaborative Web project that aims at creating a free digital world map. One can download all the data including, but not limited to, street network data (http://downloads.cloudmade.com/). Street data do not have much attributive information so one would need to perform a lot of manual data editing. The data coverage includes the whole world.

Resources:

What is Network Analyst

TeleAtlas

Navteq Network for Developers

OpenStreetMap

OpenLR™