A decision support system to design water supply and sewer pipes replacement intervention programs

Reliability Engineering and System Safety 216 (2021) 107967 Available online 19 August 2021 0951-8320/© 2021 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). A decision support system to design water supply and sewer pipes replacement intervention programs Crist´ obal Ramos-Salgado * , Jesús Mu˜ nuzuri , Pablo Aparicio-Ruiz , Luis Onieva Organization Engineering Group, School of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092 Seville, Spain ARTICLE INFO Keywords: Water distribution and sewer system Pipe replacement Grouping Voronoi cells Multi-objective optimization ABSTRACT Asset management in hydraulic infrastructures aims for the long-term sustainability of water distribution and wastewater networks. Strategic maintenance planning has thus been deeply analyzed in the literature for individual water and sewer pipes. However, water utilities do not plan and perform replacement activities on individual elements, but rather on coherent aggregations of neighboring pipes. We have developed a decision support system (DSS) to help water utilities design intervention programs for hydraulic infrastructures. It integrates a two-stage algorithm that groups water supply and sewer pipes into practical and efficient replacement works, based upon their proximity and their priority of renewal. A multi-objective genetic algorithm optimizes the work programs configurations while integrating the water company’s strategic policy into an innovative multi-objective function. We have applied our methodology to a large water company in Spain and illustrated this application with a sensitivity analysis to determine how the company’s strategic criteria influences the resulting work configurations. 1. Introduction Maintenance planning and replacement scheduling has been broadly studied for urban water pipes. Pipes deteriorate with time, and their condition is determinant for the reliability of the water supply and sewage system, which explains the growing interest to develop approaches aimed at establishing replacement priorities. These approaches are usually focused on individual pipes, setting priorities according to the observed or estimated condition of each pipe. Nevertheless, water utilities real maintenance strategies consider groups of pipes for viable and practical replacement interventions, rather than planning replacement tasks on individual pipes. A deteriorated pipe is usually replaced as part of a whole maintenance activity, in which others adjacent pipes, that may not need an urgent replacement yet but will in the near future, are simultaneously renewed. Grouping individual pipes not only into workable but efficient intervention programs is a difficult task. Water companies usually own sophisticated models to evaluate the state of their network assets and program maintenance activities relying on advanced technical and economic criteria. Nonetheless, when planning intervention programs, the consideration of external factors to the company or the hydraulic system themselves, like service interruptions, the impact on pedestrians or the traffic flow or the harmonization with other infrastructures maintenance projects, e.g., gas, electricity or road networks is required. In this matter, Salehi et al. [1] develop a comprehensive multi-criteria decision-making model to plan the rehabilitation of water networks with 42 different factors, including non-technical variables such as climate, population, local, spatial and security criteria, while Kilinç et al. [2] employ other external factors like the traffic intensity or the road surface condition. Additional non-technical factors like the company reputation or the pavement width are collected in a comprehensive review of over 100 criteria provided by Syan and Ramsoobag [3]. These external criteria are usually integrated into the decisionmaking process through the expert knowledge and experience of managers. Some works address this issue to deal with crisis or emergency situations in drinking water supply systems. For example, Ghandi and Roozbahani [4] and dos Santos et al. [5] develop two models to choose the most suitable risk management strategy considering aspects like social satisfaction and public participation, whereas Pagano et al. [6] incorporate criteria related to failure consequences such as possible interactions with other infrastructures or social acceptability. Likewise, regarding the work programs configuration, utility managers have traditionally designed them manually, under subjective * Corresponding author. E-mail address: [email protected] (C. Ramos-Salgado). Contents lists available at ScienceDirect Reliability Engineering and System Safety journal homepage: www.elsevier.com/locate/ress https://doi.org/10.1016/j.ress.2021.107967 Received 25 January 2021; Received in revised form 16 July 2021; Accepted 16 August 2021 Reliability Engineering and System Safety 216 (2021) 107967 2 opinions and without technical foundations. For example, some utilities only replace the water supply and sewer pipes between two street intersections, while other municipalities replace shorter lengths to reduce the long-term cost of sustaining the entire infrastructure network [7]. Seeking to integrate the replacement priority of individual pipes with the need to plan feasible and practical multi-pipe renovation plans, we have developed a flexible and multi-objective DSS to help water utility managers plan and design hydraulic infrastructure replacement programs, while incorporating their traditional know-how and experience. It consists of a highly configurable methodology that allows to incorporate and automate the social, urban and coordination factors along with the technical and economic criteria. The system includes an optimization process to find the work programs configurations that best meet the water company’s strategic policy. The paper is organized as follows. Section 2 reviews different methodologies for grouping hydraulic infrastructure elements considering adjacency criteria in the literature. In Section 3, the research motivation and main contributions are discussed. After showing in Section 4 how the network pipes are grouped into Voronoi cells, we describe our proposed methodology in Section 5. Following this, Section 6 explains the implemented multi-objective optimization process. Section 7 presents the results of applying our methodology to a water utility in Spain and a sensitivity analysis of the company’s criteria on the resulting work configurations. Finally, conclusions are drawn in Section 8. 2. Literature review Much of the existing literature on water asset management addresses the development of strategies and maintenance activities planning for individual water and sewer pipes. In this regard, two approaches can be distinguished. The first one relies on a life-cycle cost analysis and seeks the economically optimal replacement time for each pipe object, i.e., when the expected future repair costs exceed its replacement cost. Some works in this field use simulation models [8] or heuristic algorithms [9] to optimally schedule the water supply pipes for replacement. The second approach defines a replacement priority for every pipe object, identifying network assets that should be intervened first. In this context, machine learning techniques like logistic regression [10,11] or clustering [12,13] are becoming popular to predict pipe failures in water networks. Moreover, to address risk assessment of pipes, criteria related to the consequences of failure have to be incorporated. In this sense, the matrix risk technique has been widely used to identify critical pipes in water supply networks [14,15]. Other works, in contrast, develop and assign to every pipe a risk index, which is equivalent to a replacement priority. For this, the popular weighted sum model [2,16] and fuzzy-based [17,18] methods have been utilized. Nonetheless, water companies plan and perform developed and elaborated intervention programs, in which a group of adjacent pipes are coherently aggregated to be simultaneously replaced. In this sense, little research efforts have focused so far on applicable grouping techniques to aggregate supply and sewer pipes into practical and efficient replacement works. The existing examples can be classified in two major categories: static and dynamic grouping methodologies, as proposed by Bouvard et al. [19]. Additionally, we distinguish two different kinds of dynamic grouping techniques. This can be seen in Fig. 1, that depicts the existing replacement strategies for individual water pipes and how they can lead to the identified grouping methodologies. First of all, in the static grouping methodologies (that correspond with the first green box in Fig. 1), a set of infrastructure objects e.g., water distribution and sewer pipes, are aggregated in predefined groups that will be replaced in the same work program, i.e., are considered for replacement as a group. These grouping criteria may be geographical, like street sections between intersections, or topological, such as pipelines between infrastructure elements such as valves or manholes. Regardless of the asset management strategies implemented or maintenance activities scheduled, these groups are indivisible replacement units and are no longer to be broken up. Besides, every unified operational unit has assigned a replacement priority index as a function of the network assets contained. As an example, Elsawah et al. [20] define potential replacement units as the set of supply pipes, sewer pipes and road sections sharing the same corridor and located between the two nearest intersections. To prioritize maintenance activities on infrastructure networks segments, they developed a model based on an overall criticality index for the corridor segment. This approach optimizes budget allocation and resource usage and is applied to one borough of the City of Montreal, Canada. More recently, the same authors incorporated a dynamic weighting system to calculate the overall criticality index while considering only the water and sewer networks [21]. Another interesting static example is presented by Tscheikner-Gratl Fig. 1. Approaches addressing water pipes replacement strategies and grouping methodologies. C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 3 et al. [22]. The authors develop an integrated strategic asset management approach to prioritize rehabilitation tasks on entire street sections (including the road, water supply and sewer networks). According to the authors, a street section consists of entire valve or manhole sections with a certain length threshold to avoid too long sections. The model calculates a total priority index and ranks street sections for rehabilitation. The procedure is applied to a case study of an Austrian city with 130,000 inhabitants and for a 6-year horizon. On the other hand, dynamic grouping models aggregate individual infrastructure elements into intervention groups within the methodology. As mentioned before, within the dynamic grouping methods, two distinct types are distinguished. On the one hand, the unified replacement units derived from the static grouping methods can be further aggregated into more developed and realistic intervention programs according to similarity or proximity criteria. Hence, this technique can be seen as an enhancement of the static one. This approach, that has not been studied in the literature yet, is highlighted in yellow in Fig. 1 and will be addressed in this work. On the other hand, the second dynamic approach arranges pipe objects to benefit from the possible cost reductions if multiple networks elements are replaced simultaneously. Therefore, to promote the integration of individual pipes into unified work programs, optimization algorithms are required and objective functions such as cost minimization or replaced length maximization need to be included. Generally, this methodology produces interventions groups and schedule them for replacement so that the overall maintenance costs during a given planning period are minimized. Unlike the static grouping method, the aggregations formed are not either indivisible or definitive and change within the optimization process according to the algorithm, objectives and restrictions implemented. This methodology can be distinguished in the second green box in Fig. 1. Within this approach, the first model found was developed by Nafi and Kleiner [23]. The authors propose three different types of economies of scale to foster the aggregation of several pipes into unified replacement projects and implement a multi-objective genetic algorithm (MOGA) to minimize the total cost and maximize the available budget spent. This model was applied to a 152 pipes and 18 km length sample water distribution network in Southern Ontario, Canada. Further research by the same authors incorporates deterioration considerations by taking into account life cycle costs [24]. Another dynamic group replacement scheduling method can be found in Li et al. [25]. They propose a replacement decision optimization model to group pipeline assets that (1) are geographically adjacent, (2) require identical unique replacement machinery and (3) with similar areas of customer interruption. This model considers machinery and travel costs that can be spared if several pipes form part of the same replacement job. Also, the maximum allowable number of pipes in one group needs to be defined. A modified genetic algorithm is then implemented to find the grouping option that minimizes the total replacement and failure costs. In a more recent research [26], they incorporated new cost and service interruption models and applied a non-dominated sorting genetic algorithm (NSGA-II) to minimize the total costs and service interruption. Rokstad and Ugarelli [27] also consider economic benefits from economies of scale and prove that grouping the renewal of adjacent water pipes is more profitable. Besides, the authors define the functional unit (hydraulic link) as the set of pipe segments between two valves. Along the lines of Nafi and Kleiner [23] and Li et al. [25], this work includes a fixed setup cost that can be shared when several elements are renewed together. To limit the total pipe length simultaneously renewed, a maximum group size is required. A greedy heuristic is implemented to find local optimum solutions and a case study in a medium-sized Norwegian city with 26,000 inhabitants and 120 km of network water mains is presented. Carey and Lueke [28] propose a general cost reduction by 10% and 20% in case of contiguity and harmonization of water or sewer pipes and the corresponding road segment projects, respectively. Their model assesses every infrastructure segment with a criticality score, and an evolutionary algorithm minimizes the average yearly criticality score over the planning horizon. This methodology is applied to a small network made up of elements of varying condition and criticality. Roshani and Filion [29] implement a similar model to the Fairfield distribution network, comprised of 54 km of water mains, that provides water to a population of 15,000 people in Amherstview and Odessa (Ontario, Canada). They also introduce quantity discounts as a function of the length replaced, and adjacency discounts that benefit the synchronization of several municipal maintenance projects, such as roadwork and water pipe maintenance tasks. A NSGA-II is implemented to minimize the capital and operational costs. Furthermore, Kerwin and Adey [30] not only consider quantity discounts on large replacement projects and savings on site setup and mobilization costs, but also include a coordination factor to benefit the synchronization of diverse infrastructure interventions, e.g. road, gas or electricity network. A binary optimization is applied using the Simplex method with branch and bound to maximize the net benefit. They applied their methodology to a small network of 4.6 km and 234 pipes. Kielhauser et al. [31] describe an elaborated two-module methodology combining both static and dynamic technics. In the first module, called static neighbourhood calculation, each network asset is associated to a predefined square grid cell and its adjacent cells form their neighbourhood. The second, executed dynamically within the methodology, obtains the proximity of the asset depending on the network topology, for elements belonging to the same network, and determines Voronoi cells for objects from different infrastructures. This second stage requires the definition of two inputs: the maximum distance in which two objects could be grouped into one intervention group and the minimum number of objects forming an intervention group. Every intervention group consists of, at least, one object with urgent replacement needs, and other elements whose condition, while not critical, justify their inclusion in the same maintenance project. Then, the intervention groups are added one at a time to the work program, starting with the most urgent one, until the available budget is completely allocated. A case study of a city with a population of 30,000 inhabitants and five infrastructure networks (electricity, gas, roads, sewage and water) is presented. Finally, Kielhauser and Adey [32] apply their previously developed dynamic neighbourhood calculation [31], adding a genetic algorithm to find the economically optimal intervention programs while including considerations on intervention costs, loss of service, discounts on simultaneous networks interventions and potential impact of interventions on adjacent infrastructures. No case study is presented in this latter work. 3. Research motivation The first conclusion that can be drawn from our literature review is that grouping individual pipes not only into workable replacement jobs, but also into efficient replacement projects is not a straightforward task. This is especially true when multiple criteria, such as replacement priority and budget constraints need to be taken into account. Regarding the static grouping methodologies, the reviewed models define potential replacement units based only on geographical or topological criteria, such as street segments between intersections, but no further aggregation of these replacement units into more structured and closer to actual work configurations is considered. Thus, this approach is not sophisticated and lacks technical basis. With respect to the dynamic grouping approach, the first type of methodology proposes an enrichment of the static one since it aggregates the unified replacement units into more elaborated and practical work programs. However, this approach has not been studied so far and will be addressed in this work. In contrast, the second kind relies C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 4 exclusively on the financial advantage of replacing multiple contiguous pipes simultaneously. In other words, promoting the aggregation of pipes by including quantity discounts on large replacement projects and savings on site setup and mobilization costs. However, this approach requires the previous estimation of both figures. These estimations are usually based on experience and inevitably incorporate a certain degree of subjectivity into the analysis. With respect to additional criteria, only Kielhauser et al. [31] include considerations on condition and replacement needs to group objects into intervention programs. These models generally provide an economically efficient solution, but they offer a limited versatility, since they integrate a low level of operational configurability. In the reviewed literature, only a few configuration parameters have been identified: the maximum allowable number of pipes that could be aggregated into one intervention group [25,27], the maximum distance across which two objects could be grouped, and the minimum number of objects forming an intervention group [31]. Furthermore, most of the studied dynamic models consider pipe objects as the smallest replacement units. Since pipelines might not be in consonance with the street’s layout, these approaches “focus on mathematical analysis and techniques, rather than solutions to real problems” [33]. However, water utilities plan and perform replacement interventions according to the street’s topography and complete streets or street sections represent the smallest replacement units. Therefore, a more practical, realistic and useful perspective within the dynamic models is still missing. Additionally, nearly all of the reviewed works apply their models to small-size or sample networks [23–25,29,30,32]. This is comprehensible since dynamic models require a vast processing capacity and considerable computation time. As the network’s size and complexity increase, the possibility for these models to be unfeasible and impractical grows as well. This issue may jeopardize the viability of these models when applied to real water utilities servicing medium or large-size cities and managing highly developed and complexed networks. To fill these detected gaps, we have developed a DSS to help water utility managers plan and design hydraulic infrastructure replacement programs from a practical and technical point of view. The main contributions of our research can be summarized as follows: •First, our methodology presents a technical and operational approach that groups network elements according to their replacement needs. In other words, if a deteriorated pipe is to be replaced, then others adjacent pipes, that may not need an urgent replacement yet but will in the future, should be simultaneously considered. •Also, our developed DSS offers a high degree of operational configurability that allows the resulting work configurations and designs to meet the water utility operational criteria. This is to say, even though the outcomes will always be substantiated with technical criteria, the DSS enables to integrate the traditional water company know-how and experience. •Moreover, the DSS integrates a two-stage algorithm that provides versatility and flexibility. The first part of the algorithm produces initial work configurations with simple linear topology. This initial solution, while spreading just along single streets, is utterly feasible and valid. The second part, based on a dynamic grouping approach, restructures the initial solutions by rearranging contiguous elements according to their replacement needs. •The procedure is controlled by a set of parameters, whose values are determined by an optimization process. •Also, the water company’s strategic policy is integrated into the optimization process by an innovative multi-objective function. This function allows to integrate the company’s criteria by a set of weights, making it comprehensive and applicable to any water utility. •Apart from that, we considered street sections to be the smallest possible replacement units. These functional elements are prone to be part of a workable and coherent intervention, as they are in harmony with the real and practical water utility operational criteria. •Finally, our methodology can be applied to large water companies and highly expanded and complex networks. In fact, our DSS has been seamlessly applied to a large water company in Spain, that services a metropolitan area with over 1 million inhabitants. The network comprises of more than 230,000 pipes and adds up to almost 7,000 km. In terms of the details of our proposal, the following section describes the use of Voronoi cells to plan replacement operations. The characteristics of the grouping algorithm designed to identify replacement works are described in detail thereafter. 4. Replacement cells The aim of this work is to develop a versatile and applicable methodology to integrate individual network pipes into coherent, workable, and efficient groups to be replaced in the same work project. Since the elements forming unified single intervention works are spatially contiguous, pipes layout and connections data are essential. However, this requires an “additional dimension of complexity related to the difficulty of representing and modeling” [34], and water utilities rarely possess such accurate and complete information. Moreover, depending on the system size, the number of elements to consider can be numerous and unmanageable. To overcome this issue, the following methodology has been implemented. First, a division of the network elements into Voronoi cells is proposed (Section 4.1). Also, every cell is assigned a risk index that determines its replacement priority (Section 4.2). Thus, the operational units are ranked for replacement. Subsequently, these two steps are an input to the grouping algorithm (Section 5), that provides a prioritized list of the aggregated intervention programs to be performed. Finally, Fig. 2. Procedure followed in the developed methodology. C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 5 given a planning horizon and an annual available budget, every work program can be scheduled for intervention. This procedure can be seen in Fig. 2. 4.1. Definition of replacement cells Every single Voronoi tile or cell is a geographic area on the map and is calculated as the region of points closer to the midpoint of each street segment than to any other segment midpoint. Each cell refers to complete streets or street sections between the two nearest intersections and is prone to be part of a workable and coherent replacement intervention. For this reason, Voronoi cells will also be called “street sections” hereafter. An example of such a Voronoi tessellation can be seen in Fig. 3. In this figure, the orange lines delimit the Voronoi cells, while the blue and red dashed lines represent some of the main pipelines of both the arterial water distribution and collectors’ networks. The number of street sections thus defined is significantly lower than the number of pipes in the network, resulting in a substantial reduction of the number of elements in the analysis. Furthermore, tiles and pipes are related by geometric superposition: every pipe segment in the network is linked to the Voronoi cell it passes through. A detail of this interconnection is shown in Fig. 4. Again, the orange lines define the Voronoi cells, while the blue and red dashed lines correspond to the secondary water and sanitation networks, respectively. Also, a Voronoi cell represents the smallest possible replacement unit. This is to say, if a specific cell belongs to a replacement plan, all the pipes belonging to the same network type within that cell will be replaced. Two distinct network types are not supposed to be grouped into the same replacement plan and, therefore, replaced simultaneously. For example, if a work program includes arterial pipes, no collectors or secondary network pipes will be targeted in the same replacement work. This is due to their different locations: while arterial pipes and collectors are buried under the road pavement, secondary network pipes are typically located under the sidewalks. Moreover, both primary water supply and sanitary pipes are not generally installed together due to operational reasons and two distinct and separate intervention works must be performed anyway. Thus, the synchronization of different network objects replacement confers no benefit and distinct network pipes are considered to be replaced in independent replacement plans. To assure this, every cell will comprise only one-network-type pipelines. In case that pipes belonging to more than one network type run through the same cell, it will be split into distinct but overlapping street sections, one for each existing network type in the cell. Therefore, the grouping algorithm (that will be described in Section 5) processes the three coexisting network types separately, resulting in three different work program types. Thus, all existing network types are addressed, while two of them will not be intervened in the same work program. For each cell, its neighborhood consists of all the other adjacent Voronoi regions [31]. Consequently, all the network pipes of the same network type and belonging to two neighboring cells can be arranged into the same work project and replaced simultaneously. This utilization of Voronoi cells provides versatility, as it is applicable not only to the currently studied infrastructure, but to any similar network system. Nonetheless, Voronoi tiles are no more than geographic objects. Information regarding the condition and criticality of each cell lies in their constituting pipes, and this information needs to be transferred to the cells. 4.2. Priority of replacement cells To prioritize the operational cells for replacement, the weighted sum model developed by Mu˜ nuzuri et al. [16] was used. The authors calculate a risk index (RI) that determines the replacement priority of both water distribution and sewer network pipes. This index is based on two factors related to pipe condition (probability of failure and supply pipe leakage flow), and three factors related to the consequences of pipe failure (demand for supply pipes, maximum evacuation flow for sewer pipes, and pipe relevance). This last factor is of great importance since it allows to identify pipes that are especially sensitive to a failure, and which should be prevented from happening. For the water supply network, relevant pipes are those supplying large premises potentially exposed to water-related risks like hospitals, health institutions or accommodation facilities. In contrast, relevant sewer pipes are those located less than 100 meters from riverbeds, due to possible environmental consequences. In their work, Mu˜ nuzuri et al. [16] determine the priority of replacement for individual pipes. However, since street sections, i.e., Voronoi cells, constitute the smallest replacement units, the risk index has to be computed for the whole Voronoi cell. For this purpose, the probability of failure for a street section is calculated as the weighted average of every inner pipe’s probability of failure. The weights correspond to the length of the pipe that falls inside the cell, as pipes may belong to more than one cell. Also, for each street section, the corresponding leakage flow, demand and maximum evacuation flow are equal to the maximum existing value for each factor of all the existing pipes in the street section. A street section is considered relevant when it contains a relevant supply or sanitation pipe. Once every cell has been characterized by these five attributes, the risk index and thus a replacement priority is calculated by applying the RI formulation to every street section. Nevertheless, it is important to Fig. 3. Street sections (Voronoi cells) on the map. Fig. 4. Voronoi cells and running-through pipelines. C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 6 note that the procedure presented here can be applied using any form of replacement priority index as an input. We have used the RI formulation developed by [16], but any other indicator, based on similar or different parameters, can be applied to assign a priority ranking to pipes for replacement. The only relevant difference would affect the calibration values shown in Section 7.2, which would need to be recalculated. Apart from its RI value, each street section is clearly identified by a specific location, dimension, and network type. Also, its neighboring cells, replacement cost and total network length are perfectly known. The accumulated replacement cost and network length of a street section are obtained as the sum of all the constituting pipes replacement costs weighted by their cell-related lengths. The next step is then to aggregate all the existing sections in the network into replacement units. 5. The grouping algorithm This section describes the developed algorithm to design replacement programs by grouping street sections into practical and unified replacement interventions. The decision to do an intervention is triggered by a single street section, generally with a high value of RI that justifies its replacement. Afterwards, the work “grows” by aggregating additional street sections to the same work program. These added sections may not have a RI that demands an urgent intervention, but their inclusion in the same replacement job is nevertheless justified. These further street sections can belong either to the same street that the triggering section belongs to, henceforth “main street”, or to other “intersecting streets” crossing the main one. The algorithm consists of two differentiated and independent parts, both providing viable work programs configurations. The first stage produces initial solutions that spread along the main street, without affecting the intersecting ones. The second part improves the initial solutions by a dynamic grouping methodology that arranges contiguous street sections considering their replacement needs, i.e., their RI. Thus, the developed DSS generates interventions that prioritize the expansion along one only street (part 1 of the algorithm) but also incorporates some network segments from other crossing streets with high RI (part 2 of the algorithm). This sequential process is illustrated in Fig. 5. Five different factors are simultaneously combined within the algorithm: street sections belonging to the same work project must (1) be geographically adjacent to each other, (2) have a similar replacement priority (RI) and (3) contain the same network type. Besides, a (4) maximum work budget and a (5) minimum affected length along the main street are also considered. The algorithm therefore includes a set of parameters. Its configuration can prioritize either the work expansion along individual streets or the replacement of sections with higher RI, regardless of whether they belong to the main or intersecting streets. The following section defines these parameters and their influence on the works configuration, whereas the next sections describe the two stages of the algorithm. 5.1. Parameters for work programs configuration Five parameters are configurable in the algorithm. Three of them intervene exclusively in the first part of the algorithm (RIT1, MINRI and MSL) and one of them (RIT2), in the second one. The last parameter (MWB) applies in both stages. •RIT1: risk index tolerance for the expansion of works along the main street. This factor, multiplied by the overall network average risk index (RI), determines the RI range within which new main street sections can be added to a certain work program. In other words, if a replacement project is triggered by a street section, whose RI is RI∗, the added sections must have a RI among RI∗±RI ×RIT1. This parameter defines a similarity range to form work programs with homogeneous replacement priority. An increase of RIT1 fosters the spreading of the works along the main street. •MINRI: multiplied by the overall network average risk index (RI), this factor determines the minimum RI that allows the inclusion of main street sections in a given a work program: if a sections’ RI is higher than RI ×MINRI, it can be added to a work program, regardless of the value of RIT1. Unlike the similarity interval provided by RIT1, this parameter defines a minimum value of the RI for other sections to belong to the work program. The aim of this parameter is to incorporate in the same work program other sections that may not have a similar RI but still have a high replacement Fig. 5. Procedure followed when implementing both stages consecutively. C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 7 priority that justifies their inclusion. A decrease of this parameter benefits the works expansion along the main street. •MSL: minimum street length affected by an intervention: a given work will spread along the main street, at least, MSL meters. An increase of this parameter also benefits the works expansion along the main street. •RIT2: risk index tolerance for the expansion of works along both the main and intersecting streets. This factor, multiplied by the overall network average risk index (RI), determines the RI range within new sections can be added to a certain work program. In other words, if a replacement project is triggered by a section whose RI is RI∗, the added sections must have a RI between RI∗±RI ×RIT2. An increase of this parameter benefits the works expansion. •MWB: maximum work budget. The total cost of a work project cannot exceed MWB € . This value may differ for each network type. An increase of MWB benefits the works expansion. 5.2. Stage 1. Distribution of the main street sections into viable works The first phase of the algorithm is applied to every street and network type separately. The idea of adjacency refers not only to contiguity among sections, but they must also contain the same network type: two sections cannot be grouped together if they do not include the same network type, even though their Voronoi regions are touching. For this reason, every street will be covered as many times as distinct network types exist in it. In this stage of the algorithm, every street is separately analyzed to allocate their constituting sections into feasible intervention projects. Hence, linked to every street, a Minimum Number of Necessary Interventions to allocate all the existing sections (MNNI) can be determined. It is calculated as the replacement cost of all street sections divided by the MWB – see Eq. (1). MNNI =street total replacement cost MWB (1) Besides, every work program is defined by a series of variables: accumulated replacement cost, affected street length, involved street sections and a unique and unambiguous identifier. Also, the interval in which new sections can be added to a given work program according to its RI is calculated. To this end, all the sections from a street are sorted according to the street numbering. Then, the ending of the sorted street sections with higher RI is first assigned to a work program. Starting from this street section, (called “reference street section”) and following the established order, the remaining sections from the street and their possible addition to the work program are studied. Every intervention must satisfy the following two conditions: (1) the maximum work budget (MWB) must not be exceeded and (2) a minimum street length along the main street (MSL) has to be affected. This second condition can be problematic: every time a section is added to a work program, the remaining street length that is still to be allocated to further interventions is reduced. For this reason, the decision to include one extra street section to a work program depends not only on the section under consideration, but also on the remaining sections in the street that are still to be allocated. Thus, an adjacent street section will not be aggregated to the work program if either of the following cases occurs: 1 The incurred cost of incorporating one additional street section exceeds MWB. 2 The current work program’s accumulated cost is higher than street total replacement cost MNNI or its accumulated affected street length is superior than street total street length MNNI and the accumulated number of work programs within the street is smaller than MNNI. This condition seeks that all work programs meet the MSL condition, avoiding the formation of too small work programs. If none of these cases are given, then the work can still be spread along the main street. To add the next adjacent section to the intervention under study, two further conditions have to be considered: 1 If the accumulated affected street length is shorter than MSL meters, then the next adjacent section will be added to the work program, regardless of its replacement priority (RI). 2 If the accumulated affected street length is longer than MSL meters, to add the next adjacent section to the work program a certain replacement priority will be required: its RI must meet the specifications established by RIT1 and MINRI. More specifically, to add a given street section to a work that has been triggered by a section whose RI is RI∗the RI of this additional section must be between RI∗±RI ×RIT1 or be higher than RI ×MINRI, where RI is the overall network average risk index. If either of these conditions is met, then the section will be added to the work program. Also, the variables defining the work, i.e., accumulated cost, affected street length and number of involved street sections, are updated. Apart from that, the complementary street values (remaining replacement cost, street length and sections) are discounted. Otherwise, if none of the remaining street sections in the street satisfies any of these conditions, the work will not expand any further and its distribution along the main street will be concluded. That work will be characterized with a distinctive identifier. Also, a work execution priority (work RI) is defined as the maximum RI of their integrating street sections. Then, the next work configuration starts, and its variables are initialized. This first stage of the algorithm is applied to all existing streets and ends when all sections are assigned to a work program. Flowchart 1 represents the sequence of steps involved. This first phase developed an initial distribution of works where every intervention covers just single streets: two different streets are not affected by the same intervention. Also, these initial configurations, while completely valid and workable, can be interpreted and further developed or modified by the managers. 5.3. Stage 2. Expansion of the resulting works by incorporating intersecting street sections The second phase of the algorithm is applied to the initial work programs resulting from the first phase. These work layouts can be further spread along both the main street or intersecting streets, dynamically shifting street sections originally assigned to a work program to a different one. These reassignments will be permanent: once a street section has been reallocated, it will not be shifted again. For this reason, the sequence in which the already existing work configurations are analyzed and rearranged is decisive. In this sense, all original work programs are first reorganized according to their execution priority (RI) and the most urgent intervention programs will be reconfigured first. The procedure is as follows: first, all the sections previously assigned to the most urgent work program will not be shifted to any other and are therefore definitive. Next, all the other sections that are adjacent to the already allocated ones are identified. These new sections belong to other works with lower execution priority, i.e., smaller RI. To include these adjacent sections to the work at issue, they must comply with two conditions: the limited work budget (MWB) must not be exceeded, and the incorporated sections must have a RI that meets the specifications defined by RIT2. This is to say, to add a given street section to a work that has been triggered by a section whose RI is RI∗, then the RI of this additional section must be between RI∗±RI ×RIT2, where RI is the overall network average risk index. The adjacent sections that meet the RI requirements will be added to the work program on a C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 8 replacement priority basis, starting with the section with higher RI, until the last section has been incorporated or the available work budget (MWB) is completely allocated. If no adjacent street section satisfies both conditions, the work will not expand any further and its configuration will be concluded. It can be noted that the higher RIT2 is, the more permissive the replacement priority condition is, and consequently the more the works can be spread. Also, if RIT2 is equal to 0, the second part of the algorithm will have no effect and the initial work programs design from the first phase will be definitive. If the last section of the list has been added and there is still available budget to spend, then a next iteration of this process is performed. A new list of sections that are adjacent to the just allocated ones is identified. Then, this list is again reduced to those that meet the RI specifications and they will be reassigned following the same procedure. This process is repeated until there are no more street sections satisfying simultaneously both the adjacency and RI conditions or the available work budget is fully allocated. In that case, the work reconfiguration will be completed and the next work program (following the order established by the RI) is targeted. Every time a section is reallocated, the variables defining the two involved works are updated. This way, it is guaranteed that all the sections in the same work program are adjacent to each other, have a similar replacement priority, and do not exceed the limited work budget. Also, when rearranging work configurations, the execution priority of the involved interventions might change. If a reassigned section was the one that triggered the intervention it originally belonged to, then its overall work RI will decrease and, therefore, the sequence in which the remaining works are analyzed is reorganized. This process is identified as “work programs update”. This second part of the algorithm ends when all the original work configurations are analyzed and all the possible rearrangements are explored. A sequence of the steps involved in this process is presented in Flowchart 2. 6. Multi-objective optimization As described in Section 5.1, the algorithm depends on five parameters that influence the resulting work designs. At this point, it raises the need for an optimization process providing the set of parameters that produces the best work programs configurations for a certain criterion (described below). Since exploring the combinatorial solution space is unfeasible within a reasonable time, a multi-objective genetic algorithm (MOGA) has been implemented along the lines of most of the reviewed works [23,25,26,32]. This algorithm required a novel fitness function that evaluates a certain work programs configuration and determines whether a given parameter’s combination outperforms the rest. 6.1. Fitness function This novel fitness function contemplates three indicators to evaluate the configurations of a given work programs planning. These are: 1 Highest existing work RI value minimization. When a street section is intervened, its RI is reduced. This value refers to the highest RI value that is not scheduled in a work programs planning and therefore is not reduced (see Eq. (2)). min max ∀non−scheduled replacement works {work RI}(2) A work execution priority (work RI) is defined as the maximum RI of their integrating street sections. For a given set of work programs, this component would be at its minimum if no sections were grouped and replaced together, but intervened one by one, according only to their replacement priority, starting with the section with higher RI until the available budget is completely allocated. In other words, if the fitness function contemplated this only factor, then the optimal solution would correspond to one section per replacement activity: every section would be individually assigned to a different work program, and every work program would consist of one only section. 2 Average amount deviation from 75% MWB minimization. The second component of the objective function minimizes the accumulated amount deviation of every scheduled intervention program from a certain target cost. In this case, 75% of the maximum work budget (see Eq. (3)). min ∑∀scheduled replacement works |Accum.cost −0.75 ×MWB| 0.75 ×MWB ×Number of scheduled replacement works (3) The planning of works whose cost is approximately 75% MWB is therefore enhanced. For example, if MWB is 1M € , then a work project of 700 k € would outperform a 650 k € intervention according to this criterion. In contrast to the first one, this component benefits the synergy of creating large intervention projects by aggregating and simultaneously replacing several contiguous street sections. Of course, this factor makes sense only if MWB is higher than the average single section cost. 3 Work configurations with linear topology. The last of the three indicators aims for a linear work configuration topology. More specifically, the two following work program layouts are sought: first, the expansion along the main street; if a certain street section has to be replaced, the replacement of the entire street may be justified. And secondly, not affecting crossing streets: a branched work configuration should be avoided. In order to evaluate both features, two ratios are defined. R1 evaluates the fraction of the main street affected as part of an intervention, and R2 quantifies the percentage of the total affected length that belongs to the main street Eqs. (4) and ((5), respectively). R1=main street affected length main street length (4) R2=main street affected length total affected length (5) A given work configuration that spreads along the whole main street length (R1=1)and does not affect other intersecting streets (R2=1) would be optimal according to this criterion. Therefore, the product of both ratios for every work configuration in a given work programs planning is to be maximized (see Eq. (6)). max ∑ ∀scheduled replacement works R1×R2(6) Once the three indicators evaluating the work programs C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 9 configurations are described, the fitness function is defined in Eq. (7). Min ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ⎛ ⎜ ⎜ ⎜ ⎝ α 1×max ∀non−sched. works {work RI} ⎞ ⎟ ⎟ ⎟ ⎠ + ⎛ ⎜ ⎜ ⎜ ⎝ α 2× ∑∀sched. works |Accum.cost −0.75 ×MWB| 0.75 ×MWB ×N∘sched.works ⎞ ⎟ ⎟ ⎟ ⎠ + ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ α 3× ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ 1−∑ ∀sched. works R1×R2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎭ (7) Note that, since the third indicator was to be maximized, it has been modified as “1−∑ ∀sched. works R1×R2” in the global expression. Also, each term of the fitness function is multiplied by its corresponding weight: α 1, α 2 and α 3. These weights, that add up to 1, represent the company’s strategic policy for work programs configurations, i.e., its perspective on which factors are more relevant. Therefore, the set of weights for a given water utility may not be suitable for a different one. In order to find the parameters that obtain the best work programs configurations for a given set of weights, this is, the minimum value for the fitness function, we designed a multi-objective genetic algorithm (MOGA). The structure of the developed MOGA is described in the next section. 6.2. Structure of the MOGA and solution encodings A genetic algorithm is a metaheuristic inspired by the process of natural selection, where the fittest individuals survive and reproduce. Regarding the solution codification, an individual or chromosome consists of a five-component vector, each one of them being a parameter of the algorithm. Table 1 shows an example of chromosome. The implemented genetic algorithm presents the following structure. First, an initial population of population_size individuals is randomly generated. Then, all individuals are evaluated by the fitness function. From this population, the fittest individuals will survive and reproduce, whereas the worst evaluated will be replaced by the new generations. This process is repeated for max_iterations. The fittest individuals are selected by “tournament selection”. According to this technic, tournament_size individuals are chosen at random from the population and the two fittest chromosomes are selected for reproduction (parents). Then, with a probability of p_crossover, their genetic information is combined to generate new offspring (two new children). A two-point crossover, in which both points are randomly picked, is utilized. An adapted example of this procedure can be seen in Fig. 6. Next, with a likelihood of p_mutation, each child can mutate by altering one or more gene values in the chromosome. Again, a two-point mutation is used (see Fig. 7). In the last step of the iterative process, the children replace two other individuals from the population, which are once again chosen by “tournament selection”. On this occasion, tournament_size individuals are randomly picked from the population and the two worse chromosomes among them are removed. Finally, the best solution corresponds to the fittest individual from the last generation when all iterations are completed. A scheme of the implemented GA is shown in Pseudocode 1. 7. Application to a case study Our methodology has been applied to EMASESA, the public water Table 1. Example of individual. RIT1 (-) MINRI (-) RIT2 (-) MSL (m) MWB (k € ) 1.2 1.9 0.8 70 800 Fig. 6. Example of two-point crossover. Fig. 7. Example of two-point mutation. Fig. 8. Number of street sections within a certain RI range. Fig. 9. EMASESA network characterization according to its replacement priority (RI). C. Ramos-Salgado et al. Reliability Engineering and System Safety 216 (2021) 107967 16 [7] Shahata K, Zayed T. Integrated risk-assessment framework for municipal infrastructure. J Constr Eng Manag 2016;142:04015052. https://doi.org/10.1061/ (ASCE)CO.1943-7862.0001028. [8] Rasoulkhani K, Mostafavi A, Cole J, Sharvelle S. Resilience-based infrastructure planning and asset management: Study of dual and singular water distribution infrastructure performance using a simulation approach. Sustain Cities Soc 2019; 48:101577. https://doi.org/10.1016/j.scs.2019.101577. [9] Abu Samra S, Ahmed M, Hammad A, Zayed T. Multiobjective framework for managing municipal integrated infrastructure. J Constr Eng Manag 2018;144: 04017091. https://doi.org/10.1061/(asce)co.1943-7862.0001402. [10] Robles-Velasco A, Cort´ es P, Mu˜ nuzuri J, Onieva L. Prediction of pipe failures in water supply networks using logistic regression and support vector classification. Reliab Eng Syst Saf 2020;196:106754. https://doi.org/10.1016/j. ress.2019.106754. [11] Jara-Arriagada C, Stoianov I. Pipe breaks and estimating the impact of pressure control in water supply networks. Reliab Eng Syst Saf 2021;210:107525. https:// doi.org/10.1016/j.ress.2021.107525. [12] Chen TYJ, Guikema SD. Prediction of water main failures with the spatial clustering of breaks. Reliab Eng Syst Saf 2020;203:107108. https://doi.org/ 10.1016/j.ress.2020.107108. [13] Wang Z, Li S. Data-driven risk assessment on urban pipeline network based on a cluster model. Reliab Eng Syst Saf 2020;196. https://doi.org/10.1016/j. ress.2019.106781. [14] Baah K, Dubey B, Harvey R, McBean E. A risk-based approach to sanitary sewer pipe asset management. Sci Total Environ 2015;505:1011–7. https://doi.org/ 10.1016/j.scitotenv.2014.10.040. [15] D’Ercole M, Righetti M, Raspati GS, Bertola P, Ugarelli RM. Rehabilitation planning ofwater distribution network through a reliability-based risk assessment. Water (Switzerland) 2018;10. https://doi.org/10.3390/w10030277. [16] Mu˜ nuzuri J, Ramos C, V´ azquez A, Onieva L. Use of discrete choice to calibrate a combined distribution and sewer pipe replacement model. Urban Water J 2020;17: 100–8. https://doi.org/10.1080/1573062X.2020.1748205. [17] Phan HC, Dhar AS, Hu G, Sadiq R, Chi H, Sutra A, et al. Managing water main breaks in distribution networks––a risk-based decision making. Reliab Eng Syst Saf 2019;191:106581. https://doi.org/10.1016/j.ress.2019.106581. [18] Salehi S, Jalili Ghazizadeh M, Tabesh M, Valadi S, Salamati Nia SP. A risk component-based model to determine pipes renewal strategies in water distribution networks. Struct Infrastruct Eng 2020;0:1–22. https://doi.org/ 10.1080/15732479.2020.1842466. [19] Bouvard K, Artus S, B´ erenger C, Cocquempot V, B´ erenguer C, Cocquempot V. Condition-based dynamic maintenance operations planning & grouping. Application to commercial heavy vehicles. Reliab Eng Syst Saf 2011;96:601–10. https://doi.org/10.1016/j.ress.2010.11.009. [20] Elsawah H, Guerrero M, Moselhi O. Decision support model for integrated intervention plans of municipal infrastructure. In: ICSI 2014 Creat Infrastruct a Sustain World - Proc 2014 Int Conf Sustain Infrastruct; 2014. p. 1039–50. https:// doi.org/10.1061/9780784478745.098. [21] Elsawah H, Bakry I, Moselhi O. Decision support model for integrated risk assessment and prioritization of intervention plans of municipal infrastructure. J Pipeline Syst Eng Pract 2016;7. https://doi.org/10.1061/(ASCE)PS.1949- 1204.0000245. [22] Tscheikner-Gratl F, Sitzenfrei R, Rauch W, Kleidorfer M. Integrated rehabilitation planning of urban infrastructure systems using a street section priority model. Urban Water J 2016;13:28–40. https://doi.org/10.1080/ 1573062X.2015.1057174. [23] Nafi A, Kleiner Y. Scheduling renewal of water pipes while considering adjacency of infrastructure works and economies of scale. J Water Resour Plan Manag 2010; 136:519–30. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000062. [24] Kleiner Y, Nafi A, Rajani B. Planning renewal of water mains while considering deterioration, economies of scale and adjacent infrastructure. Water Sci Technol Water Supply 2010;10:897–906. https://doi.org/10.2166/ws.2010.571. [25] Li F, Sun Y, Ma L, Mathew J. A grouping model for distributed pipeline assets maintenance decision. In: ICQR2MSE 2011 - Proc 2011 Int Conf Qual Reliab Risk, Maintenance, Saf Eng; 2011. p. 601–6. https://doi.org/10.1109/ ICQR2MSE.2011.5976684. [26] Li F, Ma L, Sun Y, Mathew J. Optimized group replacement scheduling for water pipeline network. J Water Resour Plan Manag 2016;142:1–10. https://doi.org/ 10.1061/(ASCE)WR.1943-5452.0000559. [27] Rokstad MM, Ugarelli RM. Minimising the total cost of renewal and risk of water infrastructure assets by grouping renewal interventions. Reliab Eng Syst Saf 2015; 142:148–60. https://doi.org/10.1016/j.ress.2015.05.014. [28] Carey BD, Lueke JS. Optimized holistic municipal right-of-way capital improvement planning. Can J Civ Eng 2013;40:1244–51. https://doi.org/10.1139/ cjce-2012-0183. [29] Roshani E, Filion YR. Event-based approach to optimize the timing of water main rehabilitation with asset management strategies. J Water Resour Plan Manag 2014; 140:1–11. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000392. [30] Kerwin S, Adey BT. Optimal intervention planning: a bottom-up approach to renewing aging water infrastructure. J Water Resour Plan Manag 2020;146. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001217. [31] Kielhauser C, Adey BT, Lethanh N. Investigation of a static and a dynamic neighbourhood methodology to develop work programs for multiple close municipal infrastructure networks. Struct Infrastruct Eng 2016;13:361–89. https:// doi.org/10.1080/15732479.2016.1162818. [32] Kielhauser C, Adey BT. Determination of intervention programs for multiple municipal infrastructure networks: considering network operator and service costs. Sustain Resilient Infrastruct 2018;5:49–61. https://doi.org/10.1080/ 23789689.2018.1497879. [33] Dekker R. Applications of maintenance optimization models: a review and analysis. Reliab Eng Syst Saf 1996;51:229–40. https://doi.org/10.1016/0951-8320(95) 00076-3. [34] Zio E˜ A. Reliability engineering : old problems and new challenges. Reliab Eng Syst Saf 2009;94:125–41. https://doi.org/10.1016/j.ress.2008.06.002. C. Ramos-Salgado et al.