Number 1 Volume 20 January 2014 Journal of Engineering

Construction Time-Cost Optimization Modeling Using Ant Colony

Optimization

Mohammed Nooruldeen Azeez (1), Angham Alsaffar (2)

[Link]@[Link], anghamalsaffar@[Link]
[Link]. Candidate Baghdad University/ Civil Eng. Dep. (1), Prof. Ph.D. Baghdad University/ Civil Eng. Dep. (2)

ABSTRACT
In the field of construction project management, time and cost are the most important factors to
be considered in planning every project, and their relationship is complex. The total cost for each
project is the sum of the direct and indirect cost. Direct cost commonly represents labor, materials,
equipment, etc.
Indirect cost generally represents overhead cost such as supervision, administration, consultants,
and interests. Direct cost grows at an increasing rate as the project time is reduced from its original
planned time. However, indirect cost continues for the life of the project and any reduction in
project time means a reduction in indirect cost. Therefore, there is a trade-off between the time and
cost for completing construction activities.
In this research, modeling of time-cost optimization, generating global optimum solution for time
and cost problem, and lowering construction time and cost using ant colony optimization algorithm.

KEYWORDS: Time-Cost Optimization, Time-Cost Trade-off, Ant Colony Optimization.

‫ﻣﻮﺩﻳﻞ ﺭﻳﺎﺿﻲ ﻷﻣﺜﻠﻴﺔ ﺍﻟﻮﻗﺖ ﻭﺍﻟﻜﻠﻔﺔ ﺍﻻﻧﺸﺎﺋﻴﺔ ﺑﺄﺳﺘﺨﺪﺍﻡ ﺍﻣﺜﻠﻴﺔ ﻣﺴﺘﻌﻤﺮﺓ ﺍﻟﻨﻤﻞ‬
‫ﺍﻟﺨﻼﺻﺔ‬
‫ ﻭﺍﻥ ﺍﻟﻌﻼﻗﺔ ﺑﻴﻦ‬.‫ ﻓﻲ ﺍﺧﺘﺼﺎﺹ ﺍﺩﺍﺭﺓ ﺍﻟﻤﺸﺎﺭﻳﻊ ﺍﻻﻧﺸﺎﺋﻴﺔ‬،‫ﺍﻥ ﺍﻟﻮﻗﺖ ﻭﺍﻟﻜﻠﻔﺔ ﻫﻲ ﺍﻫﻢ ﺍﻟﻌﻮﺍﻣﻞ ﺍﻟﻤﺄﺧﻮﺫﺓ ﻓﻲ ﺗﺨﻄﻴﻂ ﺍﻱ ﻣﺸﺮﻭﻉ‬
‫ ﻭﺗﻤﺜﻞ ﺍﻟﻜﻠﻒ ﺍﻟﻤﺒﺎﺷﺮﻩ ﻛﻠﻒ‬،‫ ﻓﺄﻥ ﺍﻟﻜﻠﻔﺔ ﺍﻟﻜﻠﻴﺔ ﻓﻲ ﺍﻱ ﻣﺸﺮﻭﻉ ﺗﻤﺜﻞ ﻣﺠﻤﻮﻉ ﺍﻟﻜﻠﻒ ﺍﻟﻤﺒﺎﺷﺮﺓ ﻭﻏﻴﺮ ﺍﻟﻤﺒﺎﺷﺮﻩ‬.‫ﺍﻟﻮﻗﺖ ﻭﺍﻟﻜﻠﻔﺔ ﻣﻌﻘﺪﺓ‬
‫ ﺍﻟﺦ‬، ‫ﺍﻟﻌﻤﺎﻟﺔ ﻭﺍﻟﻤﻮﺍﺩ ﻭﺍﻟﻤﻌﺪﺍﺕ‬
.‫ﺑﻴﻨﻤﺎ ﺍﻟﻜﻠﻒ ﻏﻴﺮ ﺍﻟﻤﺒﺎﺷﺮﻩ ﺗﻤﺜﻞ ﺑﺼﻮﺭﺓ ﻋﺎﻣﺔ ﻣﺼﺎﺭﻳﻒ ﺍﻻﺷﺮﺍﻑ ﻭ ﺍﻻﺩﺍﺭﻳﺎﺕ ﻭﺍﻻﺳﺘﺸﺎﺭﻳﺔ ﺍﺿﺎﻓﺔ ﺍﻟﻰ ﺍﻟﻔﻮﺍﺋﺪ‬
‫ ﺑﻴﻨﻤﺎ ﺍﻟﻜﻠﻒ ﻏﻴﺮ ﺍﻟﻤﺒﺎﺷﺮﻩ ﺗﺴﺘﻤﺮ ﻁﻴﻠﺔ ﻋﻤﺮ ﺍﻟﻤﺸﺮﻭﻉ‬، ‫ﺍﻟﻜﻠﻒ ﺍﻟﻤﺒﺎﺷﺮﺓ ﺗﺰﺩﺍﺩ ﺑﻨﺴﺒﺔ ﻛﻠﻤﺎ ﻁﺎﻝ ﻋﻤﺮ ﺍﻟﻤﺸﺮﻭﻉ ﻋﻦ ﻋﻤﺮﻩ ﺍﻟﻤﻘﺮﺭ‬
‫ ﻟﺬﺍ ﻓﺎﻥ ﻫﻨﺎﻟﻚ ﻣﻘﺎﻳﻀﺔ ﺑﻴﻦ ﺍﻟﻜﻠﻔﺔ ﻭﺍﻟﻮﻗﺖ ﻓﻲ‬، ‫ﻭﺍﻥ ﺍﻱ ﺗﻘﻠﻴﻞ ﻓﻲ ﻣﺪﺓ ﺍﻟﻤﺸﺮﻭﻉ ﻋﻦ ﺍﻟﻤﺪﺓ ﺍﻟﻤﺤﺪﺩﺓ ﺗﻌﻨﻲ ﺗﻘﻠﻴﻞ ﺍﻟﻜﻠﻒ ﻏﻴﺮ ﺍﻟﻤﺒﺎﺷﺮﻩ‬
.‫ﺍﻛﻤﺎﻝ ﺍﻟﻔﻌﺎﻟﻴﺎﺕ ﺍﻻﻧﺸﺎﺋﻴﺔ‬
‫ ﺗﻘﻠﻴﻞ ﺍﻟﻮﻗﺖ‬،‫ ﺗﻮﻟﻴﺪ ﺣﻠﻮﻝ ﻣﺜﻠﻰ ﻋﺎﻟﻤﻴﺔ ﻟﻠﻮﻗﺖ ﻭﺍﻟﻜﻠﻔﺔ‬.‫ﺍﻟﻜﻠﻔﺔ ﺍﻻﻧﺸﺎﺋﻴﺔ‬-‫ ﺳﻮﻑ ﻳﺘﻢ ﺍﻧﺸﺎء ﻣﻮﺩﻳﻞ ﻟﺤﺴﺎﺏ ﺍﻣﺜﻠﻴﺔ ﺍﻟﻮﻗﺖ‬، ‫ﻓﻲ ﻫﺬﺍ ﺍﻟﺒﺤﺚ‬
.‫ﻭﺍﻟﻜﻠﻔﺔ ﺑﺄﺳﺘﺨﺪﺍﻡ ﻁﺮﻳﻘﺔ ﻣﺴﺘﻌﻤﺮﺓ ﺍﻟﻨﻤﻞ‬

