Solving Facility Placement (p-Hub) Problem Using Artificial Bee Colony

Abstract

Facility (p-Hub) allocation problem is known as the complexity class of decision problems that can be verified in polynomial time aiming to locate the strategies of goods, services and information distribution system. In the distribution systems, a network of nodes interconnected by dedicated lines can be designed to achieve a desired level of service quality at an acceptable cost. The designed solution of this network may not be cost effective. Therefore, in order to reduce the total transportation cost, some hubs can be used which serve as a fusion or routing point for other nodes. Transportation management, urban management, positioning of service centers, the design of sensor networks, computer engineering, the design of computer networks, the design of communication networks, power engineering, the location of repair centers, maintenance and monitoring of electrical lines, such as the design of manufacturing systems to create such networks in the hub ' s are used. A challenging point with hubs is to decide which nodes may have different network properties and be used as hub location points. A good solution in a short time is more effective than the best solution obtained by long calculations. In order to obtain both optimal solutions in a short time, heuristic based algorithms have recently been employed in the solution of p-Hub problems. Therefore, in this study, Artificial Bee Colony (ABC) algorithm is proposed to solve p-Hub position problem. In this study, ABC algorithm is applied in three different cases depending on the number of nodes for p-Hub location allocation problem solving. The first case consists of three fixed plants in the center and a total of twenty nodes, the second case consists of six fixed facilities in the center and thirty nodes connected to them, the third case consists of seven fixed facilities in the center and forty nodes connected to these facilities. The minimum space allocation cost function solutions obtained by ABC algorithm are given in tables and graphs. The results obtained were compared with the results of Particle Swarm Optimization in the literature. As a result of the study, it was seen that ABC achieved better results in p-Hub space allocation problem solving. Therefore, the proposed ABC algorithm has shown that it is a suitable method for the solution of the facility allocation (p-Hub) problem.

Keywords

• Facility location (p-Hub) problem
• Artificial Bee Colony
• Optimization

Tesis Yerleştirme (p-Hub) Probleminin Yapay Arı Kolonisi Kullanılarak Çözülmesi

Öz

Tesis (p-Hub) yerleştirme problemi, mal, hizmet ve bilgi dağıtım sistemi stratejilerini konumlandırmayı amaçlayan polinomsal zamanda doğrulanabilen karar problemlerinin karmaşıklık sınıfı olarak bilinmektedir. Dağıtım sistemlerinde istenen düzeyde bir hizmet kalitesini kabul edilebilir bir maliyetle elde etmek için birbirine tahsis edilmiş hatlarla birbirine bağlanmış düğümlerden oluşan bir ağ tasarlanabilir. Tasarlanan bu ağın uygun çözüm maliyetli olmayabilir. Bundan dolayı toplam ulaşım maliyetini azaltmatabilmek amacıyla, diğer düğümler için birleştirme veya yönlendirme noktası olarak çalışan bazı tesisler (hublar) kullanılabilir. Taşımacılık yönetimi, kentsel yönetim, servis merkezlerinin konumlandırılması, sensör ağlarının tasarımı, bilgisayar mühendisliği, bilgisayar ağlarının tasarımı, iletişim ağlarının tasarımı, güç mühendisliği, onarım merkezlerinin konumunu, elektrik hatlarının bakımı ve izlenmesi ile imalat sistemlerinin tasarımı gibi sorunların çözümünde bu tür ağları oluştururken hub'lar kullanılmaktadır. Hub'lı zorlu bir nokta, hangi düğümlerin ağ özelliklerinin farklılık gösterebileceğine ve hub konum noktaları olarak kullanılacağına karar vermektir. Hub’lı yer tahsisinde kısa zamandaki iyi bir çözüm, uzun hesaplamalar sonucunda elde edilen en iyi çözümden daha etkilidir. Hem kısa zamanda hemde optimum çözüm elde edebilmek amacıyla p-Hub problemlerinin çözümünde son zamanlarda sezgisel temelli algoritmalar işe koşulmaktadır. Bundan dolayı bu çalışmada p-Hub konum problemini çözmek için Yapay Arı Koloni (YAK) algoritması önerilmiştir. Bu çalışmada, YAK algoritması p-Hub yer tahsisi problem çözümü için düğüm sayısına bağlı olarak üç farklı durumda uygulanmıştır. Birinci durum merkezde sabit olarak bulunan üç adet tesis ve toplam yirmi düğüm, ikinci durum merkezde sabit altı adet tesis ve bunlara bağlı otuz düğüm, üçüncü durum ise merkezde sabit yedi tesis ve bu tesislere bağlı kırk düğümden oluşmaktadır. YAK algoritması ile elde edilen minimum yer tahsisi maliyet fonksiyonu çözümleri tablolar ve grafiklerle verilmiştir. Elde edilen sonuçlar literatürde yer alan Parçacık Sürü Optimizasyonu sonuçları ile karşılaştırılmıştır. Çalışma sonucunda p-Hub yer tahsisi problem çözümünde YAK’ın daha iyi sonuç elde ettiği görülmüştür. Bundan dolayı yönerilen YAK algoritmasının tesis tahsisi (p-Hub) problemi çözümü için uygun bir yöntem olduğunu göstermiştir.

