Received 28 November 2015; accepted 20 December 2015; published 23 December 2015

ABSTRACT

Meta-heuristic algorithms proved to find optimal solutions for combinatorial problems in many domains. Nevertheless, the efficiency of these algorithms highly depends on their parameter settings. In fact, finding appropriate settings of the algorithm’s parameters is considered to be a non- trivial task and is usually set manually to values that are known to give reasonable performance. In this paper, Ant Colony Optimization with Parametric Analysis (ACO-PA) is developed to overcome this drawback. The main feature of the ACO-PA is the ability of deciding the appropriate parameter values within the predefined parameter variations. Besides, a new approach which enables the pheromone information value to be proportional to the heuristic information value is introduced. The effectiveness of the proposed algorithm is investigated through the application of the algorithm to the construction site layout problems taken from the state-of-art. Results show that the ACO-PA can reduce transportation cost up to 16.8% compared to the site layouts generated by Genetic Algorithms and basic ACO. Moreover, the effects of parameter settings on the generated solutions are investigated.

Keywords:

Ant Colony Optimization, Construction Site Layout, Parameter Settings

1. Introduction

Lately, mathematical optimization models [1] - [5] , artificial intelligence techniques such as neural networks [6] [7] , Genetic Algorithms (GA) [8] - [13] and particle swarm optimization algorithms including Ant Colony Optimization (ACO) [14] - [17] have been proposed to solve optimization problems. The decision to choose one of these algorithms depends on the computational time, solution quality, interaction of parameters, complexity and behavior of the algorithms when larger problems are used. Among these methods, ACO algorithms have proved to find best solutions for optimization problems [18] . ACO algorithms are population-based optimization approaches that maintain a population of artificial ants which mimic the behavior of real ants. They were first introduced by Dorigo et al. [19] and were applied to the traveling salesman problem. Refined versions of ACO have been proposed to design and implement solutions to combinatorial problems such as routing [20] , assignment [21] , and scheduling problems [22] . Gagne et al. [23] showed that ACO has competitive and advantageous behavior for larger problems as compared to the GA, Simulated Annealing (SA), Random Search Pairwise Interchange (RSPI), and branch-and-bound algorithm. Gagne et al. [23] indicate that ACO has equal or better solution quality and lower computational times for larger problems. Milena and Borovska [24] compared the efficiency of parallel computational models for ACO, GA, and SA for finding near optimal solution in Traveling Salesman Problem (TSP) and concluded that ACO performed better in terms of speedup and solution quality.

One of the key points for getting high-quality solutions by ACO is the parameters and the main drawback is the absence of a general strategy for choosing values for these parameters. In fact, finding appropriate settings of an algorithm’s parameters is considered to be a non-trivial task. ACO algorithm parameters are usually set manually to values that are known to give reasonable performance. These parameter values do not vary from one problem domain instance to another and are fixed throughout the entire run. A better approach for the determination of these parameter values is a fine tuning process which generally results in better solutions; however, in many instances, only several values are tested for parameter tuning and are fixed throughout the entire run [25] - [27] .

In this paper, Ant Colony Optimization with Parametric Analysis (ACO-PA) is proposed to overcome this drawback, and, thus, to improve the solution. The main feature of the ACO-PA is the ability of deciding the appropriate parameter values within the predefined parameter variations. The proposed algorithm is applied to the construction site layout problem. An objective function which is related to the total of personnel movement and the distance between facilities is adopted for reducing the transportation time. Next, the effects of parameter settings on the results are investigated. The remaining of the paper is organized as follows. The next section focuses on the ant colony optimization algorithms. In Section 3, application of the proposed algorithm to construction site layout is introduced. Next, benchmark case studies, numerical analysis and conclusions are presented.

2. Ant Colony Optimization Algorithms