LITERATURE REVIEW into three types heuristic, mathematical and

Time–cost trade-off analysis is as an evolutionary based algorithms.
important aspect of any construction project Ant Colony Optimization (ACO) is introduced as
planning, and it is an interesting subject for both a new approach for deriving approximate
researchers and contractors, due to the academic / solutions for computationally sophisticated
real field nature of the problem. problems, using the Traveler Salesman Problem
Construction time-cost problems were tackled TSP as an example application (Dorigo et. al.,
repeatedly in the past decades using different 1991). Since that, ACO has been employed to
methods and modeling techniques are classified solve various problems, such as no-wait flow shop
scheduling routing problems, etc.
114
Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

In addition, ACO Algorithms was and is still Civil Engineering and other sciences, and the
widely used to solve various discrete problems outstanding performance of ACO algorithms
and still to date applied for solving complex provided the motive for applying ACO in TCO
optimization problems (Blum, 2005), ACO is also problems.
widely used in Civil Engineering and for different This research will use ACO searching behavior
applications for developing a Time-Cost Optimization Model .
Even though ACO algorithms were developed to
solve TSP problems, the extensive use of ACO in
Heuristic Models: sequence information, durations, and costs for
(Prager, 1963) showed that Time-Cost algorithm each component of the project by using linear
can be given a structural interpretation, using programming.
concepts that are familiar to civil engineers. (Patterson et. al., 1974) studied minimum
(Siemens, 1971) introduced an algorithm duration schedules for the resource constrained by
(Siemens Approximate Algorithm) for efficiently using bounding techniques in conjunction with
shortening the duration of a project when the zero-one programming to solve project scheduling
expected project duration exceeds a problems. The developed algorithms consist of
predetermined limit. The problem consists of examining the feasibility of a series of zero-one
determining which activities to expedite and by programming problems.
what amount. The objective is to minimize the (Robinson, 1975) presented a model that involves
cost of the project. a dynamic-programming approach to determine
(Goyal, 1975) modified Siemens algorithm for the allocation which minimizes the duration of the
shortening the duration of a project when the project (critical path). They presented a model
expected duration of the project exceeds a able to determine the optimum allocation for
predetermined limit. Goyal redefined "effective networks of activities with computational
cost slope", by selecting the activity with shortcuts for functions with special properties
minimum effective cost slope, and simultaneously used to increase the efficiency of their model.
de-shortening appropriate activities on adequately (Hendrickson, et. al, 1989) used linear
shortened paths while shortening the selected programming, and presented many solved
activity, examples for their method; however, the model
(Al-Samaraai, 2005) used the typical cost slope was suitable only for problems with linear time-
approach that managers take in making time-cost cost relationships.
trade-off and presented a crashing program. (Liu et al, 1995) provided a hybrid method to
Heuristic methods are widely used for their solve Time-Cost trade-off problems using
simplicity and general ability to produce good mathematical models. Their method takes
results, and they do not require a complicated advantage of linear programming for efficiency,
calculations however they are problem dependent. and integer programming to find the exact
Their results vary on different cases. In addition, solutions.
despite the good solutions they provide, they do (Chassiakos et. al., 2005) incorporated important
not guarantee optimality. Also most heuristic characteristics such as precedence relationships
methods assume only linear time-cost between activities, external time constraints,
relationships within activities. in addition, the activity planning constraints, and
solutions obtained by heuristic methods do not bonuses/penalties for early/delayed project
provide the range of possible solutions, making it completion projects, which provide more realistic
difficult to experiment with different scenarios for representation of actual construction in the
what-if analyses (Feng e. al., 1997), (Feng e. al., analysis and two solution methods (exact and
2000), and (Hegazy, 2002). approximate) are developed, The exact method
utilizes a linear/integer programming model to
Mathematical Models: provide the optimal project time-cost curve and
(Kelly, 1961) established a mathematical basis the minimum cost schedule considering all
For Crashing Cost in Critical-Path Scheduling activity time-cost alternatives together.
Method. The essential ingredient of the technique The main criticisms to mathematical
is a mathematical model that incorporates programming models is their complex

