Perbaikan Rute Bus Trans Jogja dengan Menggunakan Algoritma Floyd-Warshall
Fenny Fitriani 1 , Eka Sudilowati 2
1 Universitas PGRI Adi Buana Surabaya, fenny_f@unipasby.ac.id
2 Universitas PGRI Adi Buana Surabaya, eka250@gmial.com
Abstract. Yogyakarta  is  one  of  the  city  with  the  traffic  problems.    This  is  caused  by many  newcomers,  students  and  workers,  from  outside  the  region  Yogyakarta  which contribute  by  donate  jam  level.  Trans  Jogja  Bus  is  one  of  public  transportation  that provided by the goverment Yogyakarta to reduce traffic congestion. Trans Jogja bus has on several route. In this research is done study on the track of  Trans Jogja bus. In this researsch, we used floyd-warshall algorithms to determained the rute of Trans Jogja bus. The results obtained from this algorithm is the remain rute of Trans Jogja Bus still not steady.
Keywords : Trans Jogja, rute, Floyd-Warshall Algorithm.
Abstrak. Yogyakarta  merupakan  salah  satu  kota  yang  mengalami  permasalahan kemacetan.  Hal ini disebabkan oleh banyaknya pendatang, pelajar dan pekerja, dari luar daerah  Yogyakarta  yang  ikut  andil  dalam  menyumbangkan  tingkat  kemacetan.  Bus Trans  Jogja  merupakan  sarana  transportasi  umum  yang  disediakan  pemerintah Yogyakarta untuk mengurangi kemacetan. Bus Trans Jogja tersebut memiliki beberapa jalur trayek. Dalam penelitian ini dilakukan kajian mengenai jalur dari bus Trans Jogja. Metode  yang  digunakan  dalam  penelitian  ini  adalah  Algoritma  Floyd-Warshall.  Hasil yang didapatkan dari algoritma adalah jalur yang ada pada dari bus Trans Jogja masih belum optimum.
Kata Kunci : Trans Jogja, rute, Algoritma Floyd-Warshall .

## 1 Pendahuluan
Yogyakarta merupakan salah satu kota yang mengalami masalah kemacetan lalu lintas. Banyaknya  pendatang  yang  datang  ke  Yogyakarta  terutama  pelajar  dan  mahasiswa mengakibatkan banyak sepeda motor yang beredar di sana. Pemerintah kota Yogyakarta sebenarnya  telah  memperbaiki  pelayanan  transportasi  salah  satunya  dengan pengoperasian bis Trans Jogja.
Pengaturan  rute  merupakan  faktor  penting  yang  diperhatikan  agar  daerah-daerah di Yogyakarta dapat dijangkau menggunakan bis Trans Jogja. Harapan pemerintah kota Yogyakarta  adalah  agar  dapat  mengurangi  angka  kemacetan  lalu  lintas  karena pengendara  sepeda  motor  beralih  ke  alternatif  transpostasi  lain,  yaitu  bis  Trans  Jogja dengan perbaikan kenyamanan dari bis pendahulunya.
Salah  satu  cara  dalam  mengatur  rute  yang  telah  ada  adalah  dengan  melakukan perbaikan  jalur.  Perbaikan  jalur  tersebut  dapat  dilakukan  dengan  menggunakan beberapa  metode.  Salah  satu  metode  yang  sering  digunakan  adalah  algoritma  Floyd- Warshall. Algoritma Floyd-Warshall telah digunakan untuk menentukan jalur terpendek
pada penentuan tata letak parkir [2], penentuan jalur terpendek dari tempat  wisata [1], dan  menentukan  rute  terpendek  dari  rute  transmusi  [3].  Berdasarkan  uraian  di  atas, maka  pada  penelitian  ini  dilakukan  pengoptimalan  rute  bis  Trans  Jogja  dengan menggunakan algoritma Floyd-Warshall.

