TALEP VE KAPASİTE KISITLI OPTİMİZASYON PROBLEMİ İÇİN YENİ BİR MELEZ ALGORİTMA

Öz

Optimizasyon problemleri arasından en önemlilerinden biri de ulaştırmada Araç Rotalama Problemi’dir (ARP). ARP’nin amacı, müşterilerin taleplerini en az mesafeli rota ve araç ile karşılamaktır. Bu makalede, talep ve kapasite kısıtlı ARP ele alınmış ve bunun çözümü içinde literatürde geçen Clarke ve Wright tasarruf algoritması ile en kısa yol yöntemini esas alan yeni bir melez algoritma geliştirilmiştir. Algoritmalar farklı sayıdaki problem setleri ile denenmiş ve elde edilen sonuçlar, ANOVA testi ile yorumlanmıştır. Sonuçlar, yeni geliştirilen melez metodun daha iyi sonuçlar verdiğini göstermiştir.

Anahtar Kelimeler

• Araç rotalama problemi,Clarke ve Wright yöntemi

A NEW HYBRID ALGORITHM FOR OPTIMIZATION PROBLEM UNDER DEMAND AND CAPACITY CONSTRAINTS

Öz

Vehicle routing problem (VRP) can be considered as one of the most important optimization problems in a transportation sector. The objective of the routing problem is to meet the customers’ demand under considering minimum distance of the routes and number of cars. In this article, capacity of cars and customers’ demand were assumed as constraints of the VRP problem. A new hybrid method was developed based on the Clarke and Wright savings and the shortest path algorithms from the literature. The algorithms were tested on different problem sets.  Obtained results were interpreted by ANOVA test. The results illustrated that the new algorithm provides better results than the other two algorithms.

Anahtar Kelimeler

• Vehicle routing problem,the Clarke and Wright algorithm

Kaynakça

1. 1. Aksen, D., Özyurt, Z., Aras, N. 2007. “The Open Vehicle Routing Problem with Driver Nodes and Time Dead Lines,” Journal of the Operational Research Society, vol. 58, no. 9, p. 1223-1234.
2. 2. Alba, E., Dorronsoro, B. 2005. “Computing Nine New Best-So-Far Solutions for Capacitated VRP with a Cellular Genetic Algorithm,” Information Processing Letters, vol. 98, p. 225-230.
3. 3. Arslan, S. 2007. “Araç Rotalama Problemi ve Bir Uygulama,” Yüksek Lisans Tezi, Gazi Üniversitesi, Sosyal Bilimler Enstitüsü, Ankara.
4. 4. Aydemir, E. 2006. “Esnek Zaman Pencereli Araç Rotalama Problemi ve Bir Uygulama,” Yüksek Lisans Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
5. 5. Baker, B. M., Ayechew, M. A. 2003. “A Genetic Algorithm for the Vehicle Routing Problem," Computers & Operations Research, vol. 30, p. 787-800.
6. 6. Brandão, J. 2004. “A Tabu Search Heuristic Algorithm for Open Vehicle Routing Problem,” European Journal of Operational Research, vol. 157, p. 552-564.
7. 7. Christofides, N., Mingozzi, A., Toth, P. 1981a. “Exact Algorithms for the Vehicle Routing Problem based on Spanning Trees and Shortest Path Relaxations,” Mathematical Programming, vol. 20, no. 1, p. 255-282.
8. 8. Christofides, N., Mingozzi, A., Toth, P. 1981b. “Sta-te-Space Relaxation Procedures for the Computation of Bounds to Routing Problems,” Networks, vol. 11, no. 2, p. 145-164.