115
 Number 1 Volume 20 January 2014 Journal of Engineering

formulations, computational-intensive nature, and (Li e. al., 1997) also introduced a genetic
applicability to small-size problems (Feng et. al., algorithm model to solve time-cost trade-off
1997), and (Feng et. al., 2000). problems with less computation time of (Feng et.
Although the heuristic methods and mathematical al., 1997)
approaches have their specific strengths, their (Hegazy, 2002) also developed GA model to
weaknesses are also obvious especially as both solve time-cost trade-off problems and was able to
techniques may not always lead to optimal minimize the number of calculation used to find
solutions. The future seems to favor EOAs the solution. Also he was able to present a
(Zheng et. al., 2005), and (Ng. et. al, 2008). computer program to solve TCT problems for
Another major deficiency of those methods is both researchers and planners.
their inability to handle more than one objective. Despite its benefit, the time taken by a GA model
In addition, these methods are built upon the hill to generate a near-optimum solution can be
climbing algorithms, which has only one excessive. The main drawback of the GA-based
randomly generated solution exposed to some applications is that they require large
kind of variation to create a better solution. computational time for the search (Feng et. al.,
Therefore, it is questionable as to whether the 1997), and (Ng. et. al, 2008).
solution is a “Global” optimal one (Feng et. al., Another major drawback of GAs have to do with
1997), and (Feng et. al., 2000). genetic drift which is typified by the existence of
multiple peaks of equal height. When genetic drift
Evolutionary-Based Optimization occurs, it will converge to a single peak due to the
Algorithm (EOA) Models : stochastic errors during processing, and this is
In an attempt to reduce processing time and undesirable for any multi-objective TCO
improve the quality of solutions, particularly to problems (Feng e. al., 2000), and (Zheng et. al.,
avoid being trapped in local optima, EOAs have 2004).
been introduced during the past 10 years GAs have been used extensively in the last decade
(Elbeltagi et. al, 2005). to solve the TCT problem as mentioned above but
EOAs are stochastic search methods that mimic Except for GA, other EOA techniques were
the metaphor of natural biological evolution inspired by different natural processes including
and/or the social behavior of species. The the Ant Colony Optimization (ACO), Memetic
behavior of such species is guided by learning, Algorithms (MA), Particle Swarm Optimization
adaptation, and evolution (Hegazy, 2002), and (PSO), and Shuffled Frog Leaping Approach
(Ng. et. al, 2008). (SFL) etc. that were employed by (Elbeltagi et.
(Feng et. al., 1997) presented an algorithm based al, 2005) for solving discrete time–cost trade-off
on the principles of Genetic Algorithms (GAs) for problems.
construction time-cost trade-off, and a computer (Elbeltagi et. al, 2005) developed five TCT
program that can execute the algorithm models using all types of EOAs and provided
efficiently. The computer program used, TCGA, better optimal solutions. They also conduct
automates the execution of the new algorithm, and benchmark comparisons among the five
it provides a practical tool for practitioners to algorithms for discrete time-cost trade-off
apply the algorithm in practice. problem to check the algorithm efficiency, in
After that, (Feng et. al., 2000) developed their terms of processing time, convergence speed, and
previous work by utilizing GAs with simulation quality of the results. Based on this comparative
techniques to imitate the probabilistic nature of analysis, some guidelines for determining the best
project networks throughout the search of optimal operators for each algorithm were presented.
solutions. The approach provides more realistic Although TCT problem has been extensively
solutions for construction time-cost trade-off examined, all the researchers’ only focused on
problem under uncertainty. minimizing the total cost for an early completion.
They also demonstrated that GAs can be This does not necessarily convey any reward to
integrated with simulation techniques to provide the contractor. However, clients and contractors
an efficient and practical means of assessing are more concerned about the combined benefits
project time and cost risks. and opportunities of early completion as well as

116
Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

cost savings. This has led to the development of the segment of Pareto front within the limitation
the TCO concepts (Zheng et. al., 2005), and (Ng. of time and cost.
et. al, 2008). They revealed that the model provides managers
with greater flexibility to analyze their decisions
TIME-COST OPTIMIZATION: in a more realistic manner.
The time-cost optimization (TCO) problem is a Later on (Zheng et. al., 2005) applied a fuzzy sets
multi-objective problem, which attempts to strike theory to the original model to simulate
a balance between resource allocation costs and uncertainty and produces better results especially
project schedule duration. TCO also is one of the as the risk increases, though it is not without
greatest challenges in construction project weaknesses
planning, since the optimization of either time or Their model has significantly reduced the number
cost would usually be at the expense of the other of solutions generated for decision support, which
(Afshar, et. al, 2009),and (Kalhor et. al, 2011). is essential to multi-objective optimization, they
The goal of TCO is the same goal of any multi- proposed further refinements that are necessary to
objective optimization problems, which is to find improve its efficiency when applied to large and
the best compromise between multiple and complicated projects.
conflicting objectives. In multi objective (Kasaeian, et. al, 2007) introduced a TCO model
optimization, there is more than one solution using Gas and a novel technique called Non-
which optimizes simultaneously all the objectives dominated Archiving to find the optimal
and there is no distinct superiority between these solutions. Their model presented better solutions
solutions. Therefore, we face a set of non- when compared to (Zheng et. al., 2005) with
dominated solutions in these problems called relatively higher computations.
Pareto optimal. Among the feasible solutions, a (Xiong, et. al, 2008) presented a multi-objective
solution is identified as dominant if it is better TCO model using ACO as a searching tool,
than all other solutions in all of the considered optimal solutions were generated, and
objectives simultaneously. Among the feasible outperformed (Zheng et. al., 2004) GA model
solutions, those belonging to Pareto front are results.
known as non-dominated solutions, while the (Ng. et. al, 2008) also used ACO to find Time
remainder solutions are known as dominated. and cost optimality, the model was formulated
Since none of the Pareto set solutions is and implemented on a commercial planning
absolutely better than the other non-dominated software. When performance compared with
solutions, all of them are equally acceptable as (Zheng et. al., 2005) model on large scale
regards the satisfaction of all the objectives (Feng problems, results reveled better solutions for ACO
et. al., 2000), (Zheng et. al., 2005), and model.
(Kasaeian, et. al, 2007). (Afshar, et. al, 2009) Adopted (Kasaeian, et. al,
2007) Non-Dominated Archiving technique and
Time-Cost Optimization Models: developed TCO model using multi colony ant
There are only few researches on TCO subject algorithm. Results comparison with (Ng. et. al,
and they are summarized as follows: 2008) model favored Non-dominant model, but no
(Zheng et. al., 2004) used GA and Pareto front improvement in the solution from the original GA
approach; they developed a new algorithm for model, with the same calculation time.
optimizing construction time-cost decisions. Their Time-Cost Models can be summarized in Table 1
algorithm shows its efficiency by searching only a
small fraction of the total search space. Its MODELING TCO
accuracy was verified by only small problems. To solve the TCO problem, project network for
(Zheng et. al., 2004) compared their multi- TCO must be considered as a graphic network.
objectives modified adaptive weight approach Firstly the project is converted to an Activity-On-
model with the previous single-objective models Arrow (AOA) network as shown in Fig. (1). The
(Hegazy, 2002); The test results of the performance of ACO algorithms in TSP can be
deterministic scenario confirm that the new model seen as a reference for ACO-based TCO model.
can correctly locate the non-replaceable points on In this network, the events (1, 2, 3… etc.) could
be regarded as nodes and the different options for
117
 Number 1 Volume 20 January 2014 Journal of Engineering

