United States
Environmental Protection
Agency
Water Engineering
Research Laboratory
Cincinnati OH 45268
Research and Development
EPA/600/S5-87/002 Jan. 1988
Project Summary
Planning Models for Urban Water
Supply Expansion
David H.Marks, Fadi Karaa, Ellie Guggenheim, and Roger Kilgore
A three-volume report was developed
relative to the modelling of investment
strategies for regional water supply
planning. Volume 1 is the study of
capacity expansion over time. Models
to aid decision making for the deter-
ministic case are presented, and a
planning process under uncertainty in
future demands is suggested. Two
methods for solving the capacity ex-
pansion problem are analyzed: a heuris-
tic method and a mixed-integer pro-
gramming method.
Volumes 2 and 3 are successive parts
of this research related to the study of
cost allocation policies among partici-
pants in a regional system. Such policies
are evaluated and two methods, the
Proportional Use of Facilities and the
Shapley Value, are distinguished from
the other techniques for practicality and
theoretical soundness considerations,
respectively. The Shapley Value method
is then extended for the case allocation
over time.
This Project Summary was devel-
oped by EPA's Water Engineering
Research Laboratory, Cincinnati, OH,
to announce key findings of the
research project that is fully docu-
mented in three separate volumes (see
Project Report ordering information at
back).
this research focused on two major
problems. The first problem is related to
deriving the combination of sources and
network interconnections that would
meet future demands at minimum cost.
Also, the issue of uncertainties in future
demands are addressed within the plan-
ning framework. In this first research
effort, the major objectives were the
modelling of the capacity expansion of
regional systems over time and the
evaluation of solution methods for the
derivation of expansion strategies. In
Volume 1, two solution methods are
described: one, a simple but locally
optimizing method; the other, a globally
optimizing, more computationally difficult
method.
The second problem was analyzing cost
allocation schemes that can generate the
willingness of different participants to
join in the regional system. Various cost
allocation methods were examined and
evaluated in the context of a case study
involving the Tampa Bay region in Florida.
The Proportional Use of Facilities method
was found to be most practical, although
lacking some theoretical soundness. A
more complete but complex approach
using the Shapley Value was therefore
suggested. The cost allocation problem is
first analyzed in Volume 2, and its latest
results are found in Volume 3.
Introduction
Escalating costs of new supplies have
pushed many local water supply systems
into some form of regional organization.
Through economies of scale on upgraded
water sources, treatment, and distribu-
tion, such organization helps to ease
burdens on participants. In this context.
Capacity Expansion
The capacity expansion research con-
cerned developing an approach that could
deal most efficiently with sizing and
scheduling the expansion of a defined
regional water supply configuration.
Scheduling problems are stated as mini-
mizing the present value of capital and
-------
operational costs as related to water
supply and conveyance facilities, under
constraints such as reliably meeting
demands and budget limitations. Given
that the cost functions associated with
the development of water supply facilities
exhibit economies of scale, simple linear
optimization techniques could not be
used. Among the possible methods to
solve the dynamic expansion problem,
two different approximate approaches
were believed to be most promising: a
heuristic method and a mixed integer
programming method. Both methods were
based on deterministic projected levels of
demands over a given time.
Details of the final results of the
capacity expansion problem under deter-
ministic levels of demands are given in
Volume 1. The two different approaches
are described in the following.
The Heuristic Algorithm
The heuristic approach is iterative, and
involves the decomposition of the problem
so it can be solved in two successive
steps, which significantly reduces com-
putational requirements. In addition to
solving the problem in a logically sound
manner, the heuristic method allows
gains in economies of scale to be tracked
accurately.
The heuristic algorithm belongs to a
"satisfying" category of methods designed
to obtain a local (satisfactory) solution,
which may not be the global (exact)
optimal solution. The algorithm employs
the decomposition technique so that
linear programming (LP) and dynamic
programming can be used, while keeping
the original cost functions unchanged
The heuristic algorithm is based on the
following two steps:
1. The definition of a set of linear co-
efficients to approximate the dif-
ferent cost functions according to
the time period This permits solving
a simple LP flow program, which
derives a feasible set of flows in the
area of the network for the sequence
of time periods. The flows in the
different time periods are "priced"
or "weighted" accordingly using the
results of the previous iteration.
Except for the first iteration, the
algorithm develops an improved
solution by introducing the linear
coefficients based on the updated
last best solution. Further details on
the expressions of such linear co-
efficients can be found in Volume 3.
2. The second step utilizes a dynamic
programming procedure to process
each arc alternative developed in
the solution obtained in the first
step. This process derives the optimal
scheduling of capacities that can
meet the flow levels of the first
iteration. The net present value of
the original cost function is used,
and a cost matrix allows one to
compare the different strategies and
retain the dominant one.
Given this decomposition into two
steps, the dimensionality of the original
problem is not a blocking factor to the
capacity algorithm. In a large case study
with 67 arcs and 40 nodes with two time
periods, it was found that the higher the
real discount rate, the less significant
was the "economies of scale" effect on
the final solution. In other, smaller case
studies, an improved solution after the
very first iteration was shortly followed
by a certain settlement around a preferred
expansion strategy. Hence, the number
of iterations needed was relatively small,
and, consequently, the required computer
time was also small. However, the use of
the heuristic algorithm is only efficient
when all facilities considered are of the
"expandable" or "replicable" type. The
model and its testing on the Tampa Bay
case study are completely described in
Volume 1.
The Mixed Integer Programming
Approach
The mixed integer programming ap-
proach involves the minimization of the
cost-related objective function in such a
manner that it is possible to obtain the
exact least cost (global) solution if enough
computational iterations are performed.
The mixed-integer procedure used in this
study requires that the objective function
be approximated by piecewise linear
segments. The simplest approximation of
a nonlinear function is a linear line with
a fixed charge associated with it, and this
method is used in the study.
Mixed integer programs often require a
large number of computational iterations
to obtain the exact best solution. If the
given problem to be solved is large, this
may result in expending a large amount
of computer time. However, the mixed
integer approach has the potential for
obtaining near-optimal solutions efficient-
ly. In this study, the most favorable
approach to optimizing the capacity ex-
pansion problem was by synthesizing the
heuristic and mixed integer procedures
(see Volume 2).
Approaches To Uncertainty
The deterministic capacity expansion
models serve as the central analytical
tools for obtaining initial strategies in the
planning of regional water systems. The
initial solution of the expansion strategy
using projected levels of demand over
time must be subjected to a re-evaluation
program. The purpose of this is to modify
the original strategy, if needed, to meet
the reliability standards under the level of
uncertainty about the parameters of the
probability distributions of demands. The
modified strategy is then implemented in
its first period. At the end of that period, a
new planning cycle is performed using
the new information. A new expansion
strategy might be derived that possibly
leads to a deviation from the budgeted
capital costs for the next period. Under
this scenario, a goal programming ap-
proach is suggested to minimize the
deviation from the predetermined budgets.
In this latter mode, deviation from budgets
are "discounted" on a time priority basis.
Cost Allocation of Multiperiod
Regional Water Supply Systems
A cost allocation policy is concerned
with how costs are divided and among
whom. The structure of the regional sys-
tem and the financial viability of the
expansion plan depend on the way cost
allocation is carried out. Ten cost alloca-
tion methods, in three categories (see
below), were examined and are described
in Volume 2. Two case studies were
performed: one hypothetical and the other
related to the Tampa Bay area in Florida.
Proportional Methods
1. Proportional to Demand
2. Proportional to the Use of Facilities
Core Methods
3. Least Core
4. Nucleolus
5. Proportional Least Core
6. Weak Least Core
Miscellaneous
7. Shapley Value
8. Separable Costs Remaining Benefits
(SCRB)
9. Alternative Justifiable Expenditure
(AJE)
10. Minimum Cost Remaining Savings
(MCRS)
The criteria used to evaluate the cost
allocation methods were simplicity,
theoretical soundness, economic attrac-
tiveness, and practicality. As an example.
Table 1 presents the factors associated
with the simplicity criteria.
-------
Cost Allocation Policy
Proportional to Demand
Proportional to Use of
Facilities
Least Core
Nucleolus
Proportional Least Core
Weak Least Core
Shapely Value
Data
Requirements
- Total Project Costs
- Demands
- Component Costs
- Demands
- Flow Routing
- Total Project Costs
- All Alternative
Costs
- Total Project Costs
- All Alternative
Costs
- Total Project Costs
- All Alternative
Costs
- Total Project Costs
- All Alternative
Costs
- Total Project Costs
- All Alternative
Costs
Computational
Requirements
Simple Arithmetic
Simple Arithmetic
Linear Programming
Multiple Linear
Programs
Linear Programming
Linear Programming
Extensive Arithmetic
Intuitiveness
Intuitive
Intuitive
Somewhat Intuitive
Somewhat Intuitive
Somewhat Intuitive
Somewhat Intuitive
Very Difficult to
explain to lay
audiences
Evaluation of the Cost
Allocation Methods
Proportional Methods
Allocating costs proportional to demand
lacked theoretical rigor. It also performed
poorly with regard to economic attrac-
tiveness. If this allocation method was
considered, many competing coalitions
would see economic disincentives uni-
formly absent from the other nine policies.
This is not to say that proportional
methods are categorically undersirable.
The Use of Facilities method may be the
best of the ten conventional methods. It
is simple to use and understand and
presents only minor difficulty at deter-
mining flow paths. Theoretically, it was
much better at recognizing contributions
to economies of scale and expanding
spatial extent by tying allocations to the
cost of each facility. However, such a
close association forces the method to
ignore alternatives given up by a particular
city in joining the grand coalition. Con-
sequently, adjustments by the regional
authority may be required.
The Core Methods
The Core Methods — Least Core,
Nucleolus, Proportional Least Core, and
Weak Least Core — have the potential for
being very useful. By explicitly considering
alternative costs of each competing coali-
tion, the methods are theoretically sound
and also allocate costs in an economically
attractive manner. The proportional Least
Core approach is slightly superior because
it considers alternative costs when select-
ing an allocation from the set of feasible
solutions; the others do not.
Unfortunately, the two case studies
suggest two critical difficulties. The first
is the derivation of alternative costs. The
other is related to the fact that expressing
alternative costs is foreign to water supply
accounting and planning practices. The
problems of intertemporal cost allocation
seem to be intractable if Core Methods
are employed.
Use of Facilities Versus
Core Methods
The Use of Facilities and Core Methods
are both attractive schemes because they
are practical. The Tampa Bay area regional
authority, however, has adopted a Use of
Facilities approach partly because that
approach does not present the compu-
tational sophistication of the Core
Methods and the data required are
consistent with common planning prac-
tice. The solid performance of this
approach with respect to the different
criteria and its acceptability by practition-
ers make it more promising for wide-
spread application than the Core
Methods.
SCRB, AJE, and MCRS
SCRB is a hybrid procedure based on
alternative costs and on a proportional
allocation of remaining benefits. AJE is a
hybrid that also includes the Use of
Facilities Method to the extent that
specific costs are considered. Since SCRB
and AJE combine a relatively poor alloca-
tion mechanism (Proportional to Demand)
with relatively good ones (Use of Facilities
and the Core Methods), one would be
better off using the superior ones.
MCRS shares the drawbacks of the
Core Methods — a reliance on elusive
alternative costs and an inability to ap-
proach the intertemporal problem. It also
lacks their theoretical rigor. No particular
advantages of the method were revealed
in either of the case studies.
The Shapley Value
The Shapley Value is a cost allocation
formula that can be intuitively understood
as a "marginal cost average." The entire
system is formed as participants join it
successively. For any particular order of
formation, each participant should pay its
corresponding marginal cost, i.e., the cost
added to the system when it joins. As
different orders of joining the system
lead to different marginal costs, the
Shapley Value adjusts this problem by
taking the average of these marginal costs
over all possible orders of formation of
the system.
The Shapley Value depends heavily on
the evaluation of alternative costs and is
consequently very complex, although not
requiring mathematical programming
techniques. It is an "efficient" allocation
rule in the sense that it allocates exactly
the total cost of the regional system.
The complexity of the method was
reduced by two simplifications. First, it
was shown that costs could be ignored
for those facilities that benefit one mem-
ber and would be built no matter which
regional configuration is adopted. Second,
methodologies were established to
identify in advance the redundant coali-
tions with similar savings.
The Shapley Value method was applic-
able, in a straightforward manner, to the
problem of cost allocation over time,
which is relevant in optimal capacity ex-
pansion problems. Fairness requires that
"new consumers" be separated from
earlier ones. The Shapley Value addresses
this issue directly, which is one of its
advantages. In the Tampa, Florida, case
study, the validity of the various assump-
tions and proposed simplications were
tested. The system contained four main
-------
demand centers, which were in a state of
balanced equilibrium as far as their water
needs were concerned. An existing con-
figuration of sources and pipelines met
all the present water demands of the
communities. The Planning Authority was
interested in the evolution of this regional
system over the next 20 years, given
some projections of future demands. By
eliminating operations and maintenance
costs,whichwas theoretically justified for
this case, only capital investments were
considered. The results were very en-
couraging and supportive of the assump-
tions and approximations made and of
the Shapley Value Method in general. It
was also shown that by applying a
"naive" rule, based on the idea of
-begmmng the repayment of the corre-
sponding capital investment at every
priod, the obtained results seriously and
consistently differed from the correct al-
location. Unacceptable distortions oc-
curred not only in terms of cost shares
but even in terms of annual rates, thus
strongly suggesting that a Shapley Value
cost allocation method be used instead of
a "naive" rule, both over time and space.
Using the Shapley Value, a method
recognized as theoretically very sound, in
a simplified form is particularly appealing.
Its use as a decision-making tool provided
many new insights into the problem of
cost allocation and explored the potential
for successfully applying the Shapley
Value method in future practical problems.
Conclusions
Capacity Expansion Methods
Both the heuristic and mixed integer
capacity expansion solution methods ex-
hibit advantages and drawbacks. Although
the heuristic approach is simpler and can
be used on mini- or microcomputers, it is
a locally optimizing method and can deal
only with expandable facilities. On the
other hand, the mixed integer method
has the capability to obtain the exact best
solution, but may require large computer
resources. Ideally, the use of both
methods in an iterative manner can lead
to more efficient expansion schemes.
Cosf Allocation Methods
The cost allocation policies were evalu-
ated and tested on a case study using the
Tampa Bay area. The results of this effort
show that the Proportional Use of Facilities
method for cost allocation is the most
promising policy due to its satisfactory
evaluation according to several criteria.
The Shapley Value method, theoretically
the best allocation scheme over time,
was the focus of a significant part of this
research. Important modifications were
suggested to decrease its complexity
while keeping its superior theoretical
attractiveness.
The full report was submitted in ful-
fillment of Cooperative Agreement No.
CR806802 by the Massachusetts Institute
of Technology, under the sponsorship of
the U.S. Environmental Protection
Agency.
D. Marks, F. Karaa, E. Guggenheim, and R. Kilgore are with the Massachusetts
Institute of Technology. Cambridge. MA 01239..
Robert M. Clark is the EPA Project Officer (see below).
The complete report consists of three volumes, entitled "Planning Models for
Urban Water Supply Expansion:" {Set Order No. PB 88-109 590/AS; Cost:
$53.50)
"Volume 1. Planning for the Expansion of Regional Water Supply Systems."
(Order No. PB 88-109 608/AS; Cost: $18.95)
"Volume 2. Cost Allocation Policies for Regional Water Supply Systems,"
(Order No. PB 88-109 616/AS; Cost: $18.95)
"Volume 3. The Regional Intertemporal Cost Allocation Problem: A Simplified
Methodology Based on the Shapely Value." (Order No. PB 88-109 624/AS;
Cost: $24.95)
The above reports will be available only from: (costs subject to change)
National Technical Information Service
5285 Port Royal Road
Springfield. VA 22161
Telephone: 703-487-4650
The EPA Project Officer can be contacted at:
Water Engineering Research Laboratory
U.S. Environmental Protection Agency
Cincinnati. OH 45268
United States
Center for Environmental Research
U.S.OPPHBPMLfMA
environmental rroiecnon
Agency
imormanon
Cincinnati OH 45268
AV"' '.-^ \ rUSI/>
{ ° FEE -4'88 pi&Af¥F
"• ^ 1 JSE 5300
u«Jlrafl
MIT No G-35
~Q .2 2:
Official Business
Penalty for Private Use $300
EPA/600/S5-87/002
0000329 PS
U S ENVIR PROTECTION AGENCY
------- |