9. 9. Darcan, U. 2007. “Stokastik Araç Rotalama Algoritmalarının Karşılaştırmalı İncelenmesi,” Yüksek Lisans Tezi, Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü, İstanbul.
10. 10. Demiral, M. F. 2008. “Servis Araçlarının Rotalanmasında Optimizasyon ve Bir Uygulama,” Yüksek Lisans Tezi, Süleyman Demirel Üniversitesi, Sosyal Bilimler Enstitüsü, Isparta.
11. 11. Demircioğlu, M. 2009. “Araç Rotalama Probleminin Sezgisel Bir Yaklaşım İle Çözümlenmesi Üzerine Bir Uygulama,” Doktora Tezi, Çukurova Üniversitesi, Sosyal Bilimler Enstitüsü, Adana.
12. 12. Doyuran, T. 2008. “Enhancements of Clarke-Wright Savings Heuristics For The Capacitated Vehicle Routing Problem,” Yüksek Lisans Tezi, Sabancı Üniversitesi, Fen Bilimleri Enstitüsü, İstanbul.
13. 13. Erol, V. 2006. “Araç Rotalama Problemleri İçin Popülasyon ve Komşuluk Tabanlı Metasezgisel Bir Algoritmanın Tasarımı ve Uygulaması,” Yüksek Lisans Tezi, Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü, İstanbul.
14. 14. Eryavuz, M., Gencer, C. 2001. “Araç Rotalama Problemine Ait Bir Uygulama,” Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi, C. 6, no. 1, s. 139-155.
15. 15. Fukasawa, R., Longo, H., Lysgaard, J., Poggı de Aragao, M., Reis, M., Uchoa, E., Werneck R. F. 2006. “Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem,” Mathematical Prog. Series A, vol. 106, p. 491-511.
16. 16. Fu, Z., Eglese, R., Li, L. Y. O. 2005. “A New Tabu Search Algorithm for Open Vehicle Routing Problem,” Journal of the Operational Research Society, vol. 56, p. 267-274.
17. 17. Gambardella, L. M., Taillard, E., Agazzi, G. 1999. “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows,” New Ideas in Optimization, eds: Corne, D., Dorigo, M. and Glover, F., McGraw-Hill, London, UK, p. 63-76.
18. 18. Gendreau, M., Hertz, A., Laporte, G. 1994. “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, vol. 40, p. 1276–1290.
19. 19. Gerdan, O. 2007. “Müşteriler Arası Malzeme Akışlı Eş Zamanlı Dağıtım Toplama Yapılan Araç Rotalama Problemi ve Sezgisel Çözümü,” Doktora Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
20. 20. Girard, S., Renaud, J., Boctor, F. F. 2005. “A Simple and Efficient Perturbation Heuristic to Solve the Vehicle Routing Problem,” https://www.cirrelt.ca/DocumentsTravail/2005/DT-2005-JR-1.pdf, son erişim tarihi: 08.06.2014.
21. 21. Gonzalez, E. L., Fernandez, M. A. R. 2000. “Genetic Optimization of a Fuzzy Distribution Model,” International Journal of Physical Distribution &Logistics Management, vol. 30, no. 7/8, p. 681-696.
22. 22. İşleyen, S. K. 2008. “Lojistik Yönetim Sistemlerinde Stokastik Talepli Araç Rotalama Problemi,” Doktora Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
23. 23. Jeon, G., Leep, H. R., Shim, J. Y. 2007. “A Vehicle Routing Problem Solved by Using a Hybrid Genetic Algorithm,” Computers and Industrial Engineering, vol. 53, no. 4, p. 680-692.
24. 24. Kelly, J., Xu, J. P. 1996. “A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem,” Transportation Science, vol. 30, p. 379–393.
25. 25. Laporte, G. 2007. “What You Should Know about the Vehicle Routing Problem,” Naval Research Logistics, vol. 54, no. 8, p. 811–819.
26. 26. Laporte, G., Nobert, Y., Desrochers, M. 1985. “Optimal Routing Under Capacity and Distance Restrictions,” Operations Research, vol. 33, p. 1058-1073.
27. 27. Liu, F., Shen, S. 1999. “A Method for Vehicle Routing Problem with Multiple Vehicle Types and Time Windows,” Proc. Natl. Sci. Counc. ROC (A), vol. 23, no. 4, p. 526-536.
28. 28. Prins, C. 2004. “A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, vol. 31, p. 1985-2002.
29. 29. Reinmann, M., Doerner, K., Hartl, R. F. 2004. “D-ANTS: Savings Based Ants Divide and Conquer The Vehicle Routing Problems,” Computers and Operations Research, vol. 31, no. 4, p. 563-91.
30. 30. Rochat, Y., Taillard, È. D. 1995. “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, vol. 1, p. 147-167.
31. 31. Şahin, M., Şahin, G., Çavuşlar, G., Özcan, T., Tüzün, D., 2010. “Parçalanabilir Yüklü Birebir Toplama ve Dağıtma Problemi İçin Tabu Algoritması,” Yöneylem Araştırması ve Endüstri Mühendisliği 30. Ulusal Kongresi, Sabancı Üniversitesi, İstanbul.
32. 32. Şeker, Ş. 2007. “Araç Rotalama Problemleri Ve Zaman Pencereli Stokastik Araç Rotalama Problemine Genetik Algoritma Yaklaşımı,” Yüksek Lisans Tezi, Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü, İstanbul.
33. 33. Taillard, É. D. 1993. “Parallel Iterative Search Methods for Vehicle Routing Problem,” Networks, vol. 23, p. 661–673.
34. 34. Tokaylı, M. A. 2005. “Zaman Pencereli Araç Rotalama Problemi İçin Bir Karar Destek Sistemi,” Yüksek Lisans Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
35. 35. Toth, P., Vigo, D. 2002. “The Vehicle Routing Problem,” SIAM, Philadelphia.
36. 36. Tüfekçier, H. 2008. “İki Amaçlı Açık Araç Rotalama Problemi İçin Bir Çözüm Yaklaşımı,” Yüksek Lisans Tezi, Eskişehir Osmangazi Üniversitesi, Fen Bilimleri Enstitüsü, Eskişehir.
37. 37. Yılmaz, Ş. 2008. Çok Depolu Araç Rotalama Probleminin Karınca Kolonisi Optimizasyonu İle Modellenmesi ve Bir Çözüm Önerisi,” Yüksek Lisans Tezi, Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü, İstanbul.
38. 38. http://turkistatistik.net/upload/dosya/reganaliz.pdf, son erişim tarihi: 08.06.2014.