each activity linking them would be the “distance” and cost into one single function and prioritize the
between these nodes. time and cost according to the solutions found by
Activity B in Fig. (1) could be taken as an the ant colony solution algorithm part,
example, there are three method options to accordingly to be used again in the algorithm for
complete this activity and they could be marked evaluating these solutions and finding the best ant
as B1, B2 and B3, and they are the different in any iteration of the model calculation.
“distance” from event ①to event ④. Therefore, This approach is effective and able to optimize
in ACO, the ants will travel from the first event time and cost concurrently and generate optimal
①to the event ⑦with proper options selected for solution (Zheng et. al., 2004),and (Kalhor et. al,
each activity. 2011).
Like the shortest tour being set as the objective in The weights can be calculated using (Zheng et.
TSP, the objectives for TCO would be the al., 2005) equations :
minimal time and lowest cost. On the other hand, • If Ztmax = Ztmin and Zcmax = Zcmin:
there are many differences between TSP and Where:
TCO, for example, ants should not come back to Ztmax, Zcmax : maximal value for the objective of
the starting points in TCO which is otherwise time and total cost in the current iteration.
necessary in TSP; despite the numerous Ztmin, Zcmin : minimal value for the objective of
differences, ACO could competently handle TCO time and total cost in the current iteration.
problems. Wt = Wc = 0.5 (eq.1)
Where:
MODEL DEVELOPMENT Wt, Wc: the adaptive weight for the objective of
To create an efficient optimization tool for Time time and total Cost.
and Cost and by considering the needs of the • If Ztmax = Ztmin and Zcmax ≠ Zcmin:
decision maker an evolutionary based model is Wt = 0.1, Wc = 0.9 (eq.2)
created and developed, taking into account the • If Ztmax ≠ Ztmin and Zcmax = Zcmin:
strength and weaknesses of previous methods Wt = 0.9, Wc = 0.1 (eq.3)
stated in the literature review for making this • if Ztmax ≠ Ztmin and Zcmax ≠ Zcmin:
proposed model.
The developed model will transform time and cost , (eq.4)
from single option in an activity to optimum V= Vt + Vc (eq.5)
solutions that a construction project could be , (eq.6)
executed.
The model development process is divided into Where:
five important parts Vt, Vc, V represent Time, Cost, and project Value
(i) Fitness function. respectively.
(ii) Time and cost functions This approach will generate optimal solution and
(iii) Ant Colony Solution Algorithm ACSA will optimize both time and cost simultaneously.
(iv) Pareto Front The F.F. for any ant (k) in any given iteration will
be:
• Fitness Function
Fitness Function (F.F.) represents planners and
decision maker’s goal or what their needs are. To (eq.7) (Zheng et. al., 2005)
address a multi-objective optimization problem Where:
such as time, cost and to properly evaluate the Zt (k) and Zc (k) is the time and cost function for
solutions generated by the ACO, the fitness ant (k) in the current iteration.
function consider both objectives and must be R is a positive random number between 0 and 1.
calculated during the ant colony solution This approach imparts the ACO with greater
algorithm part. freedom to search in the multi-objective space that
overcomes the drawbacks of single objective and
The FF. used is called Modified Adaptive Weight hill-climbing algorithms.
Approach (MAWA) which integrates both time
118
 Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

