Malatya Büyükşehir Belediyesi ilaçlama araçlarının rotalarının metasezgisel algoritmalarla belirlenmesi

Abstract

Bu tez çalışmasında, Malatya Büyükşehir Belediyesi'nin ilaçlama araçlarının rotalarının optimizasyonu için metasezgisel yöntemler ile çok aşamalı bir uygulama geliştirilmiş ve sonuçları paylaşılmıştır. Çok aşamalı uygulamanın ilk aşamasında, ilgili kısıtlar göz önünde bulundurularak mahallelerin araçlara optimum dağıtımı ve rotalanması yapılmıştır. Bu aşamada problem, araç rotalama problem çeşidi olan Zaman Pencereli Araç Rotalama Problemi olup, Genetik Algoritma (GA) ile çözüm elde edilmiştir. İkinci aşama ise ilk aşamada yapılan rotalama ile artık birer bölge olarak düşünülen alanlarda ilaçlama yapacak araçların caddeleri/sokakları minumum mesafe ile gezinmesi amaçlanmaktadır. Bu aşamada ise ayrıt rotalama problemlerinden olan Çinli Postacı Problemi (ÇPP) olup, çözümü için Yapay Arı Kolonisi Algoritması (YAKA) kullanılmıştır. ÇPP'nin en önemli adımı tek dereceli düğümlerin aralarında minumum eşleşmesidir. Bu çalışmada minumum eşleşmenin sağlanması için YAKA'nın parametre değişimi kısmına modifiye işlemi yapılmıştır. Böylece çok büyük boyutlu graflarda bile optimum eşleşme başarılı şekilde sağlanmış olup, YAKA'ya yapılan modifiye işlemi literatüre kazandırılmıştır. Optimum eşleşme ile bölgeler için elde edilen Eulerian graflar üzerinde, Euler tur oluşturacak rotalar elde edilmiştir. Çok aşamalı uygulamanın verileri olan mahalleler arası mesafe matrisi ve cadde/sokak mesafe matrisleri, coğrafi bilgi sistemi (CBS) yazılımlarından QGIS yazılımı ile bizzat bu çalışma için oluşturulmuş gerçek ve orjinal verilerdir. Bu çok aşamalı uygulama, bu mesafe matrisleri üzerinde uygulanmış ve optimum sonuçlar elde edilmiştir. ANAHTAR KELİMELER: Araç Rotalama, Ayrıt Rotalama, Çinli Postacı Problemi, Eulerian Graf, Euler Tur, Metasezgisel Yöntemler, Genetik Algoritma, Yapay Arı Kolonisi Algoritması, Optimizasyon, Coğrafi Bilgi Sistemleri, QGIS Yazılımı.

In this thesis, a multistage application has been developed to optimize the routes of the pesticide vehicles of Malatya Metropolitan Municipality with metaheuristic methods and the results have been shared. In the first stage of multistage application, the optimum distribution and routing of the neighborhoods to the vehicles has been made considering the related constraints. At this stage, the problem is the Vehicle Routing Problem with Time Window which is the type of vehicle routing problem and it has been solved using Genetic Algorithm (GA). In the second stage, the areas which were obtained as a result of the routing in the first stage are considered as the region and it is aimed that the spraying vehicles will travel the streets / roads in these regions with minimum distance. At this second stage, the problem is the Chinese Postman Problem (CPP) which is one of the problems of arc routing and it has been solved using Artificial Bee Colony (ABC) Algorithm. The most important step of the CPP is the minimum matching of odd degree nodes. In this study, it is modified to the parameter change part of ABC algorithm to provide minumum matching. Thus, optimum matching is achieved successfully even in very large graphs and the modification made to ABC algorithm has been introduced into the literature. Later, on Eulerian graphs obtained for regions with the optimum matching, Euler tour routes have been obtained. The neighborhoods distance matrix and the street / road distance matrices which is the data of the multistage application, were constituted for this study with the QGIS software from the geographic information system (GIS) software and are the real, original data. This multistage application has been applied on these distance matrices and optimum results have been obtained. KEYWORDS: Vehicle Routing, Arc Routing, Chinese Postman Problem, Eulerian Graph, Euler Tour, Metaheuristic Methods, Genetic Algorithm, Artificial Bee Colony Algorithm, Optimization, Georgraphic Information Systems, QGIS Software.