Uçmak Ya Da Uçmamak

GEZGİN SATICI PROBLEMİNİN HAVAYOLU TAŞIMACILIĞINA UYGULANMASI

ÖNSÖZ
Öğretme sevgisi, bitirme tezimi yazmamdaki katkıları, bakış açısıyla son
dönemimi mutlulukla hatırlamamı sağlayan ve sevdiğim bir konuda alışmama yardım eden değerli Dr. Fuat ERGEZEN hocama çok teşekkürler. Sayesinde, tezimi yazmaya başlayana kadar beni endişelendiren bu dönem, yazdıkça daha da eğlenceli, bilgilendirici ve huzurlu bir dönem geçirmemi sağladı. Okula başlamadan bana matematiği sevdiren, bu bölümü seçmemi sağlayacak kişi olan Atatürk’e duyduğum minnet duygusunu kazandıran sevgili anne ve babama emeklerinden ötürü minnettarım. Tanıdığım andan itibaren, hayatım boyunca bana yardım eden, destekleyen ve bu tezde en az benim kadar olan emeği, yardımı için sevgili Abdullah Tufan’a çok teşekkürler. Bana matematiği sevdiren, fikirleri sayesinde bu bölümü yazmamı sağlayarak İTÜ’de güzel bir eğitim almamı sağlayan Atatürk’e, yaptıkları için ne kadar teşekkür etsem yetmeyecek ama teşekkürler Atam. Her zaman yolunda olarak bu teşekkürü en güzel şekilde göstereceğim.
Ocak 2020 Gözde TUTAN

KISALTMALAR
GSP : Gezgin Satıcı Problemi
NP-Zor : Non Deterministic Polynomial Zor
THY : Türk Hava Yolları
MATLAB : Matrix Laboratory

GEZGİN SATICI PROBLEMİNİN HAVAYOLU TAŞIMACILIĞINA
UYGULANMASI

ÖZET
Bu 1 Türk Hava Yollarına ait kargo uçaklarından B777F ve A330-200F için
planlanan KIŞ 18 Kargo Tarifesi (1-30 Kasım) rotaları incelenmiş; rotada bulunan havaalanları gezgin satıcı problemine öklid uzayda uyarlanmış ve sezgisel algoritmalardan biri olan Genetik Algoritma ile rotanın yol minimizasyonu sağlanmıştır.
Öncelikli olarak gezgin satıcı problemi hakkında bilgi verildikten sonra
problem çizge kuramında, 2 boyutlu bir çizge üzerinde açıklanarak çözümü 5 şehir için görselleştirilmiştir. Çözüm olarak En Yakın Komşu Algoritması ve En Kısa Tur Algoritması kullanılmıştır. Uçakların hareketini dünya üzerinde incelerken metrik uzay tanımındaki uzaklık formülü yerine daha doğru bir sonuç gerçekleştirecek olan haversine formülü kullanılarak şehirler arası uzaklıklar hesaplanmıştır. Genetik algoritmanın tanımı yapılarak algoritma hakkında bilgi verildikten sonra problem; genetik algoritmada bulunan kromozom, gen, mutasyon gibi tanımlamalara uyarlanmıştr. Kargo şirketleri incelenmiş ve en çok sefer yapan şirketin Türk Hava Yolları olması sebebiyle problemde Türk Hava Yolları’nın kargo uçakları için uçuş rotaları üzerinde minimizasyon yapmanın faydalı olacağına karar verilmiştir. Tezin yazımına eylül ayında başlandığı için, internette yapılan araştırma sonucu Türk Hava Yolları’nın sitesinde kasım ayının rotasına ulaşılmış ve bu tablodaki havaalanları kullanılmıştır. B777F ve A330-200F tipi uçakların seçilme sebebi en uzun rotaya ve en sık uçuş sayısına sahip olmalarıdır. Toplamda 10 farklı havaalanı seçilmiş ve başlangıç noktası olarak İstanbul Havaalanı alınmıştır. Hesaplamalar matlab programı ile görselleştirilerek genetik algoritma saysinde yaklaşık çözüm ile en iyi çözüm elde edilmiştir. Genetik algoritmada operator olarak çaprazlama kullanılmamıştır, çözüm sadece mutasyon kullanılarak iyileştirilmiştir. Yazılan kod iterasyon sayısı 100 ve 1000 için art arda birkaç kez çözülmüştür ve elde edilen sonuçların en iyiyi bulmadığı gözlemlenince kodda yapılan değişiklikler ile rotanın iyileştirilmesi yapılmıştır ve sonuç olarak 10 şehir için en kısa rota hesaplanmıştır.

APPLICATION OF TRAVELLING SALESMAN PROBLEM TO AIRLINE TRANSPORT
SUMMARY