These weights will guide the algorithms to search balance between exploration of other solutions
through a wider range against the objectives that and exploitation of existing ones.
have a relatively small exploration space in The Algorithm used in this model is ACS, due to
previous generation. its robustness in finding the shortest path and its
low deviation from the optimal solution.
• Time and cost Functions The ant colony solution algorithm is based upon
To calculate Zt (k) & Zc (k) and prepare the (Dorigo et. al. 2004) ACS algorithm modified
necessary data to find the Non-dominant solution and developed to deal with construction projects
using Pareto front, two objectives were used for networks ant to solve TCO
time and the total cost designed for this purpose The ant colony solution algorithm contains four
Time objective function main steps :
1- Initiating ACS parameters
2- Creating the solutions
3- Path retracing and pheromone updating,
Figure (2) shows how and where the model
(Researcher) development steps proceeds and interacts with
Where: each other
: Execution time of option j in the activity i
1- Initialization of ACSA parameters
selected by ant k.
Depending on (Dorigo et. al., 2004) and after
: Index used to verify which option the ant conducting Parameter Sensitivity Analysis the
selected to execute, if ant k selects option No. 4 necessary parameters are set to start ACSA:
then , if not . m: is the number of ants in each iteration
t: no. of iterations in the model (optional)
Pp: Activity Sequence of certain path. L: no. of activities the user input
P: All the Paths in the network. n: no. of options in each activity the user input
Cost Objective Function α: Coefficient represent the importance of the
pheromone value (τ)
β: Coefficient represent the importance of the
heuristic value (η)
(Researcher) τ0: initial pheromone value
Where: ρ: global pheromone evaporation rate (0<ρ<1)
: Execution direct cost of option j in the ɛ: local pheromone evaporation rate(0< ɛ <1)
activity i selected by ant k. q0: factor of the pseudorandom proportional
IC: project indirect cost rate. action choice rule (0< q0<1)
L: number of project total activities. Table (4.1) represents the parameters set by the
researcher as the optimum parameter between
• Ant Colony Solution Algorithm exploration and exploitation; other parameters are
This process is the key to find the optimal variables and depend upon time-cost data that the
solutions and the beating heart (core) of the user inputs (user oriented).
developed model that the decision makers need. It
transforms the time and cost from being a single 2- Creating the Solution
option in one activity to an optimal solution The strategy of the algorithm is to exploit
consisted of set of best options to execute the information gathered from pervious iteration
project with, throughout a sequence of intelligent (pheromone trails) (τij) and heuristic information
and efficient steps to select the best option (ηij) calculated from input variables (option
combinations and constantly update the resulted constructional properties) to construct candidate
best solution found yet. solutions and fold the information learned from
The closed cycle of searching, communicating, constructing solutions again.
evaluating, and learning is the reason of solution This step of the modeling starts by randomly
continuous improvement. it is in a sensible generating solution using the first iteration
(colony) to explore the environment and starts

119
 Number 1 Volume 20 January 2014 Journal of Engineering

learning what a good solution is. By evaluating Fig. (4) depicts the variables in one single option
the outcome of this iteration using MAWA to find (J) to execute an activity in a project, the figure
the best solution, and then direct the next iteration also shows the variables that are subjected to
(colony) towards the best solution found so far. change during model calculations from those
Fig. (2) shows that projects will have L activities which will not change. The construction variables
where each activity has nL possibilities (time and cost entered by user for this option)
(construction options). To execute the selected generates the ACSA (heuristic value and the
activity, the model will have t number of pheromone value will be generated by the
iterations (colonies). In any colony there are m algorithm according to equations 11,
ants which will travel through the network to 13,and15)respectively.
generate optimum solutions, This is the model Random proportional rule:
complexity where Ant Colony Solution Algorithm
can manage it efficiently yet it is easy for any user
to use.
The bold line in fig. (3) represent the path taken
by ant (K) selections and when the ant reaches the
Ant selects an option by generating a random No.
finishing point it will have a discrete time-cost
(q) uniformly distributed between [0,1] where it
solution. ACSA choices will be compared with
is compared to q0 (0≤q0≤1).
other ants that crossed different paths to finish the
If q≤q0, the ant selects the option with the higher
project (each ant represents a candidate solution).
value of both pheromone and heuristic value
it can be seen that the ant does not travel from an
(using eq. 4.10); otherwise, the ant selects option
activity to the next activity according to the
from probability distribution created using (eq.
network dependency no matter what they are
12)
(finish to start, start to start, start to finish, finish
to finish). Ants travel in a numerical order, the 3- Path Retracing and Pheromone Updating
model manage the ant solutions and transform the This step contains two of the most important
ant selected option to a candidate solution with concepts in ACO (learning and communicating),
respect to the activity relationships that the project which will contribute in improving the solution
is subjected to. and exploring the solution environment, either by
Ants select an option from n options by increasing the confidence in an option to become
performing pseudorandom proportional rule , the most desirable choice or decrease it. This
when the ant travel throughout the project option will be the less desirable and almost
network it will perform the same rule for every neglected, without this step the solution will not
activity until all the activities have been passed. change or improve.
Pseudorandom proportional rule: The updating and evaporating occur only for the
options selected by at least an ant, otherwise no
changes will occur.
Pheromone Updating is divided in two types:
(eq.10)
Where:
1- Local pheromone update: It retraces the
q: random variable between [0,1]
ant k path and updates the pheromone value of the
q0 : tunable parameter.
ant selection by applying equation (13). The
J: variable generated using random
importance of the local updating lies in using
proportional rule (eq.12).
local evaporation rate to minimize the pheromone
: pheromone value of activity i option j .
value of this option. To make this option less
: heuristic value of activity i option j and desirable for the ants in the same iteration, so they
calculated according to this equation : will not follow this ant directly to avoid premature
(eq.11) convergence of the solution.
Therefore, achieving the maximum exploration
possible in each iteration to and seek other
options.
120
 Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

optimum to give the decision maker only the

