Bulanık C ve K-ortalamalarla başlangıç çözümü oluşturulmuş tavlama benzetimi hibrit algoritması ile kapasite kısıtlı araç rotalama probleminin çözümü

Abstract

Bu çalışmada, popüler bir problem olan Araç Rotalama Problemi (ARP) üzerinde çalışılmıştır. Bu problemde müşteriler veya şehirler ziyaret edilmeli ve ürünler haritadaki bir noktadan başlayarak her müşteriye veya şehire taşınmalıdır. Amaç, taşıma sorununu çözerek ürünleri teslim edebilmektir. Bu problem az sayıda şehir veya müşteri ile çözülmesi kolay gibi görünse de öyle değildir. Çünkü çok fazla kısıtı sağlamak zorundadır. Dolayısıyla mevcut hesaplama gücü ile bu sorun çözülemez. Müşteri sayısı arttıkça yapılacak hesaplamalar da katlanarak artmaktadır, çünkü her müşteri için tüm kısıtlar sağlanmalı ve nispeten iyi bir çözüme kısa sürede ulaşılmalıdır. Bu çalışmadaki problemi çözmek için meta-sezgisel bir yöntem olan Tavlama Benzetimi (TB) kullanılmıştır. Genel olarak TB algoritması, metallerin tavlama işlemini taklit eden değişken sıcaklık parametresine göre tekrarlayan bir işlemdir. Bizim çalışmamız için bu yöntemin en büyük sorunu, algoritmayı başlatmak için kullanılan başlangıç çözümünü rassal olarak oluşturmasıdır. Bu sebepten dolayı optimum çözüme ulaşmak için kullanılan arama uzayı büyük olduğundan, çözüm süresi (veya iterasyon sayısı) artacaktır. Daha iyi bir başlangıç çözümüyle optimum çözüme ulaşmak daha kısa zaman alacaktır. Ulaşmak istediğimiz optimum çözüm minimum mesafe olduğundan, başlangıç çözümünü iyileştirmek için K-ortalamalar (KO) ve Bulanık c-ortalamalar (BCO) kullanılarak rotalar kümelenmiştir. Bulanık mantık gereği, her verinin 0-1 arasında birden fazla kümeye dahil olabilmesi durumu, algoritmanın her çözümünde başlangıç çözümünü değiştireceğinden dolayı optimum çözüme yaklaşma durumu olacaktır. Aynı veriler ve aynı parametreler kullanılarak rassal başlangıç çözümü kullanan TB ve BCO ile başlangıç çözümü iyileştirilmiş TB ile problem çözülmüştür. BCO başlangıç arama uzayını %57 oranında azaltmıştır. Dolayısıyla BCO aynı çözüm süresinde ve aynı iretasyon sayısında optimum çözüme daha yakın sonuçlar vermiştir. Çözüm sonuçları karşılaştırılmıştır.

In this study, a popular problem, Vehicle Routing Problem (VRP), has been studied. In this problem, customers or cities should be visited and transported to the customer or city, starting from a point in the products. The aim is to deliver products by solving the transportation problem. While this problem seems easy to solve with a small number of cities or customers, it is not. Because it has to provide too many constraints. Therefore, this problem cannot be solved with the available computing power. As the number of customers increases, the calculations to be made increase exponentially, because all constraints must be met for each customer and a relatively good solution must be reached in a short time. Simulation Annealing (SA), a meta-heuristic method, was used to solve the problem in this study. In general, the SA algorithm is a repetitive process based on the variable temperature parameter that mimics the annealing process of metals. The biggest problem with this method for our study is that it randomly generates the initial solution used to start the algorithm. For this reason, because the search space used to reach the optimum solution is large, the solution time (or number of iterations) will increase. With a better initial solution, it will take less time to reach the optimum solution. Since the optimum solution we want to reach is the minimum distance, the routes have been clustered using K-means and Fuzzy c-mean to improve the initial solution. Due to fuzzy logic, each data can be included in more than one cluster between 0-1, since it will change the initial solution in every solution of the algorithm, there will be a case of approaching the optimum solution. Using the same data and the same parameters, the problem was solved with SA using a random starting solution and with an initial solution optimized SA with FCM. FCM reduced the initial search space by 57%. Therefore, FCM gave results closer to the optimum solution in the same solution time and the same number of rashes. Solution results are compared.