An Improved Ant Colony Optimization Algorithm for Construction Site Layout Problems

Gulben Calis, Orhan Yuksel

Department of Civil Engineering, Ege University, Izmir, Turkey.

DOI: 10.4236/jbcpr.2015.34022                

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 nontrivial 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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Easa, S.M. and Hossain, K.M.A. (2008) New Mathematical Optimization Model for Construction Site Layout. Journal of Construction Engineering and Management, 134, 653-662. http://dx.doi.org/10.1061/(ASCE)0733-9364(2008)134:8(653)
[2]	Said, H. and El-Rayes, K. (2013) Performance of Global Optimization Models for Dynamic Site Layout Planning of Construction Projects. Automation in Construction, 36, 71-78. http://dx.doi.org/10.1016/j.autcon.2013.08.008
[3]	Khalafallah, A. and El-Rayes, K. (2011) Automated Multi-Objective Optimization System for Airport Site Layouts. Automation in Construction, 20, 313-320. http://dx.doi.org/10.1016/j.autcon.2010.11.001
[4]	El Ansary, A.M. and Shalaby, M.F. (2014) Evolutionary Optimization Technique for Site Layout Planning. Sustainable Cities and Society, 11, 48-55. http://dx.doi.org/10.1016/j.scs.2013.11.008
[5]	Jiang, S. and Nee, A.Y.C. (2013) A Novel Facility Layout Planning and Optimization Methodology. CIRP Annals- Manufacturing Technology, 62, 483-486. http://dx.doi.org/10.1016/j.cirp.2013.03.133
[6]	Yeh, I.-C. (1995) Construction-Site Layout Using Annealed Neural Network. Journal of Computing in Civil Engineering, 9, 201-208. http://dx.doi.org/10.1061/(ASCE)0887-3801(1995)9:3(201)
[7]	Zhang, J.P., Liu, L.H. and Coble, R.J. (2002) Hybrid Intelligence Utilization for Construction Site Layout. Automation in Construction, 11, 511-519. http://dx.doi.org/10.1016/S0926-5805(01)00071-1
[8]	Li, H. and Love, P.E.D. (1998) Site-Level Facilities Layout Using Genetic Algorithms. Journal of Computing in Civil Engineering, 12, 227-231. http://dx.doi.org/10.1061/(ASCE)0887-3801(1998)12:4(227)
[9]	Mawdesley, M.J., Al-Jibouri, S.H. and Yang, H. (1998) Genetic Algorithms for Construction Site Layout in Project Planning. Journal of Construction Engineering and Management, 128, 418-426. http://dx.doi.org/10.1061/(ASCE)0733-9364(2002)128:5(418)
[10]	Mawdesley, M.J. and Al-Jibouri S.H. (2003) Proposed Genetic Algorithms for Construction Site Layout. Engineering Applications of Artificial Intelligence, 16, 501-509. http://dx.doi.org/10.1016/j.engappai.2003.09.002
[11]	El-Rayes, K. and Khalafallah, A. (2005) Trade-Off between Safety and Cost in Planning Construction Site Layouts. Journal of Construction Engineering and Management, 131, 1186-1195. http://dx.doi.org/10.1061/(ASCE)0733-9364(2005)131:11(1186)
[12]	Sanad, H.M., Ammar, M.A. and Ibrahim, M.E. (2008) Optimal Construction Site Layout Considering Safety and Environmental Aspects. Journal of Construction Engineering and Management, 134, 536-544. http://dx.doi.org/10.1061/(ASCE)0733-9364(2008)134:7(536)
[13]	Lam, K.-C., Ning, X. and Lam, M.C.K. (2009) Conjoining MMAS to GA to Solve Construction Site Layout Planning Problem. Journal of Construction Engineering and Management, 135, 1049-1057. http://dx.doi.org/10.1061/(ASCE)0733-9364(2009)135:10(1049)
[14]	Zhang, H. and Wang, J.Y. (2008) Particle Swarm Optimization for Construction Site Unequal-Area Layout. Journal of Construction Engineering and Management, 134, 739-748. http://dx.doi.org/10.1061/(ASCE)0733-9364(2008)134:9(739)
[15]	Ning, X., Lam, K.-C. and Lam, M.C.K. (2010) Dynamic Construction Site Layout Planning Using Max-Min Ant System. Automation in Construction, 19, 55-65. http://dx.doi.org/10.1016/j.autcon.2009.09.002
[16]	Lien, L.-C. and Cheng, M.-Y. (2012) A Hybrid Swarm Intelligence Based Particle-Bee Algorithm for Construction Site Layout Optimization. Expert Systems with Applications, 39, 9642-9650. http://dx.doi.org/10.1016/j.eswa.2012.02.134
[17]	Lien, L.-C. and Cheng, M.-Y. (2014) Particle Bee Algorithm for Tower Crane Layout with Material Quantity Supply and Demand Optimization. Automation in Construction, 45, 25-32. http://dx.doi.org/10.1016/j.autcon.2014.05.002
[18]	Saka, M.P. and Dogan, E. (2012) Recent Developments in Metaheuristic Algoritms: A Review. Computational Technology Reviews, 5, 31-78. http://dx.doi.org/10.4203/ctr.5.2
[19]	Dorigo, M., Maniezzo, V. and Colorni, A. (1991) Positive Feedback as a Search Strategy. Technical Report, No. 91-016, Politecnico di Milano, Milano.
[20]	Bell, J.E. and McMullen, P.R. (2004) Ant Colony Optimization Techniques for the Vehicle Routing Problem. Advanced Engineering Informatics, 18, 41-48. http://dx.doi.org/10.1016/j.aei.2004.07.001
[21]	Maniezzo, V. and Colorni, A. (1999) The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Data and Knowledge Engineering, 11, 769-778. http://dx.doi.org/10.1109/69.806935
[22]	Colorni, A., Dorigo, M., Maniezzo, V. and Trubian, M. (1994) Ant System for Job-Shop Scheduling. JORBEL-Belgian Journal of Operations Research, Statistics and Computer Science, 34, 39-53.
[23]	Gagne, C., Price, W.L. and Gravel, M. (2002) Comparing an ACO Algorithm with Other Heuristics for the Single Machine Scheduling Problem with Sequence-Dependent Setup Times. The Journal of the Operational Research Society, 53, 895-906. http://dx.doi.org/10.1057/palgrave.jors.2601390
[24]	Milena, L. and Borovska, P. (2008) Comparison of Parallel Metaheuristics for Solving the TSP. In: Proceedings of the International Conference on Computer Systems and Technologies, ACM Press, New York, Article No 17.
[25]	Ning, X., Lam, K.-C. and Lam, M.C.K. (2010) Dynamic Construction Site Layout Planning Using Max-Min Ant System. Automation in Construction, 19, 55-65. http://dx.doi.org/10.1016/j.autcon.2009.09.002
[26]	Maniezzo, V. and Colorni, A. (1998) The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Data and Knowledge Engineering, 11, 769-778. http://dx.doi.org/10.1109/69.806935
[27]	Bell, J.E. and McMullen, P.R. (2004) Ant Colony Optimization Techniques for the Vehicle Routing Problem. Advanced Engineering Informatics, 18, 41-48. http://dx.doi.org/10.1016/j.aei.2004.07.001
[28]	Gambardella, L.M. and Dorigo, M. (1995) Ant-Q: A Reinforcement Learning Approach to the Travelling Salesman Problem. In: Prieditis, A. and Russell, S., Eds., Proceedings of the Twelfth International Conference on Machine Learning (ML-95), Morgan Kaufmann Publishers, Palo Alto, 252-260. http://dx.doi.org/10.1016/b978-1-55860-377-6.50039-6
[29]	Colas, S., Monmarche, N., Gaucher, P. and Slimane, M. (2008) Artificial Ants for the Optimization of Virtual Keyboard Arrangement for Disabled People. In: Monmarche, N., et al., Eds., Artificial Evolution, Springer, Heidelberg, 87- 99. http://dx.doi.org/10.1007/978-3-540-79305-2_8
[30]	Pellegrini, P., Favaretto, D. and Moretti, E. (2009) Exploration in Stochastic Algorithms: An Application on MAX- MIN Ant System. In: Krasnogor, N., et al., Nature Inspired Cooperative Strategies for Optimization (NICSO 2008), Springer, Berlin, 1-13.
[31]	Gharaie, E., Afshar, A. and Jalali, M.R. (2006) Site Layout Optimization with ACO Algorithm. Proceedings of the 5th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases, Madrid, 15-17 February 2006, 90-94.
[32]	Li, H. and Love, P.E.D. (2000) Genetic Search for Solving Site-Level Unequal-Area Facility Layout Problems. Automation in Construction, 9, 217-226. http://dx.doi.org/10.1016/S0926-5805(99)00006-0
[33]	Dorigo, M. and Gambardella, L.M. (1997) Ant Colonies for the Travelling Salesman Problem. BioSystems, 43, 73-81. http://dx.doi.org/10.1016/S0303-2647(97)01708-5
[34]	Dorigo, M. and Gambardella, L.M. (1997) Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53-66. http://dx.doi.org/10.1109/4235.585892
[35]	Dorigo, M. and Stützle, T. (2004) Ant Colony Optimization. The MIT Press, Cambridge, 305 p. http://dx.doi.org/10.1007/b99492