Where: optimum solutions to be used. A solution pool
ɛ: local evaporation rate (factor used to minimize created to contain the outcome of the Ant colony
the pheromone value of the selected option) solution algorithm, as shown in Fig.(5).
τ0: initial pheromone value of activity i and In each iteration ten solutions will be generated (if
calculated by applying this equation: the recommended parameter setting used) and
these solutions will be added to the solution pool
and then by applying Pareto front only the
optimum solution will be selected.
For the next iteration there will be ten more
The activity option which have min. (time * cost) options, If any new solution (x*) is better than
will be selected to calculate the initial pheromone that exists Pareto Front solution(x) with at least
value because it has a rough estimation of the one objective, then the solution will be compared
good solution. according to the performance of the other
τij :pheromone trail of activity i option j in the objective; otherwise, the new solution will be sent
previous iteration. to the solution pool so as to reduce the
τij(t): pheromone value of activity i option j in this unnecessary calculations.
iteration (t). But when a new solution is better than an existing
PF selected solution for both objectives (time and
2- Global pheromone update: When all the cost) the inferior solution will be sent back to the
ants of the colony (in single iteration) travel the solution pool. When the model stops, there will be
network and generate discrete solutions, the only dominant optimal solutions left in the PF
algorithm points the ants of the next colony Pareto Front constraints are:
(iteration) to the path that achieved the best If (x*) cost ≥ (x) cost and (x*) time ≤ (x) time 
outcome so far by updating only the path of this add x* to Pareto front
ant, the so called iteration best solution or the
iteration best ant which got the lowest value in the If (x*) cost ≤ (x) cost and (x*) time ≥ (x) time
F.F. add x* to Pareto front
The global pheromone updating is done according If (x*) cost ≥ (x) cost and (x*) time ≥ (x) time
to the following equation:
add x* to solution pool
Where: If (x*) cost ≤ (x) cost and (x*) time ≤ (x) time
ρ: global evaporation rate
Δτ: pheromone updating value for the option add x* to Pareto front
selected by the best ant in this activity and this add x to solution pool
iteration, calculated according to the following
equation: MODEL EVALUATION
Model outcome tested and compared with
credible and reliable references to confirm and
[Link] value: result of the best ant Fitness function validate the performance with other models.
calculation. This problem first will be applied to test the
This step is repeated for each activity until performance of the developed model, including
finishing the best ant traveling throughout its seven activities problem presented by (Feng, et.
project path. When the next iteration starts the al., 1997), Table (3) represents the construction
pheromone value in this option combination will values of the problem, containing time and cost
be relatively higher and will lead to more ants for each alternative option in every activity, and
selecting these options. Fig. (6) represent the network of this problem, and
the indirect cost was 1500$/day.
The activities contains 3 to 5 possible options
• Optimal Non-Dominant Solution(s) Using
(alternative), so the problem complexity will be
Pareto Front [(3^5) * 4 * 5] = 4860 possible solutions.
In this step of the model development, the Although the project activities are only 7 but the
solution will be classified into optimum and not
121
 Number 1 Volume 20 January 2014 Journal of Engineering

problem complexity is considered as medium for using only 10 ants in 20 iterations while Xiong
civil engineering problems. ACO model used 40 ants and 40 iterations to
The project critical path calculated first to find the achieve the same solution, and Zheng used 5 as a
normal duration and for that the options selected population size in each of the 5 generations
were the normal time/normal cost, and the project (iterations).
time was 105 days, and 253700 $. The developed model efficiency showed by
And after using TCO model the highest value of searching only 4% of the possible solution
time was 68 days, and the cost was 220500$. [200/4860] and generated the global optimal
From the total cost 0.15%, and 54.4% of the solutions.
project time were saved by using optimized
values. This is achieved by using the saved the CONCLUTIONS
indirect cost to use more advanced equipment and Ant Colony Optimization was able to generate
increase the number of the crews or labors in the optimal solutions in a fast and accurate way.
construction work, or a different construction The developed model was able to generate global
method may be used. optimum solutions with less iterations and faster
As we can see from Table (4), the maximum time compared to well-known time-cost
possible total cost reached was 233500$ and it optimization models.
remains below both time and cost of the normal Time and cost was optimized without dominating
duration. to only one function.
The comparison of the developed model solutions Time was saved by 54.4% while cost was 15%
with two TCO models presented by (Zheng, saved using the developed model.
2004) using GA and (Xiong, 2008) using AS Time-Cost Optimization Have A Great Effect On
algorithm, is shown in Table (5). Lowering The Construction Time And Cost Of
Construction Project In And Overcome The
By comparing the solutions of this problem with Delays And Cost Excess That Could Occurs
other reference solutions, the developed model During The Execution Of Any Construction
shows the ability to generate global optimal Project
solutions with an incredibly small time of 1 sec.

122
Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

REFERENCES:

Afshar, A.; Ziaraty, A.; Keveh, A.; and

Sharifi, F. , (2009) ” Non-dominated Goyal S. K. (1975), " A Note on A Simple
Archiving Multi-colony Ant Algorithm in CPM Time-Cost Tradeoff Algorithm”
Time–Cost Trade-Off Optimization “Journal Management Science, Feb., Vol. 21, No. 6,
of Construction Engineering and Application Series jstor.
Management, Vol. 135, No. 7, July 1, pages
668-674 ASCE,. Hegazy, T. (2002). “Computer-based
Construction Project Management” Upper
Al-Samaraai, H. Fulla (2005) “Developing Saddle River, NJ, Prentice Hall.
Computer Program To Implement Time-Cost
Relationship For Planning Construction Hendrickson C. and Au T. (1989), “Project
Projects In Iraq” [Link]. thesis submitted to the Management for Construction Fundamental
Civil Engineering Department, Al-Mustansria Concepts for Owners, Engineers, Architects
University. and Builders” first edition Prentice Hall.

Chassiakos A. P. and Sakellaropoulos S. P. Kalhor E., Khanzadi M., Eshtehardian E.,

