International Construction Specialty Conference of the Canadian Society for Civil Engineering (ICSC) (5th : 2015)

A comparison of geographic intervention grouping methods for infrastructure intervention planning across… Kielhauser, Clemens; Adey, Bryan T.; Lethanh, Nam Jun 30, 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
52660-Kielhauser_C_et_al_ICSC15_255_A_Comparison_Of.pdf [ 487.04kB ]
52660-Kielhauser_C_et_al_ICSC15_255_A_Comparison_Of_slides.pdf [ 1.1MB ]
Metadata
JSON: 52660-1.0076360.json
JSON-LD: 52660-1.0076360-ld.json
RDF/XML (Pretty): 52660-1.0076360-rdf.xml
RDF/JSON: 52660-1.0076360-rdf.json
Turtle: 52660-1.0076360-turtle.txt
N-Triples: 52660-1.0076360-rdf-ntriples.txt
Original Record: 52660-1.0076360-source.json
Full Text
52660-1.0076360-fulltext.txt
Citation
52660-1.0076360.ris

Full Text

5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction    Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015   A COMPARISON OF GEOGRAPHIC INTERVENTION GROUPING METHODS FOR INFRASTRUCTURE INTERVENTION PLANNING ACROSS MULTIPLE NETWORKS Clemens Kielhauser1,2, Bryan T. Adey1 and Nam Lethanh1 1 Swiss Federal Institute of Technology (ETH), Switzerland 2 kielhauser@ibi.baug.ethz.ch Abstract: Interventions on infrastructure networks in municipalities cause disruptions to the service provided by the network that requires the intervention. They also cause disruptions to the service provided by other networks that have to be at least partially shut down so that the intervention can be executed. Due to these effects, there is substantial benefit to be obtained by grouping interventions on all networks that are spatially close to one another, i.e. work programs for spatially close networks should be developed together. This benefit is principally due to reduced interruption to services and reduced costs of intervention. The challenge of determining such combined optimal work programs is made more difficult as it requires quantification of the value of lost services, which depends on how different stakeholders value the services as well as how the services are interrupted. In this paper the difference between two methodologies to be used to develop work programs on spatially close infrastructure networks is shown: 1) a traditional methodology based on a grid-cell based grouping method, and 2) a methodology based on a combined topology / Voronoi cell / density based clustering of interventions. Both methodologies exploit recent developments in the area of critical infrastructures and GISs. The differences are illustrated by using both methodologies to determine combined work programs for five spatially close infrastructure networks (electricity, gas, water, sewage, roads) in a municipality with approximately 1'500 inhabitants. The advantages and disadvantages of each are discussed. 1 INTRODUCTION  Infrastructure networks (INs), such as electricity, gas, road, sewer, and water distribution networks are some of the main assets but also some of the main cost drivers of a municipality. Therefore, interventions on these networks should be carried out in a way that minimises the costs of intervention and the disruption of the service, i.e. an optimal work program (OWP) should be determined. Traditionally, the managers of each IN produce their own work programs. Example methodologies to find OWPs for single INs can be found in Fenner, Sweeting, and Marriott (2000), Miyamoto, Kawamura, and Nakamura (2000), Stillman (2003), Cardoso et al. (2004), Arthur et al. (2009), Dehghanian et al. (2013), Zayed and Mohamed (2013), Lethanh, Adey, and Sigrist (2014). These work programs are then discussed with those responsible for the other INs in order to reduce the impact on service disruption and costs by manually combining the work programs to create synergy effects.  In this paper a case study on a dynamic geographic intervention grouping method is presented. This method can be used to take into consideration the structural and functional differences, as well as the different ways that the networks are typically monitored, in an automated way. The resulting work program is compared with the work program 255-1 from a static geographic intervention grouping method presented in Kielhauser, Adey, and Lethanh (2014), herein referred to as the traditional methodology. 2 METHODOLOGY The concept of the herein presented dynamic neighbourhood methodology (DNM) is based on the concept of neighbourhood. The neighbourhood of object A is defined as the region around object A, where object B would be considered close if it lies within that region. The basic process for the DNM follows 7 steps, which are explained in the following sections and shown in Fig. 1.  Fig. 1: Methodology Flowchart 2.1 Step 1: Determine Level 1 objects In this process, objects with high priority (level 1 objects) are determined. In this paper, level 1 objects are defined as follows:  Level 1 objects are objects, which are in such a state (e.g. failure probability, condition, age, level of service) that an intervention on this object is justified on its own, i.e. the decision to do an intervention is independent from other objects.  In the first step of this process, triggers for selecting an object as a level 1 object are defined. These triggers are thresholds of one value or a combination of values of the object attributes. The attribute can be of the object itself, denoted as   with the subscript  ( ) representing the object ID, and/or of the network, denoted as  with the subscript  ( ) representing the network ID. The superscript  denotes the level 1 objects. An example of the former is object condition. An example of the latter is change in network reliability. Then, objects are compared with the triggers by using a selector function . It is defined as a logical function, with  (true) when an object is selected, and 0 otherwise. This selector function is applied to a set of all objects considered (based on the boundaries of the physical area to be analysed and the jurisdiction of the manager)  in order to obtain the logical selection vector for the level 1 objects : [1]  with object vector consisting of all objects : . 255-2 2.2 Step 2: Calculate Neighbourhood This process is used to determine the neighbourhood of all level 1 objects being investigated. This is accomplished by determining the topological neighbourhood, the distance neighbourhood and the Voronoi neighbourhood. The first two of these neighbourhoods refer to objects in the same network, the last refers to objects that are in the spatial neighbourhood of the level 1 objects but are in different INs than the level 1 object. To better explain the used three different neighbourhoods, Fig. 2a shows an example network with 7 objects. Logical nodes (denoted with  ) are nodes that signify a join between two or more objects. Geometric nodes (denoted with  ) are used to detail the object shape in between the endpoints (logical nodes). Lines with the same number are used to denote one object.          (a) Example network  (b) Voronoi cells for (c) Voronoi region for (d) Voronoi region for            with objects 1-7     network nodes     network element 1    network element 5 Figure 2: Network definitions 2.2.1 Topological Neighbourhood The topological neighbourhood of an object is based on the topological distance, i.e. the number of objects between two logical nodes. In that sense, two objects are neighbours if the network distance between their closest logical nodes is below a certain threshold. For example, if the focus is on object 6 and the distance threshold is 1, then objects 1, 2, 5, and 7 can be considered to be in the same neighbourhood, as at most 1 object (namely 5) has to be crossed to reach them. Mathematically, neighbouring objects can be found as follows: Starting from the incidence matrix  (i.e. a matrix describing which edges are connected to which nodes), all nodes reachable in a distance  can be calculated by: [2]  with  Reachability matrix of network  for  steps. Each element from  shows if a node is reachable from another node with a maximum of  steps. Combining those reachability matrices to a grand matrix gives the topological neighbourhood matrix : [3]   2.2.2 Distance Neighbourhood As the sizes of network objects can differ by orders of magnitudes (e.g. compare one valve with a 300m stretch of straight pipe), neighbourhoods can also be defined by distance along the network. This is an alternative neighbourhood definition, which only takes into account the physical distance of objects along the network. For this, an object is defined as a neighbour, if it can be reached within a certain distance along the network. For example, objects 3 and 5 are within a distance dtravel of each other, as shown in 255-3 Fig. 2a, as their closest nodes are within a distance of dtravel. Mathematically, the shortest path between all logical nodes q of all objects has to be calculated (or loaded from the database if available).    [4]  with all logical node pairs distance matrix for network m, all node pairs shortest path algorithm for networks as described in Johnson (1977). The minimal distance between all object pairs is then the minimum of the minimal distances between each objects' logical nodes:   [5]   with minimal distance matrix for all objects in network m, logical nodes of network m, and objects of network m. Comparing this minimal distance matrix with a distance threshold for each network m  gives the neighbourhood matrix : [6]   Combining those distance matrices into a grand matrix gives the neighbourhood matrix : [7]    2.2.3 Voronoi Neighbourhood Both topological and distance neighbourhood definitions have the prerequisite that all objects have to belong to the same network. To overcome this limitation, the neighbourhood can also be defined by Voronoi cells (Lejeune Dirichlet 1850). Figure 2b shows a Voronoi tessellation of the example network. Starting from a given set of core points  (in this case: all network nodes, both logical and geometric), Voronoi cells  consist of every point in space whose distance to  is less or equal to any other core point . A Voronoi region  for one object is then the set of all Voronoi cells emanating from the nodes of that object (Fig. 2c,d). Combining those regions gives the set of all Voronoi regions  for all objects . This can be used to define the neighbourhood as follows: objects A and B are neighbouring, if object B touches object A's Voronoi region. The neighbourhood can then be defined as: [8]     with Voronoi regions of objects , neighbourhood matrix for Voronoi methodology and the dyadic geometric intersection between  and .  255-4 2.2.4 Neighbourhood combination In the last activity of the dynamic neighbourhood calculation, all neighbourhoods are combined to a grand neighbourhood by combining all neighbourhood matrices to the dynamic neighbourhood matrix : [9]  with the symbol  denoting the logical “or”, which only returns a value of “1” if at least one input is “1”. In words, two objects are neighbours if they are either topological, distance or Voronoi neighbours. 2.3 Step 3: Determine close objects As next step, the so-called close objects are determined. Those objects are objects that are located in the neighbourhood which is defined by the dynamic neighbourhood matrix . This process ensures that only close objects, i.e. objects that are sufficiently near to level 1 objects are considered as level 2 objects in the next step, where the object condition is compared against a threshold likewise to the determination of level 1 objects. Mathematically, the whole process can be expressed in one equation: [10]  with binary variable vector indicating if object  is part of the close object set. The superscript  denotes the close objects, the superscript  denotes the DNM, and the symbol  denotes the material non-implication, which is an operator that only returns a value of “1” if the first input is “1” and the second input is “0”. In this case: an object is only a close object for the DNM if the object is within the same neighbourhood as a level 1 object  but has not been already selected as a level 1 object. 2.4 Step 4: Determine Level 2 objects  In this subprocess, objects with lesser priority (Level 2 objects) are determined. In this paper, level 2 objects are defined as follows. Level 2 objects are objects, which are in such a state (e.g. failure probability, age, level of service) that an intervention on this object is not justified on its own but the synergies created by doing a combined intervention with a level 1 object justify an intervention, i.e. the decision to do an intervention is dependent on other proximate objects.  The selection process is similar to the one for level 1, just with different trigger values.  2.5 Step 5: Group objects In this process, the level 1 and level 2 objects which have been identified in the previous steps, are combined into intervention groups, i.e. sets of interventions that are executed together, using the DBSCAN algorithm as described in (Ester et al. 1996). This algorithm takes the centroid point coordinates of the objects requiring intervention and two values as inputs: 1) Eps - the maximum distance in which two interventions should be grouped into one intervention group, and 2) MinPts - the number of interventions, that form an intervention group. Then, the points are classified as either belonging to a group or being single objects. If they belong to a group, then the interventions are included in the work program as a group, otherwise it has to be discerned between level 1 and level 2 objects. Level 1 single objects are also included in the work program as intervention, despite not being grouped, because per definition level 1 signifies that an intervention is justified even without grouping, whereas level 2 objects belonging to no group will be discarded. Mathematically:  255-5 [12]  with intervention group matrix for the DBSCAN clusters. The cost of each group is the sum of the setup costs  for executing all interventions in group  and the unit costs without setup costs for each intervention on each object of each network  multiplied by its size . [13]  with cost vector of intervention in all groups . The WP is simply the whole set of intervention groups, i.e. all rows of . The total costs are then simply the sum of the cost vector : [14]  2.6 Step 6: Rank groups  If there are constraints (e.g. budget constraints) and not all intervention groups can be included in the work program, a priority (related to the consequences that would be incurred due to service interruption if a failure occured) is calculated so that the groups with the highest priority can be included in the work program. It is in this methodology based on two components: a) The object priority value, which relates to the object itself and its role in the network, e.g. for a sewer network object how many upstream objects will also be blocked if this object has to be blocked for maintenance, and b) a multiplicative factor related to the location, e.g. population density of the area with service interruption. Although this is multiplicatively connected with the object priority value, it is kept separate because the population density for example is not network dependent, whereas the object priority value is. Mathematically: [15]  with priority vector of group , object priority vector based on object  and network ,  group priority vector based on group location, and  representing the element-wise multiplication of vectors.  From there, the rank  of a group can be calculated:  [16]  This results in the group with the highest priority  having the lowest rank . 2.7 Step 7: Add group to constrained work program The work program with constraints is constructed from the unconstrained work program: The groups included in the unconstrained work program are added one at a time to the constrained work program (i.e. a selection variable  is changed from 0 to 1) starting with the group with the highest priority (i.e. where , then where  etc.) and then the budget is checked. If the budget is not exceeded, 255-6 the group is kept and the group with the next highest priority is tried. This process is repeated until the sum of the costs of the groups in the work program reaches the budget limit : [17]  with binary vector indicating inclusion in WP (1=yes, 0=no), budget limit. The WP is the whole set of intervention groups  subsetted by the inclusion variable : [18]  The total costs are the sum of the cost vector  times the inclusion vector.  [19]   3 CASE STUDY The DNM was used to determine a work program for five proximate municipal infrastructure networks. This work program was then compared with the work program generated using a traditional methodology Kielhauser, Adey, and Lethanh (2014). The advantages and disadvantages of each will be discussed. 3.1 Overview The infrastructure networks (electricity, gas, roads, sewage, and water) used in this case study belong to a municipality with a population of ca. 1’500. The single network maps are shown in Fig. 3a – Fig. 3e.           (a) Electricity (b) Gas  (c) Roads (d) Sewer  (e) Water Figure 3: Network maps The objects in the electricity, gas, and water networks were considered to be in one of 2 condition states, operational and not operational, the objects in the sewer network were considered to be in one of 5 discrete condition states, and the road objects were considered to be in a continuous-range condition state between 0 and 5 (Tbl.1). The thresholds for level 1 and level 2 are shown in Tbl. 2, the costs for the interventions (given in monetary units mu) in Tbl. 3.  255-7 Table 1: Network characteristics at the time of investigation    Table 2: Threshold values for levels 1 and 2   Table 3: Intervention types and costs  Using steps 1-7, a work program (with a budget constraint of 200’000 mu) was calculated and compared to the WP obtained by using the method described in Kielhauser, Adey, and Lethanh (2014). To facilitate the comparison, the work programs will be referred to as WPD (with the D representing the DNM) and WPT (the T representing the traditional methodology). Tbl. 4 shows the results.  Table 4: Results This table shows that the traditional methodology selects 4 objects for the work program. A total amount of 861.6m will be renewed. With only 300'000 mu available, the total cost is 287’387 mu, which means a budget utilisation of 96%. The DMN selects 6 objects with a total length of 874.5m for the work program.  Length Objects No.of condition states Condition state (distribution)  [km] [-]  1 (as new) 2 3 4 5 (defunct) Electricity 20.6 2’226 2 100% - - - 0% Gas 6.8 351 2 100% - - - 0% Water 8.8 182 2 100% - - - 0% Road 9.7 104 cont. (0-1] 2.9% (1-2] 25.0% (2-3] 44.2% (3-4] 23.1% (4-5] 4.8% Sewer 5.3 215 5 97.2% 2.8% 0% 0% 0%  Electricity Gas Roads Sewer Water Type Failure probability Failure probability Condition state Transition probability Failure probability Level 1 0.025 0.025 3.67 0.020 0.020 Level 2 0.013 0.013 3.10 0.005 0.005  Electricity Gas Roads Sewer Water Setup cost Type Replacement Replacement Replacement Replacement Replacement Cost per intervention setup Value 100 150 350 250 300 1’500 Unit [mu/m] [mu/m] [mu/m] [mu/m] [mu/m] [mu] Effect As-new condition As-new condition As-new condition As-new condition As-new condition   Objects Intervention Cost Avg. cost per Removed  B   Groups Length  Group Object Length Age units   [-] [-] [m] [mu] [mu/1] [mu/1] [mu/m] [y] [mu/(m*y)] WPT 4 4 861.6 287’387 71’847 71’847 334 7’965 36.1 WPD 6 4 874.5 288’672 72’168 48’112 330 8’724 33.1 255-8 A total amount of 874.5m will be renewed. With total costs at 288’672 mu, the budget utilisation is also 96%. To be better able to compare the methodologies, we have used a proxy B which is the average amount of financial resources used to improve the age of the infrastructure, expressed as monetary units divided by the amount of removed age, multiplied by extent of the object. This indicator is based on the concept, that if it is assumed that an adequate level of service is always provided, the main goal of an infrastructure manager becomes the improvement of the infrastructure for the least cost. In this case, the best work program is the one that gives the highest improvement in the infrastructure provided for the least cost. For example, when a gas pipe is 70 years old and is replaced with a new identical pipe, it is considered to have improved the condition of the infrastructure by 70 years. When this is coupled with the costs to improve the condition, one gets the costs per time. 4 COMPARISON One of the first things that can be seen by comparing the two methodologies is the difference between the numbers of interventions proposed. For the case study, this difference originates in a part of the network that is shown in Fig. 4. The left half shows the WPT, the right shows the WPD. The dashed line represents the boundary of a grid cell. The line weight represents the different levels (thick: level 1, medium: level 2, grey: no selection). For the WPT, it can be seen that within the grid cell, the level 1 object also triggers an intervention on the adjacent level 2 object, because it is in the same grid cell. For WPD, additionally, another object is included, as it is only at a topological distance of 1 from the level 1 object. This shows the main benefit of the DNM: as the neighbourhood is calculated dynamically from the network, such boundary situations can be taken into account in contrast to the traditional methodology.  Figure 4: Difference in work program As can be seen in Tbl. 4, the cost/improvement ratio B  varies between the work programs. The work program determined using the DNM gives the best (i.e. lower) ratio (33.1 vs. 36.1). Therefore, the DNM performs better than the traditional methodology. This is due to the synergy effects created by the topological approach in contrast to the traditional approach. 5 CONCLUSION In this paper, two methodologies to determine work programs for municipalities possessing multiple infrastructure networks were investigated and compared. In the investigated example, the methodologies were used to determine work programs for five infrastructure networks in a municipality with a population of ca. 1'500. It was found that the DNM for grouping objects in need of intervention within a network and on multiple networks leads to improvements over the traditional methodology. This demonstrated that the explicit consideration of the proximity of objects within multiple networks should be systematically done. It was found that the DNM leads to work programs that generated lower per unit improvement costs than the traditional methodology. This is because the traditional methodology relies on predefined grid cells, while the DNM dynamically calculates those from the individual network data. 255-9 Keeping this in mind, future research in this direction should include: • the enhancement of the investigated methodologies to determine work programs using more direct consideration of the costs of service interruption  • the extension of the investigated methodology to determine work programs over multiple time periods • the adaptation of the investigated methodology to take into consideration functional relationships between the objects within one network and within multiple networks, e.g. the effect on the amount of water flowing in a waste water network due to interventions being executed on a sewer network and a heavy rain fall occurring • the enhancement of the investigated methodology to better take into consideration real world costs, i.e. more accurate representations of the variant and invariant costs involved with intervening on one or more networks, and on one or more objects • the comparison of these methodologies with a real world situation to investigate the potential advantages and disadvantages of its use in practice References Arthur, Scott, H Crow, L Pedezert, and N Karikas. 2009. “The Holistic Prioritisation of Proactive Sewer Maintenance.” Water Science and Technology 59 (7): 1385–96. Cardoso, Maria, Sérgio Coelho, Rafaela Matos, and Helena Alegre. 2004. “Performance Assessment of Water Supply and Wastewater Systems.” Urban Water Journal 1 (1): 55–67. doi:10.1080/15730620410001732053. Dehghanian, Payman, Mahmud Fotuhi-Firuzabad, Farrokh Aminifar, and Roy Billinton. 2013. “A Comprehensive Scheme for Reliability Centered Maintenance in Power Distribution Systems — Part I: Methodology.” Power Delivery, IEEE Transactions on 28 (2): 761–70. doi:10.1109/TPWRD.2012.2227832. Ester, Martin, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.” In Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96). Fenner, Richard A., L. Sweeting, and Martin J. Marriott,. 2000. “A New Approach for Directing Proactive Sewer Maintenance.” Proceedings of the ICE - Water and Maritime Engineering 142 (Volume 142, Issue 2): 67–77(10). doi:10.1680/wame.2000.142.2.67. Johnson, Donald B. 1977. “Efficient Algorithms for Shortest Paths in Sparse Networks.” J. ACM 24 (1): 1–13. doi:10.1145/321992.321993. Kielhauser, Clemens, Bryan T. Adey, and Nam Lethanh. 2014. “An Example of the Effect of Simultaneous Planning of Interventions on Proximate Infrastructure Networks.” In Proceedings of the CSCE 2014 General Conference / Congrès Général 2014 de La SCGC. Lejeune Dirichlet, G. 1850. “Über Die Reduction Der Positiven Quadratischen Formen Mit Drei Unbestimmten Ganzen Zahlen.” Journal Für Die Reine Und Angewandte Mathematik 40: 209–27. Lethanh, Nam, Bryan T. Adey, and Manuel Sigrist. 2014. “A Mixed-Integer Linear Model for Determining Optimal Work Zones on a Road Network.” In Proceeding of the International Conference on Engineering and Applied Sciences Optimization. KOS Island, Greece. Miyamoto, Ayaho, Kei Kawamura, and Hideaki Nakamura. 2000. “Bridge Management System and Maintenance Optimization for Existing Bridges.” Computer-Aided Civil and Infrastructure Engineering 15 (1): 45–55. doi:10.1111/0885-9507.00170. Stillman, R. H. 2003. “Power Line Maintenance with Minimal Repair and Replacement.” Reliability and Maintainability Symposium, 2003. Annual, 541–45. doi:10.1109/RAMS.2003.1182046. Zayed, Tarek, and Elsayed Mohamed. 2013. “Budget Allocation and Rehabilitation Plans for Water Systems Using Simulation Approach.” Tunnelling and Underground Space Technology 36 (0): 34–45. doi:10.1016/j.tust.2013.02.004.  255-10  5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction    Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015   A COMPARISON OF GEOGRAPHIC INTERVENTION GROUPING METHODS FOR INFRASTRUCTURE INTERVENTION PLANNING ACROSS MULTIPLE NETWORKS Clemens Kielhauser1,2, Bryan T. Adey1 and Nam Lethanh1 1 Swiss Federal Institute of Technology (ETH), Switzerland 2 kielhauser@ibi.baug.ethz.ch Abstract: Interventions on infrastructure networks in municipalities cause disruptions to the service provided by the network that requires the intervention. They also cause disruptions to the service provided by other networks that have to be at least partially shut down so that the intervention can be executed. Due to these effects, there is substantial benefit to be obtained by grouping interventions on all networks that are spatially close to one another, i.e. work programs for spatially close networks should be developed together. This benefit is principally due to reduced interruption to services and reduced costs of intervention. The challenge of determining such combined optimal work programs is made more difficult as it requires quantification of the value of lost services, which depends on how different stakeholders value the services as well as how the services are interrupted. In this paper the difference between two methodologies to be used to develop work programs on spatially close infrastructure networks is shown: 1) a traditional methodology based on a grid-cell based grouping method, and 2) a methodology based on a combined topology / Voronoi cell / density based clustering of interventions. Both methodologies exploit recent developments in the area of critical infrastructures and GISs. The differences are illustrated by using both methodologies to determine combined work programs for five spatially close infrastructure networks (electricity, gas, water, sewage, roads) in a municipality with approximately 1'500 inhabitants. The advantages and disadvantages of each are discussed. 1 INTRODUCTION  Infrastructure networks (INs), such as electricity, gas, road, sewer, and water distribution networks are some of the main assets but also some of the main cost drivers of a municipality. Therefore, interventions on these networks should be carried out in a way that minimises the costs of intervention and the disruption of the service, i.e. an optimal work program (OWP) should be determined. Traditionally, the managers of each IN produce their own work programs. Example methodologies to find OWPs for single INs can be found in Fenner, Sweeting, and Marriott (2000), Miyamoto, Kawamura, and Nakamura (2000), Stillman (2003), Cardoso et al. (2004), Arthur et al. (2009), Dehghanian et al. (2013), Zayed and Mohamed (2013), Lethanh, Adey, and Sigrist (2014). These work programs are then discussed with those responsible for the other INs in order to reduce the impact on service disruption and costs by manually combining the work programs to create synergy effects.  In this paper a case study on a dynamic geographic intervention grouping method is presented. This method can be used to take into consideration the structural and functional differences, as well as the different ways that the networks are typically monitored, in an automated way. The resulting work program is compared with the work program 255-1 from a static geographic intervention grouping method presented in Kielhauser, Adey, and Lethanh (2014), herein referred to as the traditional methodology. 2 METHODOLOGY The concept of the herein presented dynamic neighbourhood methodology (DNM) is based on the concept of neighbourhood. The neighbourhood of object A is defined as the region around object A, where object B would be considered close if it lies within that region. The basic process for the DNM follows 7 steps, which are explained in the following sections and shown in Fig. 1.  Fig. 1: Methodology Flowchart 2.1 Step 1: Determine Level 1 objects In this process, objects with high priority (level 1 objects) are determined. In this paper, level 1 objects are defined as follows:  Level 1 objects are objects, which are in such a state (e.g. failure probability, condition, age, level of service) that an intervention on this object is justified on its own, i.e. the decision to do an intervention is independent from other objects.  In the first step of this process, triggers for selecting an object as a level 1 object are defined. These triggers are thresholds of one value or a combination of values of the object attributes. The attribute can be of the object itself, denoted as   with the subscript  ( ) representing the object ID, and/or of the network, denoted as  with the subscript  ( ) representing the network ID. The superscript  denotes the level 1 objects. An example of the former is object condition. An example of the latter is change in network reliability. Then, objects are compared with the triggers by using a selector function . It is defined as a logical function, with  (true) when an object is selected, and 0 otherwise. This selector function is applied to a set of all objects considered (based on the boundaries of the physical area to be analysed and the jurisdiction of the manager)  in order to obtain the logical selection vector for the level 1 objects : [1]  with object vector consisting of all objects : . 255-2 2.2 Step 2: Calculate Neighbourhood This process is used to determine the neighbourhood of all level 1 objects being investigated. This is accomplished by determining the topological neighbourhood, the distance neighbourhood and the Voronoi neighbourhood. The first two of these neighbourhoods refer to objects in the same network, the last refers to objects that are in the spatial neighbourhood of the level 1 objects but are in different INs than the level 1 object. To better explain the used three different neighbourhoods, Fig. 2a shows an example network with 7 objects. Logical nodes (denoted with  ) are nodes that signify a join between two or more objects. Geometric nodes (denoted with  ) are used to detail the object shape in between the endpoints (logical nodes). Lines with the same number are used to denote one object.          (a) Example network  (b) Voronoi cells for (c) Voronoi region for (d) Voronoi region for            with objects 1-7     network nodes     network element 1    network element 5 Figure 2: Network definitions 2.2.1 Topological Neighbourhood The topological neighbourhood of an object is based on the topological distance, i.e. the number of objects between two logical nodes. In that sense, two objects are neighbours if the network distance between their closest logical nodes is below a certain threshold. For example, if the focus is on object 6 and the distance threshold is 1, then objects 1, 2, 5, and 7 can be considered to be in the same neighbourhood, as at most 1 object (namely 5) has to be crossed to reach them. Mathematically, neighbouring objects can be found as follows: Starting from the incidence matrix  (i.e. a matrix describing which edges are connected to which nodes), all nodes reachable in a distance  can be calculated by: [2]  with  Reachability matrix of network  for  steps. Each element from  shows if a node is reachable from another node with a maximum of  steps. Combining those reachability matrices to a grand matrix gives the topological neighbourhood matrix : [3]   2.2.2 Distance Neighbourhood As the sizes of network objects can differ by orders of magnitudes (e.g. compare one valve with a 300m stretch of straight pipe), neighbourhoods can also be defined by distance along the network. This is an alternative neighbourhood definition, which only takes into account the physical distance of objects along the network. For this, an object is defined as a neighbour, if it can be reached within a certain distance along the network. For example, objects 3 and 5 are within a distance dtravel of each other, as shown in 255-3 Fig. 2a, as their closest nodes are within a distance of dtravel. Mathematically, the shortest path between all logical nodes q of all objects has to be calculated (or loaded from the database if available).    [4]  with all logical node pairs distance matrix for network m, all node pairs shortest path algorithm for networks as described in Johnson (1977). The minimal distance between all object pairs is then the minimum of the minimal distances between each objects' logical nodes:   [5]   with minimal distance matrix for all objects in network m, logical nodes of network m, and objects of network m. Comparing this minimal distance matrix with a distance threshold for each network m  gives the neighbourhood matrix : [6]   Combining those distance matrices into a grand matrix gives the neighbourhood matrix : [7]    2.2.3 Voronoi Neighbourhood Both topological and distance neighbourhood definitions have the prerequisite that all objects have to belong to the same network. To overcome this limitation, the neighbourhood can also be defined by Voronoi cells (Lejeune Dirichlet 1850). Figure 2b shows a Voronoi tessellation of the example network. Starting from a given set of core points  (in this case: all network nodes, both logical and geometric), Voronoi cells  consist of every point in space whose distance to  is less or equal to any other core point . A Voronoi region  for one object is then the set of all Voronoi cells emanating from the nodes of that object (Fig. 2c,d). Combining those regions gives the set of all Voronoi regions  for all objects . This can be used to define the neighbourhood as follows: objects A and B are neighbouring, if object B touches object A's Voronoi region. The neighbourhood can then be defined as: [8]     with Voronoi regions of objects , neighbourhood matrix for Voronoi methodology and the dyadic geometric intersection between  and .  255-4 2.2.4 Neighbourhood combination In the last activity of the dynamic neighbourhood calculation, all neighbourhoods are combined to a grand neighbourhood by combining all neighbourhood matrices to the dynamic neighbourhood matrix : [9]  with the symbol  denoting the logical “or”, which only returns a value of “1” if at least one input is “1”. In words, two objects are neighbours if they are either topological, distance or Voronoi neighbours. 2.3 Step 3: Determine close objects As next step, the so-called close objects are determined. Those objects are objects that are located in the neighbourhood which is defined by the dynamic neighbourhood matrix . This process ensures that only close objects, i.e. objects that are sufficiently near to level 1 objects are considered as level 2 objects in the next step, where the object condition is compared against a threshold likewise to the determination of level 1 objects. Mathematically, the whole process can be expressed in one equation: [10]  with binary variable vector indicating if object  is part of the close object set. The superscript  denotes the close objects, the superscript  denotes the DNM, and the symbol  denotes the material non-implication, which is an operator that only returns a value of “1” if the first input is “1” and the second input is “0”. In this case: an object is only a close object for the DNM if the object is within the same neighbourhood as a level 1 object  but has not been already selected as a level 1 object. 2.4 Step 4: Determine Level 2 objects  In this subprocess, objects with lesser priority (Level 2 objects) are determined. In this paper, level 2 objects are defined as follows. Level 2 objects are objects, which are in such a state (e.g. failure probability, age, level of service) that an intervention on this object is not justified on its own but the synergies created by doing a combined intervention with a level 1 object justify an intervention, i.e. the decision to do an intervention is dependent on other proximate objects.  The selection process is similar to the one for level 1, just with different trigger values.  2.5 Step 5: Group objects In this process, the level 1 and level 2 objects which have been identified in the previous steps, are combined into intervention groups, i.e. sets of interventions that are executed together, using the DBSCAN algorithm as described in (Ester et al. 1996). This algorithm takes the centroid point coordinates of the objects requiring intervention and two values as inputs: 1) Eps - the maximum distance in which two interventions should be grouped into one intervention group, and 2) MinPts - the number of interventions, that form an intervention group. Then, the points are classified as either belonging to a group or being single objects. If they belong to a group, then the interventions are included in the work program as a group, otherwise it has to be discerned between level 1 and level 2 objects. Level 1 single objects are also included in the work program as intervention, despite not being grouped, because per definition level 1 signifies that an intervention is justified even without grouping, whereas level 2 objects belonging to no group will be discarded. Mathematically:  255-5 [12]  with intervention group matrix for the DBSCAN clusters. The cost of each group is the sum of the setup costs  for executing all interventions in group  and the unit costs without setup costs for each intervention on each object of each network  multiplied by its size . [13]  with cost vector of intervention in all groups . The WP is simply the whole set of intervention groups, i.e. all rows of . The total costs are then simply the sum of the cost vector : [14]  2.6 Step 6: Rank groups  If there are constraints (e.g. budget constraints) and not all intervention groups can be included in the work program, a priority (related to the consequences that would be incurred due to service interruption if a failure occured) is calculated so that the groups with the highest priority can be included in the work program. It is in this methodology based on two components: a) The object priority value, which relates to the object itself and its role in the network, e.g. for a sewer network object how many upstream objects will also be blocked if this object has to be blocked for maintenance, and b) a multiplicative factor related to the location, e.g. population density of the area with service interruption. Although this is multiplicatively connected with the object priority value, it is kept separate because the population density for example is not network dependent, whereas the object priority value is. Mathematically: [15]  with priority vector of group , object priority vector based on object  and network ,  group priority vector based on group location, and  representing the element-wise multiplication of vectors.  From there, the rank  of a group can be calculated:  [16]  This results in the group with the highest priority  having the lowest rank . 2.7 Step 7: Add group to constrained work program The work program with constraints is constructed from the unconstrained work program: The groups included in the unconstrained work program are added one at a time to the constrained work program (i.e. a selection variable  is changed from 0 to 1) starting with the group with the highest priority (i.e. where , then where  etc.) and then the budget is checked. If the budget is not exceeded, 255-6 the group is kept and the group with the next highest priority is tried. This process is repeated until the sum of the costs of the groups in the work program reaches the budget limit : [17]  with binary vector indicating inclusion in WP (1=yes, 0=no), budget limit. The WP is the whole set of intervention groups  subsetted by the inclusion variable : [18]  The total costs are the sum of the cost vector  times the inclusion vector.  [19]   3 CASE STUDY The DNM was used to determine a work program for five proximate municipal infrastructure networks. This work program was then compared with the work program generated using a traditional methodology Kielhauser, Adey, and Lethanh (2014). The advantages and disadvantages of each will be discussed. 3.1 Overview The infrastructure networks (electricity, gas, roads, sewage, and water) used in this case study belong to a municipality with a population of ca. 1’500. The single network maps are shown in Fig. 3a – Fig. 3e.           (a) Electricity (b) Gas  (c) Roads (d) Sewer  (e) Water Figure 3: Network maps The objects in the electricity, gas, and water networks were considered to be in one of 2 condition states, operational and not operational, the objects in the sewer network were considered to be in one of 5 discrete condition states, and the road objects were considered to be in a continuous-range condition state between 0 and 5 (Tbl.1). The thresholds for level 1 and level 2 are shown in Tbl. 2, the costs for the interventions (given in monetary units mu) in Tbl. 3.  255-7 Table 1: Network characteristics at the time of investigation    Table 2: Threshold values for levels 1 and 2   Table 3: Intervention types and costs  Using steps 1-7, a work program (with a budget constraint of 200’000 mu) was calculated and compared to the WP obtained by using the method described in Kielhauser, Adey, and Lethanh (2014). To facilitate the comparison, the work programs will be referred to as WPD (with the D representing the DNM) and WPT (the T representing the traditional methodology). Tbl. 4 shows the results.  Table 4: Results This table shows that the traditional methodology selects 4 objects for the work program. A total amount of 861.6m will be renewed. With only 300'000 mu available, the total cost is 287’387 mu, which means a budget utilisation of 96%. The DMN selects 6 objects with a total length of 874.5m for the work program.  Length Objects No.of condition states Condition state (distribution)  [km] [-]  1 (as new) 2 3 4 5 (defunct) Electricity 20.6 2’226 2 100% - - - 0% Gas 6.8 351 2 100% - - - 0% Water 8.8 182 2 100% - - - 0% Road 9.7 104 cont. (0-1] 2.9% (1-2] 25.0% (2-3] 44.2% (3-4] 23.1% (4-5] 4.8% Sewer 5.3 215 5 97.2% 2.8% 0% 0% 0%  Electricity Gas Roads Sewer Water Type Failure probability Failure probability Condition state Transition probability Failure probability Level 1 0.025 0.025 3.67 0.020 0.020 Level 2 0.013 0.013 3.10 0.005 0.005  Electricity Gas Roads Sewer Water Setup cost Type Replacement Replacement Replacement Replacement Replacement Cost per intervention setup Value 100 150 350 250 300 1’500 Unit [mu/m] [mu/m] [mu/m] [mu/m] [mu/m] [mu] Effect As-new condition As-new condition As-new condition As-new condition As-new condition   Objects Intervention Cost Avg. cost per Removed  B   Groups Length  Group Object Length Age units   [-] [-] [m] [mu] [mu/1] [mu/1] [mu/m] [y] [mu/(m*y)] WPT 4 4 861.6 287’387 71’847 71’847 334 7’965 36.1 WPD 6 4 874.5 288’672 72’168 48’112 330 8’724 33.1 255-8 A total amount of 874.5m will be renewed. With total costs at 288’672 mu, the budget utilisation is also 96%. To be better able to compare the methodologies, we have used a proxy B which is the average amount of financial resources used to improve the age of the infrastructure, expressed as monetary units divided by the amount of removed age, multiplied by extent of the object. This indicator is based on the concept, that if it is assumed that an adequate level of service is always provided, the main goal of an infrastructure manager becomes the improvement of the infrastructure for the least cost. In this case, the best work program is the one that gives the highest improvement in the infrastructure provided for the least cost. For example, when a gas pipe is 70 years old and is replaced with a new identical pipe, it is considered to have improved the condition of the infrastructure by 70 years. When this is coupled with the costs to improve the condition, one gets the costs per time. 4 COMPARISON One of the first things that can be seen by comparing the two methodologies is the difference between the numbers of interventions proposed. For the case study, this difference originates in a part of the network that is shown in Fig. 4. The left half shows the WPT, the right shows the WPD. The dashed line represents the boundary of a grid cell. The line weight represents the different levels (thick: level 1, medium: level 2, grey: no selection). For the WPT, it can be seen that within the grid cell, the level 1 object also triggers an intervention on the adjacent level 2 object, because it is in the same grid cell. For WPD, additionally, another object is included, as it is only at a topological distance of 1 from the level 1 object. This shows the main benefit of the DNM: as the neighbourhood is calculated dynamically from the network, such boundary situations can be taken into account in contrast to the traditional methodology.  Figure 4: Difference in work program As can be seen in Tbl. 4, the cost/improvement ratio B  varies between the work programs. The work program determined using the DNM gives the best (i.e. lower) ratio (33.1 vs. 36.1). Therefore, the DNM performs better than the traditional methodology. This is due to the synergy effects created by the topological approach in contrast to the traditional approach. 5 CONCLUSION In this paper, two methodologies to determine work programs for municipalities possessing multiple infrastructure networks were investigated and compared. In the investigated example, the methodologies were used to determine work programs for five infrastructure networks in a municipality with a population of ca. 1'500. It was found that the DNM for grouping objects in need of intervention within a network and on multiple networks leads to improvements over the traditional methodology. This demonstrated that the explicit consideration of the proximity of objects within multiple networks should be systematically done. It was found that the DNM leads to work programs that generated lower per unit improvement costs than the traditional methodology. This is because the traditional methodology relies on predefined grid cells, while the DNM dynamically calculates those from the individual network data. 255-9 Keeping this in mind, future research in this direction should include: • the enhancement of the investigated methodologies to determine work programs using more direct consideration of the costs of service interruption  • the extension of the investigated methodology to determine work programs over multiple time periods • the adaptation of the investigated methodology to take into consideration functional relationships between the objects within one network and within multiple networks, e.g. the effect on the amount of water flowing in a waste water network due to interventions being executed on a sewer network and a heavy rain fall occurring • the enhancement of the investigated methodology to better take into consideration real world costs, i.e. more accurate representations of the variant and invariant costs involved with intervening on one or more networks, and on one or more objects • the comparison of these methodologies with a real world situation to investigate the potential advantages and disadvantages of its use in practice References Arthur, Scott, H Crow, L Pedezert, and N Karikas. 2009. “The Holistic Prioritisation of Proactive Sewer Maintenance.” Water Science and Technology 59 (7): 1385–96. Cardoso, Maria, Sérgio Coelho, Rafaela Matos, and Helena Alegre. 2004. “Performance Assessment of Water Supply and Wastewater Systems.” Urban Water Journal 1 (1): 55–67. doi:10.1080/15730620410001732053. Dehghanian, Payman, Mahmud Fotuhi-Firuzabad, Farrokh Aminifar, and Roy Billinton. 2013. “A Comprehensive Scheme for Reliability Centered Maintenance in Power Distribution Systems — Part I: Methodology.” Power Delivery, IEEE Transactions on 28 (2): 761–70. doi:10.1109/TPWRD.2012.2227832. Ester, Martin, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.” In Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96). Fenner, Richard A., L. Sweeting, and Martin J. Marriott,. 2000. “A New Approach for Directing Proactive Sewer Maintenance.” Proceedings of the ICE - Water and Maritime Engineering 142 (Volume 142, Issue 2): 67–77(10). doi:10.1680/wame.2000.142.2.67. Johnson, Donald B. 1977. “Efficient Algorithms for Shortest Paths in Sparse Networks.” J. ACM 24 (1): 1–13. doi:10.1145/321992.321993. Kielhauser, Clemens, Bryan T. Adey, and Nam Lethanh. 2014. “An Example of the Effect of Simultaneous Planning of Interventions on Proximate Infrastructure Networks.” In Proceedings of the CSCE 2014 General Conference / Congrès Général 2014 de La SCGC. Lejeune Dirichlet, G. 1850. “Über Die Reduction Der Positiven Quadratischen Formen Mit Drei Unbestimmten Ganzen Zahlen.” Journal Für Die Reine Und Angewandte Mathematik 40: 209–27. Lethanh, Nam, Bryan T. Adey, and Manuel Sigrist. 2014. “A Mixed-Integer Linear Model for Determining Optimal Work Zones on a Road Network.” In Proceeding of the International Conference on Engineering and Applied Sciences Optimization. KOS Island, Greece. Miyamoto, Ayaho, Kei Kawamura, and Hideaki Nakamura. 2000. “Bridge Management System and Maintenance Optimization for Existing Bridges.” Computer-Aided Civil and Infrastructure Engineering 15 (1): 45–55. doi:10.1111/0885-9507.00170. Stillman, R. H. 2003. “Power Line Maintenance with Minimal Repair and Replacement.” Reliability and Maintainability Symposium, 2003. Annual, 541–45. doi:10.1109/RAMS.2003.1182046. Zayed, Tarek, and Elsayed Mohamed. 2013. “Budget Allocation and Rehabilitation Plans for Water Systems Using Simulation Approach.” Tunnelling and Underground Space Technology 36 (0): 34–45. doi:10.1016/j.tust.2013.02.004.  255-10  ||C. Kielhauser, B. T. Adey, N. Lethanh10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 1A comparison of geographic intervention grouping methods for infrastructure intervention planning across multiple networks|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 2|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 3Methodology|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 4Methodology|| can be defined in three ways Topology Distance Voronoi-tesselation10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 5Neighbouring objects|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 6Topological neighbourhood|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 7Distance neighbourhood|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 8Voronoi-Tesselation|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 9Methodology|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 10Methodology|| DBSCAN Algorithm no pre-defined number of clusters Many variations adapted to specific problems Space-time capabilites only 2 input values min. group size max. distance within a group10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 11Grouping|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 12Methodology|| Object based Threshold excess Importance within the network Location based Population density Strategic points10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 13Ranking|| 10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 14Methodology|| Municipality (pop. ~1’500) 5 Networks Electricity (binary) Natural gas (binary) Roads (continuous 0-5) Sewer (5 discrete) Water (binary)10.11.2015C. Kielhauser, N. Lethanh, B.T. Adey 15Case study||Methodology Unit Traditional DynamicNeighbourhoodObjects [-] 4 6Interventiongroups[-] 4 4Intervention length [m] 861.6 874.5Cost [mu] 287’387 288’672Removed age units [y] 7’965 8’724Cost per improved unit [mu/(y.m)] 36.1 33.110.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 16Comparison|| Extend DNM / DNMc methodology Cluster-dependent costs and ranking Spatio-temporal clustering Extend research in the area of interaction between networks Other interaction types Cost models for service interruption Cost models for synergy effects10.11.2015C. Kielhauser, B.T. Adey, N. Lethanh 17Conclusions

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.52660.1-0076360/manifest

Comment

Related Items