Sistem Penjadwalan Pesawat

Penentuan Waktu Take Off dan Landing Pesawat Terbang disuatu Bandara Menggunakan Algoritma Genetik

Lamaaaaaaaaaa sekali saya tidak membuka blog ini. Apalagi menuliskan sesuatu didalamnya (-_-") Agak mengejutkan, ternyata traffic pengunjung menunjukkan ADA orang yang pernah kesini selama beberapa minggu lalu (lol) (*o*)d ~> thanks for coming!

Kali ini, saya akan menuliskan sesuatu yang agak ilmiah (hm). Jarang-jarang euy! Jadi mohon diperhatikan dengan seksama ya (haha)
 

Begini ceritanya....

Disuatu bandara, sebut saja inisialnya JS (Juanda Surabaya), ada masalah dalam menentukan pengaturan waktu jadwal terbang pesawat. Kapan pesawatnya terbang, kapan mendarat. Pesawatnya kan banyak. Apalagi landasannya terbatas. Biar mempersempit permasalahan, kita hitung dalam sehari (oke?). Itu masalahnya dan akan kita selesaikan dengan Genetic Algorithm (GA) menggunakan aplikasi RStudio. Untuk memperolehnya, sila nak klik untuk download R lalu RStudio

Nah sekarang muncul permasalahan lagi. Apa itu Genetic Algorithm? Tak jelasin secara singkat aja ya. Kalo kurang jelas leave a comment (y)
 .

Genetic Algorithm (GA) adalah ilmu menghitung secara logika dan komputerisasi dengan prinsip heuristik. (apalagi itu heuristik?) Heuristik adalah cara melakukan sesuatu dengan mengandalkan 'pegangan'. Jelasin emang paling gampang pake contoh, misalkan aku mau kesuatu tempat tapi tersesat dan tak tau jalan. Yang aku tau cuma tempatnya berada di utara. Jadi, aku jalan ke utara teruss walaupun berliku tetap ke utara.
.

Pada teknik GA ini, akan ada banyak kemungkinan solusi yang bisa dilakukan. Yang mana dinamakan genetic (ada banyak kromosom didalamnya). Namun teknik ini dicarikan solusi yang terbaik. Itu!

.
Sekarang, sumonggo kita bahas masalah tadi.

Asumsikan bandara JS memiliki 5 maskapai penerbangan, sebut saja inisialnya:

1. GI (Garuda Indonesia)

2. LA (Lion Air)

3. W (Wings)

4. SA (Sriwijaya Air)

5. AA (Air Asia)

.
Tiap-tiap dari maskapai penerbangan tersebut punya penjadwalan sendiri-sendiri untuk take off dan landing di bandara JS. Untuk langkah strategis mereka, tiap-tiap maskapai juga mempersiapkan waktu cadangan kalo terjadi perubahan waktu. Daftar penjadwalannya sebagai berikut:

Sebelum memulai, pastikan juga telah terinstall animation packages kalo belum download sini genalg , ggplot2 dan animation Masing-masing install di RStudio dengan cara klik tools ~> install packages ~> pilih hasil download (.zip) ~> ok. Untuk membuktikan bahwa berhasil terinstall, ketik library(genalg) ~> enter dan library(ggplot2) ~ enter

Barulah kita mainkan RStudionya, ikuti langkah-langkahnya:

1. Caranya ketik ini buat bikin tabel:

dataset <- data.frame(Maskapai = c("GI", "LA", "W", "SA"), TotalWaktu = c(45, 36, 39, 27), LamaWaktu = c(9, 9, 13, 9))
weightlimit <- 390
 

Untuk melihat hasilnya ketikkan:

View(dataset)

2. Kemudian ini buat kemungkinan:

chromosome = c(1, 1, 1, 1)
dataset[chromosome == 1, ]

3. Ini yang didapat dari kemungkinan tadi:

cat(chromosome %*% dataset$TotalWaktu)

4. Nah kita masukkan rumusnya:

evalFunc <- function(x) {
+     current_solution_TotalWaktu <- x %*% dataset$TotalWaktu
+     current_solution_LamaWaktu <- x %*% dataset$LamaWaktu
+     if (current_solution_LamaWaktu > weightlimit) 
+         return(0) else return(-current_solution_TotalWaktu)
+ }

5. Disinilah fungsi animation packages digunakan, ketik syntax berikut:

iter = 100
GAmodel <- rbga.bin(size = 4, popSize = 200, iters = iter, mutationChance = 0.01, 
+                     elitism = T, evalFunc = evalFunc)

6. Untuk summary:

cat(summary.rbga(GAmodel))

Nanti akan muncul hasil sebagai berikut:

GA Settings
  Type                  = binary chromosome
  Population size       = 200
  Number of Generations = 100
  Elitism               = TRUE
  Mutation Chance       = 0.01

Search Domain
  Var 1 = [,]
  Var 0 = [,]

GA Results
  Best Solution : 1 1 1 1  

Artinya: Solusi terbaik adalah semua maskapai pesawat diberangkatkan

7. Masukkan hasilnya disini:

solution = c(1, 1, 1, 1)
dataset[solution == 1, ]

Ini hasilnya:
 

 Maskapai TotalWaktu LamaWaktu
1       GI         45         9
2       LA         36         9
3        W         39        13
4       SA         27         9

8. Terakhir, kita buat animasinya:

animate_plot <- function(x) {
+     for (i in seq(1, iter)) {
+         temp <- data.frame(Generation = c(seq(1, i), seq(1, i)), Variable = c(rep("mean", 
+                                                                                   i), rep("best", i)), TotalWaktu = c(-GAmodel$mean[1:i], -GAmodel$best[1:i]))
+         pl <- ggplot(temp, aes(x = Generation, y = TotalWaktu, group = Variable, 
+                                colour = Variable)) + geom_line() + scale_x_continuous(limits = c(0, 
+                                                                                                  iter)) + scale_y_continuous(limits = c(0, 110)) + geom_hline(y = max(temp$TotalWaktu), 
+                                                                                                                                                               lty = 2) + annotate("text", x = 1, y = max(temp$TotalWaktu) +  
+                                                                                                                                                                                       2, hjust = 0, size = 3, color = "black", label = paste("Best solution:", 
+                                                                                                                                                                                                                                              max(temp$TotalWaktu))) + scale_colour_brewer(palette = "Set1") + 
+             labs(title = "Evolution Knapsack optimization model")
+         print(pl)
+     }
+ }

library(animation)
saveMovie(animate_plot(), interval = 0.1, outdir = getwd())

Hasil diatas digunakan untuk kategori pagi




Langkah yang sama dilakukan pada kategori siang, sore, dan malam. Berikut ini hasilnya:
 
-siang

 Maskapai TotalWaktu LamaWaktu
1       GI         35         7
2       LA         32         8
3       SA         40         8

GA Results
  Best Solution : 1 1 1 

-sore

 Maskapai TotalWaktu LamaWaktu
1       GI         56         14
2       LA         40         8
GA Results
  Best Solution : 1 1

-malam 

 Maskapai TotalWaktu LamaWaktu
1       GI         36         9
2       LA         30        10
3        W         32         8
4       SA         48         8

GA Results
  Best Solution : 1 1 1 1  

Sedangkan dalam realisasinya adalah menjadi:

Bisa dikonversikan seperti gambar berikut:

"I'm just a beginner and yet starting to learn DSS. So, CMIIW" 

03/21/2013 

 Referensi:.

 http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/tcw2/report.html

 http://www.r-bloggers.com/genetic-algorithms-a-simple-r-example/