A Comparison of Metaheuristics for the Allocation of Elevators to Calls in Buildings

Abstract

This paper deals with the car-call allocation problem in vertical transportation in buildings. We have made a wide comparison of different metaheuristic optimization algorithms to identify those with a better performance dealing with the problem. The tested approaches are Differential Evolution (DE), Simulated Annealing with Random Starts (SAR), Artificial Bee Colony (ABC), Bat Algorithm (BA), Bacterial Foraging Optimization Algorithm (BF), Particle Swarm Optimization (PSO), Genetic Algorithm (GA), and Tabu Search (TS). Each algorithm was tested in high-rise building simulations of 10 to 24 floors, with car configurations of 2 to 6 cars. Results proved that the ABC and TS algorithms generally result in better average journey times compared to other methods. It has to be noted that we introduced a new version of the Simulated Annealing, Simulated Annealing with Restarts (SAR), which ranked as the third best algorithm.

Keywords

• Elevator group control system
• evolutionary algorithms
• optimization

A Comparison of Metaheuristics for the Allocation of Elevators to Calls in Buildings

Abstract

Bu çalışma binalarda düşey taşımacılıkta kullanılan asansörler için çağrıların kabinlere dağıtılması problemi üzerinedir.  Geniş bir spektrumda farklı sezgisel optimizasyon algoritmaları problem üzerinde performans yönünden karşılaştırılmış ve başarılıları belirlenmiştir. Test edilen algoritmalar Çıkarımsal Evrim (Differential Evolution, DE), Rastgele Yeniden Başlatmalı Benzetimli Tavlama (Simulated Annealing with Random Starts, SAR), Yapay Arı Kolonisi (Artificial Bee Colony, ABC), Yarasa Algoritması (Bat Algoritması, BA), Bakteri Otlama Optimizasyon Algoritması (Bacterial Foraging Optimization Algorithm, BF), Parçacık Sürü Optimizasyonu (Particle Swarm Optimization, PSO),  Genetic Algoritma (Genetic Algorithm, GA) ve Tabu Araştırmasıdır (Tabu Search, TS). Her algoritma simülasyon ile 10 ila 24 katlı binalar ve 2 ila 6 kabin ile test edilmiştir. Sonuçlar ABC ve TS algoritmalarının daha iyi bir ortalama yolculuk zamanı verdiğini göstermiştir. Ayrıca Benzetimli Tavlama algoritmasının yeni bir versiyonu olan Rastgele Yeniden Başlatmalı Benzetimli Tavlama (SAR) algoritması geliştirilmiştir. SAR deney sonuçlarında en iyi 3. algoritma olarak çıkmaktadır.

Keywords

• Elevator group control system
• evolutionary algorithms
• optimization

References

1. 1. Fernandez J.R. and Cortes, P., “A survey of elevator group control systems forvvertical transportation: a look at recent literature”, IEEE Control Systems, 35(4): 38-55, (2015).
2. 2. Cortes P., Munuzuri J. and Onieva L., “Design and Analysis of a Tool for Planning and Simulating Dynamic Vertical Transport”, Simulation, 82: 255-274, (2006).
3. 3. Knuth D. E., “A terminological proposal”, SIGACT News, 6(1): 12-18, (1974).
4. 4. Knuth D. E. (1974). Postscript about NP-hard problems. SIGACT News, 6(2): 15-16, (1974).
5. 5. Cortes P., Munuzuri J. and Onieva L., “Genetic algorithm for controllers in elevator groups: analysis and simulation during lunchpeak traffic”, Applied Soft Computing, 4(2): 159-174, (2004).
6. 6. Bolat B., Cortes P., Yalçın E. and Alışverişçi M., “Optimal car dispatching for elevator groups using genetic algorithms”, Intelligent Automation &Soft Computing, 16(1), (2010).
7. 7. Chen T.C., Hsu Y.J, and Huang Y.J., “optimizing the intelligent elevator group control system by using genetic algorithm”, Advanced Science Letters, 9(1), (2012).
8. 8. Bolat B. and Cortes P., “Genetic and tabu search approaches for optimizing the hall call-car allocation problem in elevator group systems”, Applied Soft Computing, 11(2), (2011).