In this thesis, the planned winter 18 cargo schedule (November 1-30) routes
for the B777F and A330-200F, which are the cargo planes of Turkish Airlines, were examined, the airports on the route were adapted to the traveling salesman problem in Euclid space and route minimization was achieved by Genetic Algorithm, one of the heuristic algorithms.
The problem is explained on a 2-dimensional graph in graph theory and its
solution is visualized for 5 cities. The nearest neighbor algorithm and shortest round algorithm were used as solutions. When studying the movement of aircraft on Earth, the distance between cities was calculated using the haversine formula, which would perform a more accurate result instead of the distance formula in the metric space definition. After defining the genetic algorithm and informing about the algorithm, the problem is adapted to the definitions such as chromosome, gene and mutation in the genetic algorithm. Cargo companies were examined and it was decided that it would be beneficial to minimise the flight routes of Turkish Airlines in the case of the problem, as Turkish Airlines is the company with the most flights. Since the writing of the thesis started in September, the route of November was reached on the THY website and the airports in this table were used. B777F and A330-200F type aircraft are chosen because they have the longest route and the most frequent number
of flights. In total, 10 different airports were selected and Istanbul airport was taken as the starting point. The calculations were visualized with matlab program and the best solution was obtained by the genetic algorithm. Crossover is not used as an operator in the genetic algorithm, the solution is improved using only mutation. The number of iterations in the written code has been solved several times in succession for 100 and 1000, and when it was observed that the results obtained did not find the best, the route was improved by changes in the code, and as a result the shortest route for 10 cities was calculated

  1. GİRİŞ
    Gezgin satıcı problemi, belirli bir sayıdaki şehrin her birinin bir kez ziyaret edilip tura başlanılan şehre dönmek koşuluyla, bu turun en kısa mesafede tamamlanması için izlenilmesi gereken yolu hesaplayan ve birçok matematikçi, yazılımcı tarafından çözümü araştırılan ancak hala kesin çözümü bulunamayan, kombinatoryal bir optimizasyon problemidir. Çizge kuramında problemin tanımını yapacak olursak, n sayıda köşesi bulunan yönsüz ve ağırlıklı bir çizgede başlangıç köşesinden başlayarak tüm köşelerden bir kez geçip başlangıç köşesine geri dönecek şekilde en kısa Hamilton turunun bulunmasıdır. Bu çizgede köşeler şehirleri temsil ederken kenarlar şehirler arası uzaklığı temsil etmektedir. Gezgin satıcı problemini
    temel alan problemler ilk olarak ikisi de matematikçi olan Sir William Rowan Hamilton ve Thomas Penyngton tarafından ortaya çıkarılmıştır. “Icosian Game” Hamilton’un 1859’da bulduğu bir oyundur. Oyunun amacı düzgün 12 yüzlünün kenarlarını takip ederek, her köşeden yalnız 1 kez geçerek ve başlangıç köşesine geri
    dönecek şekilde Hamilton turu bulmaktır. Şehir sayısı az olduğunda bu problem kısa vakitlerde çözülebilmektedir ancak şehir sayısı arttığında kesin çözümü bulmak imkansızlaşmaktadır. Bu sebepten dolayı GSP’nin çözümü için sezgisel ve metasezgisel algoritmalar kullanılmaktadır. Gezgin Satıcı Probleminin kesin bir çözümü bulunamamış olmasına rağmen, geliştirilen yaklaşık çözüm yöntemleri sayesinde birçok alanda optimizasyon problemlerine katkısı olmuştur. Gezgin satıcı probleminin sezgiseller ile çözümünün kullanıldığı alanlar örneklenecek olursa;
    • Kargo uçaklarının rotalanmasını düzenleyerek en kısa uçuş süresiyle dağıtım yapmalarının sağlanması ve uçuş süresinin kısalmasıyla beraber hava kirliliği, yakıt maliyeti, kaza risklerinin azalması
    • Okul servisinin öğrencileri dağıtırken kullanacağı rotayı minimize ederek yakıt ve zaman tasarrufu yapılması
    • Telefon GSM operatörlerinin baz istasyonlarının yerleştirilmesi
    • Şehirler arası dağıtım yapan bir kargo aracının rota uzunluğunun minimize edilmesi gibi örnekler sıralanabilir.

1.1 Tezin Amacı
Bu tezin amacı gezgin satıcı problemi hakkında bilgi verilip, günümüze kadar geliştirilen çözüm yöntemlerinden bahsedildikten sonra gezgin satıcı problemini havayolu kargo uçaklarına uyarlayarak sezgisel algoritmalar ve MATLAB programı ile problemin çözümü olan rota minimizasyonunu sağlamaktır. Problemde Türk Hava Yollarına ait kargo uçaklarından B777F ve A330-200F için planlanan KIŞ 18 Kargo Tarifesi (1-30 Kasım) rotaları kullanılmıştır ve bu rotaların uzunluğunun kısaltılması amaçlanmıştır. Rotanın minimizasyonu genetik algoritma ile yapılmıştır.

1.2 Gezgin Satıcı Probleminin Tanımı
Bu problem temelde, sonlu sayıda şehir için belirli bir başlangıç noktasından başlayarak ve her şehirden sadece 1 kez geçip, tüm şehirlere uğradıktan sonra başlangıç noktasına dönecek en kısa turu bulmayı hedefleyen bir problemdir. Bu problemle ilişkili ilk problemler 1800’lü yıllarda İrlandalı matematikçi Sir William Rowan Hamilton ve İngiliz matematikçi Thomas Penyngton Kirkman tarafından yaratıldı. Hamilton’un Icosian Oyunu, düzgün 12 yüzlünün görüntüsünden oluşan ve köşelerin şehir, kenarların şehirler arası yol olarak temsil edildiği bir oyundur.
Toplamda 20 şehir bulunan bu oyunun amacı, belirli bir şehirden başlayarak tüm şehirlerden yalnızca bir kez geçip başlangıç noktasına dönmektir.

Gezgin satıcı problemini çizit üzerinde ifade edersek; n köşeli yönsüz ve bağlı bir çizitte köşeler şehirleri, kenarlar şehirler arası yolları temsil ederken çizit üzerindeki en kısa Hamilton Turu’nun bulunmasıdır. İsmi Hamilton’a itafen verilen bu tur, (yukarıda Icosian Oyunu’nda anlatıldığı gibi) bir çizit üzerindeki başlangıç köşesinden başlayarak ve her köşeden yalnızca 1 kez geçip başlangıç köşesine geri dönülen turdur. Örneğin 3 köşeli bir çizit üzerinde düşünürsek; başlangıç noktası fark etmeksizin elde edilen tek Hamilton turu 1-2-3 olacaktır. Başlangıç noktası hangi köşe seçilirse seçilsin turu veren yol aynı olacağı için sadece 1 tane Hamilton turu bulundu.

