辅导heterogeneous、讲解infrastructure systems、辅导Java/c++编程语言 解析Haskell程序|讲解Pyth
- 首页 >> 其他 This article was downloaded by:
Structure and Infrastructure Engineering:
Algorithms for bottom-up maintenance optimisation
for heterogeneous infrastructure systems
Hwasoo Yeo a , Yoonjin Yoon a & Samer Madanat b a
Department of Civil and Environmental Engineering , KAIST (Korea Advanced Institute of Science and Technology) , 335 Gwahangno, Yuseong-gu , Daejeon , Republic of Korea b
Institute of Transportation Studies and Department of Civil and Environmental
Engineering, University of California , Berkeley , CA , 94720 , USA
Published online: 21 Feb 2012.
To cite this article: Hwasoo Yeo , Yoonjin Yoon & Samer Madanat (2013) Algorithms for bottom-up maintenance optimisation
for heterogeneous infrastructure systems, Structure and Infrastructure Engineering: Maintenance, Management, Life-Cycle
Design and Performance, 9:4, 317-328, DOI: 10.1080/15732479.2012.657649
To link to this article: http://dx.doi.org/10.1080/15732479.2012.657649
PLEASE SCROLL DOWN FOR ARTICLE
Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained
in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no
representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the
Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and
are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and
should be independently verified with primary sources of information. Taylor and Francis shall not be liable for
any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever
or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of
the Content.
This article may be used for research, teaching, and private study purposes. Any substantial or systematic
reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any
form to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http://
www.tandfonline.com/page/terms-and-conditionsAlgorithms for bottom-up maintenance optimisation for heterogeneous infrastructure systems
Hwasoo Yeoa
*, Yoonjin Yoona and Samer Madanatb
a
Department of Civil and Environmental Engineering, KAIST (Korea Advanced Institute of Science and Technology),
335 Gwahangno, Yuseong-gu, Daejeon, Republic of Korea; b
Institute of Transportation Studies and Department of Civil and
Environmental Engineering, University of California, Berkeley, CA 94720, USA
(Received 17 January 2011; final version received 7 November 2011; accepted 3 January 2012; published online 21 February 2012)
This paper presents a methodology for maintenance optimisation for heterogeneous infrastructure systems, i.e.,
systems composed of multiple facilities with different characteristics such as environments, materials, and
deterioration processes. We present a bottom-up approach: facility-level optimal maintenance policies are first
found; these policies are then combined with budget constraints in the system-level optimisation. In the first step,
optimal and near-optimal maintenance policies for each facility are found and used as inputs for the system-level
optimisation. In the second step, the problem is formulated as a constrained combinatorial optimisation problem,
where the best combination of facility-level optimal and near-optimal solutions is identified. Two heuristics, pattern
search heuristic (PSH) and evolutionary algorithm (EA), are adopted to solve the combinatorial optimisation
problem. Their performance is evaluated using a hypothetical system of pavement sections. Comparison result with
real optimal solutions for 20 facilities showed that both algorithms give near-optimal solutions (within less than
0.1% difference from the optimal solution) in 978 (PSH) and 966 (EA) cases out of 1000 executions. The EA
performs better in terms of processing time than the PSH. Numerical experiments show the potential of the proposed
algorithms to solve the maintenance optimisation problem for realistic heterogeneous systems.
Keywords: infrastructure maintenance; heterogeneous systems; optimisation; pavement management systems
1. Introduction
Infrastructure management is a periodic process of
inspection, maintenance policy selection, and maintenance
activities application. Guillaumot et al. (2003)
also refer infrastructure management as ‘the process
through which agencies collect and analyze data about
infrastructure systems and make decisions on the
maintenance, repair, and reconstruction (MR&R) of
facilities over a planning horizon.’ Maintenance,
rehabilitation, and reconstruction (MR&R) policy
selection is an optimisation problem where the
objective is to minimise the expected total life-cycle
cost of keeping the facilities in the system above a
minimum service level while satisfying agency budget
constraints.
There are two approaches for MR&R optimisation:
top-down (aggregate approach) and bottom-up. For
example, in a pavement management system, the topdown
approach provides a simultaneous analysis of
an entire roadway system. The first step is to aggregate
pavements having similar structure, traffic loading, and
environment into mutually exclusive and collectively
exhaustive homogeneous groups. Individual road segments
are not represented in the optimisation; instead,
the units of analysis are the fractions of the groups in
specific condition states. As a result, much of the
segment-specific information (history of construction,
rehabilitation, and maintenance; materials; structure) is
lost. The objective of the optimisation model is to find
the MR&R polices that maximise benefits or minimise
costs subject to meeting budgetary and policy constraints.
These optimal system policies then guide the
selection of the actual facilities for MR&R.
The main advantage of the top-down approach is
that it allows the user to properly address the trade-off
between rehabilitation of a small number of facilities
and maintenance of a larger number of facilities, given
a budget constraint. One of the main disadvantages of
the top-down approach is that it does not specify
optimal activities for each individual facility: the
mapping of optimal system-level policies to facilitylevel
activities is left to district engineers. On the other
hand, this gives engineers latitude in using their
judgment, which is needed to compensate for the loss
of facility-specific information in the aggregation step.
One of the early examples of a top-down formulation
is the Arizona Department of Transportation (ADOT)
Pavement Management System (PMS). By selecting
maintenance and rehabilitation strategies that minimise
life-cycle cost, the ADOT PMS saved $200
*Corresponding author. Email: hwasoo@kaist.ac.kr
Structure and Infrastructure Engineering
Vol. 9, No. 4, April 2013, 317–328
ISSN 1573-2479 print/ISSN 1744-8980 online
2013 Taylor & Francis
http://dx.doi.org/10.1080/15732479.2012.657649
http://www.tandfonline.com
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 million over 5 years (OECD 1987). However, as a topdown
approach in which all facilities are assumed to
have same characteristics, the ADOT PMS cannot be
used for a heterogeneous system.
In the case of a heterogeneous system that is
composed of the facilities with different characteristics
such as facility type, material, deterioration
process, and environmental factors, it is necessary to
determine the facility-level activity. There are many
examples of such system: (1) a pavement system in
real road network with different pavement types of
concrete, Portland cement concrete (PCC) and
Asphalt cement concrete (ACC), each of which has
its own deterioration process; (2) a highway system
with different types of facilities: pavements, bridges,
toll facilities, etc. To solve the heterogeneous system
maintenance optimisation problem, a bottom-up
approach can be adopted to determine the maintenance
policy for each facility.
The bottom-up approach can be formulated in
several ways. A possible formulation consists of the
following steps: first, select a small set of optimal (or
near optimal) sequences of MR&R activities for each
facility, covering the desired planning horizon. Then,
for a fixed budget, select the combination of
sequences (one for each facility) that meets the
budget constraint while optimising a system-wide
objective (Robelin and Madanat 2006). The main
advantage of the bottom-up approach is that it
preserves the identity of individual facilities, with all
its information (structure, materials, history of
construction, MR&R, traffic loading, and environment).
One disadvantage of the bottom-up approach
is the combinatorial complexity of the second step.
The research presented herein is an attempt to
overcome this disadvantage. This paper addresses
the problem of MR&R planning for an infrastructure
system composed of dissimilar facilities undergoing
stochastic state transitions over a finite
planning horizon. A new two-stage bottom-up
approach is proposed, developed, and evaluated
with two different implementations: (1) pattern
search (PS) and (2) evolutionary algorithm (EA).
This paper is organised as follows. In Section 2,
state-of-the-art methods for MR&R planning are
reviewed. In Section 3, a new two-stage approach for
solving the heterogeneous system maintenance problem
is presented. In Section 4, a parametric study is
presented to illustrate and evaluate the new approach.
Finally, Section 5 presents the conclusions.
2. Literature review
Infrastructure maintenance optimisation problems
can be classified into single facility problems and
multi-facility problems (also known as system-level
problems).
For the single facility problem, the optimal policy is
the set of MR&R activities needed for each state of the
facility that achieves the minimum expected life-cycle
cost. Optimal control (Friesz and Fernandez 1979,
Tsunokawa and Schofer 1994), dynamic programming
(Carnahan 1988, Madanat and Ben-Akiva 1994),
nonlinear minimisation (Li and Madanat 2002), and
calculus of variations (Ouyang and Madanat 2006)
have been used as solution methods.
For the system-level problem, the objective is to
find the optimal set of MR&R policies for all facilities
in the system, which minimises the expected sum of
life-cycle cost within the budget constraint for each
year. The optimal solution at the system-level will not
coincide with the set of optimal policies for each
facility if the budget constraint is binding. Homogeneous
system problems have been solved by using
linear programming (Golabi et al. 1982, Harper and
Majidzadeh 1991, Smilowitz and Madanat 2000). The
decision variables for linear programming are the
proportions of facilities that need a specific MR&R
activity at a certain state. This top-down approach has
advantages, but as discussed earlier, it cannot be
directly applied to MR&R optimisation for heterogeneous
systems.
Fwa et al. (1996) used genetic algorithms, to address
the trade-off between rehabilitation and maintenance.
The authors assumed four categories of agency cost
structure, based on the relative costs among rehabilitation
and three maintenance activities for 30 homogeneous
facilities. Durango-Cohen and Sarutipand
(2007) proposed a quadratic programming (QP) platform
for multi-facility MR&R problem. While the QP
formulation successfully captures the effect of MR&R
interdependency between facility pairs, the applicability
of QP is limited to situations when the costs are
quadratic. The numerical example in the paper is
limited to the facilities with the same deterministic
deterioration process, where each facility is a member of
either a ‘substitutable’ or a ‘complementary’ network.
Although intuitively sensible, the determination of
‘substitutable’ or ‘complementary’ networks might not
be evident in large-scale networks. Ouyang (2007)
developed a new approach for system-level pavement
management problem using multi-dimensional dynamic
programming. He expanded the dynamic programming
formulation used in the facility-level optimisation to
multiple facilities. To overcome the computational
difficulty associated with the multi-dimensional problem,
he adopted an approximation method and
applied this to a deterministic, infinite horizon problem.
Recently, researchers have developed novel solutions
for heterogeneous infrastructure systems.
318 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 Robelin and Madanat (2006) used a bottom-up
approach for MR&R optimisation of a heterogeneous
bridge system. At the facility-level, all possible
combinations of decision variables are enumerated;
at the system-level, the best combination of the
enumerated solutions is determined by searching the
solution space. This system-level problem has a
combinatorial computational complexity. The authors
find a set of lower and upper cost bounds for the
optimal solution, which narrows the search space. In a
related work, Robelin and Madanat (2008) formulated
and solved a risk-based MR&R optimisation problem
for Markovian systems. At the facility-level, the
optimisation consists of minimising the cost of maintenance
and replacement, subject to a reliability
constraint. At the system-level, the dual of the
corresponding problem is solved: risk minimisation
(i.e., reliability maximisation) subject to a budget
constraint; specifically, the objective is to minimise
the maximum risk across all facilities in the system,
subject to the sum of MR&R costs not exceeding the
budget constraint. The solution to the system-level
problem turns out to have a simple structure, with a
linear computational time.
The approach used in Robelin and Madanat (2008)
is limited to risk-based MR&R optimisation, where the
objective function has a Min-Max format, and is not
applicable for serviceability-based optimisation problems.
For serviceability-based problems, the objective
function takes on an expected cost minimisation (or
expected serviceability maximisation), which does not
lend itself to solutions with such a simple structure.
This motivates the approach proposed in this paper.
3. Methodology
Consider an infrastructure system composed of N
independent facilities, with different attributes such as
design characteristics, materials, and traffic loads: this
system is a heterogeneous system. We assume that
MR&R activities and their associated costs can be
defined for all facilities. Then, the objective is to find
the optimal combination of facilities’ MR&R activities
(decision variables), minimising the total system-level
cost (objective functions).
Assuming that inspection is done at the beginning
of the current year, the state of each facility is known,
and the decision process will be performed every year.
In our two-stage bottom-up approach, we first solve
the facility-level optimisation to find a set of best
and alternative MR&R activities and costs for each
facility. In the second stage, we solve the system-level
optimisation to find the best combination of MR&R
activities across facilities by choosing among the
optimal and sub-optimal alternative activities found
in the first step. Figure 1 illustrates the system-level
optimisation for N facilities. For each facility, the
optimal activity and the first and second alternative
activities are obtained from the facility-level optimisation.
The initial solution in the system-level is the set of
optimal activities [a11, a21,..., aN1]. Our objective is to
find an optimal combination of MR&R activities,
Figure 1. System-level solution procedure using the proposed bottom-up approach.
Structure and Infrastructure Engineering 319
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 while minimising the total life-cycle cost within the
budget constraint for the current year. Due to the
presence of a budget constraint, the optimal activities
found in the facility-level optimisation are not necessarily
included in the system-level solution. Instead, the
next alternative activity may replace the optimal
activity for certain facilities if needed, as illustrated in
the case of facility 2 in Figure 1.
In this paper, we focus on a heterogeneous
pavement system as a case study since it is one of the
most widely researched systems, and has a common
problem structure for infrastructure management, i.e.,
probabilistic state transition, time discounting, and
multiple MR&R activities. In a PMS, the state of
pavement can be represented by discrete numbers
such as the pavement serviceability rating (PSR),
ranging from 1 (worst condition) to 5 (best condition).
If pavement deterioration can be represented as a
Markovian process, the serviceability (PSR) changes
over time depend only on the current state and the
maintenance activity applied at the beginning of the
time period after inspection. The transition probability
matrix, Pa(i, j) specifies the probabilities of a state
change from state i to state j after applying maintenance
activity a. An MR&R program X ? [x1,...,
xN] is a set of activities that will be applied to the N
facilities in the system in the current year. We assume a
finite planning horizon of length T. The vector X must
be feasible, i.e., it must satisfy the budget constraint for
the current year.
3.1. Facility-level optimisation
The facility-level optimisation solves for the optimal
activity and its cost pair, action cost (C) and expectedcost-to-go
(V), without accounting for the budget
constraint. It also identifies the suboptimal alternative
policies and their cost pairs. The facility-level optimisation
for a PMS can be formulated as a dynamic
program to obtain an optimal policy and the
alternative policies. The dynamic programming formulation
that solves for optimal activity a* and its
expected cost-to-go V* is
where
A is the set of feasible maintenance activities, A ? {a1,
a2,...}
S is the set of feasible states of facility
Pa(i, j) is the transition probability from state i to state
j under maintenance activity a
C(a, i) is the agency cost for activity a, performed on
facility in state i
a is the discount amount factor, a ? 1/(1 t r); where r
is the discount rate
Va(i, t) is the expected cost-to-go from time t to T for
current state i and activity a applied
User cost can be added to agency cost (C(a,i))
considering the duration of the time and period of cost
generation. MR&R activity associated user costs by
roadwork and user costs from new pavement state
after MR&R action can be added with appropriate
conversion to dollar value. Assuming salvage value of
a facility for each state at time T, we applied dynamic
programming backward iteration to solve Equations
(1) and (2) from time T7 1 to 1, to obtain the
minimum expected total cost-to-go V*(i,1) from the
current time year (t ? 1) to the end of the planning
horizon T. As illustrated in Figure 2, when the facility
state is 8 at time t, three activities are available.
Computing the expected costs-to-go for each activity,
an activity (a3) with minimum expected cost-to-go
(denoted as V1*(8,t)) is chosen as the optimal activity.
The activity a2 with the second smallest expected costto-go
(V2*(8,t) is the first alternative activity; the one
with the third smallest expected cost-to-go (V3*(8,t)) is
the second alternative, etc. a*1(8,t) ? a3, a*2(8,t) ? a2,
and a*3(8,t) a1.
The kth alternative activity a
kt1 and its expected
cost-to-go V
kt1(i,t) can be found by using the
following equations:
Note that when k0, the result of Equation (3), a
1 is
the optimal activity, and V
1, the result of Equation (4),
is the expected cost-to-go for the optimal activity.
Thus, Equations (3) and (4) are used to find both
optimal and alternative activities. Iterating backward
in time, the optimal policy and alternative policies can be
solved for the current year. Although the facility-level
optimisation can also be formulated and solved as
a linear program (for the infinite horizon case), we
adopted dynamic programming, as it also produces
the alternative policies and costs used as inputs for
320 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 the system-level optimisation without additional
calculations.
3.2. System-level optimisation
The facility-level optimisations yield a set of activities and their expected cost-to-go for each facility. Given the agency
cost for each activity, the objective is to find the
combination of activities (one for each facility) that
minimises the system-wide expected cost-to-go while
keeping the total agency cost within the budget.
Assuming that all facilities are independent, and given
a budget constraint, the system-level optimisation can
be formulated as a constrained combinatorial optimisation
problem.
Let Mn {0, 1, 2, . . .} be an alternative activity set
for facility n, where 0 represents the optimal activity
and i represents the ith alternative activity. The systemlevel
optimal activity x1; ... x
N, xn2 Mn will be
determined given the facilities’ current state
[s1,...,sN]. Let f C
n exnT denote the expected cost-to-go
function, and f
B
n exnT the activity cost function for
facility n given activity xnat current time. Note that
xnt1esn; 1T for all n, and fB
n exnT?exn;snT.
Decision variables: X1; ... ; xN
Objective function: min TEC P
n exnT B (B: Budget of the current
year)
where TEC represents the total system expected costto-go
from the current year to year T.
There exist various methods for solving the
constrained combinatorial optimisation problem including
integer programming and heuristic search
algorithms. As the constraints and objective function
might include nonlinear equations, we consider a
nonlinear solution approach. Cases of nonlinear
constraints arise when there exist functional and
economic dependencies between the facilities. For
example, contiguous facilities are best rehabilitated in
the same year to reduce delay costs during the
rehabilitation. Another example is when two facilities
provide alternative routes. In such a case, one of the
two facilities must be available during rehabilitation of
the other facility. The challenge is how to reduce the
computational complexity of the solution algorithm.
Simple method such as the brute force approach that
searches the entire combinatorial solution space finds
the optimal solution. However, with computational
complexity of exponential order, this method cannot
be applied to problems of realistic size.
3.2.1. Two-facility example
Consider a case with two facilities. Figure 3 shows the
solution space and solution path. From the initial
solution X (0,0) which is a combination of optimal
activities without budget constraint, the solution has to
move toward the constrained optimal solution. For the
first facility, the decision variable x1 can take four
values, i.e., four activities are available including the
Figure 2. Dynamic programming process for facility-level optimisation.
Structure and Infrastructure Engineering 321
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 original optimal policy and three alternatives. In this
example, the expected cost-to-go for the optimal policy
is 2, and the alternatives’ costs are 8, 15, and 21. The
second facility, as shown on the vertical axis, has an
optimal expected cost-to-go of 3.5 and alternatives’
costs as 8, 12, and 17. The diagonal lines illustrated are
loci of equal TEC points. We seek the minimum total
cost combination f C
1 ex1T t f C
2 ex2T inside the feasible
region, defined by the budget constraint. As illustrated,
starting from the point (2, 3.5) the solution moves to
the point (2, 8), which gives the smallest total cost
increase from TEC1 (5.5) to TEC2 (10). By repeating
this procedure, we can reach the optimal solution,
which is the first feasible solution visited. However, as
the number of facilities increases, it becomes more
difficult to find the next solution point from the current
solution. In the case of P activities available for all
facilities, there exist PN combinations of movements in
the solution space in the worst case. Therefore, we need
to develop solution methods that can avoid the
exponential order of complexity. We present two
heuristics that reduce the complexity of the solution
algorithms from O(PN) to O(Nb
) where b is a small
integer between 2 and 4.
3.2.2. Pattern search heuristic
PSH simplifies the procedure of movements described
in the previous section. The idea is to repeat simple
movements determined by predefined patterns to find
an advanced point instead of searching all possible
movements. Thus, the PSH is a deterministic search
method. Let dX denote a movement vector. The new
solution is Xnew ? X t dX. Decomposing the movement
vector dX to negative and positive component
vectors (dXt, dX7), movements can be classified into
patterns according to the number of positive and
negative movements. The number of negative and
positive unit direction vectors defines a movement
pattern. Thus, pattern (p, q) refers to the movement
vector composed of p negative unit vectors and q
positive unit vectors. Table 1 shows the possible
movement vector patterns. For example, pattern B
(1,1) has a negative component vector dX7 ? (. . . ,71,
. . .), which means only one component in dX7is 71,
and a positive component vector dXt ? (. . . , 1, . . .)
having only one t1 component. Combining the negative
and positive movement vectors (dX ? dX– t dXt), the
movement vector dX has one 71 component and
one t1 component while all the other components are 0.
Figure 4(a) illustrates the concept of search
procedure for the PSH. For all patterns, a set of
movement vectors is generated to form a set of new
candidate solutions. Based on the evaluation, a
candidate solution is chosen as a new solution. During
the search, all movement combinations for all patterns
in Table 1 are generated. Only patterns of lower degree
p, q 53 are used to restrict the complexity of
computation to less than O(N4
). The solution process
involves three stages: (1) movement toward the feasible
region, (2) solution improvement, and (3) optimality
check. Figure 4(b) shows the three stages for the twofacility
example. In Figure 4(b), the solution starts
from the initial solution of (2, 3.5). Investigating all
possible candidate movements defined by patterns, it
moves to an adjacent point that is closer to the feasible
Figure 3. System-level optimisation for a two-facility example: (a) solution space and (b) solution path.
322 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 region and has the lowest total cost increase. Once it
reaches the feasible region, it moves to new point
improving the current solution within the feasible
region. Finally, it checks optimality to decide whether
it has to stop searching and set the obtained result as a
final solution. If the optimality check fails, it continues
the solution search of stage 2.
Stage 1: Moving toward the feasible region
For each predetermined pattern (p, q), generate a set
of negative and positive movement vectors. Then,
combining them, generate a set of movement vectors.
Given the current solution vector X (x1, x2,..., xN),
find a direction vector dX (dx1, dx2,..., dxN), dX
dXt t dX7, which satisfies Equations (5) and (6).
Table 1. Movement vector patterns.
Movement
vector pattern p q
Movement vector
dX7 complexity dXt complexity
A (0,1) 0 1 (. . . , . . .) – (. . . , t1, . . .) O(N)
(1,0) 1 0 (. . . ,71, . . .) O(N) (. . . , . . .) –
B (1,1) 1 1 (. . . ,71,. . .) O(N) (. . . , t1, . . .) O(N)
C (2,1) 2 1 (. . . ,71, . . . ,71, . . .) O(N2
) (. . . , t1, . . .) O(N)
(. . . ,72, . . .) (. . . , t1, . . .)
D (1,2) 1 2 (. . . ,71, . . .) O(N) (. . . , t1, . . . , t1, . . .) O(N2
)
(. . . ,71, . . .) (. . . , t2, . . .)
E (2,2) 2 2 (. . . ,71, . . . ,71, . . .) O(N2
) (. . . , t1, . . . , t1, . . .) O(N2
)
(. . . ,71, . . . ,71, . . .) (. . . ,72, . . .)
(. . . ,72, . . .)
(. . . , t2, . . .) (. . . , t1, . . . , t1, . . .)
(. . . , t2, . . .)
Figure 4. The pattern search heuristic process: (a) solution search procedure with movement patterns and (b) PSH solution path
for the two-facility example.
Structure and Infrastructure Engineering 323
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 The solution moves to the new solution having the
minimum TEC (Equation (5)) with a lower action cost
(Equation(6)). As long as the new solution has a lower
action cost, the magnitude of the reduction is not
considered. Repeating for all predetermined patterns,
the best solution among all pattern searches is chosen
as the new solution. The stage 1 procedure is repeated
until the solution reaches the feasible region, i.e.,
satisfies the following condition:
n exnT B e Te Budget constraint 7T
Stage 2: Solution improvement
In the second stage, the solution obtained is improved
by searching inside the feasible region. The best
solution satisfying Equations (8) and (9) will be
chosen.
n exnT B e Te Budget constraint 9T
As shown in Table 1, for each stage, the pattern
search algorithm has a complexity of O(N4). If the
pattern E (2,2) is excluded, the algorithm works in
O(N3).
Stage 3: Optimality check
Because the pattern search method does not guarantee
finding the global optimal solution, the search range is
expanded to check the existence of a better solution.
If a better solution is found in stage 3, we return to
stage 2 with the new solution vector.
To search a broader space, two different methods
can be used. Random search can produce a random
jump from one local optimal to the other region.
Random search can be incorporated by generating
random movement vectors from a predefined distribution
such as normal distribution. Adjusting the
distribution parameters can control the search range.
For example, by increasing the standard deviation,
the direction vector has more nonzero components
and the search space is enlarged. The other way to
check for optimality is to increase p and q to 3 or 4.
However, this also increases the complexity of the
algorithm to O(N6) or O(N8). Therefore, we used
the random search method to check for optimality
in the numerical examples presented later in this
paper.
3.2.3. Evolutionary algorithm
EAs are stochastic search methods for nonlinear
optimisation. In EA, a current solution is considered
a parent that brings forth a population of mutant
offspring. The algorithm evaluates the new generation
and selects the best one as a new solution. Repeating
this process, the solution evolves, and a near optimal
solution can be found. As with the PSH algorithm, EA
do not gu
Structure and Infrastructure Engineering:
Algorithms for bottom-up maintenance optimisation
for heterogeneous infrastructure systems
Hwasoo Yeo a , Yoonjin Yoon a & Samer Madanat b a
Department of Civil and Environmental Engineering , KAIST (Korea Advanced Institute of Science and Technology) , 335 Gwahangno, Yuseong-gu , Daejeon , Republic of Korea b
Institute of Transportation Studies and Department of Civil and Environmental
Engineering, University of California , Berkeley , CA , 94720 , USA
Published online: 21 Feb 2012.
To cite this article: Hwasoo Yeo , Yoonjin Yoon & Samer Madanat (2013) Algorithms for bottom-up maintenance optimisation
for heterogeneous infrastructure systems, Structure and Infrastructure Engineering: Maintenance, Management, Life-Cycle
Design and Performance, 9:4, 317-328, DOI: 10.1080/15732479.2012.657649
To link to this article: http://dx.doi.org/10.1080/15732479.2012.657649
PLEASE SCROLL DOWN FOR ARTICLE
Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained
in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no
representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the
Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and
are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and
should be independently verified with primary sources of information. Taylor and Francis shall not be liable for
any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever
or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of
the Content.
This article may be used for research, teaching, and private study purposes. Any substantial or systematic
reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any
form to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http://
www.tandfonline.com/page/terms-and-conditionsAlgorithms for bottom-up maintenance optimisation for heterogeneous infrastructure systems
Hwasoo Yeoa
*, Yoonjin Yoona and Samer Madanatb
a
Department of Civil and Environmental Engineering, KAIST (Korea Advanced Institute of Science and Technology),
335 Gwahangno, Yuseong-gu, Daejeon, Republic of Korea; b
Institute of Transportation Studies and Department of Civil and
Environmental Engineering, University of California, Berkeley, CA 94720, USA
(Received 17 January 2011; final version received 7 November 2011; accepted 3 January 2012; published online 21 February 2012)
This paper presents a methodology for maintenance optimisation for heterogeneous infrastructure systems, i.e.,
systems composed of multiple facilities with different characteristics such as environments, materials, and
deterioration processes. We present a bottom-up approach: facility-level optimal maintenance policies are first
found; these policies are then combined with budget constraints in the system-level optimisation. In the first step,
optimal and near-optimal maintenance policies for each facility are found and used as inputs for the system-level
optimisation. In the second step, the problem is formulated as a constrained combinatorial optimisation problem,
where the best combination of facility-level optimal and near-optimal solutions is identified. Two heuristics, pattern
search heuristic (PSH) and evolutionary algorithm (EA), are adopted to solve the combinatorial optimisation
problem. Their performance is evaluated using a hypothetical system of pavement sections. Comparison result with
real optimal solutions for 20 facilities showed that both algorithms give near-optimal solutions (within less than
0.1% difference from the optimal solution) in 978 (PSH) and 966 (EA) cases out of 1000 executions. The EA
performs better in terms of processing time than the PSH. Numerical experiments show the potential of the proposed
algorithms to solve the maintenance optimisation problem for realistic heterogeneous systems.
Keywords: infrastructure maintenance; heterogeneous systems; optimisation; pavement management systems
1. Introduction
Infrastructure management is a periodic process of
inspection, maintenance policy selection, and maintenance
activities application. Guillaumot et al. (2003)
also refer infrastructure management as ‘the process
through which agencies collect and analyze data about
infrastructure systems and make decisions on the
maintenance, repair, and reconstruction (MR&R) of
facilities over a planning horizon.’ Maintenance,
rehabilitation, and reconstruction (MR&R) policy
selection is an optimisation problem where the
objective is to minimise the expected total life-cycle
cost of keeping the facilities in the system above a
minimum service level while satisfying agency budget
constraints.
There are two approaches for MR&R optimisation:
top-down (aggregate approach) and bottom-up. For
example, in a pavement management system, the topdown
approach provides a simultaneous analysis of
an entire roadway system. The first step is to aggregate
pavements having similar structure, traffic loading, and
environment into mutually exclusive and collectively
exhaustive homogeneous groups. Individual road segments
are not represented in the optimisation; instead,
the units of analysis are the fractions of the groups in
specific condition states. As a result, much of the
segment-specific information (history of construction,
rehabilitation, and maintenance; materials; structure) is
lost. The objective of the optimisation model is to find
the MR&R polices that maximise benefits or minimise
costs subject to meeting budgetary and policy constraints.
These optimal system policies then guide the
selection of the actual facilities for MR&R.
The main advantage of the top-down approach is
that it allows the user to properly address the trade-off
between rehabilitation of a small number of facilities
and maintenance of a larger number of facilities, given
a budget constraint. One of the main disadvantages of
the top-down approach is that it does not specify
optimal activities for each individual facility: the
mapping of optimal system-level policies to facilitylevel
activities is left to district engineers. On the other
hand, this gives engineers latitude in using their
judgment, which is needed to compensate for the loss
of facility-specific information in the aggregation step.
One of the early examples of a top-down formulation
is the Arizona Department of Transportation (ADOT)
Pavement Management System (PMS). By selecting
maintenance and rehabilitation strategies that minimise
life-cycle cost, the ADOT PMS saved $200
*Corresponding author. Email: hwasoo@kaist.ac.kr
Structure and Infrastructure Engineering
Vol. 9, No. 4, April 2013, 317–328
ISSN 1573-2479 print/ISSN 1744-8980 online
2013 Taylor & Francis
http://dx.doi.org/10.1080/15732479.2012.657649
http://www.tandfonline.com
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 million over 5 years (OECD 1987). However, as a topdown
approach in which all facilities are assumed to
have same characteristics, the ADOT PMS cannot be
used for a heterogeneous system.
In the case of a heterogeneous system that is
composed of the facilities with different characteristics
such as facility type, material, deterioration
process, and environmental factors, it is necessary to
determine the facility-level activity. There are many
examples of such system: (1) a pavement system in
real road network with different pavement types of
concrete, Portland cement concrete (PCC) and
Asphalt cement concrete (ACC), each of which has
its own deterioration process; (2) a highway system
with different types of facilities: pavements, bridges,
toll facilities, etc. To solve the heterogeneous system
maintenance optimisation problem, a bottom-up
approach can be adopted to determine the maintenance
policy for each facility.
The bottom-up approach can be formulated in
several ways. A possible formulation consists of the
following steps: first, select a small set of optimal (or
near optimal) sequences of MR&R activities for each
facility, covering the desired planning horizon. Then,
for a fixed budget, select the combination of
sequences (one for each facility) that meets the
budget constraint while optimising a system-wide
objective (Robelin and Madanat 2006). The main
advantage of the bottom-up approach is that it
preserves the identity of individual facilities, with all
its information (structure, materials, history of
construction, MR&R, traffic loading, and environment).
One disadvantage of the bottom-up approach
is the combinatorial complexity of the second step.
The research presented herein is an attempt to
overcome this disadvantage. This paper addresses
the problem of MR&R planning for an infrastructure
system composed of dissimilar facilities undergoing
stochastic state transitions over a finite
planning horizon. A new two-stage bottom-up
approach is proposed, developed, and evaluated
with two different implementations: (1) pattern
search (PS) and (2) evolutionary algorithm (EA).
This paper is organised as follows. In Section 2,
state-of-the-art methods for MR&R planning are
reviewed. In Section 3, a new two-stage approach for
solving the heterogeneous system maintenance problem
is presented. In Section 4, a parametric study is
presented to illustrate and evaluate the new approach.
Finally, Section 5 presents the conclusions.
2. Literature review
Infrastructure maintenance optimisation problems
can be classified into single facility problems and
multi-facility problems (also known as system-level
problems).
For the single facility problem, the optimal policy is
the set of MR&R activities needed for each state of the
facility that achieves the minimum expected life-cycle
cost. Optimal control (Friesz and Fernandez 1979,
Tsunokawa and Schofer 1994), dynamic programming
(Carnahan 1988, Madanat and Ben-Akiva 1994),
nonlinear minimisation (Li and Madanat 2002), and
calculus of variations (Ouyang and Madanat 2006)
have been used as solution methods.
For the system-level problem, the objective is to
find the optimal set of MR&R policies for all facilities
in the system, which minimises the expected sum of
life-cycle cost within the budget constraint for each
year. The optimal solution at the system-level will not
coincide with the set of optimal policies for each
facility if the budget constraint is binding. Homogeneous
system problems have been solved by using
linear programming (Golabi et al. 1982, Harper and
Majidzadeh 1991, Smilowitz and Madanat 2000). The
decision variables for linear programming are the
proportions of facilities that need a specific MR&R
activity at a certain state. This top-down approach has
advantages, but as discussed earlier, it cannot be
directly applied to MR&R optimisation for heterogeneous
systems.
Fwa et al. (1996) used genetic algorithms, to address
the trade-off between rehabilitation and maintenance.
The authors assumed four categories of agency cost
structure, based on the relative costs among rehabilitation
and three maintenance activities for 30 homogeneous
facilities. Durango-Cohen and Sarutipand
(2007) proposed a quadratic programming (QP) platform
for multi-facility MR&R problem. While the QP
formulation successfully captures the effect of MR&R
interdependency between facility pairs, the applicability
of QP is limited to situations when the costs are
quadratic. The numerical example in the paper is
limited to the facilities with the same deterministic
deterioration process, where each facility is a member of
either a ‘substitutable’ or a ‘complementary’ network.
Although intuitively sensible, the determination of
‘substitutable’ or ‘complementary’ networks might not
be evident in large-scale networks. Ouyang (2007)
developed a new approach for system-level pavement
management problem using multi-dimensional dynamic
programming. He expanded the dynamic programming
formulation used in the facility-level optimisation to
multiple facilities. To overcome the computational
difficulty associated with the multi-dimensional problem,
he adopted an approximation method and
applied this to a deterministic, infinite horizon problem.
Recently, researchers have developed novel solutions
for heterogeneous infrastructure systems.
318 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 Robelin and Madanat (2006) used a bottom-up
approach for MR&R optimisation of a heterogeneous
bridge system. At the facility-level, all possible
combinations of decision variables are enumerated;
at the system-level, the best combination of the
enumerated solutions is determined by searching the
solution space. This system-level problem has a
combinatorial computational complexity. The authors
find a set of lower and upper cost bounds for the
optimal solution, which narrows the search space. In a
related work, Robelin and Madanat (2008) formulated
and solved a risk-based MR&R optimisation problem
for Markovian systems. At the facility-level, the
optimisation consists of minimising the cost of maintenance
and replacement, subject to a reliability
constraint. At the system-level, the dual of the
corresponding problem is solved: risk minimisation
(i.e., reliability maximisation) subject to a budget
constraint; specifically, the objective is to minimise
the maximum risk across all facilities in the system,
subject to the sum of MR&R costs not exceeding the
budget constraint. The solution to the system-level
problem turns out to have a simple structure, with a
linear computational time.
The approach used in Robelin and Madanat (2008)
is limited to risk-based MR&R optimisation, where the
objective function has a Min-Max format, and is not
applicable for serviceability-based optimisation problems.
For serviceability-based problems, the objective
function takes on an expected cost minimisation (or
expected serviceability maximisation), which does not
lend itself to solutions with such a simple structure.
This motivates the approach proposed in this paper.
3. Methodology
Consider an infrastructure system composed of N
independent facilities, with different attributes such as
design characteristics, materials, and traffic loads: this
system is a heterogeneous system. We assume that
MR&R activities and their associated costs can be
defined for all facilities. Then, the objective is to find
the optimal combination of facilities’ MR&R activities
(decision variables), minimising the total system-level
cost (objective functions).
Assuming that inspection is done at the beginning
of the current year, the state of each facility is known,
and the decision process will be performed every year.
In our two-stage bottom-up approach, we first solve
the facility-level optimisation to find a set of best
and alternative MR&R activities and costs for each
facility. In the second stage, we solve the system-level
optimisation to find the best combination of MR&R
activities across facilities by choosing among the
optimal and sub-optimal alternative activities found
in the first step. Figure 1 illustrates the system-level
optimisation for N facilities. For each facility, the
optimal activity and the first and second alternative
activities are obtained from the facility-level optimisation.
The initial solution in the system-level is the set of
optimal activities [a11, a21,..., aN1]. Our objective is to
find an optimal combination of MR&R activities,
Figure 1. System-level solution procedure using the proposed bottom-up approach.
Structure and Infrastructure Engineering 319
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 while minimising the total life-cycle cost within the
budget constraint for the current year. Due to the
presence of a budget constraint, the optimal activities
found in the facility-level optimisation are not necessarily
included in the system-level solution. Instead, the
next alternative activity may replace the optimal
activity for certain facilities if needed, as illustrated in
the case of facility 2 in Figure 1.
In this paper, we focus on a heterogeneous
pavement system as a case study since it is one of the
most widely researched systems, and has a common
problem structure for infrastructure management, i.e.,
probabilistic state transition, time discounting, and
multiple MR&R activities. In a PMS, the state of
pavement can be represented by discrete numbers
such as the pavement serviceability rating (PSR),
ranging from 1 (worst condition) to 5 (best condition).
If pavement deterioration can be represented as a
Markovian process, the serviceability (PSR) changes
over time depend only on the current state and the
maintenance activity applied at the beginning of the
time period after inspection. The transition probability
matrix, Pa(i, j) specifies the probabilities of a state
change from state i to state j after applying maintenance
activity a. An MR&R program X ? [x1,...,
xN] is a set of activities that will be applied to the N
facilities in the system in the current year. We assume a
finite planning horizon of length T. The vector X must
be feasible, i.e., it must satisfy the budget constraint for
the current year.
3.1. Facility-level optimisation
The facility-level optimisation solves for the optimal
activity and its cost pair, action cost (C) and expectedcost-to-go
(V), without accounting for the budget
constraint. It also identifies the suboptimal alternative
policies and their cost pairs. The facility-level optimisation
for a PMS can be formulated as a dynamic
program to obtain an optimal policy and the
alternative policies. The dynamic programming formulation
that solves for optimal activity a* and its
expected cost-to-go V* is
where
A is the set of feasible maintenance activities, A ? {a1,
a2,...}
S is the set of feasible states of facility
Pa(i, j) is the transition probability from state i to state
j under maintenance activity a
C(a, i) is the agency cost for activity a, performed on
facility in state i
a is the discount amount factor, a ? 1/(1 t r); where r
is the discount rate
Va(i, t) is the expected cost-to-go from time t to T for
current state i and activity a applied
User cost can be added to agency cost (C(a,i))
considering the duration of the time and period of cost
generation. MR&R activity associated user costs by
roadwork and user costs from new pavement state
after MR&R action can be added with appropriate
conversion to dollar value. Assuming salvage value of
a facility for each state at time T, we applied dynamic
programming backward iteration to solve Equations
(1) and (2) from time T7 1 to 1, to obtain the
minimum expected total cost-to-go V*(i,1) from the
current time year (t ? 1) to the end of the planning
horizon T. As illustrated in Figure 2, when the facility
state is 8 at time t, three activities are available.
Computing the expected costs-to-go for each activity,
an activity (a3) with minimum expected cost-to-go
(denoted as V1*(8,t)) is chosen as the optimal activity.
The activity a2 with the second smallest expected costto-go
(V2*(8,t) is the first alternative activity; the one
with the third smallest expected cost-to-go (V3*(8,t)) is
the second alternative, etc. a*1(8,t) ? a3, a*2(8,t) ? a2,
and a*3(8,t) a1.
The kth alternative activity a
kt1 and its expected
cost-to-go V
kt1(i,t) can be found by using the
following equations:
Note that when k0, the result of Equation (3), a
1 is
the optimal activity, and V
1, the result of Equation (4),
is the expected cost-to-go for the optimal activity.
Thus, Equations (3) and (4) are used to find both
optimal and alternative activities. Iterating backward
in time, the optimal policy and alternative policies can be
solved for the current year. Although the facility-level
optimisation can also be formulated and solved as
a linear program (for the infinite horizon case), we
adopted dynamic programming, as it also produces
the alternative policies and costs used as inputs for
320 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 the system-level optimisation without additional
calculations.
3.2. System-level optimisation
The facility-level optimisations yield a set of activities and their expected cost-to-go for each facility. Given the agency
cost for each activity, the objective is to find the
combination of activities (one for each facility) that
minimises the system-wide expected cost-to-go while
keeping the total agency cost within the budget.
Assuming that all facilities are independent, and given
a budget constraint, the system-level optimisation can
be formulated as a constrained combinatorial optimisation
problem.
Let Mn {0, 1, 2, . . .} be an alternative activity set
for facility n, where 0 represents the optimal activity
and i represents the ith alternative activity. The systemlevel
optimal activity x1; ... x
N, xn2 Mn will be
determined given the facilities’ current state
[s1,...,sN]. Let f C
n exnT denote the expected cost-to-go
function, and f
B
n exnT the activity cost function for
facility n given activity xnat current time. Note that
xnt1esn; 1T for all n, and fB
n exnT?exn;snT.
Decision variables: X1; ... ; xN
Objective function: min TEC P
n exnT B (B: Budget of the current
year)
where TEC represents the total system expected costto-go
from the current year to year T.
There exist various methods for solving the
constrained combinatorial optimisation problem including
integer programming and heuristic search
algorithms. As the constraints and objective function
might include nonlinear equations, we consider a
nonlinear solution approach. Cases of nonlinear
constraints arise when there exist functional and
economic dependencies between the facilities. For
example, contiguous facilities are best rehabilitated in
the same year to reduce delay costs during the
rehabilitation. Another example is when two facilities
provide alternative routes. In such a case, one of the
two facilities must be available during rehabilitation of
the other facility. The challenge is how to reduce the
computational complexity of the solution algorithm.
Simple method such as the brute force approach that
searches the entire combinatorial solution space finds
the optimal solution. However, with computational
complexity of exponential order, this method cannot
be applied to problems of realistic size.
3.2.1. Two-facility example
Consider a case with two facilities. Figure 3 shows the
solution space and solution path. From the initial
solution X (0,0) which is a combination of optimal
activities without budget constraint, the solution has to
move toward the constrained optimal solution. For the
first facility, the decision variable x1 can take four
values, i.e., four activities are available including the
Figure 2. Dynamic programming process for facility-level optimisation.
Structure and Infrastructure Engineering 321
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 original optimal policy and three alternatives. In this
example, the expected cost-to-go for the optimal policy
is 2, and the alternatives’ costs are 8, 15, and 21. The
second facility, as shown on the vertical axis, has an
optimal expected cost-to-go of 3.5 and alternatives’
costs as 8, 12, and 17. The diagonal lines illustrated are
loci of equal TEC points. We seek the minimum total
cost combination f C
1 ex1T t f C
2 ex2T inside the feasible
region, defined by the budget constraint. As illustrated,
starting from the point (2, 3.5) the solution moves to
the point (2, 8), which gives the smallest total cost
increase from TEC1 (5.5) to TEC2 (10). By repeating
this procedure, we can reach the optimal solution,
which is the first feasible solution visited. However, as
the number of facilities increases, it becomes more
difficult to find the next solution point from the current
solution. In the case of P activities available for all
facilities, there exist PN combinations of movements in
the solution space in the worst case. Therefore, we need
to develop solution methods that can avoid the
exponential order of complexity. We present two
heuristics that reduce the complexity of the solution
algorithms from O(PN) to O(Nb
) where b is a small
integer between 2 and 4.
3.2.2. Pattern search heuristic
PSH simplifies the procedure of movements described
in the previous section. The idea is to repeat simple
movements determined by predefined patterns to find
an advanced point instead of searching all possible
movements. Thus, the PSH is a deterministic search
method. Let dX denote a movement vector. The new
solution is Xnew ? X t dX. Decomposing the movement
vector dX to negative and positive component
vectors (dXt, dX7), movements can be classified into
patterns according to the number of positive and
negative movements. The number of negative and
positive unit direction vectors defines a movement
pattern. Thus, pattern (p, q) refers to the movement
vector composed of p negative unit vectors and q
positive unit vectors. Table 1 shows the possible
movement vector patterns. For example, pattern B
(1,1) has a negative component vector dX7 ? (. . . ,71,
. . .), which means only one component in dX7is 71,
and a positive component vector dXt ? (. . . , 1, . . .)
having only one t1 component. Combining the negative
and positive movement vectors (dX ? dX– t dXt), the
movement vector dX has one 71 component and
one t1 component while all the other components are 0.
Figure 4(a) illustrates the concept of search
procedure for the PSH. For all patterns, a set of
movement vectors is generated to form a set of new
candidate solutions. Based on the evaluation, a
candidate solution is chosen as a new solution. During
the search, all movement combinations for all patterns
in Table 1 are generated. Only patterns of lower degree
p, q 53 are used to restrict the complexity of
computation to less than O(N4
). The solution process
involves three stages: (1) movement toward the feasible
region, (2) solution improvement, and (3) optimality
check. Figure 4(b) shows the three stages for the twofacility
example. In Figure 4(b), the solution starts
from the initial solution of (2, 3.5). Investigating all
possible candidate movements defined by patterns, it
moves to an adjacent point that is closer to the feasible
Figure 3. System-level optimisation for a two-facility example: (a) solution space and (b) solution path.
322 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 region and has the lowest total cost increase. Once it
reaches the feasible region, it moves to new point
improving the current solution within the feasible
region. Finally, it checks optimality to decide whether
it has to stop searching and set the obtained result as a
final solution. If the optimality check fails, it continues
the solution search of stage 2.
Stage 1: Moving toward the feasible region
For each predetermined pattern (p, q), generate a set
of negative and positive movement vectors. Then,
combining them, generate a set of movement vectors.
Given the current solution vector X (x1, x2,..., xN),
find a direction vector dX (dx1, dx2,..., dxN), dX
dXt t dX7, which satisfies Equations (5) and (6).
Table 1. Movement vector patterns.
Movement
vector pattern p q
Movement vector
dX7 complexity dXt complexity
A (0,1) 0 1 (. . . , . . .) – (. . . , t1, . . .) O(N)
(1,0) 1 0 (. . . ,71, . . .) O(N) (. . . , . . .) –
B (1,1) 1 1 (. . . ,71,. . .) O(N) (. . . , t1, . . .) O(N)
C (2,1) 2 1 (. . . ,71, . . . ,71, . . .) O(N2
) (. . . , t1, . . .) O(N)
(. . . ,72, . . .) (. . . , t1, . . .)
D (1,2) 1 2 (. . . ,71, . . .) O(N) (. . . , t1, . . . , t1, . . .) O(N2
)
(. . . ,71, . . .) (. . . , t2, . . .)
E (2,2) 2 2 (. . . ,71, . . . ,71, . . .) O(N2
) (. . . , t1, . . . , t1, . . .) O(N2
)
(. . . ,71, . . . ,71, . . .) (. . . ,72, . . .)
(. . . ,72, . . .)
(. . . , t2, . . .) (. . . , t1, . . . , t1, . . .)
(. . . , t2, . . .)
Figure 4. The pattern search heuristic process: (a) solution search procedure with movement patterns and (b) PSH solution path
for the two-facility example.
Structure and Infrastructure Engineering 323
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 The solution moves to the new solution having the
minimum TEC (Equation (5)) with a lower action cost
(Equation(6)). As long as the new solution has a lower
action cost, the magnitude of the reduction is not
considered. Repeating for all predetermined patterns,
the best solution among all pattern searches is chosen
as the new solution. The stage 1 procedure is repeated
until the solution reaches the feasible region, i.e.,
satisfies the following condition:
n exnT B e Te Budget constraint 7T
Stage 2: Solution improvement
In the second stage, the solution obtained is improved
by searching inside the feasible region. The best
solution satisfying Equations (8) and (9) will be
chosen.
n exnT B e Te Budget constraint 9T
As shown in Table 1, for each stage, the pattern
search algorithm has a complexity of O(N4). If the
pattern E (2,2) is excluded, the algorithm works in
O(N3).
Stage 3: Optimality check
Because the pattern search method does not guarantee
finding the global optimal solution, the search range is
expanded to check the existence of a better solution.
If a better solution is found in stage 3, we return to
stage 2 with the new solution vector.
To search a broader space, two different methods
can be used. Random search can produce a random
jump from one local optimal to the other region.
Random search can be incorporated by generating
random movement vectors from a predefined distribution
such as normal distribution. Adjusting the
distribution parameters can control the search range.
For example, by increasing the standard deviation,
the direction vector has more nonzero components
and the search space is enlarged. The other way to
check for optimality is to increase p and q to 3 or 4.
However, this also increases the complexity of the
algorithm to O(N6) or O(N8). Therefore, we used
the random search method to check for optimality
in the numerical examples presented later in this
paper.
3.2.3. Evolutionary algorithm
EAs are stochastic search methods for nonlinear
optimisation. In EA, a current solution is considered
a parent that brings forth a population of mutant
offspring. The algorithm evaluates the new generation
and selects the best one as a new solution. Repeating
this process, the solution evolves, and a near optimal
solution can be found. As with the PSH algorithm, EA
do not gu