Vol. 16, No. 2,  114-120,  Januari  2020 DOI: 10.20956/jmsk.v%vi%i.7016
 Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam,

## Universitas Hasanuddin
Email : karelsrheezaeffrains@gmail.com 1) ; jusmawati@gmail.com 2) ; nurdin1701@unhas.ac.id

## Penerapan Algoritma Genetika Pada Penentuan Lintasan Terpendek Jalur Bus Rapid Transit Makassar
Karels, Rheeza Effrains 1) , Jusmawati 2) , Nurdin 3 )

## Abstract
Bus  Rapid  Transit  is  a  bus  system  that  is  fast,  convenient,  safe  and  on  time  from  infrastructure, vehicles, and schedules.  As a graph problem, BRT representation in a graph is done by  assuming the bus  stop  as  a  vertices  and  the  distance  between  bus  stops  is  an  edge.  The  problem  examined  in  this paper is to find out the path that passes through all the bus stops with the smallest total distance, where the trip starts and ends at the same point, and all bus stops are crossed exactly once. The method used is the  Genetic  Algorithm,  which  works  using  objective  and  fitness  functions,  and  combines  selection, crossover  and  mutation  operators  to  find  the  best  solution.  Using  the  roulette  wheel,  OX  crossover method  and  a  0.07  of  the  probability  of  mutation,  the  distance  of  traverse  from  and  to  the  departure point after passing all bus stops is 19.66 km or 12.22 miles.
Keywords: BRT ( Bus Rapid Transit ), Genetic Algorithm, Roulette Wheel Method

## Abstrak
Bus Rapid Transit atau disingkat BRT adalah sebuah sistem bus yang cepat, nyaman, aman dan tepat waktu dari infrastruktur, kendaraan dan jadwal. Sebagai permasalahan graf, representasi BRT sebagai graf  dilakukan  dengan  menganggap  halte  sebagai  titik  dan  jarak  antar  halte  merupakan  sisi. Permasalahan  yang  dikaji  dalam  tulisan  ini  bertujuan  menemukan  jalur  yang  melewati  semua  halte dengan  total  jarak  paling  kecil,  dimana  perjalanan  berawal  dan  berakhir  pada  titik  yang  sama,  dan semua  halte  dilewati  tepat  sekali.  Metode  yang  digunakan  adalah  Algoritma  Genetika,  yang  bekerja menggunakan  fungsi  obyektif  dan  nilai  fitness,  serta  mengombinasikan  antara  operator  seleksi, crossover dan mutasi untuk menemukan solusi terbaik. Dengan menggunakan metode seleksi roulette wheel, crossover  OX  dan  peluang  mutasi  0,07  diperoleh  jarak  tempuh  dari  sejak  berangkat  sampai kembali  ke titik keberangkatan setelah  melewati  semua halte tepat sekali adalah 19,66 km atau 12,22 mil.
Kata Kunci : BRT ( Bus Rapid Transit ),  Algoritma Genetika , metode roulette wheel.

## 1.  Pendahuluan
Dalam  kehidupan  sehari  -  hari  masalah  transportasi  di  kota  -  kota  besar  sering  menjadi kendala  bagi  pemerintah  setempat  dikarenakan  jumlah  kendaraan  tiap  tahunnya  semakin bertambah,  tidak  terkecuali  di  kota  Makassar.  Hal  ini  mendorong  pemerintah  menciptakan sistem  transportasi  baru  yang  dikenal  dengan  nama  BRT  ( Bus  Rapid  Transit ).  BRT diluncurkan  oleh  pemerintah  dengan  tujuan  agar  masyarakat  memperoleh  akses  ke  tempat sarana umum yang nyaman, murah, dan mempunyai fasilitas yang lengkap serta mengurangi kepadatan  lalulintas  yang  disebabkan  oleh  kendaraan  pribadi  di  Makassar  yang  kian  hari semakin padat.