3 köşeli çizit

4 köşeli bir çizit için Hamilton turunu incelediğimizde ise 1-2-3-4, 1-2-4-3,
1-3-2-4 olacak şekilde 3 Hamilton turu buluruz.

4 köşeli çizit için Hamilton Turları

Bu şekilde diğer çizgeler incelenip Hamilton turu sayısı formülize edilirse N
köşeli bir çizit için Hamilton turu sayısı (n−1)!/2 olacaktır. Yani 20 şehirden oluşan bir çizit için en kısa Hamilton turunu bulmak istediğimizde 19!/2 turu inceleyip her birinin uzunluğunu hesaplamamız ve en kısasını seçmemiz gerekir. Her bir Hamilton turunun 1 saniyede hesaplandığı bir bilgisayar düşünürsek 20 şehirli bir çizge için en kısa turu bulmak yaklaşık 2 milyar yıl sürecektir. Bu bakımdan, gezgin satıcı problemi anlaşılması kolay ancak problemin çözümü zor bir optimizasyon problemidir.

1.3 Gezgin Satıcı Problemi Çözüm Yöntemleri
GSP, NP-Zor problemler sınıfına dahil bir optimizasyon problemidir.
Optimizasyon problemlerinin çözüm yöntemleri 2 ana başlıkta incelenebilir, Bunlar Kesin Çözüm Veren Algoritmalar ve Sezgisel Algoritmalar’dır. Optimizasyon problemlerinde kesin çözümü veren algoritmalar zaman ve iş yükü bakımından çok maliyetli olduğundan, kısa zamanda çözümü veren ama çözümün en iyisini garanti etmeyen sezgisel algoritmalar daha çok tercih edilir. Algoritmalara örnekler verdikten sonra devamında sezgisel algoritmalardan En Yakın Komşu, En Kısa Yol ve Genetik Algoritma açıklanacaktır. Bu tezde Türk Hava Yolları Kargo Uçakları Kasım 2019 rotası için sezgisel algoritma olan Genetik Algoritma kullanılarak rota uzunluğu minimize edilmeye çalışılmıştır.
Kesin çözümü veren algoritmalar:

  1. Dal Sınır Algoritması
  2. Lineer programlama yöntemleri
  3. Dinamik programlama yöntemleri
    Sezgisel Algoritmalar:
  4. Tur oluşturan sezgisel algoritmalar
    a. En yakın komşu algoritması
    b. Açgözlü Algoritma
    c. Ekleme sezgiseli algoritması
  5. Turu geliştiren sezgisel algoritmalar
    a. Genetik Algoritma
    b. Yapay zeka algoritmaları
    c. Karınca kolonisi algoritmaları
  6. Turu oluşturup daha sonra turu geliştiren melez algoritmalar
    a. Yinelemeli Lin-Kernighan algoritması

1.3.1 En Yakın Komşu Algoritması
Bu algoritmada seçilen herhangi bir başlangıç köşesine en yakın uzaklıkta
olan köşe seçilir, eğer eklenen köşe bir çevrim oluşturmuyorsa tura eklenir. Bu şekilde tüm şehirlere sadece 1 kez uğranana kadar seçim devam eder.

Ağırlıklı Yönsüz G Çizgesi

Örneğin 1 numaralı köşe başlangıç şehrimiz olsun. En kısa mesafe 2 ağırlıklı kenar olduğu için tur 1-4 olacaktır. 4 numaralı köşeye en yakın köşe 6 numaralı kenar ile 2 numaradır. Tur 1-4-2 şeklinde devam edecektir. Bu şekilde algoritma tüm köşeler için incelenirse son tur 1-4-2-5-3-1 ve toplam yol uzunluğu 29 olacaktır. Bulunan bu tur minimum turu garanti etmez, çizitte bulunan tüm hamilton yolları tek tek incelenirse belki bu çözümden daha verimli bir çözüm bulunabilir.

1.3.2 En Kısa Tur Algoritması
Bu algoritma da sezgisel bir algoritmadır. Sırasıyla algoritmanın adımlarını
listelersek:
• G çizge olmak üzere, G üzerindeki en kısa kapsayıcı ağaç bulunur. Bu ağaç T ile gösterilsin.
• T’nin her kenarı çiftlenir. Oluşan yeni çizge G1 olsun. G1 çizgesinde her
köşenin derecesi çift olacağından böyle bir çizgede Euler turu olmalıdır. Euler turu, çizge üzerinde her kenardan yalnızca 1 kez geçen ve her köşeden en az kez geçerek başlangıç köşesine geri dönen turdur.
• G1 çizgesinde bulunan Euler Turu köşelerin sırasıyla yazılır.
• Sıralanmış köşeler arasında tekrar edilen bir köşe varsa bu köşe çıkarılıp, tüm köşelerin turda sadece 1 kez uğranması sağlanan ve başlanılan köşeye geri dönen Hamilton turu bulunmuş olur.

Bu algoritmanın örneğine başlamadan önce bir çizge üzerindeki en kısa kapsayıcı ağaç tanımını ve bu ağacın nasıl bulunacağını belirtmekte fayda olacaktır.

1.3.2.1 Çizge Üzerindeki En Kısa Kapsayıcı Ağaç
Ağırlıklı ve bağlı bir çizge üzerindeki kapsayıcı ağaç; tüm köşeleri içeren ve
birbirine bağlayan bir ağaçtır ve bu ağaç çizgenin bir alt çizgesidir. Çizge üzerinde birbirinden farklı biirçok kapsayıcı ağaç bulunabilir. En kısa kapsayıcı ağaç ise bu kapsayıcı ağaçlar içerisinde ağırlığı en az olandır. Eğer en az ağırlıkta birden fazla ağaç bulunuyorsa her biri en kısa kapsayıcı ağaç olarak tanımlanır. Ağacın ağırlığı ağaçta bulunan tüm kenar ağırlıklarının toplamına eşittir. En kısa kapsayıcı ağacı bulmak için açgözlü algoritma yöntemlerinden; Dijkstra’nın en kısa yol algoritması, Kruskal’ın Algoritması ve Prim’in Algoritması örnek olarak verilebilir.

1.3.2.2 Kruskal’ın Algoritması
Kruskal’ın algoritması açgözlü bir algoritmadır. Optimizasyon problemlerinin çözümünde kullanılan açgözlü algoritmalar; problemin çözümünde o anda bulunan adımda en uygun seçimi yaparak gelecekte bu seçimin sonuçlarını göze almadan ilerleyen algoritmalardır. Hızlı olmaları açıdan gezgin satıcı probleminin çözümünde kullanılır. Çünkü gezgin satıcı problem için kesin çözümü bulmak çok uzun bir süreyi almaktadır. Hiç sonuç bulamamaktansa mevcut şartlar altında en iyi sonucu bulmak optimizasyon problemlerinin çözümünde oldukça faydalı olmaktadır.
Kruskal’ın algoritmasının adımları sırasıyla:

  1. Tüm kenarları ağırlıklarına göre küçükten büyüğe sırala
  2. En küçük ağırlıklı kenarı seç. Seçilen kenar mevcut ağaca eklendiğinde çember oluşturmuyorsa listeye ekle, çember
    oluşturuyorsa ekleme.
  3. Çizgenin kenar sayısının 1 eksiği kadar kenara ulaşana kadar 2.
    adıma devam et

1.3.2.3 En Kısa Tur Algoritmasının Çizge Üzerinde Gösterimi

Ağırlıklı Yönsüz G Çizgesi

Bu çizgede 1,2,3,4,5 köşeleri temsil etmektedir. Mavi sayılar ise kenarların
ağırlığını (gezgin satıcı probleminde bu ağırlıklar şehirler arası yol olarak
alınacaktır.) belirtmektedir. Kenarları küçükten büyüğe sıralarsak bu sıralama 2 (1-4), 4(3-5), 6(2-4), 7(2-5), 7(2-3), 9(1-5), 10(1-3), 11(1-2), 14(4-5), 18(3-4) şeklinde olacaktır. Çevrim oluşmayacak şekilde kenarları sırayla eklersek ilk kenarımız 1-4 kenarı olacaktır. Sonrasında 3-5, 2-4 ve 2-5 kenarları eklendiğinde tüm köşelerin bulunduğu en kısa kapsayıcı ağaç elde edilmiş olunur.

G çizgesi için en kısa kapsayıcı ağaç

Daha sonra bulunan bu en kısa kapsayıcı ağacın tüm kenarları çiftlenir.

En kısa kapsayıcı ağacın kenarlarının çiftlenmiş hali

Artık her köşeden çıkan kenar sayısı çift olduğuna göre bu çizgede bir euler
turu bulunabilir. Euler turu bir çizgede herhangi bir başlangıç köşesinden başlanarak ve her kenardan yalnızca bir kez geçerek başlangıç köşesine dönülen turdur. Aynı kenardan bir kez geçilebilirken aynı köşeden birden çok kez geçilebilir. Bu çizge için bulacağımız euler turu; 1-4-2-5-3-5-2-4-1 şeklinde olacaktır. Eklenen turuncu kenarlar sayesinde aynı kenarı kullanmadan Euler turu tamamlanmış olur. Şimdi bu turu Hamilton turuna çevirmek için tekrar eden köşeleri çıkarmamız gerekir.
Hamilton turu 1-4-2-5-3-1 şeklinde olacaktır ve G çizgesi için için en kısa tur
algoritmasıyla bulunacak çözüm 1-4-2-5-3-1’dir. Gezgin satıcı problemi olarak düşünülürse 1,2,3,4,5 numaralı köşeler şehirleri temsil ederken kenarlar şehirler arası yolları temsil eder. Bulduuğumuz 1-4-2-5-3-1 rotası bu çizgede gezgin satıcı problemi için En Kısa Tur Algoritması ile bulunan en iyi çözümdür.

1.3.3 Genetik Algoritma
Genetik algoritma; çözümü zor optimizasyon problemlerin çözümünde
kullanılan, populasyon oluşturup bu populasyon üzerinde, evrim sürecinde yer alan mutasyon ve çaprazlama işlemleri ile populasyondaki bireylerin daha iyi olmasını hedefleyerek en iyi çözüme ulaşmayı sağlayan sezgisel bir algoritmadır. Bu algoritma bilgisayar progamlarına uyarlanarak hızlı bir şekilde bir çözüm bulmayı sağlar. Günümüzde artık evrimin var olup olmadığı değil, bu evrim sürecinin işleyiş biçiminin nasıl olduğu bilim insanları tarafından tartışılmaktadır. Evrim sürecinin doğada bulunan bireylerde yarattığı değişiklerle bireylerin hayatta kalma olanakları
artmakta ve yaşam koşulları iyileşmektedir.
Genetik algoritmanın bir probleme uygulanması için sırasıyla izlenmesi
gereken adımlar vardır:

  1. Bireylerden oluşan populasyonun oluşturulması
  2. Populasyondaki her bireyin kromozomunun incelenmesi
  3. Herhangi 2 birey seçilerek çaprazlama ile yeni populasyon bireyinin
    oluşturulması veya seçilen bir birey üzerinde mutasyon uygulanarak
    bireyin kromozomunun değiştirilmesi
  4. Yeni jenerasyonun oluşturulması

