Dinamik yapıda yeni bir genetik algoritma önerisi: Seçilim operatörü kararcı genetik algoritma (SOKGA) ve asimetrik kapasiteli araç rotalama problemi üzerine bir uygulama
A new genetic algorithm proposal with dynamic structure: Selection operator decider genetic algorithm (SODGA) and an application on asymmetric capacitated vehicle routing problem
Yazar: BÜŞRA MENİZ
Danışman: PROF. DR. FATMA TİRYAKİ
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Doktora, 2024
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Matematik = Mathematics ; İşletme = Business Administration
Dizin: Araç yönlendirme problemi = Vehicle routing problem ; Genetik algoritmalar = Genetic algorithms ; Çok kriterli karar verme = Multi criteria decision making

Özet:
Genetik algoritma, gerçek hayattaki durumlarla doğrudan ilişkili olan optimizasyon problemlerinin karmaşıklığıyla başa çıkmak için güçlü ve esnek bir metasezgisel tekniktir. Bir optimizasyon probleminin çözümünün araştırılmasındaki öncelik, hesaplanması olanaksız optimal değere ulaşmaya çalışmak yerine, çok daha az çabayla optimale yeterince yakın bir çözüm elde etmek olabilir. Genetik algoritmalar, çözüm uzayındaki bir grup rastgele nokta (aday çözüm) ile başlayarak, bu noktaların iterasyonlar sırasında daha iyi çözümlere evrilmesini sağlamaya çalışırlar. Çözümlerin kalitesini arttırma amacına ise algoritmanın temel araçları olan genetik operatörler hizmet eder. Bir genetik algoritmanın çalışma performansı genetik operatörlere bağlı olarak önemli oranda değişebilir. Her operatör türünün iyi ve kötü yanları olmasına rağmen, seçilim operatörü genetik algoritmanın başarısını diğer operatör türlerine göre daha fazla etkileyebilir. Geleneksel genetik algoritmalar önceden belirlenmiş ve sabit genetik operatörler ile başlar ve tüm iterasyonlar da aynı operatörler ile devam eder. Bu tez çalışmasında seçilim operatörlerinin, iterasyonun ilerleyişine göre dinamik olarak ayarlanmasının genetik algoritmada özellikle sürenin azaltılması açısından çok önemli bir strateji olduğu kıyaslamalar aracılığıyla gösterilecektir. Bu amaçla, mevcut iterasyonda daha avantajlı olan operatöre kendi kendine karar veren bir sistem ile farklı seçilim operatörlerini kullanabilen yeni bir genetik algoritma yapısı önerilecektir. Bunun için, basit ve etkili bir çok kriterli karar verme yöntemi olarak bilinen TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), tasarlanacak bir dinamik karar matrisi ile genetik algoritmaya entegre edilecektir. Önerdiğimiz yeni genetik algoritma, Seçilim Operatörü Kararcı Genetik Algoritma (SOKGA), iterasyonlar içinde TOPSIS'i çalıştırarak her iterasyon için daha faydalı olan seçilim operatörüne kendiliğinden karar verebilir ve bu özelliği ile benzersizdir.

