Makine öğrenmesi ile araç rotalama problemi için önce-kümele sonra-rotala yöntemlerinin incelenmesi
Investigation of cluster-first route-second methods for vehicle routing problem using machine learning
Yazar: SEDAT GÜZELŞEMME
Danışman: DOÇ. DR. FARUK SERİN
Munzur Üniversitesi / Lisansüstü Eğitim Enstitüsü / Mühendislik Yönetimi Ana Bilim Dalı
Derece: Yüksek Lisans, 2024
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Eğitim ve Öğretim = Education and Training

Özet:
Araç rotalama, lojistik endüstrisinde dağıtım operasyonlarını optimize etmek, yakıt/elektrık tüketimini azaltmak ve teslimat sürelerini iyileştirmek için kullanılmaktadır. Ancak, karmaşıklık seviyesi arttıkça büyük ölçekli rotalama problemlerinin çözümü zor hale gelebilir. Günümüzde bir çok amaç için kullanılan vasıtaların bir noktadan diğer bir noktaya ulaşana kadar izlediği güzergahın üretilmesi kaynak ve zaman ihtiyacı bakımından oldukça maliyetli ve zor bir problem olarak bilinmektedir. Özellikle güzergah oluşturmak için kullanılacak nokta sayısı fazla ise karmaşıklık seviyesi artmakta ve çözülebilir olma özelliği azalmaktadır. Bu durumda, önce kümeleme sonra rotalama yaklaşımı önemli bir çözüm sunar. Bu yaklaşım, büyük ve karmaşık rotalama problemlerini ele almak için önce kümeleme algoritmalarını kullanarak karmaşıklık olan problemi daha küçük ve anlamlı kümelere ayırmak için kullanılan bir yaklaşımdır. Oluşan her bir kümenin içindeki teslimat noktaları arasında optimal rotalar belirlenir. Böylece büyük bir rotalama problemi daha küçük ve yönetilebilir alt problemlere bölünür. Kümeleri daha küçük parçalara ayırmak, alt kümelerin daha az teslimat noktası içermesini sağlamakla beraber, rotalama algoritmalarının daha hızlı çalışmasını ve daha optimize edilmiş rotaların bulunmasını sağlar. Bu çalışmada, farklı kümeleme algoritmaları (k-ortalama, DBSCAN, BIRCH, OPTICS) üç farklı veri seti üzerinde ayrı ayrı çalıştırılarak elde edilen sonuçlar karşılaştırılmıştır. Vektör veri seti için elde edilen bulgulara göre k-ortalama en iyi sonucu ürettiği görülmüştür. Deneysel sonuçlar, önce-kümele sonra-rotala yaklaşımının hesaplama karmaşıklığını düşürerek araç rotalama problemlerinde yol mesafesini optimize edip seyahat maliyetini düşürdüğünü göstermektedir.

Abstract:
Vehicle routing is an important operation in the logistics industry to optimize travel, reduce fuel/electricity consumption, and improve delivery times. However, as the complexity increases, solving large-scale routing problems can become challenging. In today's world, generating the route that vehicles follow from one point to another is known to be a costly and challenging problem in terms of resources and time, given the various purposes for which vehicles are used. Particularly when the number of points used for route construction is substantial, the level of complexity escalates, and the feasibility of resolution diminishes. In this scenario, the cluster-first route-second approach presents a significant solution. This approach involves using clustering algorithms initially to decompose the complexity of the problem into smaller and meaningful clusters, aiming to address large and intricate routing problems. Optimal routes are determined between delivery points within each of the resulting clusters. Consequently, a large routing problem is divided into smaller and more manageable sub-problems. Dividing clusters into smaller segments ensures that sub-clusters contain fewer delivery points, facilitating faster operation of routing algorithms and the discovery of more optimized routes. In this study, the results obtained by different clustering algorithms (K-Means, DBSCAN, BIRCH, OPTICS) on three different datasets were compared. According to the findings obtained for the main dataset, K-Means produced the best results. Experimental results demonstrate that the cluster-first route-second approach reduces computational complexity and optimizes travel distances, thereby reducing travel costs in vehicle routing problems.