1.3.3.1 Populasyon Oluşturulması
Bireyler oluşturulurken her bir bireyin kromozomu farklı olmalıdır. Kromozomun şifrelenmesi için farklı seçenekler mevcuttur: İkili kodlama, permütasyon kodlama, değer kodlama, ağaç kodlama gibi. İkili kodlama kromozomuna örnek verilecek olursa 001 ve 010 iki farklı bireyi temsil eder; kromozomda sadece 0 ve 1 sayıları kullanılır. Permütasyon kodlama gezgin satıcı probleminde ve sıralama problemlerinde kullanılır ve 124359876, 198723456 şeklinde kromozoma sahiptir.
Değer kodlamada kromozomlara yukarı, aşağı, ileri, geri gibi değerler verilebilirken 1.45, 1.67 gibi sayılar da kromozomun yapısını oluşturabilir. Ağaç kodlama değişen programlarda kullanılır.

1.4 Genetik Algoritmanın Gezgin Satıcı Problemine Uygulanması
Genetik algoritma, gezgin satıcı problemine uyarlandığında populasyondaki bireyler tur olarak tanımlanmıştır. Örneğin en kısa tur algoritması ile G çizgesi için bulduğumuz 1-4-2-5-3-1 rotası problemimiz için bir bireydir. Kromozom dizilimi 1-4-2-5-3-1 şeklindedir ve her bir rakam bir gen olarak belirtilir. Her bir gen bir şehiri temsil etmektedir. Kenarlar ise şehirler arası yoldur ve kenarın ağırlığı bağlı olduğu iki şehir arası uzaklıktır. Problemde oluşturulabilecek tüm rotaların oluşturduğu dizi populasyondur. Bu tezde amacımız populasyon içerisinden rastgele
seçilen bir kromozom üzerinde mutasyon uygulayarak her bir adımda önceki koromozom ile yeni koromozu karşılaştıracak ve belirlediğimiz döngü sayısına bağlı olarak döngü sonunda en kısa rotayı en iyi çözüm olarak alacağız.

Rota uzunluğunu bulmak için köşeler arası uzaklığı yani kenar ağırlığını
kullanacağız. Örneğin 1-4-2-5-3-1 rotasının uzunluğunu hesaplarken sırasıyla 1 ve 4 arası uzaklık bulunur, sonra 4 ve 2 arası uzaklık bulunup eklenir sırayla tüm tur için bu uzaklıklar eklenir ve rotanın uzunluğu hesaplanır.

Problemimizde Türk Hava Yolları’nın kargo uçakları için kasım ayında
kullanılan sefer tarifesi verileri kullanılarak rota uzunluğu minimize edilmeye çalışılmıştır. Dünya üzerinde uçakların hareketi 3 boyutlu düzlem içerisinde incelendiğinden 2 şehir arası uzaklığı bulmak için Haversine Formülü kullanılmıştır.

1.5 Haversine Formülü
Enlem ve boylam koordinatları kullanılarak dünya üzerinde 2 nokta
arasındaki uzaklığı bulmak için kullanılan bu formül dünyayı bir küre olarak kabul eder ve dünya bir küre olmadığından bu formülün hata payı vardır. Ancak çok uzak olmayan mesafelerde bu hata payı göz ardı edilebilecek kadar azdır. Gezgin satıcı probleminde önemli olan rotanın uzunluğundan çok hangi rotanın en kısa olduğunu bulmak olduğundan, şehirler arası bulunan mesafelerde hata payı olsa bile toplam rota uzunluğu kıyaslamasında bu önemli olmamaktadır.

Matlab’de kullanılan haversine formülü aşağıdaki biçimdedir:
d = acos( sin φ1 ⋅ sin φ2 + cos φ1 ⋅ cos φ2 ⋅ cos Δλ ) ⋅ R
d: İki nokta arası uzaklık
φ1: İlk noktanın enleminin radyan cinsinden değeri
φ2: İkindi noktanın enleminin radyan cinsinden değeri
Δλ: İki noktanın boylamlarının farkı
R: Dünyanın yarıçapı

  1. GEZGİN SATICI PROBLEMİNİN TÜRK HAVA YOLLARI UÇUŞ
    ROTASINA UYGULANMASI
    2.1 Şehirlerin Seçimi

    Problemin kargo uçakları rotalanmasına uyarlanmasına karar verildikten sonra uçuş şirketleri üzerinde yapılan araştırma sonucu en fazla uçuş gerçekleştiren şirketin Türk Hava Yolları olduğu görülmüştür. Turkish Cargo Kış-18 Kargo Tarifesi 1-30 Kasım verileri internet üzerinden bulunduktan sonra B777F tipi kargo uçağının en
    fazla şehir ziyaret eden rotalara sahip olduğu görülmüştür. Bu sebepten B77F kargo uçağının rotalarının düzenlenmesi daha fazla kar sağlayacağından şehir koordinatları olarak B77F uçağının ziyaret ettiği şehirler seçilmiştir.
    Tabloda bulunan 3 harfli kodlar havaalanı kodları olmaktadır. IST NVI ile gösterilen bir rota; IST(İstanbul Havaalanı)’den NVI(Navoiy Havalimanı)’ya olan uçuşu temsil etmektedir.