## 2 Metode Penelitian
Penelitian  dalam  perbaikan  rute  bus  Trans  Jogja  ini  dilakukan  dengan  mengubah  jalur dari bus  trans  jogja ke dalam bentuk  graf berarah berbobot.  Bobot  yang  ada pada  graf berarah tersebut adalah jarak dari satu halte ke halte berikutnya. Dari hasil graf berarah dan  berbobot  tersebut,  kemudian  di  analisis  ke  dalam  algortima  floyd-warshall.  Dari hasil analisis tersebut kemudian diambil suatu kesimpulan.

## 3 Hasil dan Pembahasan
Dalam  penelitian  yang  dilakukan,  jalur  bus  trans  jogja  yang  diteliti  adalah  jalur  dari trayek 1A, 1B, 2A, 2B, 3A, 3B, 4A, dan 4B. Hasil pembentukan graf berarah dari jalur tersebut pada Gambar 1.
Gambar 1. Graf Berarah Berbobot Jalur Bus Trans Jogja
Dari  graf  berarah  pada  Gambar  1  kemudian  dibentuk  matirks  ketetanggaan  sebagai berikut:
Dimana  nilai  A(i,j)  pada  matriks  di  atas  menunjukkan  jarak  antara  halte i ke  halte j . Nilai  pada  matriks  A  apabila  mendapatkan  nilai  A(i,j)=0,  maka i maupun j mewakili halte yang sama. Sedangkan nilai A(i,j)= inf menunjukkan bahwa halte i tidak terhubung langsung dengan halte j .
Matriks  ketetanggan  A  tersebut  kemudian  dijadikan  sebagai  inputan  dalam algoritma Floyd Warshall yang telah dituangkan dalam MATLAB. Berikut list program yang digunakan dalam  mencari jarak terpendek  dengan  menggunakan algoritma  Floyd Warshall.
%Pembentukan matriks ketetanggaan for i=1:a c=ujid(i,1); d=ujid(i,2); p(c,d)=ujid(i,3); end for i=1:e for j=1:e g=p(i,j); if g==0 if i==j p(i,j)=0;
else p(i,j)=inf;
end end end end
%Pembentukan matriks jarak terpendek antar simpul for k=1:e for i=1:e for j=1:e ban=p(i,j); ban1=p(i,k)+p(k,j); if ban1<ban
p(i,j)=ban1; end
end end end
Dari  list  program  di  atas,  setelah  dilakukan  proses running di  dapatkan  hasil berikut:
Tabel 1. Jalur Terpendek Antar Halte
Jarak tiap halte tersebut dijadikan sebagai patokan dalam perbaikan rute bus Trans Jogja. Tiap rute trayek bus Trans Jogja dipilih 2 halte utama yang digunakan sebagai patokan. Berikut  merupakan  hasil  yang  didapatkan  setelah  mencari  jarak  terpendek  dengan menggunakan algoritma Floyd Warshall:

## Trayek 1A
Halte utama yang diambil adalah halte Prambanan dan halte Malioboro 1. Hasil dari algoritma  Floyd  Warshall  untuk  trayek  1A  adalah  rute  berikut:  Halte Prambanan→Halte  KR  1→Halte  Bandara  Adi  Sucipto→Halte  Jayakarta→  Halte Janti  Fly  Over→Halte  Jogja  Bisnis→Halte  Gedung  Wanita→Halte  Urip Sumoharjo→Halte Bethesda→Halte Bumi Putera→Halte Tugu→Halte PLN →Halte
Garuda→Halte Kepatihan→Halte Benteng Vrendenburg→Halte Taman
Pintar→Halte  Puropakualaman→Halte  TMP→Halte  SGM→Halte  Gedung  Juang 45→Halte  JEC→Halte  Janti→Halte  Alfa→Halte  Maguwo  →Halte  Bandara  Adi Sucipto→Halte KR 2→Halte Kalasan→ Halte Prambanan. Jarak yang ditempuh dari rute ini sejauh 36,065 km

