YAPAY ZEKA VE KÜMELEME TEKNİKLERİ KULLANILARAK GELİŞTİRİLEN YÖNTEM İLE OKUL SERVİSİ ROTALAMA PROBLEMİNİN OPTİMİZASYONU

Abstract

Araç Rotalama Problemi (ARP) klasik yöntemler ile çözülmesi mümkün olmayan ve birçok alt dalı olan karmaşık bir problemdir. Bu çalışmada, ARP’nin bir alt dalı olan Okul Servisi Rotalama Probleminin (OSRP) optimizasyonu amaçlanmıştır. ARP ve OSRP incelenmiş, problemler ve geliştirilen çözüm yöntemleri ile ilgili literatüre yer verilmiştir. OSRP'nin optimizasyonu için kümeleme teknikleri ve yapay zeka yöntemleri kullanılarak, GPS, GIS araçları ve mobil uygulama desteği ile bir yazılım geliştirilmiştir. Geliştirilen yazılım Ankara ilinde hizmet veren servis firmalarından toplanan rota verileri üzerinde uygulanmıştır. Elde edilen deneysel sonuçlar, geliştirilen yöntemin, mesafe, zaman ve rakım değişimi parametreleri açısından rotaları başarılı bir şekilde iyileştirilebileceğini göstermiştir.

Keywords

• Araç Rotalama Problemi,Okul Servisi Rotalama Problemi,Yapay Zeka,Kümeleme,Optimizasyon

OPTIMIZATION OF SCHOOL BUS ROUTING PROBLEM BY USING A METHOD WITH ARTIFICIAL INTELLIGENCE AND CLUSTERING TECHNIQUES

Abstract

Vehicle routing problems (VRP) are complicated problems, which can be encountered in a variety of different fields and are not possible to solve using classical methods. In this study, optimization of the School Bus Routing Problem(SBRP), which is a sub-branch of VRP, is aimed. VRP and SBRP have been studied, and the literature on the problems and developed solution methods have been given. For the optimization of SBRP, by using the clustering and artificial intelligence techniques a software has been developed with the support of the GPS, GIS tools and mobile application. The developed software has been applied on the route data collected from school service companies which are in the province of Ankara. The obtained experimental results have showed that the developed method can successfully optimize the school bus routes in terms of distance, time and altitude change parameters.

Keywords

• Vehicle Routing Problem,School Bus Routing Problem,Artificial Intelligence Techniques,Clustering Techniques,Optimization

References

1. Bektaş, T., Elmastaş, S., 2004. Okul Araç Rotalama Probleminin Tamsayılı Programlama İle Çözümü. YA/EM'2004, 15-18 Haziran, Gaziantep-Adana, 61-63.
2. Ben Sghaier, S., Ben Guedria, N., Mraihi, R., 2013. Solving School Bus Routing Problem with Genetic Algorithm. In Advanced Logistics and Transport (ICALT), 2013 International Conference on IEEE, 7-12.
3. Bögl, M., Doerner, K.F., Parragh, S.N., 2015. The School Bus Routing and Scheduling Problem with Transfers. Networks, 65(2), 180-203.
4. Carpaneto, G., Toth, P., 1980. Some New Branching and Bounding Criteria for the Symmetric Traveling Salesman Problem. Management Science, 26(7), 736–743.
5. Ceselli, A., Righini, G., Salani, M., 2009. A Column Generation Algorithm for a Vehicle Routing Problem with Economies of Scale and Additional Constraints. Transportation Science, 43(1), 56-69.
6. Chabrier, A., 2006. Vehicle Routing Problem with Elementary Shortest Path Based Column Generation. Computers and Operations Research, 33(10), 2972-2990.
7. Christofides, N., Mingozzi, A., Toth, P., 1981. State-Space Relaxation Procedures for the Computation of Bounds to Routing Problems. Networks, 11(2), 145-164.
8. Clarke, G., Wright, J.W., 1964. Scheduling of Vehicles From a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568–581.

9. Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y., Semet, F., 2002. A Guide to Vehicle Routing Heuristics. The Journal of the Operational Research Society, 53(5), 512–522.
10. Çatay, B., 2010. A New Saving-Based Ant Algorithm For The Vehicle Routing Problem With Simultaneous Pickup and Delivery,. Expert Systems with Applications, 37, 6809–6817.
11. Çolak, S., Güler, H., 2009. Dağıtım Rotaları Optimizasyonu İçin Metasezgisel Bir Yaklaşım. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 11(2), 171-190.
12. Erel, R., (1995), Taşıt Rotalaması ve Çizelgelemesi: Otobüsle Kentlerarası Yolcu Taşımacılığı İçin Bir Model. Doktora Tezi, Yıldız Teknik Üniversitesi, Türkiye.
13. Fisher, M.L., 1994. Optimal Solution of Vehicle Routing Problems using Minumum k-trees. Operations Research, 42(4), 626–642.
14. Fukasawa, R., 2006. Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming, 106(3), 491-511.
15. Laporte, G., Nobert, Y., Desrochers, M., 1985. Optimal Routing Under Capacity and Distance Restrictions. Operations Research, 33, 1058-1073.
16. Laporte, G., 1992. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 59, 345-358.
17. Laporte, G., Nobert, Y., Taillefer, S., 1988. Solving a Family of Multi-Depot Vehicle Routing and Location Routing Problems. Transportation Science, 22(3), 161-172.
18. Li, L.Y.O., Fu, Z., 2002. The School Bus Routing Problem: A Case Study. Journal of the Operational Research Society, 53(5), 552 – 558.
19. Martínez, L. M., Viegas, J. M., 2011. Design and Deployment of an Innovative School Bus Service in Lisbon. Procedia - Social and Behavioral Sciences, 20, 120-130.
20. Nazif, H., Lee, S.L., 2012. Optimised Crossover Genetic Algorithm for Capacitated Vehicle Routing Problem. Applied Mathematical Modelling, 36, 2110–2117.
21. Önder, E., 2011. İstanbul Halk Ekmek A.Ş. (İHE)'ye Ait Çok Depolu Araç Rotalama Probleminin Metasezgisel Yöntemler İle Optimizasyonu. İşletme İktisadı Enstitüsü Yönetim Dergisi, 70, 74-92.
22. Padberg, M., Rinaldi, G., 1991. A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM, 33, 60–100.
23. Park, J., Kim, B., 2010. The School Bus Routing Problem: A review. European Journal of Operational Research, 202, 311–319.
24. Ralphs, T.K., Kopman, L., Pulleyblank, W.R., Trotter, L.E., 2003. On the Capacitated Vehicle Routing Problem. Mathematical Programming Series B, 94, 343.
25. Rojas, J.S.A., Jimenez, J.F., Montoya-Torres, J.R., 2012. Solving of School Bus Routıng Problem by Ant Colony Optimization. Revista EIA, 17, 193-208.
26. Schittekat, P., Sevaux, M., Sörensen, K., 2006. A Mathematical Formulation for a School Bus Routing Problem. In: Proceedings of the IEEE 2006 International Conference on Service Systems and Service Management, Ekim, Troyes, France, 1552-1557.
27. Sghaier, S.B., Guedria,N.B., Mraihi, R., 2013. Solving School Bus Routing Problem with Genetic Algorithm. In Advanced Logistics and Transport (ICALT), 2013 International Conference on IEEE, 29-31 May, Sousse, 7-12.
28. Taha, H.A., 2000. Yöneylem Araştırması. Çev. Baray, A.Ş., Esnaf, Ş. Literatür Yayıncılık, 900s, İstanbul.
29. Toth, P., Vigo, D., 2002. Vehicle Routing Problem. Siam, 367p, Philadelphia.
30. Ünsal, Ö., 2017. Dinamik Okul Servisi Rotalama Probleminin Sezgisel Yöntemler ve Kümeleme Teknikleri Kullanılarak Gerçek Zamanlı Optimizasyonu. Doktora Tezi. Süleyman Demirel Üniversitesi, Türkiye.
31. 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, Türkiye.