Optimal Path Analysis and Corridor Routing: Infusing Stakeholder Perspective in Calibration and Weighting of Model Criteria


Berry, Joseph K.

Keck Scholar, Geography Department, University of Denver

Principal, Berry and Associates

2000 South College Avenue, Suite 300, Fort Collins, Colorado USA 80525

Email: jberry@innovativegis.com  Website: www.innovativegis.com/basis




The Least Cost Path (LCP) procedure for routing linear features was one of the earliest advanced applications of GIS technology.  While the technical approach has changed little from its earliest use, procedures for calibrating and weighting model criteria have radically changed.  Of the three basic steps in LCP analysis (discrete cost, accumulated cost, steepest path) the development of a robust discrete cost surface is the most critical.  It is imperative that this summary map appropriately reflect relative preference for various conditions within each map layer (calibration) and appropriately balance the relative influence among the map layers (weighting).  Technical considerations involving a consistent data range, map value normalization and treatment of exclusion areas are important, however the calibration and weighting of model criteria are the dominant factors.  They also are the most difficult to establish in a manner that fully engages domain expert and stakeholder perspectives.  This paper describes the use of modified Delphi and Analytical Hierarchical Process (AHP) techniques for quantitatively establishing calibration ratings and data layer weights.            




Determining the best route through an area is one of the oldest spatial problems.  Meandering animal tracks evolved into a wagon trail that became a small road and ultimately a super highway.  While this empirical metamorphosis has historical precedent, contemporary routing problems involve resolving complex interactions of engineering, environmental and social concerns. 


In the past, electrical transmission line and other siting applications required thousands of hours huddling around paper maps, sketching hundreds of possible paths, and then assessing their feasibility to “eyeball” the best route using a straight edge and professional experience.  While the manual approach capitalizes on expert interpretation and judgment, often it is criticized as a closed process that lacks a defendable, documented procedure and fails to fully engage alternative perspectives of what constitutes a preferred route.




The use of the Least Cost Path (LCP) procedure for identifying an optimal route based on user-defined criteria has been used extensively in GIS applications for siting linear features and corridors.  Whether applications involve movement of elk herds, herds of shoppers, or locating highways, pipelines or electric transmission lines, the procedure is fundamentally the same— 1) develop a discrete cost surface that indicates the relative preference for routing at every location in a project area, 2) generate an accumulated cost surface characterizing the optimal connectivity from a starting location (point, line or area) to all other locations based on the  intervening relative preferences, and 3) identify the path of least resistance (steepest downhill path) from a desired end location along the accumulated surface.  See Author’s Note 1 for more information on applying LCP to routing applications.


Figure 1.  GIS-based routing uses three steps to establish a discrete map of the relative preference for siting at each location, generate an accumulated preference surface from a starting location(s) and derive the optimal route from an end point as the path of least resistance guided by the surface.


Figure 1 schematically shows a flowchart of the GIS-based routing procedure for a hypothetical example if siting an electric transmission line that avoids areas that have high housing density, far from roads, near or within sensitive areas and have high visual exposure to houses. 


These four criteria are shown as rows in the left portion of the figure.  The Base Maps are field collected data such as elevation, sensitive areas, roads and houses.  Derived Maps use computer processing to calculate information that is too difficult or even impossible to collect, such as visual exposure, proximity and density.  The discrete Preference Maps translate this information into decision criteria.  The calibration forms maps that are scaled from 1 (most preferred—favor siting, grey areas) to 9 (least preferred—avoid siting, red areas) for each of the decision criteria.


The individual cost maps are combined into a single map by averaging the individual layers.  For example, if a grid location is rated 1 in each of the four cost maps, its average is 1 indicating an area strongly preferred for siting.  As the average increases for other locations it increasingly encourages routing away from them.  If there are areas that are impossible or illegal to cross these locations are identified with a “null value” that instructs the computer to never traverse these locations under any circumstances.




The technique generates accumulation surfaces from both the Start and End locations of the proposed powerline.  For any given location in the project area one surface identifies the best route to the start and the other surface identifies the best route to the end.  Adding the two surfaces together identifies the total cost of forcing a route through every location in the project area.


Figure 2.  The sum of accumulated surfaces is used to identify siting corridors as low points on the total accumulated surface.


The series of lowest values on the total accumulation surface (valley bottom) identifies the best route.  The valley walls depict increasingly less optimal routes.  The red areas in figure 2 identify all of locations that within five percent of the optimal path.  The green areas indicate ten percent sub-optimality.


