EŞZAMANLI DAĞITIMLI VE TOPLAMALI ARAÇ ROTALAMA PROBLEMLERİNİN ÇÖZÜMÜ İÇİN BAKTERİYEL BESİN ARAMA OPTİMİZASYONU TABANLI BİR ALGORİTMA

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.

SOLVING VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS DELIVERY AND PICK-UP USING AN ALGORITHM BASED ON BACTERIAL FORAGING OPTIMIZATION

In Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRP_SDP), each customer has both delivery and pick-up demand simultaneously. VRP_SDP is very difficult combinatorial optimization problem. For this reason, in recent years, it is observed studies focused on metaheuristic methods. In this study, a heuristic solution approach based on Bacterial Foraging Optimization Algorithm (BFOA) has been improved and its performance has been evaluated. In the scope of this study VRP_SDP has been solved in order to minimize the total distanced travelled and the results have been tested with the insertion based heuristic that is known in the literature. BFOA obtained good solutions about 24 problems of 40 test problems.

___

  • 1. 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.
  • 2. Toth, P., Vigo, D., The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, 2002.
  • 3. 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.
  • 4. 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.
  • 5. 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. 6. Dethloff, J., “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up”, OR Specktrum, Cilt 23, 79–96, 2001.
  • 7. 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.
  • 8. Min, H., “The multiple vehicle routing problem with simultaneous delivery and pick-up points”, Transportation Research, Cilt 23, No 5, 377– 386, 1989.
  • 9. 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.
  • 10. 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.
  • 11. 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.
  • 12. 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.
  • 15. Bremermann, H., “Chemotaxis and optimization”, J. Franklin Inst., Cilt 297, 397– 404, 1974.
  • 16. Passino, K.M., “Biomimicry of bacterial foraging for distributed optimization and control”, IEEE Control Systems Magazine, 52–67, 2002.
  • 17. 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.
  • 18. 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.
  • 19. Mishra, S., “A hybrid least square-fuzzy bacteria foraging strategy for harmonic estimation”, IEEE Trans. Evol. Comput, Cilt 9, No 1, 61–73, 2005.
  • 20. 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.
  • 21. 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.
  • 22. 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.
  • 23. 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.
  • 24. 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.
  • 25. 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.
  • 26. 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.
  • 27. 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.
  • 28. Baker, B. M., Ayechew M.A., “A genetic algorithm for the vehicle routing problem”, Computers & Operations Research, Cilt 30, 787–800, 2003.
  • 29. 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.
Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi-Cover
  • ISSN: 1300-1884
  • Yayın Aralığı: Yılda 4 Sayı
  • Başlangıç: 1986
  • Yayıncı: Oğuzhan YILMAZ