(2005) “Time-Cost Optimization of Afshar A. (2011), “Stochastic time–cost
Construction Projects with Generalized optimization using non-dominated archiving
Activity Constraints” Journal of Construction ant colony approach”, Automation in
Engineering and Management, Vol. 131, No. Construction. Elsevier.
10, October 1, 1115–1124 ASCE.
Kasaeian, A.; Shoghli, O., and Afshar, A,
Dorigo M. and T. Stützle (2004). “Ant Colony (2007), “Non-dominated Archiving Genetic
Optimization”. London, England, The MIT Algorithm for Multi-objective Optimization
Press. of Time-Cost Trade-off” Proceedings of the
8th WSEAS International Conference on
Dorigo M. and V. Maniezzo (1991). “Positive Evolutionary Computing, Vancouver, British
feedback as a search strategy”. Dipartimento Columbia, Canada, June 19-21Pages 241-246.
Di Elettronica - Politecnico Di Milano, pages
91-116. Kelley J. E. (1961), “Critical-Path Planning
and Scheduling: Mathematical Basis”
Elbeltagi, E.; Hegazy, T. and Grierson, D. Operations Research, May - Jun., Vol. 9, No.3
(2005), “Comparison among Five jstor
Evolutionary-Based Optimization Algorithms
” Advanced Engineering Informatics, 19 , Li H., and Love P. (1997) “Using Improved
pages 43–53, Elsevier Ltd. Genetic Algorithms to Facilitate Time-Cost
Optimization” Journal of Construction
Feng C.-W. Liu L., and Burns S. A. (1997), Engineering and Management, Vol. 123
“Using Genetic Algorithms To Solve September, No.3. , 0233-0237, ASCE.
Construction Time-Cost Trade-Off
Problems”, Journal of Computing in Civil Liu L, Burns S. A. and Feng C.-W. (1995)
Engineering, Vol. 11, No.3, July, Pages 184- “Construction Time-Cost Trade-Off Analysis
189, ASCE. Using Lp/Ip Hybrid Method” Journal of
Construction Engineering and Management,
Feng C.-W. Liu L., and Burns S. A. (2000) Vol. 121, No.4, 0446-0454 December,.
“Stochastic Construction Time-Cost Trade- ASCE,
Off Analysis” Journal Of Computing In Civil
Engineering. - April 2000. - pp. 117-126 Ng. Thomas S., and Zhang Y., (2008)
ASCE. “Optimizing Construction Time and Cost
123
 Number 1 Volume 20 January 2014 Journal of Engineering

Using Ant Optimization” Journal of No. 6, Application Series Feb., pp. B354-
Construction Engineering and Management, B363 jstor.
Vol. 134, No. 9, September 1, pages 721–728,
ASCE. Xiong, Y.; and Kuang, Y. (2008), “Applying
an Ant Colony Optimization Algorithm-Based
Patterson J. H and Huber W. D. (1974) “A Multi-objective Approach for Time–Cost
Horizon-Varying, Zero-One Approach to Trade-Off”, Journal of Construction
Project Scheduling”. Management Science, Engineering and Management, Vol. 134, No.
Vol. 20, No. 6, Application Series, Feb., pp. 2, February 1, Pages 153-156, ASCE.
990-998 jstor.
Zheng, D.; Ng, T.; and Kumaraswamy. M.
Prager W. (1963) “A Structural Method of (2004),” Applying a Genetic Algorithm-
Computing Project Cost Polygons” Based Multi-objective Approach for Time-
Management Science, Vol. 9, No. 3 (Apr., Cost Optimization” Journal of Construction
1963), pp. 394-404 jstor. Engineering and Management, Vol. 130, No.
2, April 1, pages 168-176, ASCE.
Robinson D. R. (1975), “A Dynamic
Programming Solution to Cost-Time Tradeoff Zheng, D.; Ng, T.; and Kumaraswamy. M.
for CPM” Management Science, Oct., Vol. (2005),” Applying Pareto Ranking and Niche
22, No. 2 pp. 158-166Published Formation to Genetic Algorithm-Based Multi-
objective Time–Cost Optimization” Journal of
Siemens N. (1971) “A Simple CPM Time- Construction Engineering and Management,
Cost Tradeoff” Management Science, Vol. 17, Vol. 131, No. 1, January 1, pages 81–91,
ASCE.

124
Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

LIST OF ABBREVIATIONS
ACO: Ant Colony Optimization
ACS: Ant Colony System
ACSA: Ant Colony Solution Algorithm
AOA: Activity on Arrow
DC: Direct Cost
FF: Fitness Function
GA: Genetic Algorithm
IC: indirect cost rate.
MA: Memetic algorithms
MAWA: Modified Adaptive Weight Approach
PF: Pareto Front
PSO: Particle Swarm optimization
SFL: Shuffled Frog Leaping
TCO: Time-Cost Optimization
TCT: Time-Cost Trade-off

Execution of direct cost of option j in activity i selected by ant (k)

J: Variable generated using random proportional rule
K: Random ant
L: Total number of project activities
m: The number of ants in each iteration
n: No. of options in each activity the user input
P: All the Paths in the network
Pp: Activity Sequence of certain path
q: Random variable between [0< q <1]
q0: Factor of the pseudorandom proportional action choice rule [0<q0<1]
R: Positive random number between [0< R <1]
S: Total number iterations
T: No. of iterations in the model (optional)
Execution time of option j in activity i selected by ant (k)
Vt, Vc, V: Value of Time, Cost, and Project, respectively
Wt, Wc: Adaptive weight for the objective of time and total cost
Index used to verify which option the ant selected to execute
Zc (k): Objective function of cost for ant (k) in the current iteration
Zt (k): Objective function of time for ant (k) in the current iteration
Ztmax,
Maximal value for objective of time and total cost in current iteration
Zcmax:
Ztmin,
Minimal value for objective of time and total cost in current iteration
Zcmin
α: Coefficient represents the importance of the pheromone value (τ)
β: Coefficient represents the importance of the heuristic value (η)
Δτ: Best ant pheromone updating value
ɛ: Local pheromone evaporation rate [0< ɛ <1]
: Heuristic value of activity i option j
ρ: Global pheromone evaporation rate [0<ρ<1]
125
 Number 1 Volume 20 January 2014 Journal of Engineering

