Araç rotalama problemleri için kümeleme algoritmalari ile veri işleme
Data processing with clustering algorithms for vehicle routing problems
Yazar: KEREM BÜYÜKÖZDEMİR
Danışman: DR. ÖĞR. ÜYESİ ANIL BAŞ ; DOÇ. DR. KAZIM YILDIZ
Marmara Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Mühendislik Bilimleri = Engineering Sciences
Dizin: Algoritmalar = Algorithms ; Bulanık kümeler = Fuzzy sets ; Kümeleme = Clustering ; Rotalama =

Özet:
Günümüzde, gerçekleşen lojistik tedarik operasyonlarında, ürünlerin kabul edilebilir bir zaman aralığında tedarik edilmesi büyük bir önem arz etmektedir. Rotaların zaman maliyeti açısından optimum olması, gerçekleştirilecek olan lojistik operasyonlarının başarışını doğrudan etkilemektedir. Teslimat noktalarına, en kısa ve en az maliyetli rotaların tasarlanması ve oluşturulmasına literatür içerisinde "Araç Rotalama Problemi" (VRP) adı verilmektedir. Araç rotalama problemi ilk olarak Dantzig ve Ramser tarafından dile getirilmiştir. Sabit bir noktadan başlayarak, uğranması önceden planlanmış tüm noktalara en kısa zaman ve en düşük maliyet ile uğranmasını amaçlayan bir rotalama problemidir. Rotalama problemlerinin, talep miktarı, aracın kapasitesi, zaman aralığı, mevcut araç sayısı, rota uzunluğu gibi kısıtına ve kapsamına göre birçok çeşidi bulunmaktadır. Araç rotalama problemi günümüzde popüler optimizasyon problemleri arasında yer almaktadırlar. Araç rotalama problemleri için, genel geçer, optimum çözümü bulacak algoritmanın geliştirilmesi amacıyla birçok çalışma yapılmıştır. Ancak tüm araç rotalama problemlerine uyum sağlayabilecek ve en optimum çözümü vermeyi garanti edecek bir matematiksel model geliştirilememiştir. Bunun nedeni araç rotalama problemlerinin karmaşık yapılarıdır. Ayrıca problemlerin kendilerine özgü kısıtları olması nedeniyle, genel bir model oluşturma çabası, günümüze kadar olumlu sonuçlar ortaya koyamamıştır. Araç rotalama problemlerinin en optimum çözümlerinin bulunması, çözüm uzayının tamamının taranması ve çözümlenmesi ile bulunabilir. Lakin uğranılması gereken noktaların ve kısıtların sayıca fazla olduğu durumlarla araç rotalama problemlerinde sıkça karşılaşılmaktadır. Bu durumlarda en optimum çözümün bulunması makul, kabul edilebilir, zamanlar içerisinde mümkün olamamaktadır. Bu nedenle araç rotalama problemlerine çözüm arayışı aşamasında, sezgisel veya meta-sezgisel yöntemlere başvurulmaktadır. Sezgisel yöntemler, kısa ve makul hesaplama süresi içerisinde optimum duruma yakın, kaliteli çözümler üreten optimizasyon teknikleridir.  Sezgisel algoritmalardan biri olan tasarruf algoritması, her noktanın başlangıç noktasına olan uzaklıkları ile ilişkili olarak rotayı minimize, dolaşılan düğümleri maksimize etmeyi amaçlamaktadır. Tasarruf algoritması çok kısıtlı problemlerde çalışma prensibi ve son seçilen düğüm üzerine ekleme şeklinde iteratif ilerlemesi sebebi ile, çözüm uzayının belirli noktalarına yönelterek kümülatif çözümlemeyi zorlaştırmakta ve makul sonuçlar ortaya koymayı zorlaştırmaktadır. Ancak mevcut noktalar üzerinde, bir gruplama veya kümeleme algoritmasının çalıştırılması, benzer özellikleri taşıyan noktaların bir araya gelmesine sağlayarak, çözüm performansının artırılması ve rotalama maliyetlerinin azalmasına olumlu bir etkide bulunacaktır. Bu tez çalışmasında, veri setinde önceden belirlenmiş noktalar için, rotalama algoritmalarının çalıştırılmasına ön hazırlık yapılmaktadır. Tanımlanmış noktalar için veri seti içerisindeki tekrar eden noktalar çıkarılmıştır. Elde edilen noktalar için ise, tüm olası ikililer için, uzaklıklar, gerçek hayat verisi üzerinden hesaplanmış ve uzaklıklar matrisi oluşturulmuştur. İlk adım, önerilecek olan algoritmanın çalışması için hazırlık kapsamındadır. Çalışmanın ikinci adımında ise, sezgisel veya meta-sezgisel algoritmalar kullanılarak, araç rotalama problemine optimum ya da optimuma yakın makul kabul edilebilecek seviyede bir çözüm geliştirilmesi amaçlanmaktadır. Çalışmada kullanılacak olan sezgisel algoritma, k-ortalamalar ve bulanık c-ortalamalar gibi kümeleme algoritmalarını bir ön işleme adımı olarak kullanmaktadır. Buradaki temel yaklaşım, algoritma öncesi benzer noktaların bir araya getirilip çözüm performansının artırılmasıdır. Bu tez çalışmasının sonuçlarına göre, kümeleme algoritmalarının ön işleme adımı olarak kullanılması, sezgisel algoritmanın kümeleme performansını artırmıştır. K-ortalamalar kümeleme algoritması ile birlikte kullanımda, toplam rota uzunluğunda %28'lik bir iyileşme gözlenmektedir. Bulanık C-ortalamalar algoritması ile kullanımda ise, %32'lik bir iyileşme oranı yakalanmıştır.

