- Mühendislik Bilimleri ve Tasarım Dergisi
- Vol: 4 Issue: 3
- KAPASİTE KISITLI ARAÇ ROTALAMA PROBLEMLERİNDE BAŞLANGIÇ ROTALARININ KURULMASI İÇİN YENİ BİR ALGORİTM...
KAPASİTE KISITLI ARAÇ ROTALAMA PROBLEMLERİNDE BAŞLANGIÇ ROTALARININ KURULMASI İÇİN YENİ BİR ALGORİTMA
Authors : Erdal Aydemir, Kenan Karagül, Sezai Tokat
Pages : 215-226
Doi:10.21923/jesd.60313
View : 23 | Download : 6
Publication Date : 2016-12-26
Article Type : Research
Abstract :Kapasiteli araç rotalama problemi NP-Zor problem sınıfında yer alır ve gerçek hayat uygulamalarında kesin yöntemlerle çözümün bulunması genellikle olurlu değildir. Bundan dolayı, sezgisel veya stokastik yöntemler seçeneği çözüm aracı olarak kullanılır. Bu tür algoritmaların ise çözüm kaliteleri doğrudan başlangıç çözüm uzayı ile ilgilidir. Genetik algoritmalar uyarlamalı, stokastik ve evrim kuramındaki doğal seçim ve genetik bilgiden ilham alan sezgisel bir arama algoritmasıdır. Bu çalışmada, Newton’un çekim yasasını temel alan bir algoritma önerilmiştir ve GA başlangıç popülasyonunu elde etmek ve başarımını iyileştirmek amacı ile kullanılmıştır. Önerilen algoritma araç rotalama problemleri için başlangıç çözümleri üretmektedir. Augerat vd. (1995) tarafından geliştirilen A, B ve P grupları olarak ifade edilen 74 adet kapasiteli araç rotalama test problemi üzerinde önerilen algoritma koşturulmuştur. Sırasıyla A, B ve P grupları için bilinen en iyi sonuçlardan, grupların ortalama sapmaları %37.95, %32.10 ve %31.45 olarak elde edilmiştir. Daha sonra, permütasyon kodlamalı genetik algoritma, sırasıyla 0.9 ve 0.1 olasılığına sahip tek nokta çaprazlama, mutasyon, 1000 nesil ve 10 kez çalıştırılmak üzere tasarlanmış ve permütasyon kodlamalı genetik algoritma için başlangıç uzayı olarak önerilen yöntemin ürettiği çözümler kullanılmıştır. Genetik algoritma ile elde edilen sonuçların gruplar için bilinen en iyi çözümlerin ortalamalarından ortalama sapma seviyeleri sırasıyla %7.15, %4.33 ve %6.33 olarak elde edilmiştir.Keywords :