辅导heterogeneous、讲解infrastructure systems、辅导Java/c++编程语言
- 首页 >> 其他 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 guarantee global optimality. Figure 5(a) shows
the basic concept of EA search. A set of random
offspring is generated according to a normal distribution,
and evaluated. One solution among all offspring
is chosen as a new solution for the next iteration. The
EA implemented in this paper has three stages: (1)
offspring generation, (2) offspring evaluation and
selection, and (3) optimality check. The overall
procedure of EA is similar to that of PSH, but it
searches the solution space stochastically by generating
random offspring while PSH searches all possible
combinations according to the predefined patterns.
The evaluation and selection stage determines
where to move from the current solution. Before
reaching the feasible region, an offspring reducing the
budget with the smallest cost increase is selected; after
reaching the feasible region, the least cost solution
inside the region is selected to improve the current
solution. Figure 5(b) shows the application of the EA
method to the two-facility example. From point (2,
3.5), several offspring are generated and evaluated, and
point (2, 8) is chosen as the next solution because it has
the lowest cost increase among all solutions that have a
lower activity cost.
Stage 1: Mutant offspring generation
To generate mutant offspring, we use the current
solution vector X as a single parent. As in the PSH,
dX is the movement vector. A number of movement
vectors are randomly generated according to the
normal distribution, dxn Ne0;s2T; n N. The off-
spring is Xoffspring ? dX. The initial solution vector is
the optimal one found in the facility-level optimisation
without budget constraint, as in the PSH. After
generating movement vectors, they are rounded to
one of the discrete values: 73, 72, 71, 0, 1, 2, 3.
The smaller the value of s, the larger the number of
components of the movement vector with zero value
resulting in smaller search space. The number of
offspring is used to control the precision of search.
Stage 2: Offspring evaluation and selection
At this stage, generated offspring are evaluated to find
the best movement from the current solution point.
When the current agency activity cost is greater than
the budget assigned, the offspring satisfying the
following conditions is selected.
324 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014
When the solution is inside the feasible region, we
select an offspring satisfying the following condition:
n exn t dxT B e Te Budget constraint 13T
The stage 2 procedure is repeated until there is no
solution improvement.
Stage 3: Optimality check
As in the PSH approach, the search range is also
expanded to find a solution closer to the global optimal
solution. In each step when no improved solution is
found, s is increased by the multiplication factor m.
Therefore, if k steps pass without solution improvement,
dxn*N(0, m2ks2) is used for optimality checking.
If an improved solution is found, k is reset to its
initial value.
4. Numerical example
To evaluate the proposed optimisation algorithms and
show the applicability of the suggested approach to
a realistic problem, we created highway pavement
systems with random transition probability matrices
and action costs, and compared the optimality of the
solutions and the algorithm execution speeds for the
PSH and the EA.
4.1. Test system creation
Virtual highway pavement systems of 20 facilities
based on realistic data were created; the number of
facilities was increased to 200 to compare the execution
time. Finally, the EA performance was evaluated with
systems of 10–2000 facilities. The planning horizon
was set to 40 years, and the interest rate to 5%. The
agency activity costs and transition probability
matrices were generated randomly with the mean
values shown below.
4.1.1. Agency activity cost
Table 2 shows the agency activity costs for each
state and activity. These values were used as mean
values to generate virtual pavement systems for the
experiments. Note that pavement states lower than 4
are unacceptable, which is incorporated as a
constraint.
Figure 5. The evolution algorithm process: (a) solution search procedure with random offspring vectors and (b) EA solution
path for the two-facility case.
Structure and Infrastructure Engineering 325
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 Table 2. Mean activity costs ($/sqyd).
Pavement state
Maintenance activity 10 9 8 7 6 5 4 3 2 1
Acceptable Unacceptable
Do-nothing 0 0 0 0 0 0 0 0 0 0
Maintenance 0.5 3.0 8.5 16.5 43.5 53.5 55.5 57.0 58.0 58.5
Reconstruction 60 60 60 60 60 60 60 60 60 60
4.1.2. Transition probability matrix
The transition probability matrix provides the probabilities
of state transition of a pavement segment after
a maintenance activity is applied. The matrices shown
below are the transition probability matrices for donothing
and maintenance, respectively. Values shown
are also mean values for each facility, and nonzero
components are randomised keeping all row sums 1.
For the activity Reconstruction, the first column is set
to 1 while all other elements are set to 0.
4.1.3. Algorithm verification
Figure 6(a) and (b) shows the progressions of the two
algorithms. AC and TEC in Figure 6 represent the
agency activity cost and the total expected cost,
respectively. Before reaching the feasible region, the
solution moves to the budget constraint region as AC
decreases. But TEC does not necessarily decrease; in
most cases, it increases until the budget region is
reached. After reaching the feasible region, the
solution moves within the feasible region keeping AC
lower than budget. TEC always decreases, while AC
can either increase or decrease. When both TEC and
AC become constant, the algorithm lies in stage 3,
in which it searches a broader range in the solution
space to find a better solution. If no better solution is
found within a predetermined time step, the algorithms
end.
4.2. Optimality evaluation
To evaluate the solutions of the PSH and EA, 1000
random experiments were executed for a 20-facility
system. In each experiment, facilities were randomly
generated with random ACs and transition probabilities
as described in Section 4.1. The value of s for
offspring randomisation was set to 0.15, the multiplication
factor m to 1.1, and the number of offspring
for each iteration was set to 100. Real optimal costs
TECopt were calculated by exhaustive search for
comparison.
Table 3 presents the experimental results for the
PSH and EA. In both cases, the mean value of optimal
total expected cost ratio (TEC/TECopt) was lower than
1.001 (0.1%). In 978 cases and 966 cases out of 1000
experiments, for the PSH and the EA respectively, the
optimal total cost ratios were lower than 1.001. In
other words, in around 97% of cases, both algorithms
found near-optimal solutions within a 0.1% difference.
4.3. Algorithm execution speed evaluation
Actual CPU times used by the test program
(MATLAB) during the algorithm execution were
obtained and compared. A test computer with a
2 GHz CPU was used for experiments. Both algorithms
have a polynomial order of complexity: O(N3)
for EA and O(N4) for PSH. Figure 7 shows the CPU
times for PSH and EA vs. the problem size, N. The EA
shows better performance as N increases than the PSH
algorithm. For a system of 200 facilities, the PSH
reaches the solution in 925.2 seconds and the EA in
12.7 seconds. The lines denoting N3 and N4 represent
326 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 the execution time when the algorithms’ complexities
are exactly in the order of N3 and N4
, respectively.
An additional EA test was conducted for a system
up to 2000 facilities resulting in good performance as
Table 3. Comparison of the PSH and EA, and optimal cost
and budget ratio.
Algorithm PSH EA
Optimal cost ratio
(TEC/TECopt)
Mean 1.0003 1.0007
Std 0.0023 0.0041
Budget ratio
(AC/ACopt)
Mean 0.9967 0.9970
Std 0.0548 0.0548
Near optimal cases
(TEC/TECopt5 1.001)
978 cases/
1000
966 cases/
1000
Figure 7. CPU time for PSH and EA.
Figure 6. Solution progressions for the two algorithms: (a) pattern search heuristic and (b) evolution algorithm.
Structure and Infrastructure Engineering 327
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 shown in Table 4. When N is 1000, the execution time
is less than 14 minutes, and when N is 2000, the
execution time is approximately 109 minutes. Noting
that the ADOT’s PMS optimises 7400 sections of
freeway, it can be claimed that the proposed method
can be applied to a real statewide PMS.
5. Conclusions
In this paper, we proposed a two-stage bottom-up
methodology to solve the MR&R optimisation problem
for a heterogeneous infrastructure system. To
overcome the computational complexity of the brute
force search, we developed a method that utilises the
optimal and alternative solutions at the facility level.
This approach makes the search process more efficient
by specifying the search order for the alternatives. The
system-level problem is formulated as a constrained
combinatorial optimisation, and solutions are found
based on one of the two heuristic methods: (1) PSH
and (2) EA. Evaluation results suggest that the EA is
effective in identifying the close-to-optimal solutions in
relatively short solution time for large-scale network
problems. Numerical experiments showed that we
could obtain the near-optimal solutions (within less
than 0.1% difference from the optimal solution) in
most cases. Experiments also showed the potential of
the proposed algorithms to solve the maintenance
optimisation problem for realistic heterogeneous systems.
One extension of the proposed method is the
optimisation of a system composed of diverse types of
infrastructures of bridges, pavements, and other types
of facilities. Such an extension would be useful for
optimising DOT maintenance expenditure in a multiasset
management framework.
References
Carnahan, J.V., 1988. Analytical framework for optimizing
pavement maintenance. Journal of Transportation Engineering,
ASCE, 114, 307–322.
Durango-Cohen, P., and Sarutipand, P., 2007. Multi-facility
maintenance optimization with coordinated interventions.
Proceedings of the Eleventh World Conference on
Transport Research, Berkeley, CA.
Friesz, T.L., and Fernandez, J.E., 1979. A model of optimal
transport maintenance with demand responsiveness.
Transportation Research, 13B, 317–339.
Fwa, T.F., Chan, W.T., and Tan, C.Y., 1996. Geneticalgorithm
programming of road maintenance and
rehabilitation. Journal of Transportation Engineering,
ASCE, 122, 246–253.
Golabi, K., Kulkarni, R., and Way, G., 1982. A statewide
pavement management system. Interfaces, 12, 5–21.
Guillaumot, V.M., Durango-Cohen, P.L., and Madanat,
S.M., 2003. Adaptive optimization of infrastructure
maintenance and inspection decisions under performance
model uncertainty. Journal of Infrastructure Systems, 9,
133–139.
Harper, W.V., and Majidzadeh, K., 1991. Use of expert
opinion in two pavement management systems. Transportation
Research Record, No. 1311, Transportation
Research Board, Washington, DC, 242–247.
Li, Y., and Madanat, S., 2002. A steady-state solution for the
optimal pavement resurfacing problem. Transportation
Research, 36A, 525–535.
Madanat, S., and Ben-Akiva, M., 1994. Optimal inspection
and repair policies for transportation facilities. Transportation
Science, 28, 55–62.
Organization for Economic Cooperation and Development
(OECD), 1987. Pavement management systems. Road
Transport Research Report, Paris, France.
Ouyang, Y., 2007. Pavement resurfacing planning on
highway networks: a parametric policy iteration approach.
Journal of Infrastructure Systems, ASCE, 13 (1),
65–71.
Ouyang, Y., and Madanat, S., 2006. An analytical solution
for the finite-horizon pavement resurfacing planning
problem. Transportation Research, Part B, 40, 767–778.
Robelin, C.A., and Madanat, S., 2006. A bottom-up,
reliability-based bridge inspection, maintenance and
replacement optimization model. Proceedings of the
Transportation Research Board Meeting 2006 (CD-ROM),
TRB, Washington, DC. Paper #06-0381.
Robelin, C.A., and Madanat, S., 2008. Reliability-based
system-level optimization of bridge maintenance and
replacement decisions. Transportation Science, 42 (4),
508–513.
Smilowitz, K., and Madanat, S., 2000. Optimal inspection
and maintenance policies for infrastructure systems.
Computer-Aided Civil and Infrastructure Engineering,
15(1).
Tsunokawa, K., and Schofer, J.L., 1994. Trend curve optimal
control model for highway pavement maintenance: case
study and evaluation. Transportation Research, 28A,
151–166.
Table 4. EA execution time.
Number of facilities, N 10 50 100 150 200 500 1000 2000
CPU time (s) 0.03 0.78 2.09 4.75 12.92 142.61 817.17 6575.52
328 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014
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 guarantee global optimality. Figure 5(a) shows
the basic concept of EA search. A set of random
offspring is generated according to a normal distribution,
and evaluated. One solution among all offspring
is chosen as a new solution for the next iteration. The
EA implemented in this paper has three stages: (1)
offspring generation, (2) offspring evaluation and
selection, and (3) optimality check. The overall
procedure of EA is similar to that of PSH, but it
searches the solution space stochastically by generating
random offspring while PSH searches all possible
combinations according to the predefined patterns.
The evaluation and selection stage determines
where to move from the current solution. Before
reaching the feasible region, an offspring reducing the
budget with the smallest cost increase is selected; after
reaching the feasible region, the least cost solution
inside the region is selected to improve the current
solution. Figure 5(b) shows the application of the EA
method to the two-facility example. From point (2,
3.5), several offspring are generated and evaluated, and
point (2, 8) is chosen as the next solution because it has
the lowest cost increase among all solutions that have a
lower activity cost.
Stage 1: Mutant offspring generation
To generate mutant offspring, we use the current
solution vector X as a single parent. As in the PSH,
dX is the movement vector. A number of movement
vectors are randomly generated according to the
normal distribution, dxn Ne0;s2T; n N. The off-
spring is Xoffspring ? dX. The initial solution vector is
the optimal one found in the facility-level optimisation
without budget constraint, as in the PSH. After
generating movement vectors, they are rounded to
one of the discrete values: 73, 72, 71, 0, 1, 2, 3.
The smaller the value of s, the larger the number of
components of the movement vector with zero value
resulting in smaller search space. The number of
offspring is used to control the precision of search.
Stage 2: Offspring evaluation and selection
At this stage, generated offspring are evaluated to find
the best movement from the current solution point.
When the current agency activity cost is greater than
the budget assigned, the offspring satisfying the
following conditions is selected.
324 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014
When the solution is inside the feasible region, we
select an offspring satisfying the following condition:
n exn t dxT B e Te Budget constraint 13T
The stage 2 procedure is repeated until there is no
solution improvement.
Stage 3: Optimality check
As in the PSH approach, the search range is also
expanded to find a solution closer to the global optimal
solution. In each step when no improved solution is
found, s is increased by the multiplication factor m.
Therefore, if k steps pass without solution improvement,
dxn*N(0, m2ks2) is used for optimality checking.
If an improved solution is found, k is reset to its
initial value.
4. Numerical example
To evaluate the proposed optimisation algorithms and
show the applicability of the suggested approach to
a realistic problem, we created highway pavement
systems with random transition probability matrices
and action costs, and compared the optimality of the
solutions and the algorithm execution speeds for the
PSH and the EA.
4.1. Test system creation
Virtual highway pavement systems of 20 facilities
based on realistic data were created; the number of
facilities was increased to 200 to compare the execution
time. Finally, the EA performance was evaluated with
systems of 10–2000 facilities. The planning horizon
was set to 40 years, and the interest rate to 5%. The
agency activity costs and transition probability
matrices were generated randomly with the mean
values shown below.
4.1.1. Agency activity cost
Table 2 shows the agency activity costs for each
state and activity. These values were used as mean
values to generate virtual pavement systems for the
experiments. Note that pavement states lower than 4
are unacceptable, which is incorporated as a
constraint.
Figure 5. The evolution algorithm process: (a) solution search procedure with random offspring vectors and (b) EA solution
path for the two-facility case.
Structure and Infrastructure Engineering 325
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 Table 2. Mean activity costs ($/sqyd).
Pavement state
Maintenance activity 10 9 8 7 6 5 4 3 2 1
Acceptable Unacceptable
Do-nothing 0 0 0 0 0 0 0 0 0 0
Maintenance 0.5 3.0 8.5 16.5 43.5 53.5 55.5 57.0 58.0 58.5
Reconstruction 60 60 60 60 60 60 60 60 60 60
4.1.2. Transition probability matrix
The transition probability matrix provides the probabilities
of state transition of a pavement segment after
a maintenance activity is applied. The matrices shown
below are the transition probability matrices for donothing
and maintenance, respectively. Values shown
are also mean values for each facility, and nonzero
components are randomised keeping all row sums 1.
For the activity Reconstruction, the first column is set
to 1 while all other elements are set to 0.
4.1.3. Algorithm verification
Figure 6(a) and (b) shows the progressions of the two
algorithms. AC and TEC in Figure 6 represent the
agency activity cost and the total expected cost,
respectively. Before reaching the feasible region, the
solution moves to the budget constraint region as AC
decreases. But TEC does not necessarily decrease; in
most cases, it increases until the budget region is
reached. After reaching the feasible region, the
solution moves within the feasible region keeping AC
lower than budget. TEC always decreases, while AC
can either increase or decrease. When both TEC and
AC become constant, the algorithm lies in stage 3,
in which it searches a broader range in the solution
space to find a better solution. If no better solution is
found within a predetermined time step, the algorithms
end.
4.2. Optimality evaluation
To evaluate the solutions of the PSH and EA, 1000
random experiments were executed for a 20-facility
system. In each experiment, facilities were randomly
generated with random ACs and transition probabilities
as described in Section 4.1. The value of s for
offspring randomisation was set to 0.15, the multiplication
factor m to 1.1, and the number of offspring
for each iteration was set to 100. Real optimal costs
TECopt were calculated by exhaustive search for
comparison.
Table 3 presents the experimental results for the
PSH and EA. In both cases, the mean value of optimal
total expected cost ratio (TEC/TECopt) was lower than
1.001 (0.1%). In 978 cases and 966 cases out of 1000
experiments, for the PSH and the EA respectively, the
optimal total cost ratios were lower than 1.001. In
other words, in around 97% of cases, both algorithms
found near-optimal solutions within a 0.1% difference.
4.3. Algorithm execution speed evaluation
Actual CPU times used by the test program
(MATLAB) during the algorithm execution were
obtained and compared. A test computer with a
2 GHz CPU was used for experiments. Both algorithms
have a polynomial order of complexity: O(N3)
for EA and O(N4) for PSH. Figure 7 shows the CPU
times for PSH and EA vs. the problem size, N. The EA
shows better performance as N increases than the PSH
algorithm. For a system of 200 facilities, the PSH
reaches the solution in 925.2 seconds and the EA in
12.7 seconds. The lines denoting N3 and N4 represent
326 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 the execution time when the algorithms’ complexities
are exactly in the order of N3 and N4
, respectively.
An additional EA test was conducted for a system
up to 2000 facilities resulting in good performance as
Table 3. Comparison of the PSH and EA, and optimal cost
and budget ratio.
Algorithm PSH EA
Optimal cost ratio
(TEC/TECopt)
Mean 1.0003 1.0007
Std 0.0023 0.0041
Budget ratio
(AC/ACopt)
Mean 0.9967 0.9970
Std 0.0548 0.0548
Near optimal cases
(TEC/TECopt5 1.001)
978 cases/
1000
966 cases/
1000
Figure 7. CPU time for PSH and EA.
Figure 6. Solution progressions for the two algorithms: (a) pattern search heuristic and (b) evolution algorithm.
Structure and Infrastructure Engineering 327
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014 shown in Table 4. When N is 1000, the execution time
is less than 14 minutes, and when N is 2000, the
execution time is approximately 109 minutes. Noting
that the ADOT’s PMS optimises 7400 sections of
freeway, it can be claimed that the proposed method
can be applied to a real statewide PMS.
5. Conclusions
In this paper, we proposed a two-stage bottom-up
methodology to solve the MR&R optimisation problem
for a heterogeneous infrastructure system. To
overcome the computational complexity of the brute
force search, we developed a method that utilises the
optimal and alternative solutions at the facility level.
This approach makes the search process more efficient
by specifying the search order for the alternatives. The
system-level problem is formulated as a constrained
combinatorial optimisation, and solutions are found
based on one of the two heuristic methods: (1) PSH
and (2) EA. Evaluation results suggest that the EA is
effective in identifying the close-to-optimal solutions in
relatively short solution time for large-scale network
problems. Numerical experiments showed that we
could obtain the near-optimal solutions (within less
than 0.1% difference from the optimal solution) in
most cases. Experiments also showed the potential of
the proposed algorithms to solve the maintenance
optimisation problem for realistic heterogeneous systems.
One extension of the proposed method is the
optimisation of a system composed of diverse types of
infrastructures of bridges, pavements, and other types
of facilities. Such an extension would be useful for
optimising DOT maintenance expenditure in a multiasset
management framework.
References
Carnahan, J.V., 1988. Analytical framework for optimizing
pavement maintenance. Journal of Transportation Engineering,
ASCE, 114, 307–322.
Durango-Cohen, P., and Sarutipand, P., 2007. Multi-facility
maintenance optimization with coordinated interventions.
Proceedings of the Eleventh World Conference on
Transport Research, Berkeley, CA.
Friesz, T.L., and Fernandez, J.E., 1979. A model of optimal
transport maintenance with demand responsiveness.
Transportation Research, 13B, 317–339.
Fwa, T.F., Chan, W.T., and Tan, C.Y., 1996. Geneticalgorithm
programming of road maintenance and
rehabilitation. Journal of Transportation Engineering,
ASCE, 122, 246–253.
Golabi, K., Kulkarni, R., and Way, G., 1982. A statewide
pavement management system. Interfaces, 12, 5–21.
Guillaumot, V.M., Durango-Cohen, P.L., and Madanat,
S.M., 2003. Adaptive optimization of infrastructure
maintenance and inspection decisions under performance
model uncertainty. Journal of Infrastructure Systems, 9,
133–139.
Harper, W.V., and Majidzadeh, K., 1991. Use of expert
opinion in two pavement management systems. Transportation
Research Record, No. 1311, Transportation
Research Board, Washington, DC, 242–247.
Li, Y., and Madanat, S., 2002. A steady-state solution for the
optimal pavement resurfacing problem. Transportation
Research, 36A, 525–535.
Madanat, S., and Ben-Akiva, M., 1994. Optimal inspection
and repair policies for transportation facilities. Transportation
Science, 28, 55–62.
Organization for Economic Cooperation and Development
(OECD), 1987. Pavement management systems. Road
Transport Research Report, Paris, France.
Ouyang, Y., 2007. Pavement resurfacing planning on
highway networks: a parametric policy iteration approach.
Journal of Infrastructure Systems, ASCE, 13 (1),
65–71.
Ouyang, Y., and Madanat, S., 2006. An analytical solution
for the finite-horizon pavement resurfacing planning
problem. Transportation Research, Part B, 40, 767–778.
Robelin, C.A., and Madanat, S., 2006. A bottom-up,
reliability-based bridge inspection, maintenance and
replacement optimization model. Proceedings of the
Transportation Research Board Meeting 2006 (CD-ROM),
TRB, Washington, DC. Paper #06-0381.
Robelin, C.A., and Madanat, S., 2008. Reliability-based
system-level optimization of bridge maintenance and
replacement decisions. Transportation Science, 42 (4),
508–513.
Smilowitz, K., and Madanat, S., 2000. Optimal inspection
and maintenance policies for infrastructure systems.
Computer-Aided Civil and Infrastructure Engineering,
15(1).
Tsunokawa, K., and Schofer, J.L., 1994. Trend curve optimal
control model for highway pavement maintenance: case
study and evaluation. Transportation Research, 28A,
151–166.
Table 4. EA execution time.
Number of facilities, N 10 50 100 150 200 500 1000 2000
CPU time (s) 0.03 0.78 2.09 4.75 12.92 142.61 817.17 6575.52
328 H. Yeo et al.
Downloaded by [University of Newcastle, Australia] at 20:53 30 December 2014