In the application process of ACO to optimization problems, a pheromone value is associated with each edge (i, j). The pheromone value represents the attractiveness of a specific edge for the ants, according to the experience gained at runtime: the higher the amount of pheromone on an edge, the higher the probability that ants choose it when constructing solutions. Pheromone values are iteratively updated by two ways: pheromone evaporation and pheromone deposit. In addition to the pheromone trails, the ants’ solution construction process is also biased by a heuristic value, which represents the attractiveness of each edge (i, j). Besides, the relative influence of the pheromone (α) and heuristic values (β) contribute to the ants’ solution construction. The role of these parameters in biasing the ants’ search is intuitively similar. Higher values of α emphasize differences in the pheromone values, and β has the same effect on the heuristic values. The initial value of the pheromones, 0 ≤ α ≤ 1, has a significant influence in the convergence speed of the algorithm and the evaporation rate parameter, 0 ≤ ρ ≤ 1, is used to avoid unlimited accumulation of the pheromone trails, and, thus, allows the algorithm to forget previous bad choices. (1 − ρ) represents the evaporation. If ρ is low, the influence of the pheromone values will persist longer, while high values of ρ allow a fast forgetting of previously very attractive choices and, hence, allow a faster focus on new information that becomes included into the pheromone matrix. Another parameter is the number of ants in the colony. For a given maximum computation time, the number of ants is a critical parameter for determining the tradeoff between the number of iterations that can be done and how good the solution construction at each of the iterations is.

There is an ongoing interest on parameter tuning in the ACO literature. In general methods for parameter settings can be divided into three main approaches. Method of pre-scheduled variations of parameters propose to decrease or increase linearly over the run of the algorithm. In adaptative approaches, some parameters are modified according to some rules that changes the behavior of the algorithm. λ-branching factor [28] , entrophy-based measures for the pheromone, dispersion of solutions generated by the algorithm and the quality of the solutions generated [29] [30] can be listed among these rules. In search-based parameter adaptation methods, the algorithm tunes itself by incorporating the parameters into the search task. However, few of the studies analyze the effect of individual parameters, and thus, the decision of which parameters to adapt and how to adapt them continue to be mostly arbitrary. The proposed algorithm, Ant Colony Optimization with Parametric Analysis (ACO- PA) would be beneficial not only to decide parameter settings which may be worth varying during runtime, but also to understand how to perform variations.

3. Application of ACO-PA to Construction Site Layout Problem

3.1. Problem Definition

A construction site layout problem is the allocation of a number of predetermined facilities to a number of predetermined locations. A well-planned site layout is vital for any construction project, since space is one of the most important resources at a construction site. Furthermore, it has significant impact on construction cost and time, especially in the case of large projects in which traveling between facilities can be time consuming. Spatial problems may also occur during the setup of temporary facilities due to the limited amount of available space. This task is typically carried out by project managers or decision makers based on trial-and-error, experience, and intuition. However, as not all of the options are evaluated in these decision making processes, the outcome might be an improper layout, which can result in increased transportation time and costs. Possible alternatives for any construction site layout increases exponentially with the number of facilities.

The problem could be modeled as a quadratic assignment problem, in which equal numbers of facilities and locations exist. If the number of locations is more than that of facilities, dummy facilities should be added to make the numbers equal. In this study, it is assumed that there are equal numbers of facilities as well as locations, namely equal-area facility layout problem, and each of the predetermined location is available for accommodating the largest facility. The predetermined locations are represented as rectangles. The objective of construction site layout is to minimize the total traveling distance of personnel trips between facilities.

The total distance is defined as Equation (1) and Equation (2)

(1)

Subject to

(2)

where TD is the total traveling distance; n is the number of facilities; δ_xi is the permutation matrix variable (=1 if the facilities is assigned to site i); f_ij is the frequencies of trips made by construction personnel between facilities i and j; and d_ij is the distance between locations i and j. If the two locations are next to each other, then the distance is calculated as the distance between the centers of the two locations. If there is more than one path linking the two locations, then the shorter path is defined as the distance between two locations.

3.2. Solution Steps of the ACO-PA

Main aspects of the ACO-PA algorithm are heuristic information, solution construction, pheromone updating rule, local search and termination rule. Steps established for the proposed algorithm are as follows.

Step 1. Heuristic information: Heuristic information is defined in accordance with the problem characteristics, which enable the ACO-PA algorithm to be more applicable in solving any combinatorial problem.

The heuristic information (e) is given by Equation (3)

(3)

The heuristic desirability (η) is defined as Equation (4)

