Paper presented at the 2005 Intergraph User Conference, San Jose, USA.
Optimum Routing of Pipelines in Predefined Corridor Network
___________________________________________________________________________
Arvinder Bawa
___________________________________________________________________________
Introduction
Finding optimum ways to connect points on a CAD model is something that interests designers in a variety of application areas, such as Geographic Information Systems (GIS), transportation, PCB layouts, electrical cables and the routing of piping on a process plant layout. In GIS this may take the form of finding the best route to go from one location to another, using roads in a geographical model. In route planning for transportation often the shortest journey when passing through given key points, is of some interest. In problems relating to routing cables or pipelines around a plant, least cost is usually the prime criterion, and this may depend on fittings, structure of the carrying trays or racks and the cost of the pipe or cable itself.
The solution of this problem in many cases involves the use of Artificial Intelligence methods such as the heuristic or formal space search techniques. Within the search algorithms it is possible to follow different approaches which may lead to lengthy processing or large amounts of computer resource. In general 'off the shelf' software to solve typical routing problems are not numerous and can be expensive.
Because of the high cost of automatic routing software available in the marketplace, Air Products have opted to develop their own solution to the specific problem of finding optimum routing of pipelines that form the interconnection between plant equipment. The application uses MDL programs and DialogBoxes under Microstation and is intended for use in the bid phase of the project cycle, when alternatives need to be explored quickly. The paper describes how this system is used to create proposal estimation models and the approach taken to obtain optimum routes through user defined corridors.
The Overview
The general scenario of the use of this software is as follows.
* Assemble the requirements for a new project
* Choose equipment modules that may be used in this project
* Construct graphical layout of the equipment modules
* Construct pipeline interconnect points
* Define corridors that pipelines may follow
* Autoroute optimum pipelines
* Report autorouted pipeline materials
* Create interface data to other applications such as PDS and Modeldraft
* Construct estimates
The first two items in the above list deal with estimating activities and are outside the scope of the software described here. In the same way the last item would also belong to an estimating system. The automatic routing of pipelines in this software is part of the graphical set of activities which are highlighted in the above list.
The starting point in a sequence of operation of this software may be as shown Figure 1. Here a set of equipment module boundaries as selected for use in the project are shown on a plant boundary.
Figure 1. Plant area with selected equipment module boundaries
At this point module graphics may be relocated and populated with relevant equipment symbols. Other layout items may be drawn using conventional graphics. Figure 2 shows a possible layout of a typical plant.
Figure 2. Typical plant layout with items in required locations
The software is then used to define pipeline termination points and to layout pipe route corridors. Figure 3 shows the plant area in more detail, and the termination points can be seen as zero length lines (little squares) and the corridors are the dashed multiline elements.
Figure 3. Rearranged Equipment modules with Termination points and Corridors
The routing algorithms are then used to create the optimum pipelines. Figure 4 shows the result of this operation on the example used here.
Figure 4. Final result after routing pipelines
At this stage the user would typically review the pipelines generated and ensure that all routings are logical with believable quantities. The layout of the equipment and choice of routing parameters may need to be reviewed for any rogue results and the routings generated again until a satisfactory arrangement is obtained.
At the end of the routing all external interfaces are created and the material reports are generated. These may then be picked up by the estimating systems to construct the relevant documents.
Autoroute Software Main Functions
The main functions in the Routing software consist of the following.
* Import of equipment modules based on information stored in libraries
* Facilities to define interconnection points for routing pipelines
* Facilities to define corridor networks along which the pipelines can run
* Facilities to control the routing of pipelines
* Facilities to review the generated pipelines
* Functionality to build interface files to external systems
Termination Points
The termination points represent pipeline start and end points. Physically they are zero length lines with pipeline attribute data such as name, size, spec, fluid and insulation information. The user can create, review, modify or delete these points using the facilities provided by the system. Additionally the direction in which a pipeline leaves a termination point can be selected by the user and this affects the end conditions of the pipeline route.
Corridors
Corridors are orthogonal horizontal spaces which can be used by pipelines when routing. For the routing process they act as attractors and the user can specify which type of corridors a pipeline can route through. Corridors are constructed as multiline elements with attribute data about their structural type. The system incorporates rules for determining which corridor the pipeline uses to enter and leave the network and the optimum route is then determined between these points.
As pipelines are routed thay are spaced on the corridor according to standard practice and when there is no more space at a certain elevation the software builds the next layer of pipelines at a user specified layer spacing. The user reviews the use of all corridors at the end of the routing process to determine the practicality of having over or under populated corridors.
Routing Process
The Autoroute system builds a list of pipelines to be routed and determines how many nodes define the pipeline. Lines that are defined as having more than two termination points are treated as several two noded pipelines emanating from the same initial point. A topography building routine disassembles these lines and reassembles them by removing sections which are duplicated over the lines generated between different pairs of these points.
Each pair of points is processed through the optimum route algorithm to determine which corridor network nodes lie in the path of the route. The routings must follow a set of rules some of which are discussed in the section below. Once the topography of each line has been determined then the system will generate the necessary interface files to pass data to the relevant estimating or design systems.
For a pipeline to route successfully along the corridors available a link must exist through the network between the start and end points. If this link is not found then the system defaults to a direct route outside the corridor networks. This generates some material quantities for the pipeline which may be incorrect, and the user needs to review the pipelines to improve the routing where possible.
The processing of the search algorithm is fast and in tests up to a hundred lines have been generated in interactive sessions in 30 seconds. This allows various cases to be analysed quickly and progressively the user may arrive at a usable layout.
The system provides functionality to review the routes generated and the materials associated with each line, and the user can use this to determine the acceptability of each pipeline routed.
Routing Rules
The generation of the topology of a pipeline follows a certain set of rules which may be classed under the following headings:
* Corridor entry/exit rules
* Change of direction rules and
* Rules for pipeline spacing on a corridor
See Figure 5 below which pictorially defines these categories
Figure 5. Rules for pipeline topology
These rules typically define how pipelines enter and leave corridors and how they are spaced on a corridor. Pipelines enter and leave corridors vertically. External tables are used to define pipeline spacing as acceptable for insulation and access and the process work practice defines the rest of the rules.
Best Route Algorithm
The algorithm at the heart of this system uses a depth first, space search technique to arrive at the best routes. The difference between the approach taken here and most of the software in the marketplace is that instead of using shape based routines to optimise, here the corridors are the only spaces in which the pipelines can route. In applications where this software is to be used the corridors are usually orthogonal and this makes the task of reaching optimum solutions somewhat easier. The corridors act as attractors and links between corridors are searched until the destination point is located.
However instead of mapping the entire network space this algorithm uses strategic blocks of routes that it has examined to guide the algorithm to search all the possibilities. In general this presents quite a problem but, by making use of several layers of blocks and some application specific rules, solutions are achieved quickly. The main advantage of this method is that the memory requirements are low and since the searches are manipulating small arrays the processing is fast.
The other technique used in limiting the processing required is to introduce some intelligent rules. Some of the rules associated with this algorithm are given below.
* The pipeline can only route through selected corridor types
* The route must meet optimum criteria
* The route must not use the same corridor twice
* The route must not pass through the same point twice
Once the optimum route has been determined the software performs the following steps for each pipeline before proceeding to the next pipeline route.
* Build the topology of the pipeline following the rules built into the system
* Use the topology to display the pipeline graphically
* Construct the material data for the pipeline and add to MTO file
* Construct information to review the pipeline at the end of the routing process
* Construct the PDS Alpha Language file for subsequent use in PDS
If a route is not possible between the given points then the system builds a default topology which connects the two points with a minimum number of changes of direction, outside of all corridors.
When all pipelines have been routed the software puts corridor usage information in a report before returning control to the user in the graphical environment.
Autoroute System Interfaces
The following list describes the interfaces of this system with other software, some of which have already been mentioned above.
* Graphical interface with Plant layout facilities and equipment libraries
* Graphical interface with Civil applications for calculation of foundation volumes
fencing, access ways etc.
* Material interface with estimation systems
* Neutral file interface with Plant Design System
* Neutral file interface with structural design and modelling of racks etc.
Current Developments
The use of the autorouting software has led to new ideas from the user community which requires continuous improvement of the software, and extension of the facilities provided. Some of these ideas lead to situations which may be better handled in design systems, however to achieve accurate material quantities it is necessary to include special cases which fall outside the general functionality of this system.
The items currently under consideration include the following:
* Hybrid corridors.
These include corridors which have different elevations along their length. Such corridors may be used when trying to represent access ways, for example, where pipelines are either raised or lowered under a road.
* Special cases of pipelines.
In general the software is aimed at interconnection pipeline which is considered to be homogeneous between fittings. However some special cases fall outside the general functionality. These include ring mains and large bore pipelines that change diameter along their length.
* Quality control.
All rules are continuously under review to compare material generated with past projects to obtain a confidence level of quality. In tests conducted so far the quantities are within 5 percent of the manually calculated values.
Last Word
The decision to develop or purchase software of this nature is difficult, however in this case the cost of the solutions in the marketplace created the incentive to develop. Since the problem to be resolved was very specific, it was possible to reach an acceptable solution. From the user point of view it was imperative that the system should be simple, reliable and interactive. Therefore the success of the system depended on, among other considerations, the ability to analyse conditions quickly so that a user could experiment with plant layout. This has been achieved.
The theory of using this software is straight forward.
The user can save time in analysing different scenarios.
If historical project data exists then the proposal model would take little effort.
The estimation cycle can therefore be reduced dramatically.
The practice of the use of this software may be different.
The successful implementation will depend on how this software fits into the work practice of producing estimates and how it can be used to develop the design stages of the project cycle. Additionally the software needs to be compatible with the new technologies now emerging, such as Intergraph's Jupiter based software, to succeed in the long term.
Acknowledgments
In developing the route search algorithms the author would like to acknowledge the following sources of inspiration:
Lugar G.F. and Stubblefield W.A., Artificial Intelligence-Structures and Strategies for Complex Problem Solving, Benjamin Cummings, 1993.
Hofstadter D.R., Godel, Escher & Bach-The Eternal Golden Braid, Penguin, 1979.
Optimum Routing of Pipelines in Predefined Corridor Network
___________________________________________________________________________
Arvinder Bawa
___________________________________________________________________________
Introduction
Finding optimum ways to connect points on a CAD model is something that interests designers in a variety of application areas, such as Geographic Information Systems (GIS), transportation, PCB layouts, electrical cables and the routing of piping on a process plant layout. In GIS this may take the form of finding the best route to go from one location to another, using roads in a geographical model. In route planning for transportation often the shortest journey when passing through given key points, is of some interest. In problems relating to routing cables or pipelines around a plant, least cost is usually the prime criterion, and this may depend on fittings, structure of the carrying trays or racks and the cost of the pipe or cable itself.
The solution of this problem in many cases involves the use of Artificial Intelligence methods such as the heuristic or formal space search techniques. Within the search algorithms it is possible to follow different approaches which may lead to lengthy processing or large amounts of computer resource. In general 'off the shelf' software to solve typical routing problems are not numerous and can be expensive.
Because of the high cost of automatic routing software available in the marketplace, Air Products have opted to develop their own solution to the specific problem of finding optimum routing of pipelines that form the interconnection between plant equipment. The application uses MDL programs and DialogBoxes under Microstation and is intended for use in the bid phase of the project cycle, when alternatives need to be explored quickly. The paper describes how this system is used to create proposal estimation models and the approach taken to obtain optimum routes through user defined corridors.
The Overview
The general scenario of the use of this software is as follows.
* Assemble the requirements for a new project
* Choose equipment modules that may be used in this project
* Construct graphical layout of the equipment modules
* Construct pipeline interconnect points
* Define corridors that pipelines may follow
* Autoroute optimum pipelines
* Report autorouted pipeline materials
* Create interface data to other applications such as PDS and Modeldraft
* Construct estimates
The first two items in the above list deal with estimating activities and are outside the scope of the software described here. In the same way the last item would also belong to an estimating system. The automatic routing of pipelines in this software is part of the graphical set of activities which are highlighted in the above list.
The starting point in a sequence of operation of this software may be as shown Figure 1. Here a set of equipment module boundaries as selected for use in the project are shown on a plant boundary.
Figure 1. Plant area with selected equipment module boundaries
At this point module graphics may be relocated and populated with relevant equipment symbols. Other layout items may be drawn using conventional graphics. Figure 2 shows a possible layout of a typical plant.
Figure 2. Typical plant layout with items in required locations
The software is then used to define pipeline termination points and to layout pipe route corridors. Figure 3 shows the plant area in more detail, and the termination points can be seen as zero length lines (little squares) and the corridors are the dashed multiline elements.
Figure 3. Rearranged Equipment modules with Termination points and Corridors
The routing algorithms are then used to create the optimum pipelines. Figure 4 shows the result of this operation on the example used here.
Figure 4. Final result after routing pipelines
At this stage the user would typically review the pipelines generated and ensure that all routings are logical with believable quantities. The layout of the equipment and choice of routing parameters may need to be reviewed for any rogue results and the routings generated again until a satisfactory arrangement is obtained.
At the end of the routing all external interfaces are created and the material reports are generated. These may then be picked up by the estimating systems to construct the relevant documents.
Autoroute Software Main Functions
The main functions in the Routing software consist of the following.
* Import of equipment modules based on information stored in libraries
* Facilities to define interconnection points for routing pipelines
* Facilities to define corridor networks along which the pipelines can run
* Facilities to control the routing of pipelines
* Facilities to review the generated pipelines
* Functionality to build interface files to external systems
Termination Points
The termination points represent pipeline start and end points. Physically they are zero length lines with pipeline attribute data such as name, size, spec, fluid and insulation information. The user can create, review, modify or delete these points using the facilities provided by the system. Additionally the direction in which a pipeline leaves a termination point can be selected by the user and this affects the end conditions of the pipeline route.
Corridors
Corridors are orthogonal horizontal spaces which can be used by pipelines when routing. For the routing process they act as attractors and the user can specify which type of corridors a pipeline can route through. Corridors are constructed as multiline elements with attribute data about their structural type. The system incorporates rules for determining which corridor the pipeline uses to enter and leave the network and the optimum route is then determined between these points.
As pipelines are routed thay are spaced on the corridor according to standard practice and when there is no more space at a certain elevation the software builds the next layer of pipelines at a user specified layer spacing. The user reviews the use of all corridors at the end of the routing process to determine the practicality of having over or under populated corridors.
Routing Process
The Autoroute system builds a list of pipelines to be routed and determines how many nodes define the pipeline. Lines that are defined as having more than two termination points are treated as several two noded pipelines emanating from the same initial point. A topography building routine disassembles these lines and reassembles them by removing sections which are duplicated over the lines generated between different pairs of these points.
Each pair of points is processed through the optimum route algorithm to determine which corridor network nodes lie in the path of the route. The routings must follow a set of rules some of which are discussed in the section below. Once the topography of each line has been determined then the system will generate the necessary interface files to pass data to the relevant estimating or design systems.
For a pipeline to route successfully along the corridors available a link must exist through the network between the start and end points. If this link is not found then the system defaults to a direct route outside the corridor networks. This generates some material quantities for the pipeline which may be incorrect, and the user needs to review the pipelines to improve the routing where possible.
The processing of the search algorithm is fast and in tests up to a hundred lines have been generated in interactive sessions in 30 seconds. This allows various cases to be analysed quickly and progressively the user may arrive at a usable layout.
The system provides functionality to review the routes generated and the materials associated with each line, and the user can use this to determine the acceptability of each pipeline routed.
Routing Rules
The generation of the topology of a pipeline follows a certain set of rules which may be classed under the following headings:
* Corridor entry/exit rules
* Change of direction rules and
* Rules for pipeline spacing on a corridor
See Figure 5 below which pictorially defines these categories
Figure 5. Rules for pipeline topology
These rules typically define how pipelines enter and leave corridors and how they are spaced on a corridor. Pipelines enter and leave corridors vertically. External tables are used to define pipeline spacing as acceptable for insulation and access and the process work practice defines the rest of the rules.
Best Route Algorithm
The algorithm at the heart of this system uses a depth first, space search technique to arrive at the best routes. The difference between the approach taken here and most of the software in the marketplace is that instead of using shape based routines to optimise, here the corridors are the only spaces in which the pipelines can route. In applications where this software is to be used the corridors are usually orthogonal and this makes the task of reaching optimum solutions somewhat easier. The corridors act as attractors and links between corridors are searched until the destination point is located.
However instead of mapping the entire network space this algorithm uses strategic blocks of routes that it has examined to guide the algorithm to search all the possibilities. In general this presents quite a problem but, by making use of several layers of blocks and some application specific rules, solutions are achieved quickly. The main advantage of this method is that the memory requirements are low and since the searches are manipulating small arrays the processing is fast.
The other technique used in limiting the processing required is to introduce some intelligent rules. Some of the rules associated with this algorithm are given below.
* The pipeline can only route through selected corridor types
* The route must meet optimum criteria
* The route must not use the same corridor twice
* The route must not pass through the same point twice
Once the optimum route has been determined the software performs the following steps for each pipeline before proceeding to the next pipeline route.
* Build the topology of the pipeline following the rules built into the system
* Use the topology to display the pipeline graphically
* Construct the material data for the pipeline and add to MTO file
* Construct information to review the pipeline at the end of the routing process
* Construct the PDS Alpha Language file for subsequent use in PDS
If a route is not possible between the given points then the system builds a default topology which connects the two points with a minimum number of changes of direction, outside of all corridors.
When all pipelines have been routed the software puts corridor usage information in a report before returning control to the user in the graphical environment.
Autoroute System Interfaces
The following list describes the interfaces of this system with other software, some of which have already been mentioned above.
* Graphical interface with Plant layout facilities and equipment libraries
* Graphical interface with Civil applications for calculation of foundation volumes
fencing, access ways etc.
* Material interface with estimation systems
* Neutral file interface with Plant Design System
* Neutral file interface with structural design and modelling of racks etc.
Current Developments
The use of the autorouting software has led to new ideas from the user community which requires continuous improvement of the software, and extension of the facilities provided. Some of these ideas lead to situations which may be better handled in design systems, however to achieve accurate material quantities it is necessary to include special cases which fall outside the general functionality of this system.
The items currently under consideration include the following:
* Hybrid corridors.
These include corridors which have different elevations along their length. Such corridors may be used when trying to represent access ways, for example, where pipelines are either raised or lowered under a road.
* Special cases of pipelines.
In general the software is aimed at interconnection pipeline which is considered to be homogeneous between fittings. However some special cases fall outside the general functionality. These include ring mains and large bore pipelines that change diameter along their length.
* Quality control.
All rules are continuously under review to compare material generated with past projects to obtain a confidence level of quality. In tests conducted so far the quantities are within 5 percent of the manually calculated values.
Last Word
The decision to develop or purchase software of this nature is difficult, however in this case the cost of the solutions in the marketplace created the incentive to develop. Since the problem to be resolved was very specific, it was possible to reach an acceptable solution. From the user point of view it was imperative that the system should be simple, reliable and interactive. Therefore the success of the system depended on, among other considerations, the ability to analyse conditions quickly so that a user could experiment with plant layout. This has been achieved.
The theory of using this software is straight forward.
The user can save time in analysing different scenarios.
If historical project data exists then the proposal model would take little effort.
The estimation cycle can therefore be reduced dramatically.
The practice of the use of this software may be different.
The successful implementation will depend on how this software fits into the work practice of producing estimates and how it can be used to develop the design stages of the project cycle. Additionally the software needs to be compatible with the new technologies now emerging, such as Intergraph's Jupiter based software, to succeed in the long term.
Acknowledgments
In developing the route search algorithms the author would like to acknowledge the following sources of inspiration:
Lugar G.F. and Stubblefield W.A., Artificial Intelligence-Structures and Strategies for Complex Problem Solving, Benjamin Cummings, 1993.
Hofstadter D.R., Godel, Escher & Bach-The Eternal Golden Braid, Penguin, 1979.
