An Evolutionary approach for the single agu routing problem

Abstract

oz TEK OYA ROTA PROBLEMİ İÇİN EVRİMSEL BİR YAKLAŞIM Tulu, Bengisu Yüksek Lisans, Bilişim Sistemleri Programı Tez Yöneticisi: Doç. Dr. Nur Evin Özdemirel Temmuz 2000, 152 sayfa Bu çalışmada, Otomatik Yönlendirilen Araç (OYA) rota probleminin özel bir şekli incelenmiştir. Amaç. birçok malzeme taşıma isteğini yerine getirmek zorunda olan tek. serbest dolaşan bir OYA için en kısa turu bulmaktır. Bu problem gerçekte NP- tamam olduğu bilinen Asimetrik Gezgin Satıcı Problemine (AGSP) benzemektedir. Problemi çözmek için iki genetik algoritma ve bir yerel geliştirme algoritması önerilmiştir. Algoritmaların performansı, çeşitli parametre değerleri altında, farklı iş yerleşim kalıpları ve problem büyüklükleri için test edilmiştir ve en iyi çözüm, yapay sinir ağları yaklaşımı ve en yakın komşu kuralıyla karşılaştırılmıştır. Hem çözüm kalitesi, hem de hesaplama süresi bakımından ümit verici sonuçlar elde edilmiştir. Anahtar Kelimeler: OYA Rota. Genetik Algoritmalar, Yerel Geliştirme. Bakışımsız Gezgin Satıcı Problemi. IV

ABSTRACT AN EVOLUTIONARY APPROACH FOR THE SINGLE AGV ROUTING PROBLEM Tulu, Bengisu M.S., Information Systems Program Supervisor: Assoc. Prof. Dr. Nur Evin Özdemirel July 2000, 152 pages In this study, a special form of Automated Guided Vehicle (AGV) routing problem is investigated. The objective is to find the shortest tour of a single, free- ranging AGV that has to carry out multiple move requests. This problem is in fact similar to the Asymmetric Traveling Salesman Problem (ATSP) which is known to be NP-complete. Two genetic algorithms and a local improvement algorithm is proposed to solve the problem. Performances of the algorithms are tested under various parameter settings for different job layout patterns and problem sizes, and compared with the optimal solution, an artificial neural network approach and the nearest neighbour rule. Promising results are obtained in terms of solution quality and computation time. Keywords: AGV Routing, Genetic Algorithms, Local Improvement, Asymmetric Traveling Salesman Problem. Ill