Genetik algoritmaların optimal güzergah belirlenmesine uygulanması

Abstract

Bu çalışmanın amacı İETT'nin uygulama alanında çalışan denetim ekibinin durak, hat, araç ve işletmeleri denetlemesi için gereken optimal güzergahın belirlenmesi hedeflenmektedir. Bu kapsamda en çok bilinen ilişkisel optimizasyon problemi olan Gezgin Satıcı Problemi belirlenmiş olup çözüm yöntemi olarak genetik algoritmalar kullanılmıştır. Gezgin Satıcı Problemi (Traveling Salesman Problem) veya kısaca GSP; aralarındaki mesafeleri bilinen belirli sayıdaki şehirlerin (nokta, düğüm veya parça gibi) her birinden yalnızca bir defa geçerek başlangıç şehrine dönen en kısa turun bulunmasına denir. Gezgin Satıcı Problemlerinin pek çok çözüm yöntemi vardır. GSP'de kullanılan kesin çözüm algoritmaları, orta büyüklükteki problemleri çözmek için çok uzun sürelere ihtiyaç duyduğu için pek tatmin edici değildir. Bunun yerine Sezgisel yöntemler ise kısa sürede optimuma yakın sonuçlar vermektedir. Bu çalışmada GSP çözüm yöntemi olarak sezgisel algoritmalardan genetik algoritmalar yöntemi ile çözülmüştür. Genetik Algoritmalar (GA) doğal evrimin teorisinden esinlenilerek biyolojik süreci modelleyerek fonksiyonları optimize eden evrim algoritmalarıdır. Genetik algoritmalar özellikle; kaynak tahsisi, iş atölyesi çizelgelemesi, makine parça gruplaması ve bilgisayar ağ tasarımı, lojistik alanda, okul otobüsü rotalaması, posta kutusuna dağıtım problemleri, çöp toplama, baskı devre kartlarının montajı veya muayenesi, ders programı hazırlama, GSM operatörlerinin baz istasyonlarının yerleşim yerlerinin belirlenmesi problemi, malzeme akış sistem tasarımı, araç rotalama problemleri, depolardaki vinç güzergâhlarının programlaması, stok alanındaki malzeme toplama problemleri, uçaklar için havaalanı rotalaması, elektronik devre tasarımı gibi çeşitli alanlarda uygulanmaktadır.Bu çalışmada: optimizasyonun ne olduğu ve bunların bir çeşidi olan genetik algoritmaların tarihçesi, tanımı, süreci, kodlama yöntemleri, operatörleri, parametreleri, avantaj ve dezavantajları, uygulama alanları hakkında bilgi verilmiştir. Gezgin satıcı problemin tarihçesi, çözüm yöntemleri, literatürdeki çalışmalar hakkında detaylı bilgi verilmiştir. Uygulama kısmında ise optimal güzergah belirlenmesi için genetik algoritma çözüm yöntemi ile Micirosoft Visual Studio 2010 ortamında Asp.Net, C# programlama dili, Java Script ve Google Maps Apisi ve Microsoft SQL Server 2008 veri tabanı kullanılarak bir yazılım geliştirilmiştir.

The purpose of this study İETT application stops working in the field audit team, line, equipment, and businesses need to oversee the optimal route will be determined. In this context, the most well-known traveling salesman problem with relational optimization problem is defined as a method of solution used in genetic algorithms.Traveling Salesman Problem (Traveling Salesman Problem), or GSP for short, known distances between them a certain number of cities (points, nodes, or as part) only once from each of the short tour through the initial finding is returning to the city. Travelling Salesman Problem has many solutions method. GSP algorithms used in the final solution, to solve problems of medium size needed for very long periods is not very satisfactory. Instead, heuristic methods results in the shortest period of time is near optimum. GSP in this study as a method of solution is solved with heuristic algorithms such as genetic algorithms method. Genetic Algorithms (GA), inspired by the biological process of natural evolution, the theory of evolution by modeling functions that optimize the algorithm. Genetic algorithms, in particular, resource allocation, job shop scheduling, machine parts grouping and computer network design, logistics area, school bus rotalaması, mail box, distribution problems, garbage collection, assembly, or inspection of printed circuit boards, curriculum development, placement of base stations of GSM operatorsLocating the problem, the material flow system design, vehicle routing problems, scheduling routes crane warehouses, inventory problems in the collection of material, rotalaması airport for aircraft, applied in various fields such as electronic circuit design.In this study, which is a variant of genetic algorithms and their optimization is what the history, definition, process, coding methods, operators, parameters, advantages and disadvantages, are given information on the application areas. The history of traveling salesman problem, the solution methods, are given detailed information about the studies in the literature. In the second part of the solution of genetic algorithm to determine the optimal route in Visual Studio 2010 environment Micirosoft Asp.Net, C # programming language, java Script and apis google maps and the software has been developed using Microsoft SQL Server 2008 database.