Joseph K. Berry

Senior Consultant, New Century Software

2627 Redwing Road, Suite 100, Fort Collins, Colorado, USA  80526

Phone: (970) 215-0825 – Email: joeb@newcenturysoftware.com


Michael D. King

Senior Pipeline Engineer, UTG-Pipeline Transportation, BP America

501 Westlake Park Boulevard, Houston, Texas, USA  77079


Chuck Lopez

Senior Engineer, SAIC

501 Westlake Park Boulevard, Houston, Texas, USA  77079


<Click here> for a printer-friendly copy (.pdf)




A .NET web-based application for siting pipelines is described that integrates a routing model for alternative route generation and hydraulic, cost and economic models for evaluation and selection of the best route.  The routing model identifies a project area, start and end points and then invokes one of three routing model levels depending on data availability and resolution to identify an optimal route and corresponding corridor containing the top Nth best paths.  The approach used in development of the routing model (ArcGIS) is discussed including criteria selection, map layer calibration and weighting.  The route evaluation and selection process is extended through an integrated hydraulic model (Excel) to optimize pipe diameter, compressor station location and other engineering factors; a cost model (Excel) to estimate construction cost based on several GIS-derived and user-defined factors; and an economic simulation model (Excel) to investigate economic viability over the project life.  Lessons learned in the four major aspects of project development are presented—routing model, database development, model integration and web-based deployment.




The Least Cost Path (LPC) method for determining the optimal route of a linear feature is a well-established grid-based GIS technique.  It consists of three basic steps: Discrete Cost Map, Accumulated Cost Map and Optimal Route.  An optional step to derive an Optimal Corridor often is performed to identify routing “pinch points” throughout a project area.


The first and most critical step establishes the relative “goodness” for locating a pipeline at any grid cell in a project area.  The individual map layers are calibrated from 1= best to 9= worst conditions for locating a pipeline.  In turn, the calibrated maps are weight-averaged to derive a Discrete Cost Map as shown in figure 1.


(Paper with full color figures is posted online at www.innovativegis.com/basis/Present/GITA_Oil&Gas_04/ )


Figure 1. Discrete Cost Map.


Saddle points between areas of high cost act as “passes” that severely constrain routing in a manner analogous to early explorers crossing a mountain range.  However, the explorers had to tackle each situation independently as they encountered them and a wrong choice early in the trek could commit them to punishing route that was less than optimal.  The second and third steps of the LCP procedure, on the other hand, enable a comprehensive analysis of the discrete cost map to identify the optimal route.  


Figure 2. Accumulated Cost Map.


The second step of the LCP procedure uses a propagating wave-front from a starting location to determine the least “cost” to access every location in the project area (figure 2).  It is analogous to tossing a rock or stick into a pond with the expanding ripples indicating the distance away.  In this case however, the computer moves one “ripple” away from the start and incurs the cost indicated on the discrete cost map—if it is an easy “low cost” step the value would be 1.0 (or 1.414 for a diagonally adjusted step).  If the step to the next ring also is easy, the accumulated cost would be 1+1= 2.  On the other hand, if the first two steps were high cost steps the accumulated cost would be 9+9=18.


As the expanding ripples move across the discrete cost map an Accumulated Cost Map is developed by recording the lowest accumulated cost for each grid cell.  In this manner the total “cost” to construct the preferred pipeline from the starting location to everywhere in the project area is quickly calculated.


Note that the accumulation surface has a bowl-like appearance with the starting location at the bottom (zero cost).  All of the other locations have increasing accumulated cost values with the increase for each step being a function of the discrete cost of traversing that location.  The ridges in the bowl reflect areas of high cost; the valleys represent areas of low cost.  Note the effect around the low cost “pass” areas.  The contour lines of accumulated cost seem to shoot out in these areas indicating lower total cost than their surroundings.  The same areas in the 3D view appear as saddles along the ridges—points of least resistance (total cost) on the slopping bowl-like surface.


Figure 3. Optimal Route.


The bowl-like nature of the accumulated cost map is exploited to determine the Optimal Route from any location back to the starting location (figure 3).  By simply choosing the steepest downhill path over the surface, the path that the wave-front took to reach the end location is retraced. 


By mathematical fact this route will be the line having the lowest total cost connecting the start and end locations.  Note that the route in the figure goes through the two important “passes” that were apparent in both the discrete and accumulated cost maps.


The optimal corridor identifies the Nth best route.  These form a set of “nearly optimal” alternative routes that a siting team might want to investigate.  In addition, optimal corridors are useful in delineating boundaries for detailed data collection, such as high resolution aerial photography and ownership records. 


