Abstract: Pavement management encompasses a wide range of tasks from data collection and data processing to maintenance management and life cycle cost analysis. This study concentrates on maintenance management at a project level and a network level. A decision support system provides optimum maintenance actions over time to enhance the performance of a pavement network and prolong its life span. A heuristic method i.e., Genetic Algorithm is applied to tackle this optimization problem. Due to complexity of the problem, applying an optimum Genetic Algorithm structure results in significant enhancements in the Genetic Algorithm procedure and saves computation time which has not been received enough attention to date by researchers. An experimental design is conducted to investigate the optimum Genetic Algorithm structure for solving a pavement maintenance problem. Since the current Genetic Algorithm software is not suitable to run the experiment, an accurate spreadsheet program has been developed for this purpose to conduct the experiment. Two types of objective functions have been applied: single objective functions (minimizing cost) vs. multiple objective functions (minimizing cost and maximizing benefit).
INTRODUCTION
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, 2007).
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.
| Table 1: | Summary of pavement management literature incorporating soft computing methods |
| 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 new offsprings.
| Fig. 1(a-b): | Mating process; (a) Crossover techniques and (b) Mutation techniques |
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 not horizontally).
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:
| (1) |
Where:
| A | = | Area under the performance curve |
| V | = | Annual Average Daily Traffic (AADT) (veh h-1) |
| L | = | 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:
| (2) |
| (3) |
| (4) |
| (5) |
| (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:
| (7) |
| (8) |
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.
COMPUTATIONAL STUDY
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.
| Fig. 2(a-b): | 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 GA’s 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 operator’s 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).
EXPERIMENTAL DESIGN
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.
| Fig. 3(a-b): | 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.
| Table 2: | Six scenarios to the mating process |
| Table 3: | Evaluation of different crossover and mutation operation probabilities |
| Fig. 4(a-b): | 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.
CONCLUSION
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.