Least Cost Paths

Least Cost Path Options.  Start from Analyze  menu, or Set on Analysis tab of the Options form. Impossible Cost : for points with no cost in the cost surface. Max Impossible In Path: do not consider paths with this many impossible points Buffer Cost: cost per pixel when driveways are not in the roads database; Buffer Rounds: pixels to go out to account for missing driveways.  If this is too big, paths will cross rivers and bays or interior blocks. Cost Surface Resolution: size in meters of the grid; Start Free : Pixels around the starting point to have no cost.  Needed if the point is perhaps a shopping center, and the database shows no roads; Precint Field: field to use for naming the accumulated cost surface.  If this field is not present you will have to pick it.  Ideally it would meet the rules for naming a dBase field. Distance: can be either pixels, or distance (with adjustment for diagonals) Save path surface Overwrite Weight diagonals: increase costs and distances for diagonal pixels by √2 Compute Least cost path, using the weights Shortest distance with all roads the same cost Files Road network Route starting points DBF file: this should be a small number, because you will have to create the cost surface and diretion of motion for every record. Route ending points:  this can be a large number, because it just involves a lookup in the cost surface. Procedures Create cost surface: pick a lines shapefile, such as a road network, with a COST field, to create the cost surface. Create path surfaces: using the route starting points DBF file, the three grids will be created for each record in the Precint Field set above. Create route costs One step

Least cost path procedure:

• Open TIGER county file edges file (or you could use OSM) 
  • You could use this with any line or area shape file, as long as there was a COST field with integer values.
  • The "tiger_rules_vNNN.dbf" file in the MICRODEM directory has the cost for each category of road, in a "COST" field.  Think of it as the number of seconds for a distance like 100 m, with low cost being best (fastest travel time).  The actual numbers do not matter so much as the relative costs. 
• Report, Create cost surface from TIGER file's db Form.  The file will be created in the directory with the TIGER file, with the name of the file and then a description added at the end.
• Open point shapefile with starting points for the least cost paths.
• Double click on the record for the point to start the paths.  This will create three grids, based on a field in the point data base:
  • The cost surface, with the cost for the point to get back to the starting location.
  • The direction of motion, needed to plot the paths.
  • The length of the path, either in meters or pixels

To add the cost to each point in a database.

• Open the cost surface.
• Open the desired point database on the cost surface map.
• Enable edits.
• Edit,  DEM, Add nearest elevation from DEM

To show least cost path:

Scripting Least Cost Path

• Run the program from the GUI, and set all the parameters.  If you do not, it will use the defaults built into the program.  The defaults are saved and will be used for every running of the program.
• Close the program.
• Run a script with the following (these are NOT case sensitive):
  • microdem.exe
  • space (then no more spaces; this syntax follows web protocols for running the program as a web service, and the & separates parameters)
  • ?act=lcp (this is the action the program will take)
  • Optional parameters to override the settings you made in the MICRODEM GUI.  If the files are not present, the program will prompt for you to select them.
    • &road_file= complete path to file, with no spaces allowed (TIGER edges shape file, but OSM might also work if costs were added).  Output will go into this file's  directory.
    • &start_pts= complete path to file, with no spaces allowed (we have not tested sending a CSV, but that might work)
    • &end_pts= complete path to file, with no spaces allowed (we have not tested sending a CSV, but that might work)
    • &ini= complete path to an INI file, which only makes sense if you are multitasking with several executables, and want them to use the same intial settings apart from the three files above.
• MICRODEM will open and create the files. During debugging MICRODEM does not yet automatically close.

Grid size for the cost surface. If you use a large grid, it will process faster and produce smaller files, but there could be paths through many of the urban blocks. The grid for 10 m resolution will be 9 times larger (3*3), and could present problems if you have a really large area and a wimpy computer.

References

• Collischonn, W., and Pilar, J. V., 2000, A direction dependent least-cost-path algorithm for roads and canals: International  Journal of  Geographical Information Science, 14(4): 397-406. 
• Lee J, and Stucky, D., 1998, On applying viewshed analysis for determining least-cost paths on Digital Elevation Models: International  Journal of  Geographical Information Science, vol.12, no. 8, p. 891-905.
• Yu, C., Lee, J., and Munro-Stasiuk, M.J. , 2003, Extensions to Least-cost Path Algorithms for Roadway Planning. International Journal of Geographical Information Science, vol.17, no.4, p.361-376.

	Original DEM (Hanging Rock Canyon, CA).
	Create cost surface.  Create this DEM/grid, for instance by creating a derivative grid, multiplying a grid (Edit, data manipulation form), or adding multiple grids (Raster GIS menu).  This is a critical step for the operation.  If there are points in the original DEM you do not want considered, you can Edit them out before you create the cost surface. You can edit out regions you do not want the program to consider for the cost surface and eventually the least cost path, either by removing values within a certain range of z values or outlining regions with the mouse (both on the Edit menu).  You can edit out regions on the cost surface using an image.  To do so, you must associate the cost surface as the DEM to go with the image, on the Modify menu. You can mask so that you are either close to, or away from roads. You could also mask with any other grid. In this example, we are just using a slope map
	Create accumulated cost surface, on Raster GIS menu.  You select a point (in the SW corner in this example, near the mouth of the canyon in a low slope (low cost) location) by double clicking. This surface is good only for the selected starting point. The colors indicate the cost to get to each point in the grid from the starting location you specified (or to get back to the starting point from every other point in the grid)--blue are "cheap", and red are "expensive". There is also no consideration of directionality for the surface; diagonal segments are the same cost as straight segments.
	Grid showing downhill direction at each point on accumulated cost surface.  This grid will be created and used to create least cost paths, but you do not have to open it.
	Create least cost paths.  Open the accumulated cost surface DEM, and then select option on Raster GIS menu for that grid.  You select a point by double clicking and the program will trace the paths back to the starting location and save results as a point shape file. This shows three different paths, which all converge toward the starting point.  To minimize the slopes crossed, the paths go almost straight downhill from the starting points, and then follow the drainage channels. The path shape files have been displayed on the original DEM. This step is very fast.

Last revision 5/5/2019