Keywords: ant colony optimization, critical path, construction scheduling.

Activity scheduling and critical path calculations are of fundamental importance to construction engineering and management since they form one of the most important pillars on which time, resource and cost control are based. Currently, the most widely used method for analyzing construction project networks and solving for longest (critical) paths in such networks is the Critical Path Method (CPM), a deterministic approach that relies on forward and backward pass calculations that exhaustively traverse the network adding activity durations to arrive at the total network duration and thus the longest path in a network. The longest path calculations and relevant time and resource optimizations are typically performed by linear programming and optimization algorithms, subject to imposed constraints (time, resource and logic constraints). Some of the existing limitations of currently available CPM-based tools are (a) the inability to calculate longest (or shortest) paths from a given node (activity) to any other node in the project network, (b) the inability to account for resource-driven activity relationships ("AND"/"OR" combinations of resources), and (c) the computational inefficiency of the critical path method.

The paper presents a methodology to arrive at critical path calculations in construction networks using Ant Colony Optimization (ACO) algorithms. ACO is a population-based, artificial multi-agent, general-search technique, proposed by Dorigo [1,2,3], for the solution of difficult combinatorial problems. The method's theoretical roots are based on the behaviour of real ant colonies and the collective trail-laying and trail-following of its members in searching for optimal solutions in traversing multiple paths, a behaviour characterized by "the combination of a priori information about the structure of a promising solution with a posteriori information about the structure of a previously obtained good solution" (Maniezzo et al. [5]). In essence, ACO is inspired by the foraging behaviour of natural ant colonies which optimize their path from an origin (ant nest) to a destination (food source) by taking advantage of knowledge acquired by ants that previously traversed the possible paths and the pheromone trail these ants leave behind as the traverse the paths to optimal solution. The common framework for ACO applications was proposed posteriori to be the ACO metaheuristic [4], with artificial ants seen as stochastic solution procedures and acting as agents. The generic problem topology and solution procedure were also described posteriori [6].

The paper outlines the fundamental mathematical background of the ACO method and a suggested possible implementation strategy for solving for longest (critical) paths in construction schedule networks. The ACO virtual multi-agent approach is supplemented by a database management system and a custom software interface that allows for the merging of this artificial intelligence technique with more traditional critical path calculation (CPM) techniques. The methodology is examined by means of several random topologies and the results compared to the ones obtained by traditional CPM calculations, concluding that the ACO metaheuristic provides users with an alternative way of constructing longest-path solutions in acyclic (unidirectional) network topologies. Despite the seemingly iterative approach of the ACO method, the method utilizes intelligent selection procedures to perform the optimization and arrive at the longest paths in a prescribed network topology.

Even though this paper presents longest-path calculations in construction networks and identification of longest path activities and project total duration, the applied ACO methodology can be modified and extended to account for resource and cash flows, and node-to-node longest path calculations. The former can be achieved by considering the respective activity assignments and including them in the cost function of each arc, used in the optimization process. The latter can be achieved by setting the start node of the node-to-node sequence of interest as "ant nest" and the end node as "food source" and reconstructing the solution path (longest path) while all other nodes are set as plain network nodes. Ongoing work on the subject matter addresses the inclusion of resource-based scheduling techniques to account for AND/OR resource-combination requirements at the network nodes, and ways to generate total-float values for each activity (the current ACO method does not generate these values).

1

Dorigo, M. (1991). "Ant Colony Optimization, New Optimization Techniques in Engineering", by Onwubolu, G.C., and B.V. Babu, Springer-Verlag Berlin Heidelberg, 101-117.

2

Dorigo M. (1992). "Optimization, Learning and Natural Algorithms". Ph.D.Thesis, Politecnico di Milano, Italy.

3

Dorigo, M., Maniezzo, V., and Colorni, A. (1996). "The Ant System: Optimization by a Colony of Cooperating Agents". IEEE Transactions on Systems, Man, and Cybernetics Part B, vol.26(2), pp. 29-41. doi:10.1109/3477.484436

4

Dorigo, M., Di Caro, G. and Gambardella, L.M. (1999). "Ant Algorithms for Discrete Optimization". Artificial Life, vol.5(2), pp. 137-172. doi:10.1162/106454699568728

5

Maniezzo V, Gambardella L.M., De Luigi F. (2004). "Ant Colony Optimization, New Optimization Techniques in Engineering", by Onwubolu, G.C., and B.V. Babu, Springer-Verlag Berlin Heidelberg, 101-117.

6

Stützle, T. and Dorigo, M. (2002). "The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances". In F. Glover and G. Kochenberger (editors), Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £135 +P&P)