## Karels, Rheeza Effrains, Jusmawati, Nurdin
Salah  satu  hal  yang  menjadi  pertimbangan  dalam  membangun  BRT  adalah  menentukan jalur terpendek dari halte ke halte sehingga waktu tempuh maupun biaya operasional menjadi lebih  efisien.  Penentuan  jalur  terpendek  merupakan  salah  satu  kajian  graf  yang  berkaitan dengan    permasalahan  Traveling  Salesman  Problem  (TSP).  Prinsip  dari  TSP  adalah menemukan  jalur  (tour)  yang  paling  pendek  serta  urutan  kota-kota  yang  harus  dilalui  oleh salesman, sehingga diperoleh waktu tempuh/biaya/jarak paling  minimum sampai setiap kota dikunjungi tepat satu kali.
Traveling  Saleseman  Problem  merupakan  permasalahan  optimisasi,  dan  salah  satu metode  yang  tepat  digunakan  untuk  permasalahan  tersebut  adalah  Algoritma  Geentika. Algoritma Genetika tidak membtuhkan syarat dan asumsi tertentu, tetapi hanya menggunakan fungsi  obyektif  dan  dapat  menemukan  alternative  solusi  terbaik  untuk  permasalahan  yang tidak mempunyai solusi sekalipun.

## 2. Beberapa Konsep Dasar dan Permasalahan Graf
Permasalahan  yang  sering  dijumpai  di  dunia  nyata  dapat  diselesaikan  melalui  formulasi matematis, dan salah satu di antaranya adalah dengan melalui graf.
Graf  merupakan  struktur  diskrit  yang  terdiri  dari  pasangan  himpunan  berhingga  dari obyek yang disebut titik ( vertex ) dan pasangan titik yang disebut sisi ( edge ).
Definisi  1. Suatu  graf  G  merupakan  suatu  pasangan  himpunan  (V,  E)  dinotasikan  dengan G = (V, E), dengan V adalah himpunan berhingga dan tidak kosong dari objek - objek yang disebut titik (vertex) dan E adalah himpunan pasangan tidak terurut dari elemen  - elemen V yang berbeda yang disebut sisi (edge).
Salah  satu  permasalahan  di  dalam  graf  yang  dapat  digunakan  untuk  menyelesaikan berbagai fenomena di dunia nyata adalah Traveling Salesman Problem (TSP) . TSP berkaitan dengan  pencarian  rute  optimal  sedemikian  sehingga  seorang  salesman  dapat  mengunjungi semua tempat tepat satu kali, dimulai dari dan kembali ke tempat asal yang sama.
Permasalahan Bus Traffic Transit merupakan permasalahan yang dapat direpresentasikan sebagai permasalahan TSP. Contoh lain yang berkaitan dengan TSP  adalah pencarian rute bis sekolah  untuk  mengantarkan  siswa,  pengambilan  tagihan  telepon,  efisiensi  pengiriman  surat atau  barang,  perancangan  pemasangan  pipa  saluran  dan  lain-lain.  Persoalan  yang  muncul adalah bagaimana cara mengunjungi node (simpul) pada graf dari titik awal ke setiap titik  - titik  lainnya  dengan  bobot  minimum  (biaya  paling  murah)  dan  kembali  lagi  ke  asal  node. Bobot atau biaya ini sendiri dapat mewakili berbagai hal, seperti berapa biaya minimum, jarak minimum, bahan bakar minimal, waktu minimum dan lain - lain.

## 3. Algoritma Genetika

## 3.1 Istilah dalam Algoritma Genetika
Algoritma  genetika  merupakan  teknik  pencarian  heuristic.  Istilah-istilah  dan  parameter- parameter yang sering muncul dalam Algoritma Genetika adalah:
- Populasi, merupakan sejumlah kemungkinan solusi dan merupakan kumpulan kromosom.
- Gen,  variabel  dasar  yang  membentuk  suatu  kromosom.  Gen  dapat  bernilai  biner,  float, integer maupun karakter.
- Kromosom,  individu  yang  terdapat  dalam  satu  populasi  dan  merupakan  gabungan  gen  - gen yang membentuk nilai tertentu.
- Generasi, populasi awal dibangun secara acak sedangkan populasi selanjutnya merupakan hasil  evolusi  kromosom-kromosom  melalui  iterasi  dan  menyatakan  satu  siklus  proses evolusi atau satu iterasi di dalam algoritma genetika.
- Fungsi Fitness, alat ukur yang digunakan untuk proses evaluasi kromosom. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut.
- Offspring yang  terbentuk  dari  gabungan  dua  kromosom  induk  ( parent )  yang  muncul sebagi akibat dari seleksi , penyilangan (crossover) atau mutasi

