FORM 2
THE PATENTS ACT, 1970 (39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
1. Title of the invention: METHOD AND SYSTEM FOR BOOSTER PUMP PLACEMENT
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Nirmal Building, 9th Floor, Nariman Point,
Indian
SERVICES LIMITED Mumbai, MH 400021, India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.

TECHNICAL FIELD
[0001] The subject matter described herein relates to water distribution networks and,
particularly but not exclusively, to systems and methods for determining locations for placement of pumps in a water distribution network.
BACKGROUND
[0002] Water distribution networks are commonplace in urban, semi-urban, and
nowadays, even in rural areas. A water distribution network is generally planned in a manner so that it can satisfy water demands of all end users, or consumers, in a manner so as to provide water suitable for consumption. Generally, a utility manages the water distribution network in and around a locality and takes care of operation and maintenance-related needs of the water distribution network.
[0003] A typical water distribution network includes various components necessary
for water supply including pipes, pumps, valves, and storage tanks. Generally, these components are deployed for being used over a long period of time. For example, a pipe, which is typically laid underground, is generally deployed for a period of around 60 years. The implication of such a high life time of these components is that once they are laid, they are not replaced until well after their life time. Moreover, it will not be cost-effective to make changes to the current infrastructure on a frequent basis. However, during the last few decades, human population has grown at a significantly high rate, with most of it occurring in sub-urban and urban areas. For instance, population in Faridabad (a city in northern India) has increased by nearly 1000% in a span of three decades--from 122,000 in 1971 to over 1,000,000 in 2001. Such phenomenal growth in population has put a substantial pressure on the water utilities.
SUMMARY
[0004] This summary is provided to introduce concepts related to supplying water in a
water distribution network. These concepts are further described below in the detailed description. This summary is neither intended to identify essential features of the claimed

subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[0005] The subject matter described herein relates to systems and methods for
determining locations for the placement of one or more pumps, as well as pump capacities, in a water distribution network to meet requirements of one or more pressure deficient locations in the water distribution network. In an implementation, the method includes receiving, through a user interface, a first set of information and a second set of information pertaining to the water distribution network that includes links that include at least one of one or more pipes, one or more junctions, one or more pumps, one or more valves, and one or more reservoirs. The first set of information includes information about a location of at least one link. The second set of information includes at least one of a flow rate and a pressure value at a junction in the water distribution network. An initial graph is generated, wherein the initial graph includes a plurality of nodes and a plurality of edges, wherein each edge represents a pipe and each node represents a junction. Further, a weight is assigned to the plurality of nodes of the initial graph, wherein the weight assigned to a node is indicative of a cumulative cost of placement and operation of a pump at a location for managing pressure requirement of one or more nodes, including the node, downstream of the location. Based on the initial graph, a weighted transformed graph is generated by applying a graph-theoretic approach.
BRIEF DESCRIPTION OF THE DRAWINGS
[0006] The detailed description is provided with reference to the accompanying
figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and components.
[0007] Fig. 1 illustrates a pump location identifier system, in accordance with an
embodiment of the present subject matter.
[0008] Fig. 2 illustrates an initial graph and a transformed graph generated by the
pump location identifier system, in accordance with an embodiment of the present subject matter.

[0009] Fig. 3 illustrates a method for determining an optimal location for placement of
a pump in a water distribution network, in accordance with an implementation of the present subject matter.
[00010] Fig. 4 illustrates a method for generating a transformed graph, in accordance
with an embodiment of the present subject matter.
DETAILED DESCRIPTION
[00011] The subject matter described herein relates to systems and methods for
determining locations for placement of pumps and pump capacities, in a water distribution network to boost a delivery pressure at certain end-points in the water distribution network. The system(s) and method(s) described herein can be implemented on a variety of devices, such as a server, a desktop computer, a notebook or a portable computer, a mainframe computer, a mobile computing device, and the like.
[00012] Water distribution networks having a “tree” topology are known in the art.
Generally, in such networks, as water demand increases, a water utility managing the water distribution network increases a flow rate through pipes. Because of the increased flow rate, pressure drops at endpoints of a segment through which the flow rate has increased. The pressure drop, as will be appreciated by a person skilled in the art, is due to frictional losses, and is proportional to a square of a velocity of the flow in the pipe. However, water utilities cannot let the pressure at an end point fall to low values as they are generally bound to supply water at a minimum delivery pressure. For instance, water utilities in Great Britain compensate a consumer if the pressure of their supply falls below a minimum of 21.3psi. Therefore, the water utilities boost the delivery pressure at such pressure deficient end-points, for which they need to install booster pumps or replace existing booster pumps with higher capacity booster pumps. However, finding locations for the placement of the booster pumps as well as determining capacities of the booster pumps is in itself a technical challenge, and require a lot of cost-related considerations.
[00013] In case the delivery pressure at a certain end-point is reported to be low or
below a threshold for a substantial period of time, or is expected to drop in the near future due

to an expected growth in consumption, or some more end-points are newly added to the water distribution network, the water utilities install booster pumps, hereinafter referred to as pumps. The pumps boost pressure at one or more pressure deficient end-points in the water distribution network. Besides, the water utility may also replace a low capacity pump with a higher capacity pump to meet the increased delivery pressure demands at the one or more pressure deficient end-points. This typically solves the delivery pressure problem. However, conventional solutions do not approach the problem in order to solve it in a cost-effective manner. Moreover, the whole task of determining pump locations is in itself a technical challenge.
[00014] To determine locations for placement of pumps in a water distribution
network, the present subject matter describes a system and a method that help transform the aforesaid delivery pressure problem into a minimum weighted dominating set problem. In addition, the present subject matter allows determination of pump capacities required for boosting pressure at one or more pressure deficient locations as well as operating conditions required for providing an acceptable delivery pressure to one or more end user(s). The system, by implementing the method as described herein, based on various sets of information received, for example, from on-field devices, generates a hydraulic model for the water distribution network and executes the hydraulic model to provide a set of locations for the placement of pumps that are capable of meeting the delivery pressure demands of the one or more pressure deficient locations in the water distribution network. The resulting placement of pumps not only meets the water pressure requirements, but is also is cost-effective and optimal.
[00015] In an implementation, a first set and a second set of information pertaining to
the water distribution network is received by the system. The water distribution network may comprise links that include components such as pipes, pumps, valves, and reservoirs. Further, a location where any two pipes meet or a single delivery pipe terminates may be referred to as a junction, or interchangeably a node. The first set of information may include information about the links, i.e., the pipes, the pumps, the valves, and the reservoirs, in the water distribution network. The second set of information includes details such as pressure values at one or more junctions, flow rates along one or more pipes, etc. The nodes may either be an

already existing node in the water distribution network or a new node added recently to the water distribution network or a node expected to be added in the future.
[00016] Based on the information received, the system generates an initial graph. In an
implementation, the system generates a hydraulic model on the basis of the information received, and the initial graph is based on the hydraulic model. In an implementation, the initial graph may be directly generated based on the information received. In another implementation, the initial graph is generated partly based on a location constraint or a cost function or both. The location constraint may include a pump placement constraint at a location upstream of a node, while the cost function can be a function considered by the water utility for saving on costs. The initial graph includes a plurality of nodes and edges, wherein each edge represents a pipe section and each node represents a junction or an end-point. Further, a weight may be assigned to each node of the initial graph. The weight assigned to a node, for example, is indicative of a cumulative cost of placement and operation of a pump at a location for managing a pressure requirement of one or more pressure deficient nodes downstream including the node itself. Further, a graph-theoretic approach is applied to generate a weighted transformed graph based on the initial graph. In an implementation, the first set of information may also include information related to a geographical terrain on which the water distribution network is deployed. Further, the second set of information may further include information about a plurality of types of pumps available, their corresponding capacities, related costs, etc.
[00017] In order to generate the weighted transformed graph, all nodes, both existing
and expected, in the water distribution network are added to provide a first set of nodes indicative of all possible pump placement locations in the water distribution network. Further, pressure deficient nodes, both existing and expected, in the water distribution network are added to form a second set of nodes. In addition, directed edges from a node in the first set to the nodes in the second set whose pressure requirement can be satisfied by placing a pump at the node are added. Also, internal edges among the nodes in the first set that are indicative of redundancy existing in pump placement locations are added. The resultant directed edges and the internal edges are added to provide the transformed graph.

[00018] The method further includes converting the weighted transformed graph into
an instance of a minimum weighted dominating set, wherein the minimum weighted dominating set includes one or more nodes that are indicative of locations for the placement of pumps. Once the locations are identified, pump capacities are determined accordingly.
[00019] Furthermore, in accordance with an embodiment of the present subject matter,
a pump location identifier system for determining locations for placement of pumps as well as pump capacities, in a water distribution network, is described. The water distribution network includes links that include one or more of pipes, junctions, valves, reservoirs, etc. The pump location identifier system includes a processor, a memory coupled to the processor, and various modules stored in the memory including a hydraulic modeling module. The hydraulic modeling module generates a hydraulic model based on information comprising at least one of topological information pertaining to the one or more links in the water distribution network and at least one of a flow rate and a water pressure at one or more links. Further, an execution module executes the hydraulic model to provide an initial graph, wherein a weight is assigned to each node of the initial graph. In an implementation, the weight assigned to a node is indicative of a cumulative cost of placement and operation of the pump at a location for managing pressure requirement at one or more nodes, including the node, downstream of the location. Further, the system includes a graph-theoretic module which generates a weighted transformed graph based on the initial graph, wherein the graph-theoretic module converts the weighted transformed graph into an instance of a minimum weighted dominating set, which is indicative of one or more locations for the placement of pumps.
[00020] In an implementation, the execution module executes the hydraulic model
based at least on one of information about capacities of a plurality of types of pumps available and information about a pump placement constraint, a cost function as defined by the water utility, or both.
[00021] The system and method as described herein may be implemented in an existing
water distribution network as well as in a newly planned water distribution network for an upcoming town. The system may also respond to current as well as future delivery pressure needs of one or more water pressure deficient locations in a given network. The system achieves these aims by determining locations for the placement of pumps by taking into

consideration costs as well as capacities of different pumps available in the market. The system also takes into consideration factors including a cost of placement and/or operation of such pumps, placement constraints in a given location, cost function as defined by the water utility, etc., thus providing a cost-effective solution to the delivery pressure problem.
[00022] While aspects of described systems and methods for determining locations for
placement of pumps in a water distribution network can be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following exemplary system architecture(s).
[00023] Fig. 1 illustrates a pump location identifier system 100, in accordance with an
embodiment of the present subject matter. The pump location identifier system 100, hereinafter interchangeably referred to as system 100, may be implemented in a variety of computing systems, such as a laptop computer, a desktop computer, a notebook, a workstation, a mainframe computer, a server, a network server and the like. In one implementation, the system 100 includes interface(s) 105, one or more processor(s) 110, and a memory 115 coupled to the processor(s) 110.
[00024] The interfaces 105 may include a variety of software and hardware interfaces,
for example, interfaces for peripheral device(s), such as a keyboard, a mouse, an external memory, and a printer. Further, the interfaces 105 may enable the system 100 to communicate with other devices, such as web servers and external databases. The interfaces 105 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example local area network (LAN), cable, etc., and wireless networks such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the interfaces 105 may include one or more ports for connecting a number of computing systems with one another or to another server computer.
[00025] The processor 110 can be a single processing unit or a number of units, all of
which could include multiple computing units. The processor 110 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals

based on operational instructions. Among other capabilities, the processor 110 is configured to fetch and execute computer-readable instructions and data stored in the memory 115.
[00026] The memory 115 may include any computer-readable medium known in the art
including, for example, volatile memory such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. The memory 115 also includes program module(s) 120 and program data 125. The program modules 120, amongst other things, include routines, programs, objects, components, data structures, etc., which perform particular tasks or implement particular abstract data types. The program modules 120 further include a hydraulic modeling module 130, an execution module 133, a graph theoretic module 135, and other modules 140. The other modules 140 may include programs or coded instructions that supplement applications and functions of the system 100.
[00027] Further, the program data 125 includes pressure data 145, flow data 150, and
other data 155. The other data 155 includes data generated as a result of the execution of one or more modules in the other modules 140. The interface(s) 105 may include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, etc., allowing the system 100 to interact with a user, for example, a line man doing inspection of water lines to take various readings from various junctions. Further, the interface(s) 105 may enable the system 100 to communicate with one or more computing devices, such as web servers and external data servers (not shown in figure). The interface(s) 105 may include one or more ports for connecting the system 100 to a number of devices to the system 100 or to another server. On the other hand, the program data 125 serves, amongst other things, as a repository for storing data processed, received, and generated by one or more of the program modules 120.
[00028] In one implementation, the system 100 is associated with a reference database
160. The reference database 160 can be either external or internal to the system 100. In an implementation, the reference database 160 includes a node pressure database 162, which stores information pertaining to a pressure boost required at each node in the water distribution network. The system 100 communicates with the reference database 160 to

analyze various inputs received by the system 100. The system 100 may compare, for example, pressure values received from various nodes with predetermined pressure values at those particular locations as stored in the node pressure database 162, or a particular pressure value that is required for all the nodes in the water distribution network.
[00029] In an implementation, the system 100 receives data pertaining to flow and
pressure at various pipes and nodes, respectively, in the water distribution network and accordingly calculates pressure deficiency at a node, by methods and/or expressions known in the art. In an environment in which the present system works, various pressure meters and flow meters may be installed at various nodes and pipes in the water distribution network. These meters may measure the pressure data or the flow data and either provides the same to the system 100, preferably in real time, through a communication network, or the data can be recorded for the purpose of being fed later into the system 100. Subsequently, the hydraulic modeling module 130, based on such data, generates a hydraulic model of the water distribution network. The hydraulic modeling module 130 then executes the hydraulic model to predict existing as well as expected pressure deficiencies at various nodes in the water distribution network considering current and future demands. This predicted existing and expected pressure deficiencies at various nodes can be stored in the node pressure database 162 for future reference.
[00030] The reference database 160 may also include a network topology database 164,
which stores information pertaining to an interconnection between various links of the water distribution network such as locations of pipes, pumps, valves, etc. The network topology database 164 may further include terrain information including height, slope, and other geographical information affecting the flow in a locality in the water distribution network. Further, the reference database 160 includes a pumps database 166 and a utility database 168. The pumps database 166 contains a list of types of pumps and corresponding capacities as available in the market. The pumps database 166 also includes data pertaining to costs of setting up a pumping station at a given location to boost the pressure at a set of nodes. These costs may include cost of real estate of the location, cost of shelter for the pumping station, cost of pump controls, etc. On the other hand, the utility database 168 may store information relating to various constraints and/or preferences that a water utility may have in terms of

placing a pump at and around a node, for example, lack of real estate and lack of availability of a particular pump in the market. The utility database 168 may also contain objective functions that the water utility may be interested in optimizing, for example, capital expenditure (capex), operation expenditure (opex), total cost of ownership, etc.
[00031] In an implementation, the hydraulic modeling module 130 generates a
hydraulic model of the water distribution network based partly on information including topological information pertaining to the water distribution network, structural characteristics of pipes, operational schedule of available pumps, nodal demands, etc. The execution module 133 may assimilate such information to provide the hydraulic model. The execution module 133, based on the hydraulic model, then generates an initial graph. In another implementation, the execution module 133 may directly provide the initial graph based on the information received. For example, flow meters and pressure meters may be installed at pipes or junctions in the water distribution network to measure flow rates and water pressures, respectively, at various locations in the water distribution network. All such measured information, for example, flow rates and pressure, may be provided to the hydraulic modeling module 130 to generate the hydraulic model. The initial graph includes nodes which represent all possible pump placement locations in the water distribution network. In an implementation, the execution module 133 receives information such as information about capacities of a plurality of pump types available in the market, information about pump placement constraints at a given location, and a cost function to be lowered as desired by the water utility. The execution module 133 may also assign weights to each of the nodes. The weight assigned to a node may represent, for example, a cumulative cost of placement and operation of the pump at a location to boost pressure at one or more pressure deficient nodes, including the node itself, downstream of the location.
[00032] In order to elucidate the functioning of the system 100 in synchronization with
the reference database 160, one may refer to figure 2. Figure 2 shows transformation of an initial graph 200 to a transformed graph 200’, wherein the transformed graph 200’ represents a redundancy among various locations in the water distribution network for the placement of the pumps to satisfy pressure needs of the one or more pressure deficient nodes. The transformed graph 200’ is solved using the system and/or method as described herein so as to

provide a set of locations for the placement of pumps in the water distribution network. The water distribution network represented by the initial graph 200, may include a number of pump stations 202-1, 202-2, …202-z, hereinafter collectively referred to as the pumps 202, and valves (not shown), which will also be in operation to control a flow in the water distribution network. For the purpose of ease of explanation, the pipes, the valves, the pumps, and/or the reservoirs may also be referred to as "links," either individually or collectively. Also, each junction in the water distribution network, i.e., a location where a pipe meets another pipe or a consumer end point will be hereinafter interchangeably referred to as a node.
[00033] In an implementation, the initial graph 200 includes nodes or junctions A, B,
C, D, E, and edges or links (shown by arrows between the nodes). Out of these nodes, nodes C, D, and E are assumed to be pressure deficient nodes. To boost the pressure at these nodes, the pumps 202 can be placed at different locations in the water distribution network. For instance, a pump of appropriate size can be placed along the edge [D, E] in front of the node E to satisfy pressure requirements at E. As an alternative, a bigger, and probably costlier, pump could be placed along the edge [B, D] in front of the node D to satisfy pressure requirements at both D and E. One may also place an even bigger, and even costlier, pump in front of the node B along the edge [A, B] to meet the pressure requirements of all the three nodes C, D, and E. Thus, placing a pump at or around a node in the flow graph may meet the pressure requirements of zero, one, or more pressure deficient nodes in such a water distribution network at an appropriate cost.
[00034] This implies that a set of all the nodes served through the water distribution
network represents a universal set of all possible locations where a pump can be placed. In an implementation, a number of such locations can be filtered down based on certain predefined constraints and/or parameters, such as constraints defined by the utility, real-estate constraints, cost constraints, and pump specification constraints. For each node that is part of the universal set, a required pump capacity and corresponding cost can be determined. Let the cost of placement of a pump in front of a node X be c(X). This cost includes a cost of the pump itself and a cost of ownership of the pump at that particular location. In an implementation, this cost is assigned as a weight to the node X.

[00035] In an implementation, in order to find a set of locations for the placement of
the pumps 202 in the water distribution network, the initial graph 200 is processed using graph theoretic approaches. In an implementation, the following algorithm may be used to process the graph 200 (interchangeably referred to as Graph P):
Graph P = (V, E);
wherein V indicates set of nodes, E indicates set of edges in the form of adjacency list. For all source nodes S in V: PRE-PROCESSING(S)
PROCESS-LEAF(N):
N is a leaf node
1 if N.inFlow > 0:
2 N.deficiency = N.pressure – P_MIN
3 if N.deficiency > 0:

4 N.pumpPower = N.inFlow*N.deficiency* const
5 N.cost = getCost(N.pumpPower);
PROCESS-NON-LEAF(N):
N is a non-leaf node
1 if N.inFlow > 0:
2 N.deficiency = N.pressure – P_MIN
3 for each successor M of N:
4 if M.deficiency > N.deficiency:
5 N.deficiency = M.deficiency;
6 if N.deficiency > 0:
7 N.pumpPower = N.inFlow*N.deficiency* const
8 N.cost = getCost(N.pumpPower);
PRE-PROCESSING(root)
Post order traversal 1 stack = {}

2 stack. append(root)
3 while stack is not empty:
4 N = stack.peek(); // Get the most recently inserted element in stack
5 if N has successors:
6 hasVisitedAllSuccessors = True;
7 for each successor M of N:
8 if M. visited == False:
9 hasVisitedAllSuccessors = False;
10 stack. append(M)
11 if hasVisitedAllSuccessors == True:
12 PROCESS-NON-LEAF (N)
13 N. visited = True
14 Remove N from stack
15 else:
16 PROCESS-LEAF (N)
17 N. visited = True
18 Remove N from stack
[00036] Further, a set of locations Q for the placement of pumps in the water
distribution network is determined. In an implementation, the following algorithm may be used to model a redundancy among various locations for the placement of the pumps 202 in the water distribution network to satisfy pressure needs of one or more pressure deficient nodes
P is the input flow graph; Q = (V, E) is returned;
Let V = V1 UV2 ;
Let N(v) be the set of neighbors of vertex v; V1 ←{ }; V2 ← { }; E ← { };
for each node x in P
do V1 ← V1 U {x);

if x is pressure deficient then V2 ←V2 U(x '); for each node x in V1
do for each y in V2;
if a pump at x can give required boost at y then E ← E U(x,y);
for each x in V1
do for each y in {V1 - x};
if (N(y) ∩ V2) (N(x)∩V2)
then E ← E U(x,y) return Q
[00037] Here, P, or the initial graph 200, following preprocessing, is provided as an
input to the graph theoretic module 135. Based on the input, the graph theoretic module 135 provides a transformed graph Q, wherein Q can be represented in the form of a matrix structure (V, E). V represents a total number of nodes in the water distribution network while E represents a total number of edges. Further N (v) is taken as a set of neighbors of a node v.
[00038] The graph theoretic module 135 adds existing nodes in the water distribution
network to provide a first set indicative of all possible pump placement locations in the water distribution network. In an implementation, the graph theoretic module 135 sums up pressure deficient nodes, both existing and expected, in the water distribution network to form a second set. Then, directed edges from a node in the first set to the nodes in the second set whose pressure requirement can be satisfied by placing a pump at the node are added to the transformed graph. For example, placing a pump at B can meet the pressure requirements of nodes C, D’, and E’. So, edges {(B, C), (B, D’), (B, E’)} are added to Q. Further, internal edges among the nodes in the first set are added to the transformed graph, wherein the internal edges are indicative of redundancy existing in the pump placement locations. For example, a pump placed at node A in the initial graph will make the pumps placed at nodes B, C, D, and E redundant. Therefore, the edges {(A, B), (A, C), (A, D), (A, E)} are added to Q.

[00039] In an implementation, the graph theoretic module 135 determines a weighted
transformed graph 200’ based on the transformed graph by assigning weights to the each of the nodes of the transformed graph. It will be appreciated that the weights that were assigned to each node of the initial graph would correspond automatically to the same node of the transformed graph. Based on the weighted transformed graph 200’, the graph theoretic module 135 determines a MWDS based on the weighted transformed graph, wherein the MWDS comprises at least one junction indicative of a location for the placement of a pump. Such a weighted transformed graph has the property that its nodes correspond to a set of locations at which pumps should be placed. The MWDS on Q can be determined using any conventional methodology.
[00040] For example, the MWDS can be determined based on the following algorithm:
Consider a weighted minimum dominating Set G = {V, E}
1 C ← { }
2 N(s) = {neighbor of s}
3 f(C) = { N(s) for all s Є C } U {C}
4 Repeat until f(C) = V

5 choose s Є {V - C} such that (Ws /│ f(C U{s})-f(C) │) is minimized
6 C ← C U {s}
[00041] Once these locations are identified, pump capacities can be accordingly
prescribed. In an implementation, the capacity of a pump to be placed is chosen such that it can provide a pressure boost required by any one of a downstream node. It will be appreciated that the pressure boost required to satisfy any one downstream node is equal to a maximum pressure boost required by all the downstream nodes. The required boost capacity can be approximated by calculating a product of the pressure boost required and a flow volume to be handled by the pump. Once the required capacity is known, the availability of such a pump is checked in the market. In case there is no pump available in the market with the required pump capacity, a pump with the nearest high capacity available is chosen and a cumulative cost of placement and operation, i.e., capex and opex, is determined. In an implementation, if

the capacity requirement is too high to be satisfied by a single pump, multiple pumps, in series, and having a sum total capacity equal to the required capacity, may be used.
[00042] Fig. 3 illustrates a method 300 for determining an optimal location for
placement of a pump in a water distribution network, in accordance with an implementation of the present subject matter. Fig. 4 illustrates a method 400 for generating a transformed graph with nodes depicting locations for placement of pumps, in accordance with an embodiment of the present subject matter. The methods 300 and 400 are described with reference to the description of preceding figures for the purpose of ease of description and should not be construed limiting as such.
[00043] The order in which the methods 300 and 400 are described is not intended to
be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the methods 300 and 400. Additionally, individual blocks may be deleted from the methods 300 and 400 without departing from the spirit and scope of the subject matter described herein. Furthermore, the methods 300 and 400 can be implemented in any suitable hardware, software, firmware, or combination thereof.
[00044] With regard to method 300, at block 302, a first set and second set of
information is received. The first set of information may include information related to a topology of the water distribution network, for example, a location of one or more pipes, a location of one or more pumps existing in the water distribution network, a location of one or more valves, and a location of one or more tanks in the water distribution network. The second set of information may include flow rates, pressure values, or both, received from at least one pressure deficient location in the water distribution network. The first set of information may also include information of a geographical terrain on which the water distribution network is deployed. The second set of information may further include at least one of a pressure deficiency at a new node, capacities of a plurality of types of pumps available, and related costs of the plurality of pumps.
[00045] At block 304, an initial graph is generated. In an implementation, a hydraulic
model of the water distribution network is generated based on the first and the second sets of information. Subsequently, the initial graph is generated based on the hydraulic model by

executing the hydraulic module. However, the initial graph may be generated directly as well. In an implementation, the initial graph generation may also depend on at least one location constraint, a cost function, etc. The location constraint may include a geographical constraint or a real estate constraint, while the cost function can be a function considered by the water utility managing the water distribution network for saving on the costs. The initial graph comprises a plurality of nodes and edges, and wherein each edge represents a pipe and each node represents a junction between any two pipes. In an implementation, the hydraulic model can be calibrated based on techniques known in the art using data from flow and pressure meters installed at various locations in the water distribution network.
[00046] At block 306, a weight is assigned to each node of the initial graph. The weight
assigned to a node is indicative of a cumulative cost of placement and operation of a pump at that node to meet the pressure deficiencies of that node and its downstream nodes.
[00047] At block 308, a transformed graph is generated based on the initial graph by
applying a graph-theoretic approach. In an implementation, the initial graph having weighted nodes is transformed into the transformed graph, which is again a weighted graph, by using a graph-theoretic approach as defined by the present subject matter. It will be appreciated that each node of the initial graph is present in the transformed graph and carries the same weight as was assigned to the node in the initial graph. The transformed graph includes a minimum weighted dominating set, wherein the minimum weighted dominating set includes at least one node that is indicative of the optimal location for placement of a pump. This minimum weighted dominating set can be determined using any conventional solution methodologies.
[00048] In the context of figure 4, a method 400 describing generation of a transformed
graph having nodes depicting locations for placement of pumps includes, at block 402, inputting an initial graph having nodes and edges. For example, a graph such as the graph 200 is input to the system 100. At block 404, all nodes in the initial graph are added to provide a first set of nodes indicative of all possible pump placement locations in the water distribution network. This means that the first set is a universal set comprising all the nodes, such as the nodes A, B, C, D, and E in the water distribution network.

[00049] At block 404, all pressure deficient nodes, both existing and expected, with
regard to the water distribution network are added to form a second set of pressure deficient nodes. For example, according to graph 200’ shown in Fig. 2, new nodes C’, D’, and E’ are added to the second set as representative of water deficient nodes.
[00050] At block 406, directed edges from a node in the first set to the nodes in the
second set whose pressure requirement can be satisfied by placing a pump at the node are added. For example, placing a pump at node B, according to graph 200’, can meet the pressure requirements of the nodes C’, D’, and E’.
[00051] At block 408, internal edges among the nodes in the first set are added. The
internal edges are indicative of redundancy existing in pump placement locations. For example, a pump placed at a node A in the graph 200 will make the pumps placed at nodes B, C, D, and E redundant. This is because, any pump if placed at A will be chosen such that it has the minimum capacity to meet the pressure requirements of all downstream nodes. Therefore, no pumps are required at nodes B, C, D, or E to meet the pressure boost requirements.
[00052] At block 410, the transformed graph is returned by adding results derived at
blocks 406 and 408. As already discussed in the description of method 300 earlier, weights are assigned to the nodes corresponding to the graph 200, which also correspond to the same nodes in the graph 200’. Thus, the transformed graph is a weighted graph and has the property that it includes a minimum weighted dominating set (MWDS), which can be identified by using techniques known in the art. The MWDS provides a set of locations for the placement of pumps in the water distribution network that would be the most cost effective. By virtue of the graph transformation and the MWDS property, the nodes in the MWDS will have nodes C, D, E and also nodes C’, D’, and E’ as their neighbors. This neighborhood relation implies that the set of pumps placed at solution location indicated by the MWDS will automatically satisfy the requirements of the existing nodes, that is, C, D, and E, and expected nodes such as C’, D’, and E’.

[00053] The advantage of the proposed system is that the pump placement problem as
discussed above can be solved in lesser time than conventional solutions. Also, the proposed system provides cost-effective solution to the pump placement problem.
[00054] Although implementations for determining an optimal location for a placement
of a pump in a water distribution network have been described in language specific to structural features and/or methods, it is to be understood that the appended claims are not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as exemplary implementations for determining an optimal location for the placement of the one or more pumps, including their capacities, in the water distribution network.

I/We Claim:
1. A computer-implemented method for determining locations for placement of pumps in
a water distribution network, the method comprising:
receiving, through a user interface, a first set of information and a second set of information related to a water distribution network, the water distribution network comprising links that include at least one of one or more of pipes, one or more junctions, one or more pumps, one or more valves, and one or more reservoirs, wherein the first set of information comprises information about at least one link, and the second set of information comprises information about at least one of a flow rate and a pressure value at a junction in the water distribution network;
generating an initial graph, wherein the initial graph comprises a plurality of nodes and a plurality of edges, and wherein each edge represents a pipe and each node represents a junction;
assigning a weight to the plurality of nodes of the initial graph, wherein the weight assigned to a node amongst the plurality of nodes is indicative of a cumulative cost of placement and operation of a pump at a location for satisfying a pressure requirement of one or more nodes, including the node, downstream of the location; and
generating a weighted transformed graph based on the initial graph by applying a graph-theoretic approach.
2. The method as claimed in claim 1, further comprising generating a hydraulic model based on the first set and the second set of information, which when executed generates the initial graph.
3. The method as claimed in claim 1, wherein the first set of information comprises information of a geographical terrain on which the water distribution network is deployed.
4. The method as claimed in claim 1, wherein the second set of information further comprises at least one of a pressure value at one or more nodes, capacities of a plurality of types of pumps available, and related costs of the plurality of the types of pumps available.

5. The method as claimed in claim 1, wherein the generating the initial graph is partly based on at least one of a location constraint and a cost function.
6. The method as claimed in claim 1, wherein the location constraint comprises at least one of a pump placement constraint.
7. The method as claimed in claim 1, further including converting the weighted transformed graph into an instance of a minimum weighted dominating set, wherein the minimum weighted dominating set comprises one or more nodes that are indicative of the locations for the placement of pumps.
8. The method as claimed in claim 1, wherein the generating the transformed graph comprises:
adding new and existing nodes in the water distribution network to provide a first set of nodes indicative of all possible pump placement locations in the water distribution network;
adding pressure deficient nodes, including existing and new nodes, in the water distribution network to form a second set of nodes;
adding directed edges from a node in the first set to the nodes in the second set whose pressure requirement can be satisfied by placing a pump upstream of the node; and
adding internal edges among the nodes in the first set, the edges indicative of redundancy existing in pump placement locations, wherein resultant directed edges and resultant internal edges are added to provide the transformed graph.
9. A pump location identifier system (100) for determining locations for placement of
pumps in a water distribution network that has links that comprises pipes and junctions, the
pump location identifier system (100) comprising:
a processor (110);
memory (115) coupled to the processor (110), wherein the memory (115) comprises:

a hydraulic modeling module (130) to generate a hydraulic model based on information comprising at least one of topological information pertaining to one or more links in the water distribution network and at least one of a flow rate and a water pressure at the one or more links;
an execution module (133) to execute the hydraulic model to provide an initial graph, wherein a weight is assigned to each node of the initial graph;
a graph theoretic module (135) to generate a weighted transformed graph based on the initial graph.
10. The pump location identifier system (100) as claimed in claim 7, wherein the graph-theoretic module further converts the weighted transformed graph into an instance of a minimum weighted dominating set, which is indicative of one or more locations for the placement of pumps.
11. The pump location identifier system (100) as claimed in claim 7, wherein the weight is indicative of a cumulative cost of placement and operation of the pump to boost pressure at the node.
12. The pump location identifier system (100) as claimed in claim 7, wherein the execution module (133) generates the initial graph from the hydraulic model based at least one of an information about capacities of a plurality of types of pumps available in the market, a location constraint, and a cost function.
13. A computer readable medium having a set of computer readable instructions, which when executed, perform acts including:
receiving, through a user interface, a first set of information and a second set of information related to a water distribution network, the water distribution network comprising pipes, junctions, valves, reservoirs, and pumps, the first set of information comprising information about at least one or more of a location of one or more pipes, a location of one or more pumps, a location of one or more valves, and a location of one or more tanks in the water distribution network, and the second set of information

comprising information about at least one of a flow rate and a pressure value at a junction in the water distribution network;
generating a hydraulic model of the water distribution network based on the first set and the second set of information;
generating an initial graph based on an execution of the hydraulic model, wherein the initial graph comprises a plurality of nodes and a plurality of edges, wherein each edge represents a pipe and each node represents a junction;
assigning a weight to the plurality of nodes of the initial graph, wherein the weight assigned to a node amongst the plurality of nodes is indicative of a cost of placement and operation of a pump at a location for managing pressure requirement of one or more nodes downstream including the node;
generating a transformed graph based on the initial graph by applying a graph-theoretic approach; and
determining a minimum weighted dominating set for the weighted transformed graph, wherein the minimum weighted dominating set comprises one or more nodes that are indicative of locations for placement of pumps.