Eşzamanlı Dağıtımlı Ve Toplamalı Araç Rotalama Problemlerinin Çözümü İçin Bakteriyel Besin Arama Optimizasyonu Tabanlı Bir Algoritma

Year 2013, Volume: 28 Issue: 2, 0 - , 28.02.2014

Seda Hezer Yakup Kara

Abstract

Eşzamanlı Dağıtımlı ve Toplamalı Araç Rotalama Probleminde (EDT_ARP), her müşteri dağıtım talebi ile birlikte aynı zamanda toplama talebinde bulunmaktadır ve müşterilere eşzamanlı olarak hizmet verilmektedir. EDT_ARP çözümü oldukça zor kombinatoryal optimizasyon problemidir. Bu nedenle son yıllarda yapılan çalışmalarda metasezgisel metotlar üzerinde odaklanıldığı gözlemlenmiştir. Bu çalışmada oldukça yeni bir metasezgisel algoritma olan Bakteriyel Besin Arama Optimizasyonu Algoritması (BBAOA) tabanlı bir sezgisel çözüm yaklaşımı geliştirilmiş ve performansı değerlendirilmiştir. Çalışma kapsamında EDT_ARP katedilen toplam mesafe minimize edilerek çözülmüş ve sonuçlar literatürde bilinen ekleme tabanlı sezgisel bir algoritma ile karşılaştırılmıştır. Önerilen BBAOA ile göz önünde bulundurulan, toplam 40 test probleminden 24’ünde karşılaştırma yapılan algoritmaya göre daha iyi sonuçlara ulaşılmıştır.

Keywords

Eşzamanlı Dağıtımlı Ve Toplamalı Araç Rotalama Problemi, Bakteriyel Besin Arama Optimizasyonu Algoritması

References