(4)

The vector d_j represents the sum of the distances from location j to all other locations, which mean that the lower the value of d_j is, the more the location is closer to the center. The vector f_i presents the sum of flows from facility i to all other facilities, where the higher the value of f_i shows the more important the facility is. This formulation reveals the importance of facilities with higher flows and locations having less distance potentials; as the total traveling distance cost is directly proportional to the distances and flows between facilities.

Step 2. Solution construction: At each construction step, an ant k places an unassigned facility i to an available location with a probability of

(5)

where τ_ij is the pheromone trail at iteration t. It should be noted that α and β are the parameters that determine the relative influence of the pheromone and heuristic information, respectively. is the set of locations that are still available in the neighborhood of node i. During the first solution construction, the initial pheromone value is generally defined as a “very little value” in the literature. This approach causes the pheromone value to be non-problem-specific. Moreover, the relative importance of the pheromone information value to the heuristic information value is being neglected. In the proposed algorithm, the initial pheromone value is defined according to the objective function value of the first solution which is generated by using only heuristic information. This approach enables the pheromone information value to be proportional to the heuristic information value and that any of the values would not dominate the solution construction.

The assignment sequence of the facilities is generally decided according to the flow rate in an ascending or vice versa orders. However, keeping the same assignment sequence, especially on small-dimensional problems, causes continual increase in pheromone information values and that the algorithm cannot generate different solutions. To avoid this early convergence to a specific solution, the ACO-PA uses the first assignment sequence of the facilities in a non-decreasing order of the flow f_i. After determining heuristic and pheromone information, facilities are randomly sorted to construct solutions.

Step 3. Pheromone updating: The pheromone trail update is applied after a complete solution is constructed. Pheromone trails of all couplings (i, j) are updated in accordance with Equation (6)

(6)

is the amount of pheromone added by ant k is given by Equation (7)

(7)

where is the kth ant solution and Q is a constant value. In general Q is considered as 1. In the proposed algorithm, ACO-PA, Q is taken as the value of pheromone trail evaporation rate ρ so that the proportion of pheromone and heuristic information values are maintained.

Step 4. Local search: Local search procedure is added to the algorithm to avoid finding a local optimum solution. Although there are several different local search strategies, one of them (2-opt) has been found as the most promising one, which was also selected for the developed algorithm. Local search starts from an initial solution and tries to improve the solution by local chances. If a layout with less objective function value could be found by swapping two distinct nodes in the current assignment, then the current solution is replaced by that assignment’ and the search continues until no better solution is found.

Step 5. Parameter analysis: In the proposed model, parameter values are defined within the prescheduled parameter variations. The algorithm also enables to set maximum and minimum limits for parameter values and steps. The algorithm changes one parameter value at a time and evaluates the solution according to the objective function. Therefore, the algorithm has the ability of generating more layout options and deciding the optimal solution among them.

Step 6. Termination rule: ACO algorithm can be terminated in several ways, such as, constructing solutions for a maximum number of iterations, running the algorithm for a stipulated time or until a stagnation situation is encountered in which all ants converge into the same solution. In the proposed model, the algorithm runs for a certain number of iteration to avoid stagnation in early stages. The flowchart of the proposed algorithm is illustrated in Figure 1.

4. Benchmark Case Studies

The proposed algorithm was coded in C++ and executed on IntelCore2 Duo processor at 2.66 GHz and 4 Gb of RAM. A comparison with previously proposed algorithms is conducted to demonstrate the effectiveness of the developed algorithm. Three case studies were selected from the literature [8] [31] [32] . These case studies were selected as they used the same construction site layout problem, and, thus, they can act as a good benchmark.

In case 1 (C1), it is assumed that each of the predetermined location is available for accommodating every facility [31] . The facilities to be located within the site boundaries are shown in Table 1.

The frequencies of trips (in one day) between facilities are as listed in Table 2. As seen from table, the frequency of the trips from one facility to another and the other way around are the same and that the matrix is symmetric. For example, the daily trips from site office to concrete batch workshop and vice versa are 9.

The distances of the available locations are as listed in Table 3. It should be noted that the site does not offer alternative roads from one location to another.