The corridors are useful in delineating boundaries for detailed data collection, such as high resolution aerial photography and ownership records.  The detailed data within the macro-corridor is helpful in making slight adjustments in centerline design, or as we will see next month in generating and assessing alternative routes. 




Implementation of the LCP routing procedure provides able room for interpretation and relative preferences.  For example, one of the criteria in the routing model seeks to avoid locations having high visual exposure to houses.  But what constitutes “high” …5 or 50 houses visually impacted?  Are there various levels of increasing “high” that correspond to decreasing preference?  Is “avoiding high visual exposure” more or less important than “avoiding locations near sensitive areas.”  How much more (or less) important?


The answers to these questions are what tailor a model to the specific circumstances of its application and the understanding and values of the decision participants.  The tailoring involves two related categories of parameterization—calibration and weighting. 


Figure 3.  The Delphi Process uses structured group interaction to establish a consistent rating for each map layer.


Calibration refers to establishing a consistent scale from 1 (most preferred) to 9 (least preferred) for rating each map layer used in the solution.  Figure 3 shows the result for the four decision criteria used in the routing example. 


The Delphi Process, developed in the 1950s by the Rand Corporation, is designed to achieve consensus among a group of experts.  It involves directed group interaction consisting of at least three rounds.  The first round is completely unstructured, asking participants to express any opinions they have on calibrating the map layers in question.  In the next round the participants complete a questionnaire designed to rank the criteria from 1 to 9.  In the third round participants re-rank the criteria based on a statistical summary of the questionnaires.  “Outlier” opinions are discussed and consensus sought.


The development and summary of the questionnaire is critical to Delphi.  In the case of continuous maps, participants are asked to indicate cut-off values for the nine rating steps.  For example, a cutoff of 4 (implying 0-4 houses) might be recorded by a respondent for Housing Density preference level 1 (most preferred); a cut-off of 12 (implying 4-12) for preference level 2; and so forth.  For discrete maps, responses from 1 to 9 are assigned to each category value.  The same preference value can be assigned to more than one category, however there has to be at least one condition rated 1 and another rated 9.  In both continuous and discrete map calibration, the median, mean, standard deviation and coefficient of variation for group responses are computed for each question and used to assess group consensus and guide follow-up discussion.  See Author’s Note 2 for more information on applying Delphi to routing applications.   




Weighting of the map layers is achieved using a portion of the Analytical Hierarchy Process (AHP) developed in the early 1980s as a systematic method for comparing decision criteria.  The procedure involves mathematically summarizing paired comparisons of the relative importance of the map layers.  The result is a set map layer weights that serves as input to a GIS model. 


Figure 4.  The Analytical Hierarchy Process uses pairwise comparison of map layers to derive their relative importance.


In the routing example, there are four map layers that define the six direct comparison statements identified in figure 3 (#pairs = (N * (N – 1) / 2) = 4 * 3 / 2= 6 statements) as shown in figure 4.  Members of the group independently order the statements so they are true, then record the relative level of importance implied in each statement.  The importance scale is from 1 (equally important) to 9 (extremely more important).


This information is entered into the importance table a row at a time.  For example, the first statement in the figure views avoiding locations of high Visual Exposure (VE) as extremely more important (importance level= 9) than avoiding locations close to Sensitive Areas (SA).   The response is entered into table position row 2, column 3 as shown.  The reciprocal of the statement is entered into its mirrored position at row 3, column 2.  Note that the last weighting statement is reversed so its importance value is recorded at row 5, column 4 and its reciprocal recorded at row 4, column 5.  


Once the importance table is completed, the map layer weights are calculated.  The procedure first calculates the sum of the columns in the matrix, and then divides each entry by its column sum to normalize the responses.  The row sum of the normalized responses derives the relative weights that, in turn, are divided by minimum weight to express them as a multiplicative scale.  See Author’s Note 2 for more information on calculations and applying AHP to routing applications.


The relative weights for a group of participants are translated to a common scale then averaged before expressing them as a multiplicative scale.  Alternate routes are generated by evaluating the model using weights derived from different group perspectives. 


EPRI-GTC Transmission Line Siting EXPERIENCE


Figure 5 shows the results of applying different calibration and weighting information to derive alternative routes for a routing application in central Georgia.  Four routes and corridors were generated emphasizing different perspectives—Built environment (community concerns), Natural environment (environmental), Engineering (constructability) and the Simple un-weighted average of all three group perspectives.


These results are from a comprehensive model recently developed during a project funded by the Electric Power Research Institute (EPRI) and Georgia Transmission Corporation (GTC).  The project team consisted of academics, siting engineers, GIS specialists and various administrators, public relation personnel, legal advisors and other industry experts.  Several group sessions involving federal agencies, industry representatives and community groups were held that used Delphi and AHP to calibrate and weight more than twenty criteria.  See Author’s Note 3 for more information on the EPRI-GTC Transmission Line Siting Methodology.


While all four of the routes in figure 5 use the same criteria layers, the differences in emphasis for certain layers generate different routes/corridors that directly reflect differences in stakeholder perspective.  Note the similarities and differences among the Built, Natural, Engineering and un-weighted routes.  The bottom line is that the procedure identified constructible alternative routes that can be easily communicated and discussed. 


The final route is developed by an experienced transmission line siting team who combine alternative route segments for a preferred route.  Engineers make slight centerline realignments responding the detailed field surveys along the preferred, and then design the final pole placements and construction estimates for the final route.


Figure 5.  Alternate routes are generated by evaluating the model using weights derived from different group perspectives. (Courtesy of Photo Science and Georgia Transmission Corporation)


The ability to infuse different perspectives into the routing process is critical in gaining stakeholder involvement and identifying siting sensitivity.  It acts at the front end of the routing process to explicitly identify routing corridors that contain constructible routes reflecting different perspectives that guide siting engineer deliberations.  Also, the explicit nature of the methodology tends to de-mystify the routing process by clearly identifying the criteria and how it is evaluated.


In addition, the participatory process 1) encourages interaction among various perspectives, 2) provides a clear and structured procedure for comparing decision elements, 3) involves quantitative summary of group interaction and dialog, 4) identifies the degree of group consensus for each decision element, 5) documents the range of interpretations, values and considerations surrounding decision criteria, and 6) generates consistent, objective and defendable parameterization of GIS models. 