## Trayek 1B
Halte utama yang diambil adalah halte Bandara Adi Sucipto dan halte RS Dr. YAP. Hasil  dari  algoritma  Floyd  Warshall  untuk  trayek  1B  adalah  rute  berikut:  Halte Bandara  Adi  Sucipto→  Halte  Jayakarta→  Halte  Janti  Fly  Over→Halte  Jogja Bisnis→Halte Gedung Wanita→Halte Urip Sumoharjo→Halte Bethesda→Halte RS Dr YAP→Halte Kosudgama→Halte UNY→Halte UNY (BPD)→Halte
Santren→Halte  Terminal  Condong  Catur→Halte  JIH→Halte  Stikes  Guna Bangsa→Halte Instiper 1→Halte Binamarga→Halte Maguwo→ Halte Bandara Adi Sucipto. Jarak yang ditempuh rute ini sejauh 20,191 km

## Trayek 2A
Halte utama yang diambil adalah Terminal Jombor dan halte Gedung Kuning (Dep. Kehutanan). Hasil dari algoritma Floyd Warshall untuk trayek 2A adalah rute berikut: Halte  Terminal  Jombor→Halte  Monjali  1→Halte  AM  Sangaji  2  (Jetis)→Halte Tugu→Halte PLN→Halte Garuda→ Halte Kepatihan→Halte Benteng Vrendenburg→Halte Taman Pintar→Halte Purawisata→Halte SD
Pujokusuman→Halte RSI Hidayatullah→Halte Ngesigondo→ Halte Gedung Kuning (Dep.  Kehutanan)→Halte  Gembira  Loka→Halte  SGM→Halte  STPP  →Halte Moseum Biologi →Halte Taman Senopati→Halte Taman Pelajar 1 (SMP14)→Halte
Jetis→Halte  Karang  Jati→Halte  Monjali  2→Halte  Terminal  Jombor.  Jarak  yang ditempuh rute ini sejauh 28,080 km

## Trayek 2B
Halte  utama  yang  diambil  adalah  halte  Terminal  Jombor  dan  halte  Gedung  Kuning (Banguntapan).  Hasil  dari  algoritma  Floyd  Warshall  untuk  trayek  2B  adalah  rute berikut: Halte Terminal Jombor→Halte Monjali 1→Halte Jetis→Halte Tugu→Halte PLN→Halte  Garuda→  Halte  Kepatihan→Halte  Benteng  Vrendenburg→Halte Taman Pintar→Halte Puropakualaman→Halte
TMP→Halte SGM→Halte
Banguntapan→  Halte  Diklat  PU→Halte  Pasar  Seni  Kerajinan  Yogyakarta→  Halte Museum  Perjuangan→Halte  Imaculata→  Halte  Taman  Senopati→Halte  Taman Pelajar  1  (SMP14)→Halte  Jetis→Halte  Karang  Jati→Halte  Monjali  2→Halte Terminal Jombor. Jarak yang ditempuh rute ini sejauh 28,118 km

## Trayek 3A
Halte  utama  yang  diambil  adalah  halte  Terminal  Giwangan  dan  halte  FK  UGM. Hasil  dari  algoritma  Floyd  Warshall  untuk  trayek  3A  adalah  rute  berikut:  Halte Terminal  Giwangan→Halte  SMK  5→Halte  SGM→Halte  Mandala  Krida  →Halte SMP  5  Yogya→Halte  Bathesda→Halte  RS  Dr  YAP  →Halte  Kosudgama→Halte UNY→Halte UNY (BPD)→Halte Santren→Halte Terminal Condong Catur →Halte Manggung→Halte FK UGM→Halte Kopma UGM→Halte Museum Korem→Halte SMP 5 Yogya→Halte Puropakualaman →Halte Taman Siswa→Halte UAD→Halte Terminal Giwangan. Jarak yang ditempuh rute ini sejauh 26,580 km