Abstract:
In logistics supply operations, it is of great importance that the products are supplied at an acceptable time interval. The fact that the routes are optimal in terms of time cost directly affects the success of the logistics operations to be carried out. The design and creation of the shortest and least costly routes to the delivery points is referred to as the "Vehicle Routing Problem" (VRP) in the literature. The vehicle routing problem was first mentioned by Dantzig and Ramser. It is a routing problem that aims to reach all previously planned points, starting from a fixed point, with the shortest time and lowest cost. There are many types of routing problems depending on the constraint and scope such as the amount of demand, the capacity of the vehicle, the time interval, the number of available vehicles, the length of the route. VRP is one of the popular optimization problems today. For vehicle routing problems, many studies have been carried out to develop an algorithm that will find the general and optimum solution. However, a mathematical model that can adapt to all vehicle routing problems and guarantee the optimum solution has not been developed. This is because of the complex nature of vehicle routing problems. In addition, since each problem has its own limitations, the effort to create a general model has not yielded positive results until today. Finding the most optimal solutions for vehicle routing problems can be found by scanning and solving the entire solution space. However, vehicle routing problems are frequently encountered in situations where the number of points and constraints to be visited are high. In these cases, it is not possible to find the optimum solution in a reasonable, acceptable time. For this reason, heuristic or meta-heuristic methods are used in the search for solutions to vehicle routing problems. Heuristics are optimization techniques that produce close-to-optimal, quality solutions within a short and reasonable computation time.The savings algorithm, one of the heuristic algorithms, aims to minimize the route and maximize the nodes circulated in relation to the distances of each point from the starting point. The saving algorithm complicates the cumulative analysis by directing it to certain points of the solution space and makes it difficult to produce reasonable results due to its working principle in very constrained problems and its iterative progress in the form of addition on the last selected node. However, running a grouping or clustering algorithm on existing points will have a positive effect on increasing solution performance and reducing routing costs by bringing together points with similar characteristics. In this thesis, preliminary preparation is made for running routing algorithms for predetermined points in the data set. For the defined points, the repeating points in the data set were removed. For the obtained points, for all possible pairs, the distances were calculated over the real-life data and the distance matrix was created. The first step is in preparation for the proposed algorithm to work. In the second step of the study, it is aimed to develop an optimum or near-optimally reasonable solution to the vehicle routing problem by using heuristic or meta-heuristic algorithms. The heuristic algorithm to be used in the study uses clustering algorithms such as k-means and fuzzy c-means as a preprocessing step. The basic approach here is to bring together similar points before the algorithm and increase the solution performance. According to this thesis results, the use of clustering algorithms as a preprocessing step has increased the clustering performance of the heuristic algorithm. When used together with the K-means clustering algorithm, a 28% improvement in total route length is observed. When using the fuzzy C-means algorithm, an improvement rate of 32% has been achieved.