The Optimal Corridor Map (figure 4) is created by calculating an accumulation cost map from the end as well as the starting location.  The two surfaces are added together to indicate the effective “cost” distance from any location along its optimal path connecting the start the end locations. 


The lowest value on this map forms the “valley floor” and contains the optimal route.  The valley walls depict increasingly less optimal routes.  Nearly optimal routes are identified by “flooding” the surface. 


Figure 4. Optimal Corridor.


In the example, a 5% optimal corridor is shown.  Notice the “pinch point” along the route at the location of the low cost “passes.”  The corridor is allowed to spread out in areas where there is minimal cost difference but is tightly contained around critical routing locations.




The data supporting the routing collaboration tool is organized into two databases—the Application Database consisting of numerous tables that store program initialization, input and output information and other necessary data and the GIS Database containing all of the input and output mapped data.  The GIS data is organized into three levels: global (1km), regional (30-90m) and local (<30m) resolution. The global database is always online for macro corridor analysis while the regional and local databases are developed on a project basis for detailed routing considerations.


Figure 5 identifies the basic set of data used and processing steps at the regional level of analysis.  The twenty-three criteria maps are divided into five categories—Exclusion, Environmental, Construction, Hazards and Consequences.  The exclusion maps identify locations that prohibit pipeline siting, such as large water bodies or extremely steep slopes.  The other categories identify locations that siting could take place but with varying degrees of preference, or “cost.” For example, certain land cover types such as grasslands are much better for pipeline location than dense forests.  Similarly, gentle slopes are preferred over steeper ones and loose soils preferred over extremely rocky outcrop areas.  


Each of the individual criteria maps are calibrated to a preference scale from 1= best through 9=worst location for siting a pipeline.  This critical step incorporates expert judgment on the relative “goodness” for the different conditions occurring on a map.  The calibrated map layers within a category are in turn weighted to reflect their relative importance compared to the other maps in the category.  For example in the Construction category, Terrain Slope is deemed eight times more important than Land Use classification.



Figure 5.  Model Criteria Map Processing.


The final step in deriving an overall cost surface involves weight-averaging the five category maps (all maps equally weighted as 1 in figure 5) and “masking” the result with the exclusion areas.  The final map layer identifies whether any location could contain a pipeline (Exclusion= null), and if so, what is its relative goodness (1 to 9 worst).  The routing procedure uses this information in attempting to follow a path of smaller avoidance values.  However, a location with a high avoidance value (cost) could be part of the solution if a direct path through it is more optimal and results in the lowest total cost for the entire route.


Figure 6 shows the results of a route simulation with a 1% corridor from Fort Collins, Colorado to San Diego, California considering just terrain slope.  The process took about 10 minutes to run using the global level data. 


The results identify a route/corridor moving along the Colorado Front Range, down through New Mexico and across Arizona to Southern California.  However, note that there is also a little corridor that runs a bit further to the north that happens to follow Interstate 40 (coincidence?) for a large portion of the route.  The result of another simulation relaxing the corridor to 4% of the best paths enlarges the feasible planning space.     


Traditional routing procedures would “box” a large area around the begin/end points and collect detailed data within the entire box.  The global level analysis suggests that information in the northwest is not needed as none of the top potential routes (1% to 4% optimal corridors) seek solution in this area. 


Figure 6.  Route Simulation Example.


In practice, the model would be run several times varying criteria map layers and weighting to more fully understand the routing sensitivities for a proposed pipeline.  Where the route/corridor changes, and doesn’t change, is valuable information for determining regional level data acquisition and model simulations to identify the best pipeline route.


Once a candidate route has been generated it is evaluated for its hydraulic engineering, construction cost and economic viability.  The route is divided into segments and then metrics are derived for Hydraulic and Cost model input.  The hydraulic segmentation procedure is terrain-based and divides a route into variable length segments that represent similar terrain configuration as determined by major inflection points and slope characteristics.  Necessary spatial information, such as soil and terrain factors are assigned to each segment and automatically passed to the Excel-based Hydraulic Model and combined with other user specifications to determine the optimal engineering design of the pipeline route, such as pipe characteristics and compressor station types and locations.


In turn, the output from the Hydraulic Model is passed to a Cost Model for use in deriving construction costs associated with the proposed pipeline.  In addition, the route is re-segmented to reflect spatial considerations, such as river/road crossings, land use and soil conditions impacting construction.  The result is a detailed report of maps, charts and tables of the estimated cost to construct the pipeline.  In the final step, the cost data is passed to the Economic Model that assesses the financial viability over the project life based on fiscal considerations, such as initial and operating costs, projected revenue stream and interest rates.