9. 9. Bolat B., Altun O. and Cortes P., “A particle swarm optimization algorithm for optimal car-call allocation in elevator group control systems”, 13(5), (2011).
10. 10. Li Z, Tan H,Z, and Zhang Y., “Particle swarm optimization applied to vertical traffic scheduling in buildings in”, 11 th International Conference KES and XVII Italian Workshop on Neural Networks Conference on Knowledge-Based Intelligent Information and Enginnering Systems : Part I, (2007).
11. 11. Fei L., Xiaocui Z. and Yuge X., “A new hybrid elevator group control system scheduling strategy based on particle swarm simulated annealing optimization algorithm in intelligent control and automation”, 8th World Congress, 5121-5124, (2010).
12. 12. Li Z., Mao Za and Wu J., “Research on dynamic zoning of elevator traffic based on artifical immune algorithm”, 8th Control, Automation,Robotics and Vision Conference, 3: 2170-2175, (2004).
13. 13. Liu J. and Liu Y., “Ant colony algorithm and fuzzy neural network- based intelligent dispatching algorithm of an elevator group control system, IEEE International Conference on Control and Automation, (2007).
14. 14. Cortes P., Onieva L, Munuzuri J. and Guadix J., “A viral system algorithm to optimize the car dispatching in elevatro group control sytems of tall buildings, Computers&Industrial Engineering, 64(1) :403-411, (2013).
15. 15. Cortes P., Fernandez J.R, Guadix J. and Munuzuri, J., “Fuzzy logic based controller for peak traffic detection in elevator systems”, Journal of Computational and Theoretical Nanoscience, 9(2): (2012).
16. 16. Jamaludin J., Rahim N. and Hew W.P., “An elevator group control sytem with a self –tuning fuzzy logic group controller”, IEEE Transactions on Industrial Electronics, 57(12): 4188-4198, (2010).
17. 17. Rashid M., Kasemi B., and Faruq A. Alam., “Design of fuzzy based controller for modern elevator group with floor priority constraints, 4th International Conference on Mechatronics, (2011).
18. 18. Fernandez J.R., Cortes P., Munuzuri J. and Guadix J., “Dynamic fuzzy logic elevator group control system with relative waiting time consideration”, IEEE Transaction on Industrial Electronics, 61(9): (2014).
19. 19. Fernandez J.R., Cortes P., Guadix J., and Munuzuri J., “Dynamic fuzzy logic elevator group control system for energy optimization”, International Journal of Information Technology and Decision Making, 12(3): (2013).
20. 20. Kennedy J. and Eberhart R.C., “Particle swarm optimization, IEEE International Conference on Neural Networks, 4: 1942-1948, (1995).
21. 21. Clerc M. and Kennedy J., “The particle swarm- explosion, stability, and convergence in a multidimensional complex space”, IEEE Transactions on Evolutionary Computation, 6(11): (2002).
22. 22. Karaboğa D., “An idea based on honey bee swarm for numerical optimization, Technical Report-tr06, Erciyes University, Engineering Faculty, Computer Engineering Department, (2005).
23. 23. Karaboğa D. and Basturk B., “A powerful and efficient algorithm for numerical function optimization : artifical bee colony (ABC) algorithm”, Journal of Global Optimization, 39(3): 459-471, (2007).
24. 24. Luke S., “Essentials of Metaheuristics, Lulu, Second Edn., (2013).
25. 25. Yang X.S., “A new metaheuristic bat-inspired algorithm, in J. Gonzalez, D. Pelta, C. Cruz, G. Terrazas, N.Krasnogar (eds.), Nature Inspired Cooperative Strategies for Optimization, 284: (2010).
26. 26. Passino K., “Biomimicry of bacterial foraging for distributed optimization and control, “IEEE Control Systems, 22(3): 52-67, (2002).