- Gazi Mühendislik Bilimleri Dergisi
- Vol: 7 Issue: 2
- A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs
A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs
Authors : Erdener Özçetin, Gürkan Öztürk
Pages : 90-98
View : 17 | Download : 3
Publication Date : 2021-08-30
Article Type : Other
Abstract :Bu çalışmada, NP-Hard kombinatorik optimizasyon problemlerinden olan araç rotalama problemi (ARP), grafik işlem birimleri (GPU) üzerinde ele alınmıştır. Problem boyutunun büyümesiyle birlikte ARP'nin herhangi bir türünü optimal olarak çözmek oldukça zorlaşmaktadır. Araştırmacılar bu yüzden metasezgisel yöntemlere yönelmektedir. Her ne kadar bu metasezgisel algoritmalar kabul edilebilir sürelerde optimale yakın sonuçlar üretse de büyük boyutlu problemler için bu durum farklıdır. Bu durumu aşmak için, araştırmacılar önerilen algoritmalar için yeni, hızlı ve akıllıca tasarlanmış paralel operatörlere ihtiyacı bulunmaktadır. Bu operatörlerin başarısı doğrudan çözümün temsil edilme şekline bağlıdır. Bu makale, ARP'yi GPU'lar üzerinde etkin bir şekilde ele alabilmek için yeni bir permütasyon tabanlı çözüm gösterim tekniği (π +) sunmaktadır. Sonuçlar, önerilen tekniğin hesaplamaları hızlandırmak için birçok algoritmada kullanılabileceğini göstermektedir.Keywords : Araç rotalama problemi, Paralel programlama, GPU