Açık araç rotalama problemi için metasezgisel algoritma tasarımı ve uygulaması

Abstract

Bu çalışmada, firmaların daha çok üçüncü parti lojistik hizmetleri kullanması ile birlikte, uygulamada yaygın şekilde ortaya çıkan Açık Araç Rotalama Problemi ele alınmıştır. Bu problem, yüksek boyutlu ve karmaşık eniyileme problemleri sınıfında yer almaktadır. Öncelikle, heterojen araç filosunun bulunduğu bir gerçek hayat problemi için model tabanında matematiksel modeller ile popülasyon temelli bir metasezgisel algoritmanın yer aldığı bir karar destek sistemi geliştirilmiştir. Daha sonra, özellikle büyük boyutlu problemleri etkin şekilde çözmek üzere üç evreli bir Değişken Komşuluk Arama Algoritması önerilmiştir. Önerilen bu yöntemde dört adet rota içi ve dört adet rotalar arası olmak üzere sekiz farklı komşuluk ve sarsma stratejisi kullanılmıştır. Yöntemin performansı literatür test problemleri üzerinde test edilmiş ve başarısı karşılaştırmalı olarak raporlanmıştır. Ayrıca, önerilen değişken komşuluk arama algoritmasının eş zamanlı hesaplamaya uygun olan kısımlarının, grafik işlem birimleri üzerinde paralelleştirilmesi için farklı stratejiler tasarlanmış ve uygulanmıştır. Bu stratejilerin uygulanması ile elde edilen paralel yöntem, seri versiyonuna göre anlamlı şekilde hızlandırılmıştır.

In this study, the Open Vehicle Routing Problem, which is widely employed by the companies in practice with the use of third party logistics services, is discussed. This problem is in the class of high-dimensional and complex optimization problems. First of all, a decision support system based on a mathematical models and a population based meta-heuristic algorithm was developed for a real-life problem with a heterogeneous vehicle fleet. Then, a three-phase Variable Neighborhood Search Algorithm was proposed in order to solve large-scale problems efficiently. In this proposed method, eight different neighborhoods and shaking strategies was used. The performance of the method was tested on literature test problems and its success was reported comparatively. In addition, different strategies were designed and implemented for the parallelization of parts of the proposed variable neighborhood search algorithm that are suitable for simultaneous calculation on the graphics processing units. A significant speed up was observed in the parallel method obtained by the implementation of these strategies compared to the serial version.