The pipeline routing application consists of three broad components— Databases , Models and Web Environment.  The databases provide a standardized schema for storage of application and spatial data.  The models are used for generating feasible pipeline routes and evaluating their hydraulic, cost and economic considerations to better understand the siting sensitivity within a project area and ultimately selection of the best route.  The web environment controls user access and security, viewing existing project data and simulations, generating new simulations, storage of results and database maintenance. 


Upon logging-in, users are presented with a listing of existing projects they are authorized to view (left side of figure 7).  Selecting a project enables them to interact with existing project simulations they or others have created, or generate new project simulations to identify new alternative routes or to specify different evaluation model assumptions.


When a user selects an existing project an interactive map view and tabular description is generated.  If the user is authorized, a new project area can be defined by zooming/panning on a global map set and either click-and-drag a rectangular box or entering the latitude/longitude coordinates of the project extent.  Once a new project is established the project Administer assigns users and the Data Administrator adds additional map layers beyond the standard global data set as appropriate for the level of analysis anticipated. 



Figure 7. Project Listing and Simulation Tree Interfaces.


Another way to view an existing or new project is through its simulations (right side of figure 7).  A “tree-view” of the existing simulations for a project organizes the sets of Routing, Hydraulic, Cost and Economic simulations as separate branching levels.  The base of the tree is the user’s assigned projects.  The first branch identifies all of the alternative routes developed for the project area.  Within each route simulation the cascading hydraulic, cost and economic simulations are hierarchically listed. 


This organization follows the processing flow of first generating a potential route and then using the route segment summaries and user input to execute Hydraulic, Cost and Economic simulations input into the Hydraulic and Cost models.  The tree-view can be expanded and collapsed for easy viewing.  Selecting an existing simulation displays its results in graphic, tabular or chart form.  At any level, a user can specify an entirely new simulation or clone an existing simulation then edit its input parameters to generate a new simulation.  New simulations are queued for processing, its status is tracked and an email is sent to the user when it is complete. 


Administrator level users provide overall program management.  The User Administrator oversees user access, authorization and security.  The Project Administrator handles creation of new projects and assignment of users.  The Model Administrator is responsible for changes in the defaults values and logical structure of the routing, hydraulic, cost and economic models.  The Data Administrator manages the standard databases used by the application and is well-versed in GIS data issues for loading additional map data into the system as appropriate for new projects.




The Pipeline Routing Collaboration tool delivers cutting-edge capabilities for route generation and evaluation within a web-based environment.  Providing route simulation and evaluation capabilities as a web-based service enable personnel to pose “what if” scenarios in a collaborative environment, regardless of their location or special skills and equipment.


 The approach is analogous to a “spatial spreadsheet” enabling users to rapidly generate alternative routes and evaluate their relative engineering, cost and economic considerations.  This collaborative environment provides a GIS-based pipeline routing application that is objective, consistent, comprehensive and cost-effective.


The major advantages of the application include:


Ÿ         web-based service with access to maintained server hosting data storage, program executables/licenses, using a standard web browser;

Ÿ         collaborative environment organizing alternative simulations by multiple users;

Ÿ         fully integrated environment for pipeline route generation (Routing) and evaluation models (Hydraulic, Cost, Economic);

Ÿ         flexibility for adding, calibrating and weighting routing map criteria; and

Ÿ         minimal GIS experience required.


A working version of the tool is currently being refined with rollout planned for early fall.  




Berry, J. K., 2004.  Online book entitled Map Analysis, Topic 19, “Optimal Paths and Routing” at… www.innovativegis.com/basis/MapAnalysis/Default.html.   


Glasgow, J., et. al., 2004.  Online GeoWorld feature article entitled “A Consensus Method Finds Preferred Routing” at… www.geoplace.com/gw/2004/0404/0404pwr.asp.


LoPresti, F. and B.l Miller, 2004.  Online paper entitled “Finding the Best Path for a Pipeline: Interactive Route-Planning on NYU Web” at… www.nyu.edu/its/pubs/connect/archives/96summer/loprestipipeline.html.


Yusof, K. W. and S. Baban, 2004.  Online paper entitled “Least-cost Pipelines Path to the Langkawi Island, Malaysiaat… www.gisdevelopment.net/application/Utility/others/mi04053.htm.