The construction site, where two permanent buildings are to be constructed, is shown in Figure 2 [31] .

In case 2 (C2), it is assumed that side gate and main gate are assigned to locations 1 and 10, respectively [8] . This case was defined to represent a real life solution approach in a construction site, which is usually determining the side and main gates before the construction starts as the location of gates are important for access and, thus, transportation. Therefore, these gates have to be positioned on predetermined locations.

In case 3 (C3), it is assumed that site office, labor residence concrete batch shop cannot be allocated to the relatively smaller locations 7 and 8 [32] . Case 3 was used to illustrate the constraint in which facilities that are relatively larger than other facilities cannot be accommodated to every possible location. Unequal area constraint has to be stated to ensure that no larger facilities are positioned to smaller locations.

5. Numerical Analysis

In the first solution construction, which is used to define the initial pheromone values, parameters were set to α = 0.1, β = 2 and ρ = 0.1 where α, β, and ρ are the parameters that show relative influence of pheromone trail, heuristic information, and pheromone trail evaporation rate, respectively. Number of ants was set to 10 and Q is taken as the value of pheromone trail evaporation rate ρ. The parameter settings were taken from the literature [33] [34] as recommended. Variations of parameters and their steps were defined as follows:

5.1. Comparison with the Best-Known Solutions

A comparison between the ACO-PA and the best-known results in the literature for the benchmark case studies are shown in Table 4 and Figure 3.

In C1, none of the facilities were assigned to the locations that were proposed by Gharaie et al. [31] . Reinforcement steel workshop, which has the maximum flow of 55 trips per day, was assigned to location 6, which has the minimum total distance (242 m). Side gate was located to the right side of the construction side. This allocation might enable material entrance an ease as it is on the road side. Besides offering reasonable location selections, ACO-PA was able to generate a layout where total travel distance was reduced by 3.2% compared to the literature.

In C2, it can be seen that the ACO-PA met all the constraints, which were to assign side gate and warehouse to locations 1 and 10, respectively. Apart from these two facilities, none of the facilities were assigned to the same locations that were proposed by Li et al. [8] . Reinforcement steel workshop, which has the maximum flow of 55 trips per day, was assigned to location 4, which has relatively less total distance to all available locations (259 m). Labor residence was assigned to location 8, and that moving around became easier for workers as location 8 was in the center of both buildings. With the generated site layout, total travel distance was reduced by 16.6% with ACO-PA compared to the literature.

In C3, side gate and warehouse had the priority to be assigned as their locations were predetermined in the problem. Next, site office, labor residence, and concrete batch workshop were assigned as they had area constraints. According to the generated site layout by ACO-PA, all the constraints were met and total travel distance was reduced by 16.8% compared to the literature.

With respect to computational processing time, the optimal solution was found in 1.15 seconds on Intel Core 2 Duo processor at 2.66 GHz and 4 Gb of RAM. A comparison of computational time cannot be provided due to the lack of related information in the studies taken from the literature.

With the case studies, the proposed model is applied to both equal-area and unequal area facility layout where feasible solutions are generated. In equal-area facility layout, each of the predetermined places is capable of accommodating any of the facilities as in C1. On the other hand, in unequal-area facility layout, like in C2 and C3, the number of predetermined places should be equal to or greater than facilities so that no larger facilities are assigned to smaller locations. Objective values of C2 and C3 are slightly higher than the results of C1. This indicates that the unequal-area constraints can affect the layout solution. It is observed that the ACO-PA performed better under constraints. As more constraints are defined, the better objective function values are found.

5.2. Comparison among Parameters

These parameter values show that the influence of heuristic and pheromone information do not dominate the solution construction regardless of introducing constraints to the problem. Parameter settings used in each case and the objective function values are as in Table 5, in which α, and β are the parameters that show relative influence of pheromone trail and heuristic information, respectively, and ρ is the pheromone trail evaporation rate.

