Bulanık c-ortalama algoritması ile başlangıç çözümü iyileştirilmiş tavlama benzetimi algoritması ile kapasiteli araç rotalama problemi

Year 2022, Volume: 37 Issue: 2, 783 - 798, 28.02.2022

Ahmet Fatih Eker , Ahmet Yunus Çil , İbrahim Çil

https://doi.org/10.17341/gazimmfd.784653

Cited By: 3

Abstract

Bu çalışmada, popüler bir problem olan Araç Rotalama Problemi (VRP) üzerinde çalışılmıştır. Problemi çözmek için meta-sezgisel bir yöntem olan Tavlama Benzetimi (SA) kullanılmıştır. Genel olarak SA 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 Bulanık c-ortalama (FCM) 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 SA ve FCM ile başlangıç çözümü iyileştirilmiş SA ile problem çözülmüştür. FCM başlangıç arama uzayını %57 oranında azaltmıştır. Dolayısıyla FCM aynı çözüm süresinde ve aynı iterasyon sayısında optimum çözüme daha yakın sonuçlar vermiştir. Çözüm sonuçları karşılaştırılmıştır.

Keywords

Araç rotalama problemi,, tavlama benzetimi,, bulanık c-ortalama,, optimizasyon

Capacitated vehicle routing problem with simulated annealing algorithm with initial solution improved with fuzzy c-means algorithm

Abstract

In this market, a popular problem, Vehicle Routing Problem (VRP), has been studied. Simulation Annealing (SA), a meta-heuristic method, was used to solve the problem. 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 Fuzzy c-mean (FCM) 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.

Keywords

Vehicle routing problem,, simulated annealing,, fuzzy c-means,, optimization

References

• Referans1 Doç. Dr. Gülşen Aydın KESKİN Balıkesir Üniversitesi, Endüstri Mühendisliği Bölümü [e-mail] [phone] (6405)
• Referans2 Dr.Öğr.Üyesi Halil İbrahim DEMİR Sakarya Üniversitesi, Endüstri Mühendisliği Bölümü [e-mail]