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

Yıl 2018, , 7 - 20, 23.03.2018

Özkan Ünsal , Tuncay Yiğit

https://doi.org/10.21923/jesd.340220

Cited By: 5

Öz

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.

Anahtar Kelimeler

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

Öz

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.

Anahtar Kelimeler

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

Kaynakça

• 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.
• 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.
• Bögl, M., Doerner, K.F., Parragh, S.N., 2015. The School Bus Routing and Scheduling Problem with Transfers. Networks, 65(2), 180-203.
• Carpaneto, G., Toth, P., 1980. Some New Branching and Bounding Criteria for the Symmetric Traveling Salesman Problem. Management Science, 26(7), 736–743.
• 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.
• Chabrier, A., 2006. Vehicle Routing Problem with Elementary Shortest Path Based Column Generation. Computers and Operations Research, 33(10), 2972-2990.
• Christofides, N., Mingozzi, A., Toth, P., 1981. State-Space Relaxation Procedures for the Computation of Bounds to Routing Problems. Networks, 11(2), 145-164.
• 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.
• 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.
• Ç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.
• Ç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.
• 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.
• Fisher, M.L., 1994. Optimal Solution of Vehicle Routing Problems using Minumum k-trees. Operations Research, 42(4), 626–642.
• Fukasawa, R., 2006. Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming, 106(3), 491-511.
• Laporte, G., Nobert, Y., Desrochers, M., 1985. Optimal Routing Under Capacity and Distance Restrictions. Operations Research, 33, 1058-1073.
• Laporte, G., 1992. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 59, 345-358.
• 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.
• 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.
• 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.
• Nazif, H., Lee, S.L., 2012. Optimised Crossover Genetic Algorithm for Capacitated Vehicle Routing Problem. Applied Mathematical Modelling, 36, 2110–2117.
• Ö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.
• Padberg, M., Rinaldi, G., 1991. A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM, 33, 60–100.
• Park, J., Kim, B., 2010. The School Bus Routing Problem: A review. European Journal of Operational Research, 202, 311–319.
• Ralphs, T.K., Kopman, L., Pulleyblank, W.R., Trotter, L.E., 2003. On the Capacitated Vehicle Routing Problem. Mathematical Programming Series B, 94, 343.
• 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.
• 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.
• 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.
• Taha, H.A., 2000. Yöneylem Araştırması. Çev. Baray, A.Ş., Esnaf, Ş. Literatür Yayıncılık, 900s, İstanbul.
• Toth, P., Vigo, D., 2002. Vehicle Routing Problem. Siam, 367p, Philadelphia.
• Ü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.
• 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.