As can be seen from Figure 4 and Table 5, parameter values differ from case to case. Although some of the best solutions were generated by using the same values for some parameters (i.e. relative influence of pheromone trail and heuristic information had zero value for both C2 and C3 cases), it is not possible to generalize the values even for the same optimization problem and that assigning constant values to parameters might cause low effectiveness in the optimization process. Therefore, it could be concluded that every problem has its own appropriate parameter value, and there is no similarity among the cases. On the other hand, the number of ants is robust at a value of 1.00 which indicates that the other parameters are dominant in finding the optimal solution and thus identifying the best settings for those parameters have priority than of identifying the number of ants.

In this study, the initial value of pheromones (τ₀) is defined as a function of the objective function value of the initial solution, where only heuristic information is used. Therefore, the value τ₀ is avoided to be too high or too low with this improvement. If the initial value of τ₀ is too low, then the search is quickly biased towards the first solutions of the ants and this leads to the exploration of inferior zones in the search space. However, if the initial pheromone values are too high, then many iterations are wasted in waiting until enough pheromone evaporation is done and, thus, the pheromone added by ants can start to bias the search [35] . In addition, the constant Q in the pheromone trail update rule is taken as the value of the evaporation rate in the ACO-PA, which enables the amount of pheromone evaporated and added to be proportional to each other.

Furthermore, 3-D surface map indicating the effect of α and ρ variations on cost function of C1 case is given in Figure 4. As can be derived from the surface map, deviation of the parameter result in fluctuations of the cost

function, and it is not possible to observe a tendency (or pattern). Even though this graph indicating the effects of two parameters on one case, other parameter (β) also exhibited the same influence, and conclusions were found to be same in all cases.

6. Conclusions

In this study, an improved ACO algorithm, ACO-PA, was proposed for the construction site layout problem and was applied to case studies with different constraints. The construction site layout problem is formulated as a quadratic assignment problem with an objective function of minimizing the total transportation distance, and, thus, total transportation cost. The proposed algorithm is applied to three case studies in which feasible solutions for both equal-area and unequal area facility layouts are generated.

The developed algorithm introduced several improvements, which enhances the solution construction process. Firstly, a new approach to define initial pheromone values was integrated to existing ACO frameworks. The first solution was constructed according to only the heuristic information and initial pheromone values were defined using the objective function value of this solution. This approach enabled the initial pheromone values to be proportional to the heuristic information values and that the solution construction was not dominated by the information which had higher values. The ratio between heuristic and pheromone information should prove to be useful to speed the convergence.

Secondly, the developed algorithm is capable of deciding the better parameter settings for α, β and ρ, where α, and β are the parameters that show relative influence of pheromone trail and heuristic information, respectively, and ρ is the pheromone trail evaporation rate. The maximum-minimum limits and steps are defined for each of the parameters. The algorithm changes one parameter value at a time and evaluates the solution according to the objective function. Therefore, the algorithm finds out the proper parameter settings automatically, which leads to the best solution. It should also be noted that the effect of model parameters, namely α, β, and ρ, is noteworthy and the surface map illustrating the effect of these parameters on the variation of the cost function showed us the difficulty of selecting manually.

There are several advantages of applying the ACO-PA algorithm to site layout problems. First, key facilities can be assigned to certain locations. In site layout planning, the project manager would assign facilities one by one to locations that are left over based on experience, trial-and-error, or intuition. In the ACO-PA algorithm, more layout choices can be considered and evaluated in a reasonable time. Secondly, the ACO-PA algorithm uses pheromone and heuristic information which make the algorithm more effective and controllable in the solution of real-life problems. The developed algorithm should enable construction managers and site engineers to plan and optimize the utilization of construction site space in order to minimize the total traveling distance. The developed ACO-PA algorithm has a number of possible extensions which are currently being pursued by the authors. These include developing hybrid systems based on ACO-PA, incorporating multi-objectives in the optimization and extending the research to the dynamic construction site layout planning problem. Future studies may also focus on expanding the application areas of the proposed algorithm to other construction tasks such as equipment routing planning and material storage layout on site.

Cite this paper

GulbenCalis,OrhanYuksel, (2015) An Improved Ant Colony Optimization Algorithm for Construction Site Layout Problems. Journal of Building Construction and Planning Research,03,221-232. doi: 10.4236/jbcpr.2015.34022

References

NOTES

^*Corresponding author.