## 3.2 Operator Algoritma Genetika Sederhana
Secara garis besar, operator dalam algoritma genetika terdiri dari 3 operator, yaitu:
1. Seleksi (Reproduksi)
Operator  reproduksi  memiliki  beberapa  metode  seleksi  diantaranya  yaitu roulettewheel , tournament selection dan lain-lain. Dalam masalah kali ini digunakan seleksi dengan metode roulettewheel .  Seleksi  ini  bertujuan  untuk  memberikan  kesempatan  reproduksi  yang  lebih besar bagi anggota populasi yang memiliki fitness tinggi untuk melakukan reproduksi.
2. Penyilangan ( crossover )
Operator  selanjutnya  setelah  reproduksi  yaitu  penyilangan  ( crossover ).  Penyilangan dilakukan atas 2 kromosom untuk  menghasilkan kromosom  baru/ offspring . Kromosom anak yang  terbentuk  akan  mewarisi  sebagian  sifat  kromosom  induknya.  Metode crossover yang paling  sering  digunakan  antara  lain  adalah  penyilangan  satu  titik  ( one-point  crossover ), penyilangan  banyak  titik  ( multi-point  crossover ),  atau  penyilangan  dengan  Metode  Order (OX).

## 3. Mutasi
Operator  mutasi  akan  mengubah  nilai  dari  suatu  kromosom  pada  posisi  tertentu berdasarkan  peluang mutasi. Peluang mutasi menunjukkan presentasi jumlah total gen pada populasi yang akan mengalami mutasi.

## 3.3 Penentuan Parameter
Parameter kontrol dalam Algoritma Genetika meliputi ukuran populasi (popsize), peluang crossover (p c ) dan peluang mutasi (p m ). Beberapa nilai yang direkomendasi untuk penentuan parameter diberikan sebagai berikut:
- Untuk  permasalahan  yang  memiliki  kawasan  solusi  cukup  besar,  De  Jong merekomendasikan nilai parameter : (popsize; p c ; p m ) = (50; 0,6; 0,001).
- Bila  rata-rata  fitness  setiap  generasi  digunakan  sebagai  indikator,  maka  Grefenstette merekomendasikan : (popsize; p c ; p m ) = (30; 0,95; 0,01).
- Bila  fitness  dari  individu  terbaik  dipantau  pada  setiap  generasi,  maka  usulannya  : (popsize; p c ; p m ) = (80; 0,45; 0,01).
- Ukuran  populasi  sebaiknya  tidak  lebih  kecil  dari  30,  untuk  sembarang  jenis permasalahan.

## 4. Hasil Dan Pembahasan
- Sebagaimana  telah  disebutkan  sebelumnya,  permasalahan  BRT  dapat  diterjemahkan sebagai  sebuah  permasalahan  graf.  Dalam  hal  ini,  sebuah  halte  digambarkan  sebagai sebuah titik graf, sedangkan jalur yang menghubungkan antar halte digambarkan sebagai sebuah sisi graf. Secara lebih khusus, persoalan jalur BRT ( Bus Rapid Transit ) berkaitan dengan  graf  terboboti,  dimana  sisi  -  sisi  graf  memiliki  bobot  yang  bersesuaian  dengan jarak koordinat antara 2 halte terhubung. Data diperoleh dari penelusuran jalur BRT kota Makassar  melalui  Google  Map  sebagaimana  diperlihatkan  pada  Gambar  1  dengan  titik koordinat  dan  jarak  antara  halte  ditampilkan  pada  Tabel  1.  Jarak  dari titik  ke  titik menggunakan perhitungan jarak Euclidean
Gambar 1. Peta jalur BRT kota Makassar
Tabel 1.

## Karels, Rheeza Effrains, Jusmawati, Nurdin
Berdasarkan  Gambar  1.  maka  representasi  graf  yang  bersesuaian  memiliki  titik sebanyak 11 dan sisi sebanyak 10.