The use of Delphi and AHP techniques provides a structure for infusing diverse perspectives into calibrating and weighting criteria maps used in GIS-based routing.  Traditional siting techniques rely on unstructured discussions that often seem to mystify the routing process by not clearly identifying the criteria used or how it was derived and evaluated.  The approach described in this paper is objective, consistent and comprehensive and encourages multiple perspectives for generating alternative routes as well as thoroughly documenting the decision process itself.  The general approach is readily applicable to other siting applications of linear features, such as pipelines and roads. 


Author’s Notes:


1) The online book Map Analysis, Topic 19, “Optimal Paths and Routing” presents a detailed discussion on the Least Cost Path procedure for GIS-based identifying optimal routes and corridors.  See…



2) Supplemental discussion and an Excel worksheet demonstrating the calculations are posted at www.innovativegis.com/basis/, select “Column Supplements” for Beyond Mapping, September, 2003.

·         Delphi and AHP Worksheet an Excel worksheet templates for applying the Delphi Process for calibrating and the Analytical Hierarchy Process (AHP) for weighting as discussed in this sub-topic (GeoWorld, September 2003)

·         Delphi Supplemental Discussion describing the application of the Delphi Process for calibrating map layers in GIS suitability modeling

·         AHP Supplemental Discussion describing the application of AHP for weighting map layers in GIS suitability modeling

3) The EPRI-GTC transmission Line Siting Model methodology is discussed in detail in a GeoWorld feature article, April 2004, and is posted online in the GeoWorld archives at…


The EPRI-GTC project team consists of the author and Dr. Paul Zwick, Chair, Department of Urban and Regional Planning, University of Florida, Gainsville, Florida, Dr. Steven French, Director, Georgia Tech Center for Geographic Information Systems, Georgia Institute of Technology, Atlanta, Georgia, Dr. Elizabeth Kramer, Research Scientist, Institute of Ecology, University of Georgia, Athens, Georgia, several GIS specials headed by Jesse Glasgow, Senior GIS Analyst, Photo Science Incorporated, Tucker, Georgia and several siting engineers headed by Gayle Houston, Environmental and Regulatory Coordinator, Georgia Transmission Corporation, Tucker, Georgia.




Dr. Joseph K. Berry is the Principal of Berry and Associates // Spatial Information Systems, consultants and software developers in Geographic Information Systems (GIS) technology since 1986.  Also he serves as a Special Faculty member at Colorado State University and the Keck Scholar in Geosciences at the University of Denver.  He is the author of the “Beyond Mapping” column for GeoWorld and has written over two hundred papers on the analytic capabilities of GIS.  He is the author of the popular books Beyond Mapping and Spatial Reasoning and is involved in the development of the MapCalc software system for grid-based map analysis.  He holds a B.S. degree in forestry, a M.S. degree in business management emphasizing operations research and finance, and a Ph.D. emphasizing remote sensing and land use planning.