THY Kış 18 Kargo Tarifesi 1-30 Kasım B777F Rotaları

Kodun verimliliğinin daha detaylı gözlemlenebilmesi için bu tabloda bulunan şehirlere ek olarak birkaç tane daha havaalanı eklenmiştir. Amaç gezgin satıcı probleminde kullanacağımız şehir sayısını arttırmaktır. Toplamda 10 şehir kullanılmıştır. Şehirler için enlem ve boylam değerleri ve havaalanlarının kodlarının bulunduğu tablo son olarak aşağıdaki gibidir.

Kullanılan havaalanlarının koordinatları

Problemde kullanılacak havaalanları, gezgin satıcı probleminin şehirleri gibi düşünülebilir. Havaalanları arası mesafe de, GSP’deki şehirler arası uzaklıktır. Çizit üzerinde problem açıklanacak olursa; her bir havaalanı çizitin farklı bir köşesi olmak üzere havaalanları arasındaki mesafe de çizitin kenarlarının ağırlığı olacaktır. Ve bu çizit üzerindeki en kısa Hamilton turunun bulunması, THY uçağının bu havaalanlarını kullanarak gerçekleştireceği uçuşun en kısa mesafede gerçekleşmesini sağlayacaktır. Bu da zaman ve nakit tasarrufu sağlarken oluşabilecek can, mal kaybını ve hava kirliliğini minimize edecektir.
Problemin yaklaşık çözümü MATLAB kullanılarak yapılmıştır. Toplamda
yukarıdaki listede bulunan 10 havaalanı kullanılmıştır. Kodun enlem boylam değerlerinin yazıldığı matris satırında eklemeler yapılarak kolaylıkla kullanılan şehir sayısı arttırılabilir veya azaltılabilir.

2.2 Enlem ve Boylam Değerlerinin Koda Yazılması
Latt ve Lon şeklinde 2 matrise enlem ve boylam değerleri girilmiştir.

latt = [40.982555, 40.4839, 21.0353, 4.7008, 12.1842, 50.91,
29.98555556, 52.7012, 51.131470, 40.64416667];
lon = [28.820829, -3.5680, -86.8728, -74.141499, -68.955, 5.77,
-95.34222222, -8.9215, -114.010559, -73.78222222];

Havaalanları arası mesafe hesaplanırken bu enlem ve boylam değerleri
radyana çevrilerek haversine formülü uygulanmıştır.

  1. PROBLEMİN MATLAB’DE GENETİK ALGORİTMA İLE ÇÖZÜMÜ
    3.1 MATLAB

    İngilizce açılımı Matrix Laboratory olan MATLAB; optimizasyon, cebir,
    analiz, istatistik ve daha birçok matematik problemlerinin hesaplanmasında kullanılan matris tabanlı bir bilgisayar programıdır. Aynı zamanda 2 ve 3 boyutlu grafikler ile çözümü görselleştirebilir. Dünya çapında birçok mühendis ve bilim insanı tarafından kullanılan MATLAB, analizleri büyük veri kümelerinde çok hızlı bir biçimde çalıştırabilir.
    Genetik algoritma ile çözümü gerçekleştirilen gezgin satıcı problemi, veri sayısı bakımından büyük olmasından dolayı çözümü zor ve uzun bir problemdir. Bu sebepten dolayı çözümü için bilgisayar programı kullanılması problemin çözüm süresini oldukça kısaltmaktadır. Çözümün grafikler ile görselleştirilebilmesi, büyük veri gruplarıyla çalışabilmesi sebebiyle MATLAB uygulaması tercih edilmiştir.

3.2 Kodun Algoritması
Programın algoritmasını maddeleyecek olursak:

  1. Kullanılacak 10 şehir için enlem ve boylam değerleri 2 farklı matris
    içine yerleştirilir.
  2. Enlem ve boylam değerleri radyana çevirilir.
  3. 10×10’luk boş bir d matrisi oluşturulur.
  4. Haversine formülü kullanılarak her şehirin birbirine olan uzaklığı
    matrise yerleştirilir. Bu tüm şehirler için yapılır.
  5. İterasyon sayısı belirlenir.
  6. Krom isminde satır sayısı iterasyon sayısı kadar olan; sütun sayısı
    rotada kullanılan şehir sayısı kadar olan bir matris tanımlanır.
  7. Rastgele bir rota belirlenir ve rotanın uzunluğu bulunur. Bu rota ilk kromozom olacaktır. Krom matrisinin ilk satırına yerleştirilir.
  8. Kromozom mutasyona uğratılarak rota değiştirilir ve yeni rota ile eski rota uzunluğu karşılaştırılır. Daha kısa olan seçilir. Seçilen iterasyon sayısı kadar bu işlem tekrarlanır.
  9. Son iterasyonda seçilen rota sıralaması ve rota uzunluğu ekrana yansıtılır.

Programda rastgele belirlenen ilk kromozom 1 4 3 7 2 6 5 8 9 10 1 dir.
Kromozomun şifrelenmesi permütasyon kodlama yöntemiyle yapılmıştır. Bu kromozomda bulunan her sayı kromozom için bir gendir. Toplamda 11 gen bulunur. Her bir sayı şehir numarasını temsil eder. Kodda ilk tanımladığımız enlem boylam matrisine göre 1 numaralı şehir matriste bulunan 1. elemanın değerlerini alır. Görüldüğü üzere başlangıç şehri 1’dir ve turun sonunda tekrardan başlangıç şehrine dönüş gerçekleştirilmiştir. Genetik algoritma operatörü olarak mutasyon seçilmiştir. Mutasyon bu kromozomda rastgele yapılacak bir değişikliktir. Mutasyon kuralını
değiştirmek daha sonrasında mümkündür.

