联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2019-04-05 10:15

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-conditions

Algorithms 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


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp