Optimizasyon problemlerinin çözümünde melez metasezgisel bir algoritmanın tasarımı
Designing a hybrid meta heuristic algorithm for optimization problems solutions
Yazar: GANİMET NİLAY YÜCENUR
Danışman: YRD. DOÇ. DR. NİHAN ÇETİN DEMİREL
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Doktora, 2011
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Genetik algoritma tekniği = Genetic algorithm technique

Özet:
Optimizasyon gerçek yaşam problemlerinin matematiksel modeller haline dönüştürülmesi ile karşımıza çıkar ve günlük hayatımızdaki birçok sorun için en iyi çözümü bulmayı amaçlar. Optimizasyon konusunun en önemli dallarından biri de lojistik sektöründe karşımıza çıkar. Lojistik sektöründeki araç rotalama problemlerinde de amaç toplam seyahat mesafesini ve çözümde kullanılan toplam araç sayısını minimize ederek problemde var olan kısıtları da göz önüne alarak optimum rotaları tasarlamaktır. Bu çalışmada, çok depolu araç rotalama probleminin çözümü için karınca kolonisi optimizasyonu ve genetik algoritmanın bir arada kullanılmasıyla oluşturulan melez metasezgisel bir yapı önerilmiştir. Problemde amaç, tüm araçlar tarafından kat edilen toplam seyahat mesafesinin minimize edilmesidir. Problemde araç filosu homojendir, araç kapasiteleri ve müşteri talepleri bilinmektedir. Çok depolu araç rotalama probleminin çözümü için önerilen bu metasezgisel yapı iki aşamadan oluşmaktadır. Problemin çözümü için önerilen ilk aşamada müşterilerin hangi depolardan hizmet alacağının belirlendiği gruplama, ikinci aşamasında ise müşterilerin hangi sıra ile depolardan hizmet alacağının belirlendiği rotalama işlemleri gerçekleştirilir. Birinci aşamadaki gruplama işlemi için genetik algoritma, Thangiah ve Salhi'nin 2001 yılında ortaya koydukları genetik kümeleme yönteminin geliştirilmiş hali ile kullanılmıştır. İkinci aşamadaki rotalama işlemi ise karınca kolonisi optimizasyonu algoritmalarından Gambardella ve Dorigo tarafından 1997 yılında önerilen karınca kolonisi sistemi yaklaşımı ile gerçekleştirilmiştir. Ortaya konan yeni melez metasezgisel yöntem literatürde kabul gören Cordeau vd.'nin (1997) önerdikleri problem setleri ile test edilmiş ve elde edilen sonuçlar var olan diğer yöntem çözümleriyle karşılaştırılmıştır. Sonuç olarak, klasik araç rotalama problemlerinin önemli kollarından biri olan çok depolu araç rotalama problemlerinin çözümü için önerilen karınca kolonisi optimizasyonunun ve genetik algoritmanın bir arada kullanıldığı bu tez çalışması bu konu ile ilgili literatüre kazandırılan ilk çalışmadır.

Abstract:
Optimization is the simulation of the real world problems as mathematical models. Vehicle routing problems are very important issue for logistics sector. The objectives of the vehicle routing problems are to design optimal routes minimizing total traveled distance, minimizing number of vehicles which are used for the solution that satisfy corresponding constraints. In this study, for the solution of the multi-depot vehicle routing problem, a new hybrid metaheuristic structure is proposed with ant colony optimization and genetic algorithm. The aim of the problem is to minimize the total traveled distance by the all vehicles. In problem, vehicle fleet is homogeneous, capacity of vehicles and customer demands are known. The metaheuristic structure of the multi-depot vehicle routing problem solution consists of two phases. In the first phase is about the grouping that decides which customer is served by which depot and in the second phase is about the routing that decides the customers sequencing for the serving. In the first phase for grouping Thangiah and Salhi?s (2001) genetic clustering method is developed and in the second phase for routing Gambardella and Dorigo?s (1997) ant colony system approach is used. The proposed metaheuristic method is tested with the Cordeau et al.?s (1997) problem sets and the results are compared with the other solution techniques in the literature. In conclusion, the multi-depot vehicle routing problems are the important types of the classical vehicle routing problems, to our knowledge this is the first study that investigates the solution with ant colony optimization and genetic algorithm.