Thomas Balstroem
Abstract A procedure is presented to calculate the least cost route when visiting 16 sites within a
mountainous watershed on the Island of Vagar, the Faeroe Islands located in the
Northern Atlantic Ocean. The least cost route is derived from an optimization of paths
calculated from each site to all other sites based on calculations of 16 individual cost
surfaces. The cost surfaces are established from combinations of field observations on
actual time spent when walking around in a mountainous terrain crossing steep slopes
and rivers. Introduction Network software to solve the travelling salesman's problem has been available for
years in order to find the shortest route within a road network between two or more
locations. A friction based network analysis considering the passage problems caused
by the varying driving quality of the roads, their traffic loads, locations of traffic lights,
directional information and so on may also be carried out to give a more realistic
estimation of the travelling salesman's travel time. If, however, you are put into an area where neither roads nor paths exist - for example
in a mountainous area and you want to find the easiest or least cost trekking route
between several locations you want to explore - then the abovementioned network
software turn out to be insufficient simply because there is no information about the
'infrastructure'. However, if you are able to define possible pathways between the
various individual locations you want to visit in a preceding step then you may later
calculate the least cost route between these locations using the abovementioned
network routing software. Background The background for the present study of finding least cost routes in mountainous terrain
was triggered off in 1988 during a research course for graduate physical geography
students on the Faeroe Islands in the northern part of the Atlantic Ocean. The main
purpose of the course was to introduce the students to hydrological methods related to
investigations of orographically caused differences in precipitation within small
subcatchment areas contributing to a major watershed. To get an impression of the
precipitation differences caused by combinations of various exposures (aspects) of the
landscape and their heights above sea level a monitoring programme was set up within
an area of approximately 6 km2 located in UTM zone 29V N6886000-6890000,
E589000-593000 presented in Figure1. Within this area the elevation differences range
from 94-551 metres a.s.l. To unveil the orographic conditions of the landscape 16 rain
gauges were set up in each of 16 landscape units characterised by a combination of 4
elevation zones (94-200, 200-300, 300-400 and 400-551 metres a.s.l.) and 4 aspect
zones (northern, eastern, southern and western exposures). The 16 zones were
depicted from a raster-based analysis of a digital elevation model (DEM) covering the
area of interest and presented in Balstroem (1992). Figure 1. Presentation of the location of the study area on the Island of Vagar,
The Faeroe Islands. Adapted from Balstroem (1992).
The 16 gauges were inspected daily over 5 days by 2 persons who were not familiar
with the landscape but both were experienced mountain walkers. Based on topographic
maps and trial and errors they depicted what they believed to be the least cost route
when visiting all the gauges. However, the walking tour took several hours and was very
exhausting. Since this field trip the author of this current paper has born in mind how to depict the
least cost route to inspect the 16 gauges using GIS and a suggestion to solve this
problem is hereby finally presented. Unfortunately, this result is presented a little late to
assist the walking around within the area presented but, hopefully, the demonstrated
technique may be considered in the planning of other field campaigns in the future. A literature study has been carried out to reveal other attempts to solve the problem of
finding least cost routes when walking around in wildernesses but, yet, no distinct
references have been discovered with specific reference to this topic. It was assumed
that within the sports of orienteering a reference to a similar analysis like the one
presented in the next section would have been published but it doesn't seem to be the
case. In the field of military strategy planning such analysis may have been carried out
but, so far, no unclassified papers hereon have been found, either. Method and theory In this section the method behind the least cost route finding will be presented.
Summarised, the finding involves the following GIS tools and data in 5 major steps: Figure 2 Workflow diagram on how to find the least cost route in a mountainous area.
In Figure 2 the 5 steps above are presented in a workflow diagram. The cost surface based technique to find the least cost path given a number of
frictions to pass across a surface was thought out and implemented by C. D. Tomlin & J.
Berry in the beginning of the 1980s and included in their raster based GIS named the
Map Analysis Package (MAP) developed at Harvard University. This technique is today
a.o. implemented in Esri's ARC/INFO GRID module and ArcView's Spatial Analyst
extension. In short, a path across a piece of land can be determined from a two-step procedure: Depending upon the locations and the values of the friction cells one may imagine that
the cost surface if viewed in 3D will have the shape of a more or less skewed bowl and
that the path from a point upon the edge or the side of this bowl always will be towards
the bottom of this one which is the point (origin) from where the building up of the
accumulated costs were initiated. All friction values must be expressed as whole numbers >= 1. Thus, a value of, say, 5
indicates that this cell is 5 times more costly to pass through than a cell with a value of
1. For a more comprehensive presentation of cost surfaces and cost path principles
please refer to Tomlin (1990) or Berry (1993) and discussions of the Cost Distance and
Cost Path requests included in the documentation to ArcView's Spatial Analyst
extension. Friction parameters For this project it has been decided to express the friction of movement across the
landscape in time units. Two major components have been selected to describe the
friction and represented in 2 grids: Grid A) A stereo-pair of aerial photographs at a scale of approximately 1:25,000 were
mounted and rectified using an analytical plotter and points along elevation curves for
each 10 metre were digitized together with spot heights located on hilltops and in low-lying areas. In total 25,304 elevation points were collected and later used to create a
TIN based DEM from ArcView's 3DAnalyst extension. Afterwards, the TIN was
converted to a cell based DEM with a spatial resolution of 5 metres and slopes for the
whole area was calculated in %. Results from field experiments concerning time spent walking on slopes within the area
are shown in Table 1. It is seen that the time spent walking on slopes of approx. 30%
steepness is the double of the time spent crossing a horizontal unit. If the steepness
exaggerates 30% one normally is inclined to look for a path that has a lesser slope or
one may choose to walk in hairpin bends. So, a 'time-friction' based grid was created by
looking up the friction values of the slope grid's cells according to Table 1. Steep
hillsides with slopes >30% were assigned a value of 9999 indicating that they are
regarded as impassable (i.e. absolute barriers). Table 1. Time spent to walk 5 metres uphill or downhill. Grid B) The area is dominated by a large number of rivers. Because most of these are
shallow (in general only approximately 0.25 m deep at least during the summer) they
are not difficult to cross but it may take some time if the stones in the river are slippery
and it should be avoided getting a wet foot. It is estimated that the time spent to cross a 5 metre wide river was 17 seconds. From the stereo-photographs mentioned above the
locations of major and minor rivers were digitized and converted to a grid file with a
spatial resolution of 5 metres. All rivers' cells were then assigned a value of 17 indicating
the time to cross 1 cell in the field. The extent of Lake Fjallavatn in the western part of the area was digitized from the
aerial photographs as well. As the lake is very deep just a few metres from the shoreline
it is considered that the lake should be treated as an absolute barrier and, thus, all cells
within the lake were assigned the value 9999 (like the slopes mentioned in the previous
section). The local sum on a cell-by-cell basis of the friction values in the grids A and B now
expresses the total friction of walking around the area of interest. The summed friction
values are presented in Fig. 3. Figure 3 Presentation of the friction values within the area and the locations of the 16 rain gauges (1-16) and the base camp (17).
Creation of the cost surfaces A shapefile called stations.shp represents the location of the 16 rain gauges set up
within the study area together with the location of a base camp (point no. 17) - the
starting point of all daily inspection trips to the rain gauges. The locations of these 17 points were then used individually to calculate 17 independent
cost surfaces using Spatial Analyst's costsurface algorithm - one cost surface for each
location - as presented in the process diagram, Figure 2. If, for example, a cost surface
was accumulated from point no. 1 and outwards this surface was later used to find the
paths from all the other 16 individual locations and back to point no. 1 using Spatial
Analyst's costpath algorithm. In this way all least cost paths between all points were
calculated and the resulting paths from these 17 shapefiles were then merged into one
single shapefile. So, this shapefile includes 17x16 paths interconnecting all points that
should be visited daily, see Figure 4.
Slope in %
Time in seconds 0-12
4 12-19
5 20-25
6 25-29
7 29-30
8 30
9999
