Tez No |
İndirme |
Tez Künye |
Durumu |
496357
|
|
Aircraft parking optimization using genetic algorithm / Genetik algoritma kullanarak uçak park yeri optimizasyonu
Yazar:BURAK GÜLER
Danışman: DR. ETİ MİZRAHİ
Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Mühendisliği Ana Bilim Dalı
Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Matematik = Mathematics
Dizin:
|
Onaylandı
Yüksek Lisans
İngilizce
2018
61 s.
|
|
Havacılığın büyümesi bir çok yeni probleme neden oldu. Bu problemlerden bir tanesi
de GAP (Kapı Atama Problemi [Gate Assignment Problem]) dir. Uçak sayısındaki
artı¸sın sebep oldu˘gu yoğunluk havalimanlarının verimli şekilde kullanılmasını zorunlu
kılmaktadır. Uçakların park pozisyonları operasyonel maliyetleri etkilediği gibi
transit yolcuların ve yolculara ait bagajların bir sonraki uçağa yetişebilmesini de
etkilemektedir. GAP in amacı uçakları en uygun şekilde park ettirerek havalimanının
verimli kullanılmasını sağlamaktır. Literatürde, ilk olarak toplam yürüme mesafesi
hedef fonksiyon olarak, ardından toplam yürüme mesafesi ve bagajların bir sonraki
uçuşa olan uzaklıkları hedef fonksiyon olarak kullanıldı.
GAP, Babic ve diğerleri [2] tarafından 1980'lerde tam-sayılı program kullanılarak
araştırılmaya başlandı ve bu konuda yapılan araştırmalar sürdü. İlerleyen yıllarda,
deterministik model yerine istatistiksel modeller tercih edildi. Çeşitli simulasyon
modelleri Yu Cheng tarafından problemin çözümü olarak önerildi [3]. Bolat [4] ise
hedef fonksiyonunu transit yolcu ya da bagaj uzaklığı almayıp operasyonel maliyetleri
hedef fonksiyonu seçmiştir. İlk defa 1998'de GA (Genetik Algoritma [Genetic
Algorithm]) , GAP için kullanıldı [5]. Bu karma¸sık problemin hesaplanması GA ile
kısaltılmıştır. 2001 yılında çoklu hedef fonksiyonu önerildi [6]. Bağlantı (Linkage) ve
düzenli dağılım metodu GAP için Paolo [7] tarafından kullanıldı.
Bu tezde, GAP, GA yöntemi kullanılarak çözüldü. Toplam transit yolcu yürüme
mesafesi hedef fonksiyon olarak seçildi. Bu metod havacılık maliyetlerini dü¸sürmeyi
ve mü¸steri memnuniyetini yükseltmeyi hedeflemektedir. Bu da gecikmeleri ve
geciken uçak sayısını azaltmaktadır. GA uygulaması herhangi bir hazır program
kullanmadan GAP için, web arayüzü kullanılarak "http://genetik1.netf13.com/home"
üzerinde geliştirildi.
Bu tezde özellikle aktarma merkezi olan havalimanları için operasyon maliyetlerini
minimize edecek ¸sekilde uçak yerleştirme optimizasyonu yapıldı. GAP'in uçak
yerleştirme süreci yeterince dikkatli takip edilmezse havalimanlarının programları
etkilenebilmektedir. Benzer çalışmalar daha önce yapılmış olsa da bu çalışma
uygulama web arayüzü ile etkile¸simli bir programdır. Bu çalışmada, GA'nın
doğadan ilham aldığı vurgulanmaktadır. Bu tarz programlar doğanın doğal seçim
kurallarından etkilenerek çalı¸sırlar. Genetik algoritma evrimsel bir algoritma olup
uygun parametreler ile çalışmaktadır. Bu parametreler GAP'e uygun ve problemin
veri hacmine göre seçilmiştir.
Geliştirilmiş Permütasyon kodlama bu çalı¸sma için uygundur çünkü normal
permütasyon kodlama boş değerlerin gösteriminde yetersiz kalmaktadır. OX (Düzenli
parça değişimi [Ordered Crossing over]) ve PMX (kısmi eşleştirmeli parça değişimi
PMX [Partially Mapped Crossing-over]) permütasyon kodlama için uygundur fakat OX
tekniği boş değerler içeren permütasyon kodlama için daha iyidir.
Bu çalışmada PHP programı algoritma için, HTML ise GUI (kullanıcı arayüzü
[Graphic User Interface]) için ve MySQL4 ise veritabanı için kullanılmıştır. Bu
programda GUI olduğundan kullanıcılar web sitesini ekileşimli şekilde kullanabilir.
Kullacı istediği parametreleri kullanarak, en iyi 5 çözüme ulaşabilir, bu çözümleri
analiz edebilir ve inceleyebilir.
Tablo, '0data_set_gate' bir kare matris olup kapılar arasındaki uzaklı˘gı göstermektedir.
'data_set_plane' matrisi kare matris olup uçaklar arasındaki transit yolcu sayısını
göstermektedir. Buna ek olarak "açık" tablo programın kolay kullanılması ve
parametrelerin hafızada tutulması ve küme olarak kullanılabilmesi içindir. Son
olarak, parametreler ve sonuçlar "stat" tablosunda tutulmaktadır. Program arka planda
veritabanı ile haberleşmekte, algoritmayı çalıştırmaya başlamadan parametreleri
kontrol etmekte ve son olarak PHP ile çalıştırılmaktadır. PHP kodları Burak Durukan
tarafından, algoritma tasarımı ise Burak Güler tarafından yapılmıştır.
Program testlerinde, en son adım metodu sonuç bulmak için kullanıldı˘gında sonuçlar
büyük bir rassallık göstermektedir. Algoritma çok net sonuçlar vermemektedir.
Algoritma'nın yapay zeka gibi çalı¸sıyor olması için durgun adım (stagnant step)
parametresi kullamalıdır. Durgun adım parametresi kullanıldığında algoritma, çok
büyük adımlara gelmeden de sonuç bulabilmektedir. Durgun adımlar parametresi ile en
iyi sonuçları erken adımlarda bulabiliyoruz. Bu çalışma durgun adım parametresinin,
final adım sayısının 1/5 ile 1/9 arasında olduğunu gösterdi. Diğer sonuç süresini
etkileyen, kullanılabilir parametre ise mutasyon oranıdır. En iyi mutasyon oranı
ise 0,06 ile 0,11 arasındadır. Daha yüksek mutasyon oranı sonuca olumsuz yansır
ve çözüm süresini uzatır. Sonucun iyileşmesini sağlayan bir diğer parametre ise
elitizmdir.
Sonuç olarak benzer çalışmalar yapılmış olsa da bu çalışma halka açık ve web
sitesi üzerinde yürütülebilmektedir. Bu program kolayca geliştirilebilirdir çünkü
bir sınıfta yapılan değişik sadece ilgili kısmı etkilemekte, programın geri kalanını
etkilememektedir.
|
|
The growth of aviation industry created new problems. One of these problems is the
GAP (Gate Assignment Problem). Increasing aircraft traffic at large airports requires
the effective use of gates. Airplane parking positions have affected the operational
costs as well as the ability of transit passengers and their baggage to reach the next
flight. The goal of GAP is to park aircrafts at the appropriate locations on the ground
to ensure that airport parking area is used in a most efficient way. In literature, first the
total walking distance of transit passengers, then the distance from the parking position
to the baggage area and the total distance to the next flights of transit passengers are
used as the target function.
In 1980s, Babic et al. [2] did some research on this problem by using
integer-programming and it got investigated by many others. In the following years,
statistical models were preferred instead of deterministic models. Various simulation
models were proposed by Yu Cheng [3]. Bolat [4] took operational costs as a target
function instead of transit passengers or baggage distance. For the first time in 1998,
GA [5] was used for GAP. The calculation of this complicated problem (GAP) is
shortened using GA. In 2001, multiple targeted problems have been proposed [6].
Linkage and uniform gene exchange methods were used for GAP by Paolo [7].
In this thesis, GAP is solved by GA method. Total transit passenger walking distance is
used as an objective function. This method aims to minimize airline cost and maximize
customer satisfaction. This will also minimize the time delay and the number of
delayed planes. The GA has been developed properly for GAP without any use
of GA program package, and it has been introduced in the interface of a web page
'http://genetik1.netf13.com/home'.
This paper aims the optimization of planes allocation in order to minimize the
operation cost, especially in hub airports. Gate assignment problem (GAP) is a process
which affects hub airports scheduling if it is not handling with a great attention. Even
there are similar studies, this paper's application runs on an interactive and open to
public web page. In this thesis, it is emphasized that GA gets inspiration from natural
selection. These type of algorithms are successful in problem-solving because they
use the nature's rules of survival. A genetic algorithm is an evolutionary algorithm.
So there must be appropriate parameters of the algorithm to work properly. These
parameters are chosen in accordance with GAP and the size of the problem.
While coding the program, a modular structure was constructed. This program can be
developed easily because changes in a specific class are only effective within its class.
As a result of this, changes do not affect the general working protocol.
Enhanced Permutation Code is appropriate for this study because normal permutation
code is insufficient for null values in representation. OX and Partially Mapped CO
(PMX) are appropriate for permutation representation but OX is better for permutation
with null values.
xix
In this application, PHP is used for the algorithm, HTML is used for GUI and MySQL4
is used for the database. As this program is a GUI, it allows other people to go
to the web-site and interact. While coding the programme, a modular structure was
constructed. The user can choose any parameter and start the program. However, by
using their preferred parameters, they can get top 5 results, analyze and examine them.
0data_set_gate0 table is a square matrix that indicates the distance between the
gates. 0data_set_plane0 table is a square matrix that indicates the number of transit
passengers on a plane. Furthermore, 'open' table is for the easy use of the program with
memorizing and accessing usable parameter sets. In the end, parameters and results are
kept in the "stat" table. On the background, communication with the database, the start
of the algorithm and parameter checks and setup is provided from PHP. This object
oriented PHP system is coded by Burak Durukan and algorithm is designed by Burak
Güler. The program and the code in the thesis is stored in a CD. Running parameters
and results can be seen 3.1 and 3.2 sections.
During the trials, when the final step is used to get a result, the outcome turns out to be
random. The algorithm does not give palpable results in the final step. The algorithm
should work like an artificial intelligent so stagnant step is preferable parameter for it.
Using stagnant step gives a chance for algorithm to find a solution before the final step
which is determined earlier but in big numbers. The stagnant step forces algorithm
to stop after getting the best result. This study shows that the best stagnant step is
between 1/5 and 1/9 of the final step.
Another usable parameter that affects run time of the algorithm is mutation rate.
Studies show that the best mutation rate for this algorithm is between 0,06 and 0,11.
Due to direct changes in solutions, higher mutation rate is unnecessary and negative
for the result. Another parameter behind the best result is elitism.
There have been similar studies about GAP before. However, what makes this
application unique is that it can be run on a web-page and is open to public. This
program is open to further development as changes in a class are only effective within
its class. Changes do not affect the general working protocol. |