Infrastructure management consists of systematic planning and programming of
resource allocation or expenditure, design, construction, maintenance, operation
and in-service evaluation of physical facilities. It is a wide range of activities
involving in providing and maintaining infrastructure at the level of service
satisfying public or owners. These activities encompass data acquisition, planning,
programming, execution of new construction, maintenance, rehabilitation and
renovation (Hudson et al., 1997).
Several researchers have been working on various methods to tackle pavement
management optimization problems (Flintsch and Chen, 2004;
Shekharan, 2000; Fwa et al.,
1998a; Pilson et al., 1999; Bandara
and Gunaratne, 2001). Genetic Algorithm (Chan et
al., 1994; Fwa et al., 1994; Chan
et al., 2001; Ferreira et al., 2002;
Fwa et al., 1996, 1998b;
Hegazy, 2006; Maji and Jha, 2007),
Markov Chain (Carnahan, 1988; Dekker,
1996), artificial neural network (Fwa and Chan, 1993),
Regression Analysis (Fwa and Sinha, 1986), Integer Programming
(Fwa et al., 1988) and Fuzzy Logic (Golroo
and Tighe, 2009) have been widely employed to overcome the pavement management
problems. Several researchers applied hybrid approaches to solve these problems.
Bosurgi and Trifiro (2005a, b)
used Genetic Algorithm and Artificial Neural Network to tackle road pavement
maintenance. Genetic Algorithm and simulation have been applied for pavement
maintenance scheduling by Cheu et al. (2004)
and Chootinan et al. (2006). Loia
et al. (2000) incorporated fuzzy logic, artificial neural networks
and genetic algorithm for managing pavement maintenance activities. Recently,
application of iPad terminal with GIS has been used for management and service
platform for pavement (Jiao et al., 2012).
Engineers have faced with a major challenge to overcome the complexity of pavement
management problems. For instance, STxN solutions are feasible for
N pavement sections with S maintenance actions over a planning horizon of T
years. It is time consuming to obtain a global optimum solution for a moderate
real problem even by using the most powerful supercomputers and the latest techniques.
Consequently, it is believed that the problem should be tackled by employing
heuristic methods to probe a good/near optimal solution without
necessarily guaranteeing to obtain the best/global optimum solution.
Yedjour et al. (2011) attempted to combine the
exact analytical optimization and Genetic Algorithm (GA) to overcome ineffectiveness
of GA when it comes to find the exact solution of the optimum in the space.
GA is one of the most efficient tools to deal with the computationally complex
problems. Therefore, GA has been widely acknowledged in various fields to reduce
complexity of computational problems (Asfaw and Saiedi,
2011; Mosavi, 2011; Samimi and
Golkar, 2012; Seyedzade and Attar, 2009; Al-Husainy,
Although several research studies have been conducted to solve the infrastructure
management problem (Hegazy et al., 2004; Wang
et al., 2007; Elbeltagi et al., 2005)
using GA, a practical study which probes optimum GA parameters (e.g., mating
process) in a simplified/educational way to tackle pavement management problems
is still lacking. For instance, Fwa et al. (1996)
introduced nine objective functions for pavement maintenance planning and discussed
multi-objective assessment of functions. However, the mating process (not assessed)
was restricted to the one point crossover and uniform flipping mutation by the
authors. Ferreira et al. (2002) tested a complete
list of GA parameters and operators to solve a pavement management problem.
But, they only applied two crossover methods and one mutation operator (while
more operators would be applicable and applied herein). A summary of relevant
literature which focuses on solving pavement management problems by incorporating
soft computing methods is shown in Table 1. The GA parameters
(crossover technique, mutation technique, crossover probability, mutation probability
and population size) are also presented in Table 1.
The objective of this study was to investigate an optimum GA structure to be applied for developing a maintenance scheme. The scope of this study was to execute sensitivity analysis on the outcome of the problem with respect to the GA structure. It also provided an optimum technique by searching among various combinations of crossover and mutation operators with different probabilities to reach the near optimum solution by performing a lower number of iterations which would lead to time/cost saving. A spreadsheet program was, furthermore, developed herein by authors to handle various types of mating processes of GA (for educational purposes) which has more detailed/useful specifications than similar existing software.
|| Summary of pavement management literature incorporating soft
|GA: Genetic Algorithm, NN: Neural network, MC: Markov chain,
S: Simulation, RA: Regression analysis, IP: Integer programming FL: Fuzzy
logic, OP: One point crossover, TP: Two point crossover, U: Uniform crossover,
UF: Uniform flipping and SG: Switching genes
AN OVERVIEW OF GENETIC ALGORITHM
Genetic Algorithm has been widely acknowledged in infrastructure management
although the optimum GA structure to obtain the near optimum solution faster
and more accurate has not received enough attention. In light of scarcity of
analyzing GA structure to achieve appropriate solutions, it is reasonable to
explain fundamental concepts of GA here. Presentations of GA principles can
be found in Mitchell (1996) in depth.
In GA, a population of strings (called chromosome), which encode candidate solutions to an optimization problem, evolves toward better solutions. Finally, the algorithm terminates once either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.
Initialization and selection: The first step is to generate an initial population of solutions/chromosomes randomly. An important step in solving any problems using GA is to use an adequate methodology to evaluate the fitness of initial solution/string (called a parent). During each successive generation, a proportion of the current population is selected to create a new generation (called an offspring). Selection can be carried out arbitrary or through a fitness-based process, where fitter solutions are more likely to be selected.
Reproduction: Having selected parents, a processing technique is required to mate parents and produce two offsprings. There are two major techniques: crossover and mutation.
Crossover is the most common operator through which two parents are selected
and the genes (each parent consists of a number of genes) are shifted. This
shifting process can be executed using various methods: two points, one point
and uniform. These methods are illustrated in Fig. 1a. Two
random numbers are generated in the two-point crossover to specify a range (i.e.,
2 and 4 in Fig. 1a) to be shifted between two parents to produce
two offsprings which have different genes as compared to parents. In the one-point
crossover, a random number (i.e., 2 in Fig. 1a) is generated
and the genes before and after the crossover point are shifted to create two
|| Mating process; (a) Crossover techniques and (b) Mutation
Finally, every other gene is shifted from one parent to the other parent in
the uniform crossover to provide two offsprings. The crossover operator does
not change the genetic material. For instance, gene number two of a parent is
replaced with gene number two of other parent. In other words, a cell can be
shifted by the other cell in a same location/column (genes only move vertically
Mutation is an operator of generating new genetic materials as oppose to crossover. That is, a gene can be shifted by other gene in another location/column (genes can move both vertically and horizontally). Two major methods are proposed herein to execute the mutation operation: uniform flipping and switching genes. The mutation operator selects a parent to produce an offspring. In the uniform flipping method, the value of each gene is flipped (replaced with a random selection from the existing options) to produce an offspring that is different from a parent. While, in the switching genes method, a selected number of genes (determined at random) are switched. The two mutation techniques are illustrated in Fig. 1b.
The fitness of new generated offspring is compared with the current parents in the population. If the offspring fitness is higher than the lowest parent fitness in the population, the parent with the lowest fitness is removed and the new offspring is entered into the population. These processes finally result in the next generation population with higher average fitness.
Termination: This evolutionary process is repeated until a termination condition has been satisfied. Common terminating conditions are:
||A solution is achieved that provides minimum criteria
||Pre-specified number of generations achieved
||Assigned budget (computation time/money) reached
||Successive iterations no longer produce better results (reached a plateau)
PAVEMENT MANAGEMENT SYSTEM
The fundamental elements of a pavement management system at network or project level are as follows:
||Pavement management system models
||Pavement management system constraints
||Decision support system
These elements are presented to be able to demonstrate the versatility of GA in solving pavement management problems through investigation of an optimum GA structure.
Pavement management system models: Pavement management system models include performance models, cost models and improvement models which are briefly described below.
Performance models indicate the deterioration rate of a pavement throughout
its service life. There are several performance models used for pavement management
which are widely divided into deterministic and probabilistic (Ben-Akiva
et al., 1993).
Cost models predict user cost (e.g., Vehicle Operating Costs (VOCs)) with regards
to pavement condition level, percentages of vehicle types and traffic volume.
For instance, a pavement section with high roughness and severe distress would
result in higher VOCs than a smooth section with lower distress. Improving the
condition level of pavement would reduce VOCs and prolong the life span of pavements.
The cost of maintenance actions is strictly limited to the annual budget. The
challenge is to manage trade-offs between applying appropriate maintenance actions
and accommodating budget constraints to minimize user cost.
The improvement models are employed to evaluate the effectiveness of each maintenance action. These models estimate condition level of pavement after implementing maintenance actions. Improvement models usually provide the improvement in terms of an increase in a pavement condition index (e.g., the International Roughness Index (IRI)).
Pavement management system constraints: Several constraints have been taken into consideration to solve pavement management problems: a trigger/terminal level of a pavement condition index (e.g., IRI), available budget, government/user/owner constraints, etc.
Decision support system: Having defined performance models, cost models, improvement models and constraints, a decision support system (objective function) is required to investigate optimum maintenance actions that should be implemented at proper time on degraded pavement sections to meet constraints and enhance the performance of pavement sections.
To evaluate and determine possible solutions, objective functions are needed. The following objective functions are commonly utilized:
||Minimization of maintenance cost
||Maximization of saving in VOCs
||Maximization of effectiveness
||Maximization of saving in VOCs over cost
||Maximization of effectiveness over cost
Effectiveness is defined as the area under a pavement performance curve multiplied
by section length and traffic volume. The effectiveness of pavement can be estimated
using Eq. 1 (Haas, 1997). The more the
effectiveness the better the overall pavement condition level is:
||Area under the performance curve
||Annual Average Daily Traffic (AADT) (veh h-1)
||Length of a pavement section (km)
In order to investigate a near optimum solution, a model which represents an
objective function is required. The mathematical formulations presenting abovementioned
objective functions are expressed in Eq. 2-6:
where, Ctn is cost of a maintenance action of pavement section n at time period t; VOCtn is vehicle operation cost of pavement section n at time period t; Etn is effectiveness of pavement section n at time period t; r is a discount rate; T is a planning horizon (years) and N is a number of pavement sections. The discount rate is applied to estimate the net present value annually. The maintenance strategy should accommodate various constraints as follows:
||Total maintenance strategies < total budget
||A pavement condition index of an individual pavement section in each year
< trigger level
Since GA is based on random process, the constraints cannot be simply formulated. The common approach to serve the constraints is to eliminate solutions/strings which violate the constraints from a population. Although this approach is easy to use, it removes strings that may be useful in mating processes. Hence, the Lagrangian relaxation method is employed to benefit from the total strings whether or not strings violate the constraints. Namely, these constraints are not rigidly enforced but a penalty for violating the constraints would be assigned to associated solutions. The penalty is usually a function of the amount of violation. That is, the more the violation ratio the more the penalty is. The penalties for violating a maintenance budget and pavement condition trigger level are presented as follows:
Although, two major constraints have been defied here, other constraints can be readily added to the model such as considering a trigger level for overall network condition or annual budget limit.
Single-objective vs. multi-objective functions: The results can be demonstrated using either single-objective functions or multi-objective functions. A common approach to obtain a single-objective function out of various objective functions is to combine them (e.g., calculate weighted summation of objective functions). The ratio of benefit to cost is proposed as a single objective function. The benefit can be effectiveness or saving in VOCs. Maintenance cost has been widely used as a single objective function to determine optimum maintenance strategies; however, considering only maintenance cost is not a wise approach since benefits achieved by implementing a maintenance strategy plays a significance role in decision making in infrastructure management so that it is suggested to take account of both benefit and cost.
The multi-objective functions may be benefit vs. cost (e.g., effectiveness
vs. cost). This later approach has been commonly overlooked by the pavement
engineers due to the computationally complexity of the problems, while has been
acknowledged by research in other fields (Touat et al.,
2010; Cao and Cleghorn, 2011). However, multi-objective
functions would specify the trade-off between benefit and cost which is useful
for decision makers to find an optimum solution which matches with the engineers
need. Both approaches are presented herein. A single-objective function is employed
to date to reach the near optimum solution. In fact, multi-objective functions
provide better overview for engineers and assist decision makers to assess the
trade-off between two opposite objectives. In order to evaluate the fitness
of each solution, an efficient set of non-dominant solutions should be investigated.
Since two objective functions (i.e., maximizing the benefit and minimizing the
cost) should be considered concurrently, a set of non-dominant solutions is
searched. In this case, instead of specifying an individual string as an optimum
solution, a set of non-dominant solutions is proposed. Non-dominant solutions
are alternatives that contain the best value for cost and benefit.
A solution can be presented as a string that has N x T cells/genes (Fig.
2a). Each cell expresses a maintenance action (i.e., action 1, 2,
, S) in each year (over planning horizon, T years) which should be implemented
on a pavement section (i.e., section 1,2,
, N). For instance, the string
presented in Fig. 2b shows that action numbers 1, 1 and 2
will be executed on pavement sections 1, 2 and N in the first year, respectively.
|| Problem setting; (a) Problem presentation and (b) String/solution
It also expresses that pavement section number 1 and 2 are not selected for
treatment in the second year.
Cost, effectiveness, vehicle operation cost, etc. (Eq. 2-6)
which were proposed as objective functions along with constraints (Eq.
6, 7 and 8) were applied to evaluate
fitness of strings in a population. Detailed presentation of GA calculations
is out of scope of this paper and only outcomes of investigation of optimum
GA structure will be presented.
OPTIMUM GA STRUCTURE
In order to investigate the optimum GA structure (simulation number, mating
operator methods, operators probability), an experimental design has been
conducted. This experimental design requires independent replicates to be executed
for different GA structures. Appropriate software which is able to set up different
GA structures is essential to conduct the experiment. Although available software
in the market (http://www.palisade.com)
is powerful and can sufficiently run GA for various problems, they do not provide
various operators methods as discussed earlier or not able to change GA
settings such as operators method and their probabilities. Therefore,
a spreadsheet program was developed which is able to run GA with various GAs
settings including combinations of different operators and their probabilities.
Microsoft Excel software is chosen for execution of this model due to its user friendly interface and powerful programming features. The Marco Language of Microsoft Excel is employed to code the procedure of implementing GA for solving pavement management problems. Every attempt was taken to provide powerful and accurate coding for various GA structures along with providing a user friendly interface. As shown in Fig. 3a, users can set detailed setting of GA such as population size and number of simulation. Users are capable to continue evolving the existing population instead of generating new population in each trial. Moreover, the operators probabilities i.e., percentage of time in which the crossover operator is used versus mutation can be selected. More importantly, the desired operators method of mating can be specified which includes uniform, one-point and two-point methods for the crossover operator and uniform flipping and switching genes methods for the mutation operator. In the case of choosing switching genes method, a number of switched genes should be additionally determined.
As Fig. 3b shows, the objective function values are presented as outputs together with the single objective function curve (benefit/cost vs. solution#), the multiple objective function curve (benefit vs. cost) and the convergence rate curve. Moreover, the process of mating (crossover or mutation) can be observed while the simulation is running. Finally, once the simulation process finishes, the pop up window appears on the screen showing the best solution number, the corresponding string and the associated objective function value (in terms of benefit/cost).
An experimental design was conducted to cover all possible combinations with regards to operators methods. There are three types of crossover methods and two types of mutation methods proposed herein to execute the mating process. Thus, the two-level factorial experiment was applied. Six experiments were defined with respect to various methods of crossover and mutation demonstrated in Table 2. To investigate an optimum setting of GA, three criteria were examined which included a number of simulation, optimum combination of operators methods and operators probabilities.
First, to search for a sufficient number of simulations, five replicates/series
of population with a same size (i.e., 50 strings/parents) but consisting different
strings were generated at random.
||Spreadsheet program; (a) Genetic algorithm setting screen
and (b) Main worksheet
The percentage of application of crossover and mutation operators was considered
consistent (80 and 20, respectively) for all replicates to be able to analyze
the effect of simulation number on convergence. Various numbers of simulations
were tested at an interval of 50 (starting from 0) to reach convergence of an
objective function value (which is discussed later). As shown in Fig.
4a, the convergence rate is equal to 500 according to several trials.
Secondly, to search for optimum combinations of mating methods (six combination according to the factorial design shown in Table 3), the GA was run for three replicates (sets of population which were populated at random). Based on an objective function value, various combinations were ranked. As shown in Fig. 4b, experiment 4, US (i.e., crossover method: uniform and mutation method: switching genes) is the optimum combination, while experiment 2, OU (i.e., crossover: one point and mutation: uniform flipping) is the worst.
Thirdly, the Genetic Algorithm criterion that has not been received enough attention by researchers is to dedicate optimum percentages/probability of applying mutation and crossover operators. Various percentage values range from 100 to 70% at interval of 5% for the crossover operator probability and from 0 to 30% at the same interval for the mutation operator probability were run for 500 simulations using the optimum mating scenarios proposed earlier (i.e., US: uniform crossover and switching gene mutation). Each pair of probabilities (for crossover and mutation) was replicated five times each time for 500 simulations. The convergence rate (a simulation number within 500 which an objective function converges) and the population evolution rate (percentage of increase in the value of an objective function) have been determined and are presented in Table 3.
It can be observed from Table 3 that the best scenario in terms of the convergence rate is scenario 1 (crossover probability = 100 and mutation probability= 0), while the best one in terms of the population evolution rate is scenario 3 (crossover probability = 90, mutation probability= 10). Regarding the fact that the population evolution rate is more important than convergence rate and the difference between the convergence rate of scenario 1 and scenario 3 is not significant, the third scenario is proposed as the optimum scenario.
|| Six scenarios to the mating process
|| Evaluation of different crossover and mutation operation
||Effective genetic algorithm approach, (a) Convergence to a
near optimum solution and (b) Ranking of various genetic algorithm approaches
for three population sets
Ultimately, the optimum problem setting for the Genetic Algorithm can be summarized as follows:
||Number of simulation: 500
||Crossover technique: uniform
||Mutation technique: switching genes
||Percentage of running crossover operator: 90%
||Percentage of running mutation operator: 10%
The methodology used to conduct the experimental design for investigating the
optimum GA settings seems statistically sound and it provides reasonable results
which are consistent with the researchers achievements to date (Bosurgi
and Trifiro, 2005a, b). The contribution of this
study was to examine statistical experiments to achieve the optimum GA settings
while researchers (Pilson et al., 1999; Maji
and Jha, 2007) commonly applied selected/assumed GA settings.
A decision support system plays significant role in pavement management both at a network level and a project level. This system searches for optimum maintenance actions at adequate time to be implemented on an appropriate pavement section. Genetic Algorithm was found to be an efficient tool to deal with such a computationally complex problem. Since the problem is significantly complex especially where a pavement network has thousands of kilometers of roads, the GA settings are of significant importance. Having applied optimum GA settings would result in a significant amount of saving in computation time. An experimental design was conducted in a developed spreadsheet program to examine several combinations of operators and statistically sound results were achieved. The GA settings provided optimum number of simulations, operators methods and their probabilities.