τ0: Initial pheromone value

: Pheromone value of activity i option j

TSP: Traveler salesman problem

FIGURES

D
2 5
A
F I
B1
B2 H
1 4 7
B3
G J
C
E
3 6

Fig. (1): TCO Project (AOA Network).

Fig (2): Developed Model Flowchart.

126
Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

Start

Activity 1 (option no.)

1(1) 1(2) 1(3) 1(4) 1(j) 1(n1)

Activity 2 (option no.)

2(1) 2(2) 2(3) 2(4) 2(j) 2(n2)

Activity 3 (option no.)

3(1) 3(2) 3(3) 3(4) 3(j) 3(n3)

Activity 4 (option no.)

4(1) 4(2) 4(3) 4(4) 4(j) 4(n4)

Activity 5 (option no.)

5(1) 5(2) 5(3) 5(4) 5(j) 5(n5)

Activity i (option no.) i(ni)

i(1) i(2) i(3) i(4) i(j)

Activity L (option no.)

L(1) L(2) L(3) L(4) L(j) L(nL)

Finish

Fig. (3): Graphical Representation of Ants’ traveling through construction projects Activities
(Researcher).

127
 Number 1 Volume 20 January 2014 Journal of Engineering

Option j
Time Cost

Heuristic Value

Pheromone

Value

Don’t need updating

Always need updating

Fig. (4): Option j Variables (Researcher).

Time Pareto Front

solution Inferior (not optimal)
solution

Solution
Pool

Cost

Fig.(5): Pareto front and solution pool.

128
 Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

Activity 2

Activity 5

Activity 1 Activity 3 Activity 7

Activity 6

Activity 4

Fig. (6): Network representation of the 7 activity reference problem.

Table (1) Time-Cost Models (Researcher)

Time-Cost Trade-off Time-Cost Optimization
Evolutionary-Based Evolutionary-Based
Heuristic Models Mathematical Models Optimization Optimization Algorithm
Algorithm Models Models
Linear Programming Genetic Algorithms Genetic Algorithms
Structural (Kelly, 1961) (Feng et. al. 1997) (Zheng et. al. 2004)
Interpretation
(Prager, 1963) Zero-One Programming Genetic Algorithms Genetic Algorithms
(Patterson, 1974) (Feng et. al. 2000) (Zheng et. al. 2005)

Cost Slope Dynamic Programming Genetic Algorithms Genetic Algorithms

(Siemens, 1971) (Robinson, 1975) (Li et. al. 1997) (Kasaeian et. al. 2005)

Effective Cost Slope Linear Programming Genetic Algorithms, Ant Colony Optimization
(Goyal, 1975) (Handrickson, 1989) Particle Swarm, (Xiong, et. al. 2008)
Ant Colony,
Linear/Integer Shuffled Frog Leaping Ant Colony Optimization
Cost Slope Programming and Mimetic (Ng, et. al. 2008)
(Al-Samaraai, (Lui, et. al. 1995) Algorithms
2005) (Elbaltagi, et. al 2005)

Linear Programming Ant Colony Optimization

(Chassiakos et. al. 2005) (Afshar, et. al. 2008)

129
 Number 1 Volume 20 January 2014 Journal of Engineering

Table (2): Model recommended parameters (Researcher)

Parameter Value Parameter Value

m 10 ρ 0.002
α 1 ɛ 0.1
β 2 q0 0.4

Table (3): Reference Problem (7 Activity) (Feng, et. al., 1997)

Option No.1 Option No.2 Option No.3 Option No.4 Option No.5
Preced
Activity Tim
ence Time Time Time Time
(Days
Cost (Days
Cost (Days
Cost (Days
Cost e Cost
) ($) ) ($) ) ($) ) ($) (Days ($)
)

1-Site Preparation - 14 23,000 20 18,000 24 12,000 - - - -

2-Forms and rebar 1 15 3,000 18 2,400 20 1,800 23 1,500 25 1,000

3-Excavation 1 15 4,500 22 4,000 33 3,200 - - - -

4-Precast concrete
1 12 45,000 16 35,000 20 30,000 - - - -
girder

5-Pour foundation
2.3 22 20,000 24 17,500 28 15,000 30 10,000 - -
and piers

6-Deliver PC
4 14 40,000 18 32,000 24 18,000 - - - -
concrete

7-Erect girders 5.6 9 30,000 15 24,000 18 22,000 - - - -

130
Mohammed Nooruldeen Azeez Construction Time-Cost Optimization Modeling
Angham Alsaffar Using Ant Colony Optimization

Table (4): Option selection and solution generated for the 7 activity reference problem
(indirect cost is 1500$/day)
Project Project Options selected by the model to execute the
Solution Time Total Cost corresponding activity
(Days) ($) 1 2 3 4 5 6 7
1 60 233500 1 1 1 1 1 3 1
2 62 233000 1 1 1 3 2 2 1
3 63 225500 1 1 1 2 2 3 1
4 67 224000 1 1 1 3 3 3 1
5 68 220500 1 1 1 3 4 3 1

Table (5): Solution comparison of (7activity) reference problem

Zheng Model 2004 Xiong Model Developed Model

Time Total cost Time Total cost Time Total cost
(Days) ($) (Days) ($) (Days) ($)
66 236500 60 233500 60 233500
73 251500 62 233000 62 233000
84 251000 63 225500 63 225500
- - 67 224000 67 224000
- - 68 220500 68 220500

131