Ürünlerin müşterilere en uygun koşullarda ulaştırılması, şirketler için en az üretimin kendisi kadar önemlidir. Dikkate alınması gereken optimizasyon stratejilerinden biri, en az sayıda araçla taşımacılık yaparken lokasyonlar arasında en az mesafeye sahip rotaların seçilmesidir. Diğer bir deyişle, araç rotalama probleminin, özellikle de daha gerçekçi bir modelleme yaklaşımı olan kapasiteli araç rotalama probleminin ve çözümünün incelenmesi önem arz etmektedir. Günlük dağıtım koordinasyonuna ihtiyaç duyan ve müşterilere sık sık dağıtım yapan işletmeler için dağıtımın zamanında bitirilmesi de büyük önem taşımaktadır. Tezimizin bir diğer odak noktasında da önerdiğimiz genetik algoritmanın bir gerçek hayat araç rotalama problemine uygulanması yer almaktadır. Ele aldığımız problemde, gerçek veri kullanımından kaynaklı, noktalar arasındaki gidiş ve dönüş mesafelerinin farklı olduğu asimetrik kapasiteli araç rotalama problemidir. Modelimizde, İstanbul Halk Ekmek işletmesinin Anadolu yakasında bulunan fabrikasından, tamamı Anadolu yakasında bulunan halk ekmek büfelerine günde üç kez dağıtımı olan dağıtım ağı incelenecektir. 215 halk ekmek büfesi içeren problem, Seçilim Operatörü Kararcı Genetik Algoritma ile çözülecek ve optimize edilmiş bir ulaşım ağı sunulacaktır. Rotaların optimizasyonu ile taşıma süresinin, maliyetin ve trafik yoğunluğunun optimize edilmesi öngörülmektedir. Çevresel fayda açısından bakıldığında ise, egzoz emisyonundan kaynaklanan karbon ayak izinin azaltılması ve geri dönüştürülemeyen yakıt tüketiminin en aza indirilmesi ile sürdürülebilir ve çevre dostu olması hedeflenmektedir.

Abstract:
The genetic algorithm is a powerful and flexible metaheuristic technique for dealing with the complexity of optimization problems that are directly related to real-life situations. The priority in the search for a solution to an optimization problem may be to obtain a solution close enough to optimal with much less effort instead of trying to reach the optimal value that is unlikely to be computed. Genetic algorithms start with a group of random points (candidate solutions) in the solution space and try to provide these points to evolve into better solutions through iterations. The genetic operators, which are the essential tools of the algorithm, serve the goal of increasing the quality of the solutions. The execution performance of a genetic algorithm can vary considerably depending on the genetic operators. Although each type of operator has its good and bad sides, the selection operator can affect the success of the genetic algorithm more than the other operator types. Traditional genetic algorithms initialize with predetermined and fixed genetic operators and continue with the same operators in all iterations. In this thesis study, it will be shown that the dynamical adjustment of the selection operators according to the progress of the iteration is a very important strategy through benchmarks, especially in terms of time reduction for the genetic algorithm. For this purpose, a new genetic algorithm structure that can use different selection operators with a system that decides on its own which is the more advantageous operator for the current iteration will be proposed. Hence, TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), known as a simple and effective multi-criteria decision-making method, will be integrated into the genetic algorithm with a dynamic decision matrix to be designed. The novel genetic algorithm we propose, the Selection Operator Decider Genetic Algorithm (SODGA), can selfly decide the selection operator that is more favorable, and it is unique with this feature.

Delivery of the products to customers under optimal conditions is as important for companies as production itself. One of the optimization strategies to regard is to select routes with the least distance between locations when transporting with the least number of vehicles. In other words, it is essential to study the solution for the vehicle routing problem, particularly the capacitated vehicle routing problem and its solution, which is a more realistic modeling approach. For businesses that need daily distribution coordination and make frequent deliveries to customers, finishing the delivery on time is also of great importance. The other focus of our thesis is the application of the genetic algorithm that we propose to a real-life vehicle routing problem. The problem we handle is an asymmetric capacitated vehicle routing problem with different going and returning distances between points induced by the usage of actual data. In our model, the distribution network of Istanbul People's Bread company from the factory located on the Asian side, which distributes all sited on the Asian side bread-selling buffets three times a day, will be analyzed. The problem, which involves 215 bread-selling buffets, will be solved with the Selection Operator Decider Genetic Algorithm, and an optimized transportation network will be presented. By the optimization of the routes, it is anticipated to optimize the transport time, cost, and traffic density. In terms of environmental benefits, it is aimed to be sustainable and environmentally friendly by the reduction of the carbon footprint that occurs from exhaust emissions and the minimization of non-recyclable fuel consumption.