Utility of Genetic Algorithms for Solving Large-Scale Construction Time-Cost Trade-Off Problems

Abstract

The time-cost trade-off (TCT) problem has long been a popular optimization question for construction engineering and management researchers. The problem manifests itself as the optimization of total costs of construction projects that consist of indirect project costs and individual activity costs. The trade-off occurs as project duration and, as a result, indirect project costs decrease with reduced individual activity duration. This reduction in individual activity duration is achieved by increasing resource allocation to individual activities, which increases their costs to completion. Historically, metaheuristic solutions have been applied to small-scale problems due to computational complexities and requirements of larger networks. Findings in this article demonstrate that the metaheuristic approach is highly effective for solving large-scale construction TCT problems. A custom genetic algorithm (GA) is developed and used to solve large benchmark networks of up to 630 variables with high levels of accuracy (<3% deviation) consistently using computational power of a personal computer in less than 10 min. The same method can also be used to solve larger networks of up to 6,300 variables with reasonable accuracy (∼7% deviation) at the expense of longer processing times. A number of simple, yet effective, techniques that improve GA performance for TCT problems are demonstrated, the most effective of which is a novel problem encoding, based on weighted graphs, that enables the critical path problem to be partially solved for all candidate solutions a priori, thus significantly increasing fitness evaluation. Other improvements include parallel fitness evaluations, optimal algorithm parameters, and the addition of a stagnation criteria. This article also presents some guidelines of optimal algorithm parameter selection through a comprehensive parameter sweep and a computational demand profile analysis. Moreover, the methods proposed in this article are based on open source development projects that enable scalable solutions without significant development efforts. This information will be beneficial for other researchers in improving computational efficiency of their solution in addressing TCT problems.