## 4.1  Pengukuran Populasi
- Nilai obyektif
Setiap  individu  di  dalam  populasi  menggambarkan  sebuah  jalur  dengan  nilai  objektifnya berupa  total  bobot  sisi dari  graf.  Dalam  hal ini  setiap  individu  dikodekan  ke  dalam  susunan acak 11 bilangan integer yang  menggambarkan urutan jalur-jalur bus dimulai dari titik awal yang  tetap  dan  selanjutnya  menuju  ke  halte  yang  bersesuaian  dengan  bilangan  berikutnya yang muncul pada kode individu. Nilai objektif dari setiap individu dihitung dengan rumus
∑
dengan  ( ) merupakan jarak antara dua titik/halte sebagimana diberikan pada Tabel 1.
Sebagai  contoh,  individu:  1    10    2    4    7    3    6    9    8    5    11  menggambarkan  rute  yang dimulai  dari  titik  awal  1,  kemudian  berturut-turut  ke  halte  10,  2,4,7  dan  terakhir  ke  11 sebelum akhirnya kembali ke titik awal 1. Nilai obyektif untuk individu tersebut adalah 28,07. Nilai obyektif tersebut menyatakan jarak tempuh dengan urutan halte seperti tersebut di atas.
- Nilai Fitness
Setiap  individu  memiliki  nilai  ukuran  yang  disebut  fungsi  fitness.  Makin  besar  nilai fitness  dari  suatu  individu,  makin  besar  kemungkinan  individu  tersebut  bertahan  sampai generasi  berikutnya.  Jika  permasalahan  yang  dikaji  berkaitan  dengan  penentuan  nilai maksimal,  maka  fungsi  fitness  dikonstruksi  sebagai  fungsi  yang  berbanding  lurus  dengan fungsi obyektif.  Sebaliknya, jika permasalahan yang dikaji berkaitan dengan penentuan nilai minimal,  maka  fungsi  fitness  dikonstruksi  sebagai  fungsi  yang  berbanding  terbalik  dengan fungsi obyektif.
Karena  masalah  BRT  berkaitan  dengan  persoalan  meminimalkan  jarak  tempuh,  maka nilai fitness dikonstruksi dengan  menggunakan rumus :

## ( )
Tabel 2. menunjukkan populasi awal berukuran 10 dengan nilai fitness masing-masing.
Tabel 2.
Dengan  proses  seleksi  menggunakan  metode  roulette  wheel,  crossover  menggunakan metode order OX, dan dengan peluang mutasi 0,07, ukuran populasi 10 serta jumlah generasi 100,  maka  diperoleh  nilai  fitness  minimum  0,05084.  Nilai  ini  tercapai  dari  generasi  ke  80 sampai  generasi  sesudahnya.  Pengulangan  running  program  menghasilkan  nilai  minimum yang sama.  Individu yang bersesuaian dengan nilai fitness minimum adalah,
1 7 6 11 8 5 4 2 3 9 10
dengan urutan jalur sebagaimana diperlihatkan pada Gambar 2. berikut ini:
Gambar 2. Jalur BRT dengan total jarak minimum

## 4.  Kesimpulan
Permasalahan  BRT  ( Bus  Rapid  Transit )  yang  dikaji  dalam  tulisan  ini  berkaitan peminimalan  total  jarak  antara  halte  sekali  tempuh  hingga  kembali  ke  titik  awal keberangkatan. Terminologi jarak yang digunakan dibatasi pada jarak Euclid antara halte dan tidak  mempertimbangkan  jalur  yang  dilewati.  Dengan  menggunakan  Algoritma  Genetika pada  populasi  berukuran  10  dengan  pengulangan  atau  generasi  sebesar  100,  maka  nilai optimal diperoleh ketika fungsi fitness bernilai 0,05084, dengan total jarak minimum sebesar 19,66  km  atau  setara  dengan  12,22  mil.  Rute  yang  ditempuh  direpresentasikan  oleh kromosom: 1 7 6 11 8 5 4 2 3 9 10 dengan rute seperti pada Gambar 2.

## Karels, Rheeza Effrains, Jusmawati, Nurdin

## Daftar Pustaka
[1]  Amin, A. R., Ikhsan, M., & Wibisono, L., 2003. Traveling   SalesmanProblem. Institut Teknologi Bandung.
[2]  Chartrand,  G.,  &  Zhang,  P.,  2005. Introduction  to  Graph  Theory. McGraw-Hill,  New York
[3]  Kumara Sastry, David Goldberg. https://pdfs.semanticscholar.org/ 8ed1/
d9f5a017c61abfec4089aba828b398aa3e7e.pdf  (diakses 10 Junli 2019)