3.3 Kromozomun Mutasyona Uğratılması
Krom matrisinin ilk satırına yerleştirilen 1 4 3 7 2 6 5 8 9 10 1
kromozomunun ilk ve son şehir numarası değiştirilmeksizin 2. ve 10. numaralar arasından rastgele 2 sayı randperm komutu ile seçilir ve bu iki sayının yeri değiştirilerek yeni bir kromozom oluşturulur. Örneğin 3 ve 5 sayısı seçilirse kromozomun 3. sayısı olan 3 ile 5. sayısı olan 2 sayısı yer değiştirecektir ve yeni kromozom 1 4 2 7 3 6 5 8 9 10 1 olacaktır.

Haversine formülü ile daha önce tüm şehirler arası uzaklık bulunduğundan iki kromozomun rota uzunluğu kolaylıkla hesaplanabilir. Sonrasında karşılaştırma yapılarak kısa olan seçilecek ve iterasyon sayısına kadar mutasyon ve karşılaştırma işlemlerine devam edilecektir. Son mutasyon sonucunda daha kısa olan tur, problem için en uygun seçim olarak alınacaktır.

3.4 Grafikler
Kromozomda mutasyon oluşturulurken genler rastgele değiştirildiği için
iterasyon sayısı ve ilk kromozom aynı kalsa bile en iyi çözümde farklı rotalar elde edilebilir. Şekil 3.1’de bulunan iki rota da iterasyon sayısı 100 alındığında elde edilen en iyi çözümlerdir. İlk çözüm oldukça kısa bir rota bulmuştur. Ancak 2. çözümün, görselde görüldüğü üzere en kısa çözüm olmadığı aşikardır. Bunun sebebi kromozomun mutasyona uğrarken seçilen 2 geninin, 100’lük iterasyon boyunca belli bir adımdan sonra değişime uğrayamamış olmasıdır. Yani daha detaylı açıklanacak olursa; ilk kromozomumuz 1 4 3 7 2 6 5 8 9 10 1 rotasını temsil etmekteydi. Bu
rastgele belirlenmiş bir dizilimdi. Mutasyonda değiştirilecek genler 4 ve 3 olsun. Yeni kromozom 1 3 4 7 2 6 5 8 9 10 1 olacaktır. Ve kabul edelim ki ilk kromozom daha iyi (rotası daha kısa) olsun. Bu sefer 2. adımda iyi olan ilk kromozom seçilecek ve tekrar mutasyona uğratılacaktır. Randperm komutu tekrar 4 ve 3 genini seçsin. Eğer bu işlem 100 iterasyon boyunca tekrar ederse kromozomda bir değişim olmaz ve kod en iyi çözüm olarak ilk kromozomu verir.

Yani rastgele seçilen 2 gen hep aynı kalırsa bu kodun yanlış çözümü verme
ihtimali hep olacaktır. Bu sebepten kodun algoritmasında değişikliğe gidilmiştir. Randperm satırı değiştirilmeden önceki kodun grafiklerinin de teze eklenmesinin sebebi, sürecin doğru bir şekilde anlatılmasıdır. Programın düzenlenmiş ve daha doğru çalışan versiyonu için grafikler 3.5 başlığı altında verilecektir.

3.4.1 İterasyon Sayısı 100 İçin En İyi Sonuç
Görsellerde görüldüğü üzere program 2 kez art arda çalıştırıldığında farklı
sonuçlar vermektedir. Bunun sebebi randperm komutunun rastgele şekilde şehir sırasını değiştirmesidir. İlk görselde en kısa tur doğru bir biçimde bulunmuştur. Ancak 2. Kez çalıştırıldığında döngüde belli bir adımdan sonra değişim yapılmadığı için oldukça uzun bir rota oluşturulmuştur. Bunun düzeltilmesi için kodda randperm komutunun olduğu satırın düzeltilmesi yani algoritmanın değiştirilmesi gerekmiştir. Yeni kodda seçilen 9 şehirden 2’sinin yer değiştirilmesi yerine; 2. ve 9. genler arasında seçilen 9 gen rastgele değiştirilecektir.

İterasyon sayısı 100 için en iyi rotalar

3.4.2 İterasyon Sayısı 1000 İçin En İyi Sonuç
Randperm komutunda değişiklik yapılmadan önce seçilen 2 şehrin rastgele
değiştirildiği program 1000 iterasyonluk bir döngüyle 4 kez art arda çözülmüş ve rotanın 100’lük olandan daha iyi bir şekilde oluşturululduğu görülmüştür.

İterasyon sayısı 1000 için en iyi rota

3.5 Randperm Satırının Yeniden Düzenlenmesi
1000 döngülük grafiklerin 100 döngülük grafiklerden daha iyi olması, döngü sayısını arttırdığımızda doğru çözüme ulaşmayı kolaylaştırsa da, koddaki mutasyon kuralını biraz değiştirerek kısa sürede aynı çözüme ulaşmayı sağlayabilir. Bu sebepten ilk kodun nerede yanlış çalıştığı anlaşıldıktan sonra kodda düzenleme yapılmıştır. Bulunan uzun rotaların randperm komutunda 2 şehirde değişim yapmasından kaynaklandığı anlaşılınca bu sorunun düzeltilmesi için kodda mutasyonu sağlayan randperm komutunun bulunduğu bölüm değiştirilmiştir