Anahtar Kelimeler

• Tesis (p-Hub) Yerleştirme Problemi
• Yapay Arı Kolonisi
• Optimizasyon

References

1. Alpaslan, F., Eğrioğlu, E., Aladağ, Ç. H., İlter, D., & Dalar, A. Z. (2013). TEK ÇARPIMSAL SİNİR HÜCRELİ YAPAY SİNİR AĞI MODELİNİN EĞİTİMİ İÇİN ABC VE BP YÖNTEMLERİNİN KARŞILAŞTIRILMASI. Anadolu University of Sciences & Technology-A: Applied Sciences & Engineering, 14(3).
2. Alumur, S., & Kara, B. Y. (2008). Network hub location problems: The state of the art. European journal of operational research, 190(1), 1-21.
3. Aversa, R., Botter, R., Haralambides, H., & Yoshizaki, H. (2005). A mixed integer programming model on the location of a hub port in the east coast of South America. Maritime Economics & Logistics, 7(1), 1-18.
4. Basti, M. (2012). The p-median Facility Location Problem and Solution Approaches. AJIT-e, 3(7), 47.
5. Campbell, J. F. (2009). Hub location for time definite transportation. Computers & Operations Research, 36(12), 3107-3116.
6. Farahani, R. Z., Hekmatfar, M., Arabani, A. B., & Nikbakhsh, E. (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4), 1096-1109.
7. Hsu, C.-C., & Chen, Y.-C. (2007). Mining of mixed data with application to catalog marketing. Expert Systems with Applications, 32(1), 12-23.
8. Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Retrieved from

9. Karaboga, D., & Akay, B. (2009). A comparative study of artificial bee colony algorithm. Applied mathematics and computation, 214(1), 108-132.
10. Karaboga, D., & Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of global optimization, 39(3), 459-471.
11. Karaboga, D., & Basturk, B. (2008). On the performance of artificial bee colony (ABC) algorithm. Applied soft computing, 8(1), 687-697.
12. Küçüksille, E. U., & Tokmak, M. (2011). Yapay arı kolonisi algoritması kullanarak otomatik ders çizelgeleme. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitü Dergisi, 15(3), 203-210.
13. Marín, A. (2005). Formulating and solving splittable capacitated multiple allocation hub location problems. Computers & Operations Research, 32(12), 3093-3109.
14. Mohammadi, M., Tavakkoli-Moghaddam, R., Siadat, A., & Rahimi, Y. (2016). A game-based meta-heuristic for a fuzzy bi-objective reliable hub location problem. Engineering Applications of Artificial Intelligence, 50, 1-19.
15. Ozcakar, N., & Bastı, M. (2012). P-Medyan kuruluş yeri seçim probleminin çözümünde parçacık sürü optimizasyonu algoritması yaklaşımı. İstanbul Üniversitesi İşletme Fakültesi Dergisi, 41(2), 241-257.
16. Pamuk, F. S., & Sepil, C. (2001). A solution to the hub center problem via a single-relocation algorithm with tabu search. Iie Transactions, 33(5), 399-411. Puerto, J., Ramos, A., Rodríguez-Chía, A. M., & Sánchez-Gil, M. C. (2016). Ordered median hub location problems with capacity constraints. Transportation Research Part C: Emerging Technologies, 70, 142-156.
17. Sarvari, P. A., Yeni, F. B., & Çevikcan, E. (2018). Hub Location Allocation Problems and Solution Algorithms Handbook of Research on Applied Optimization Methodologies in Manufacturing Systems (pp. 77-106): IGI Global.
18. Tavakkoli-Moghaddain, R., & Shayan, E. (1998). Facilities layout design by genetic algorithms. Computers & Industrial Engineering, 35(3-4), 527-530.
19. Yaman, H. (2008). Star p-hub median problem with modular arc capacities. Computers & Operations Research, 35(9), 3009-3019.