How to find least-cost paths including tunnels (where slopes are too steep)?

Question

I'm currently working on a road path finding project for a motorway in ArcGIS 10. One criterion is obviously the slope angle. What I would like to do is to create a new cost surface which finds possible crossings where high mountains are --> Where would be a good path for a tunnel instead of going around the mountain? Any ideas how I could do that?

Answer 1

I strongly doubt there is anything in ArcGIS 10 (or any other GIS for that matter) that will accomplish this accurately.

One basis for this doubt is that I researched similar problems years ago and, finding no solutions, developed a general one. After five years of close review of related literature (including the GIS journals on which ESRI relies for sources of its algorithms), the US PTO awarded a patent for it. The method concerns ways to overlay multiple different ways to "travel" or "spread" across a surface, with multiple ways accessible at various points in the surface. (Imagine, for instance, finding least-cost routes using multiple transportation systems, including--if you like--getting out of the vehicle and walking across open areas as short cuts.)

This method, dubbed "GridRoute," can be applied here by creating a network describing all possible tunnels and their construction costs. Although such a network could be huge, it probably is not that difficult to construct given a formula or algorithm to determine the cost of a tunnel between arbitrary pairs of points in terms of other data such as elevation and rock type. (That in itself is an auxiliary cost-distance problem that can be pre-computed once and for all.) By combining this tunnel network with the implicit local cost raster (based on slope and direction of travel), the least-cost solution can be found in standard efficient ways (such as Dijkstra's algorithm).

This is Figure 4D in the patent. The numbers (which are visually represented by the colors) are the least costs of travel from a point near the upper right. The green lines are part of an overlaid network, which could in this case represent potential tunnel routes. In a purely network solution it would not be possible to travel or spread into surrounding cells, but this is possible in the illustration (although relatively costly). Notice the apparent discrepancies among values in the middle of this grid: they arise because the "tunnels" do not actually join one another where they appear to intersect in the middle. This fact is represented explicitly by the vertex-edge connections in the "tunnel" network but is impossible to represent in a raster format: that's why it is essential to have a combined raster-network data structure to solve this problem.

Evidently you would need to write much of this code yourself (just as I had to): I am unaware of any GIS that has built-in capabilities to create the hybrid raster-vector data structures essential for efficient solution of this problem.