Eski Kodda Bulunan Mutasyon Kodu

r = randperm(9,2)+1
krom(k,:) = krom(k-1,:)
krom(k, r(1)) = krom(k-1, r(2))
krom(k, r(2)) = krom(k-1, r(1))

Yeni Kodda Bulunan Mutasyon Kodu

For
k = 2:a
ra = randperm(9,2)+1;
krom(k,:) = krom(k-1,:);
krom(k, ra(2)) = krom(k-1, ra(1));
krom(k, ra(1)) = krom(k-1, ra(2));
end
for
r = randperm(9,9)+1;
krom(k,:) = krom(k-1,:);
krom(k, 2) = krom(k-1, r(1));
krom(k, 3) = krom(k-1, r(2));
krom(k, 4) = krom(k-1, r(3));
krom(k, 5) = krom(k-1, r(4));
krom(k, 6) = krom(k-1, r(5));
krom(k, 7) = krom(k-1, r(6));
krom(k, 8) = krom(k-1, r(7));
krom(k, 9) = krom(k-1, r(8));
krom(k, 10) = krom(k-1, r(9));
end

Yeni mutasyon kuralına göre artık seçilen 2 şehir rastgele değiştirildikten
sonra elde edilen en kısa çözüm üzerinde 9 şehir rastgele değiştitilerek iterasyona devam edilmektedir. Koddaki bu değişiklik sayesinde bulunan en iyi rotanın uzunluğu ve programın çalışma süresi kısalmıştır.

3.5.1 İterasyon Sayısı 1000 İçin En İyi Sonuç

3.5.2 İterasyon Sayısı 10000 İçin En İyi Sonuç

İterasyon sayısı 10000 için en iyi rotanın grafiği

3.5.3 İterasyon Sayısı 100000 İçin En İyi Sonuç

İterasyon sayısı 100000 için en iyi rotanın grafiği
İterasyon sayısı 100000 için en iyi rota
  1. SONUÇ VE ÖNERİLER
    Matlab kullanılarak yazılan kod sayesinde Gezgin Satıcı Problemi’nin Türk Hava Yolları kargo uçakları kasım ayı rotalanmasına uygulanmış halinin çözümü genetik algoritma sezgiseli ile en kısa rota olacak şekilde bulunmuştur. Kod büyük bir işlem yükünü geride bırakmasının yanında oldukça hızlı çalıştığından zamandan da tasarruf sağlamaktadır. Havaalanı sayısı 10 alınarak çözülen problem için, dilenirse koda çok kısa bir ekleme yapılarak istenildiği kadar havaalanı koordinatları eklenip minimum rota oluşturulabilir.

    Programın geliştirilmesi genetik algoritma kuralının değiştirilmesiyle
    sağlanabilir. Örneğin ilk kurala göre yalnızca rastgele 2 gen değiştirildiğinde belli bir adımdan sonra kromozom dizilimi değişmiyordu ve bu minimum rotaya ulaşılmasını engelliyordu. Bu sorun, rastgele seçilip değiştirilen gen sayısını 9’a çıkarılarak
    çözülmüştü ancak bunun yerine rastgele seçilen 2 gen’in yarattığı sorunu düzeltecek yeni bir kural mutasyon parametresi olarak eklenebilir.

    Tezin yazım aşamasında keşfedilen başka bir durum da mevcuttur. Yalnızca 2 gen değiştirildiğinde minimum rotaya ulaşılamamasının sebebi, bulunulan adımda minimum rotaya yalnızca 2 geni değiştirerek ulaşılmasının imkansız olmasıdır.
    Detaylı açılanacak olursa; mutasyon kuralının işleyiş biçimi:

    1- Rastgele 2 geni seç ve yerlerini değiştir, ilk kromozom A, değiştirilen
    kromozom B olsun
    2- B kromozomu A kromozomundan iyiyse, yani rotası daha kısaysa B
    üzerinde tekrar mutasyon uygula ve bu adımı iterasyon sayısı kadar
    devam ettir şeklindeydi. 4 köşeli bir çizit için problemi düşünelim.
    Örneğin en iyi rota 12341 ve başlangıç kromozomu 14231 olsun.
    Görüldüğü gibi en iyi rotada 1’den sonra 2 şehrine gidiliyor.
    Kromozomun ilk mutasyondan sonra 12431 olduğu kabul edilsin. Bu
    kromozomun 14231’den iyi olmama ihtimali vardır ancak en iyi rotada olduğu gibi 1’den sonra 2 şehrine gidildiği aşikardır. Ancak bu kromozom ilk kromozomdan iyi olmadığı takdirde bu mutasyon gerçekleşmeyecektir. Yani en iyi rotaya ulaşmak yalnızca 2 genin değiştirilmesiyle çok mümkün değildir. Kodun yazılma aşamasında bu sorunun fark edilmesi ve 9 genin değiştirilmesi kuralı eklenmesi sayesinde problem için en iyi çözümler elde edilebilmiştir. Tabi ki yine de kullanılan algoritmanın sezgisel bir algoritma olması sebebiyle her zaman en iyi çözümü elde etme imkanı bulunmamaktadır ancak kodun tekrar tekrar çalıştırılmasıyla %90 oranında en iyi çözümü bulduğu kaydedilmiştir.

Yazar: Gözde Tutan

Next Post

Previous Post

Leave a Reply

© 2022 Uçmak Ya Da Uçmamak

Theme by Anders Norén