• Chen, J. F., Wu, T. H., “Vehicle routing problem with simultaneous deliveries and pickups”, Journal of the Operational Research Society, Cilt 57, 579–587, 2006.
• Toth, P., Vigo, D., The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, 2002.
• Wassan, N. A., Wassan, A. H., Nagy, G., “A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries”, J Comb Optim., Cilt 15, 368–386, 2008.
• Ai, J., Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery”,Computers & Operations Research, Cilt 36, No 5, 1693- 1702, 2009.
• Altıparmak, F., Dengiz, B., Kara, İ., Karaoğlan İ., “Eş zamanlı topla-dağıt araç rotalama problemi için yeni matematiksel formulasyonlar”. YA/EM 2008-Yöneylem Araştırması ve Endüstri Mühendisliği XXVIII. Ulusal Kongresi Bildiri Özetleri Kitabı, Galatasaray Üniversitesi, İstanbul, Sayfa No. 130, 30 Haziran - 2 Temmuz 2008.
• Dethloff, J., “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up”, OR Specktrum, Cilt 23, 79–96, 2001.
• Zachariadis, E, E., Tarantilis, C, D., Kiranoudis, C, T., “A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service”, Expert Systems with Applications, Cilt 36, No 2, 1070–1081, 2009.
• Min, H., “The multiple vehicle routing problem with simultaneous delivery and pick-up points”, Transportation Research, Cilt 23, No 5, 377–386, 1989.
• Crispim, J., Brandao, J., “Metaheuristics applied to mixed and simultaneous extensions of vehicle routingproblems with backhauls”, Journal of the Operational Research Society, Cilt 56, 1296–1302, 2005.
• Dell’Amico, M., Righini, G., Salani, M., “A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection”, Transportation Science, Cilt 40: 2, 235–247, 2006.
• Montané, T, F, A., Galvão, R, D., “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, Computers & Operations Research, Cilt 33, No 3, 595–619, 2006.
• Bianchessi, N., Righini, G., “Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery”, Computers & Operations Research, Cilt 34, No 2, 578–594, 2007. 13. Gajpal, Y., Abad, P., “An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup”, Computers & Operations Research, Cilt 36, No 12, 3215–3223, 2009. 14. Subramanian, A., Drummonda, L.M.A., Bentes, C., Ochi, L.S., Farias, R., “A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery”, Computers & Operations Research, Cilt 37, No 11, 1899–1911, 2010.
• Bremermann, H., “Chemotaxis and optimization”, J. Franklin Inst., Cilt 297, 397– 404, 1974.
• Passino, K.M., “Biomimicry of bacterial foraging for distributed optimization and control”, IEEE Control Systems Magazine, 52–67, 2002.
• D.H. Kim, J.H. Cho, “Adaptive tuning of PID controller for multivariable system using bacterial foraging based optimization”, in: Piotr S. Szczepaniak, Janusz Kacprzyk, Adam Niewiadomski (Eds.), Third International Atlantic Web Intelligence Conference, AWIC 2005, Lodz, Poland, Lecture Notes in Computer Science, Vol. 3528, Advance in Web Intelligence, pp. 231–238, 2005a.
• Kim, D. H., Cho C. H., “Bacterial foraging based neural network fuzzy learning”, Proceedings of 1st Indian International Conference on Artificial Intelligence, 2030-2036, 2005b.
• Mishra, S., “A hybrid least square-fuzzy bacteria foraging strategy for harmonic estimation”, IEEE Trans. Evol. Comput, Cilt 9, No 1, 61–73, 2005.
• Majhi, B., Panda, G., Sahoo, G., Dash, P., Das D., “Stock market prediction of s&p 500 and djia using bacterial foraging optimization technique”. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC’2007), Singapore, IEEE Service Center, 2569–2575, September 2007.
• Tripathy, M., Mishra, S., Lai, L. L., Zhang,Q. P., “Transmission loss reduction based on FACTS and Bacteria Foraging Algorithm”, Proceedings of 9th International Conference on Parallel Problem Solving from Nature, 222-231, 2006.
• Majhi, B., Panda, G., “Bacteria foraging based identificacion of nonlinear dynamic system”, In Proceedings of the IEEE Congress on Evolutionary Computation, Singapore, IEEE Service Center, 1636–1641, 2007.
• Wu, C., Zhang, N., Jiang, J., Yang, J., Liang, Y., “Improved bacterial foraging algorithms and their applications to job shop scheduling problems”, ICANNGA, Part I, LNCS 4431, 562 – 569, 2007.
• Kim, D. H., Abraham, A., Cho, J. H., “A hybrid genetic algorithm and bacterial foraging approach for global optimization”, Information Sciences, Cilt 177, No 18, 3918-3937, 2007.
• Biswas, A., Dasgupta, S., Das, S., Abraham A., “Synergy of pso and bacterial foraging optimization: a comparative study on numerical benchmarks”, Second International Symposium on Hybrid Artificial Intelligent Systems, 2007a.
• Biswas, A., Dasgupta, S., Das, S., Abraham, A., “A synergy of differential evolution and bacterial foraging algorithm for global optimization”, International Journal on Neural and Mass-Parallel Computing and Information Systems Neural Network World, Cilt 17, No 6, 607-626, 2007b.
• Başbuğ S. Bakteriyel besin arama algoritması ile lineer anten dizilerinin diyagram sıfırlaması. Yüksek Lisans Tezi, Erciyes Üniversitesi, Fen Bilimleri Enstitüsü, Kayseri, 2008.
• Baker, B. M., Ayechew M.A., “A genetic algorithm for the vehicle routing problem”, Computers & Operations Research, Cilt 30, 787–800, 2003.
• Gencer, C., Yaşa, Ö., “Ulaştırma Komutanlığı Ring Seferlerinin Eş Zamanlı Dağıtım Toplama Karar Destek Sistemi (Simultaneous Pick-Up And Delivery Decısıon Support Systems Of Transportatıon Command Shuttle Tour’s)”, Journal of the Faculty of Engineering and Architecture of Gazi University, Cilt 22, No 3, 437–449, 2007.