## Trayek 3B
Halte  utama  yang  diambil  adalah  halte  Terminal  Giwangan  dan  halte  RSUP  Dr Sarjito.  Hasil  dari  algoritma  Floyd  Warshall  untuk  trayek  3B  adalah  rute  berikut: Halte  Terminal  Giwangan→Halte  SMK  5→Halte  SGM→Halte  Mandala Krida→Halte SMP 5 Yogya→Halte Bathesda→Halte RS Dr YAP→ Halte Pertanian UGM→Halte  RSUP  Dr  Sarjito→Halte  Kentungan→Halte  Terminal  Condong Catur→Halte  Susteran  Novisat→Halte  Sanata  Darma  (Realino)→Halte  De Brito→Halte  UIN  2  Timur→Halte  APMD  2→Halte  SMK  5→Halte  SGM→Halte PSKY→Halte  UAD→Halte  Terminal  Giwangan.  Jarak  yang  ditempuh  rute  ini sejauh 25,526 km

## Trayek 4A
Halte  utama  yang  diambil  adalah  halte  Hayam  Wuruk  (Lempuyangan)  dan  halte Terminal  Giwangan.  Hasil  dari  algoritma  Floyd  Warshall  untuk  trayek  4A  adalah rute  berikut:  Halte  Hayam  Wuruk  (Lempuyangan)→Halte  SMP  5  Yogya→Halte Puropakualaman→Halte Taman Siswa→Halte UAD→Halte Terminal Giwangan→Halte SMK 5→Halte SGM→Halte STP→Halte Moseum
Biologi→Halte Hayam Wuruk (Lempuyangan). Jarak yang ditempuh rute ini sejauh 14,016 km

## Trayek 4B
Halte  utama  yang  diambil  adalah  UIN  Sunan  Kalijaga  2  Timur  dan  halte  Terminal Giwangan. Hasil dari algoritma Floyd Warshall untuk trayek 4B adalah rute berikut: Halte  UIN  Sunan  Kalijaga  2  Timur→Halte  APMD  2→Halte  SMK  5→Halte SGM→Halte  PSKY→Halte  UAD→Halte  Terminal  Giwangan→Halte  SMK 5→Halte  SGM→Halte  Mandala  Krida→Halte  SMP  5  Yogya→Halte  AA YKPN→Halte De Brito→Halte UIN Sunan Kalijaga 2 Timur. Jarak yang ditempuh rute ini sejauh 17,012 km.

## 4 Kesimpulan
Dari  hasil  di  atas,  apabila  dibandingkan  dengan  rute  dari  tiap  trayek  yang  sudah  ada, maka hanya pada jalur 1A  yang memiliki rute  yang sama. Sedangkan untuk rute  yang lainnya  dengan  pengambilan  halte  utama  seperti  pencarian  di  atas,  di  dapatkan  bahwa rute yang sudah ada tidak optimum. Hal ini disebabkan masih ditemukannya rute yang lebih pendek dari pada rute yang sudah ada.
Dalam  penelitian  ini,  apabila  pengambilan  halte  yang  dianggap  utama  berbeda, maka  rute  yang  masih  memiliki  kemungkinan  untuk  mendapatkan  rute  yang  berbeda. Sehingga  perlu  adanya  kajian  lebih  lanjut  untuk  menentukan  titik  manakah  yang menjadi  titik utama pada setiap trayek.  Hal  ini dimungkinkan untuk  memperoleh hasil yang lebih optimum dalam menghubungkan semua area yang ada di Yogyakarta.

## Daftar Pustaka
[1]  Andriani, Anik. 2014. Rancang Bangun Sistem Informasi Rute Wisata Terpendek Berbsis Algoritma Floyd-Warshall . Bianglala Informatika . 2(1) : 98 – 107.
[2]  Jayanti,  Ni  Ketut  Dewi  Ari.  2014.  Penggunaan  Algoritma  Floyd  Warshall  dalam  Masalah  Jalur Terpendek pada Penentuan Tata Letak Parkir. Seminar Nasional Informatika . 75 – 81.
[3]   Kriswanto,  Y.  Rudi,  R.  Kristoforus  Jawa  Bendi,  Arif  Aliyanto.  2014.  Penentuan  Jarak  Terpendek Rute Transmusi dengan Algoritma Floyd-Warshall. SEMANTIK . 209 – 216.