## Penentuan Rute Transportasi Kendaraan Umum Kota Medan Dengan Menggunakan Nearest Neighbor Method Dan Closed Insertion Method
Fani Darmawan Putra 1 , Fibri Rakhmawati 2 , Hendra Cipta 3
1 Universitas Islam Negeri Sumatera Utara Medan, fanidarmawan98@gmail.com
2 Universitas Islam Negeri Sumatera Utara Medan, fibrirakhmawati@uinsu.ac.id
3 Universitas Islam Negeri Sumatera Utara Medan, hendracipta@uinsu.ac.id
DOI 10.31102/zeta.2021.6.2.6-10

## ABSTRACT
The  density  of  population  will  have  an  impact  on  the  ability  of  transportation  to  serve  needs  of  the population  where  people  often  face  problems  in  using  public  transportation  especially  in  city  of  Medan.  The purpose of this research is to compile the route of the public transportation system in  city of Medan into a graph and find the closest route solution. The data used is data on travel routes and travel time of public transportation from Terminal Pinang Baris to Terminal Amplas. The results obtained from the public transportation system of Medan City at KPUM 64, RMC 120 and U-MORINA 138 can be represented in a graph. The results of calculating the distance of transportation routes using the Nearest Neighbor Method for KPUM 64 are 22,9 km, RMC 120 are 21,05 km and U-MORINA 120 are 22,7 km. While the calculation of the distance of transportation routes using the Closest Neighbor Method for KPUM 64 is 42,3 km, RMC 120 is 41,65 km and U-MORINA 138 is 44,7 km. From the calculation results of Nearest Neighbor Method has a smaller calculation result than the calculation result of the Closest Neighbor Method. With the preparation of this transportation route system, it makes  easy for the people in city of  Medan to choose which route is the fastest and the lowest cost.
Keywords: Public Transportation, Routing Graph, Nearest Neighbor Method, Closed Insertion Method.

## ABSTRAK
Tingkat  kepadatan  penduduk  akan  berdampak  terhadap  kemampuan  transportasi  melayani  kebutuhan penduduk dimana masyarakat sering menghadapi permasalahan dalam penggunaan transportasi umum khususnya di  kota  Medan,  permasalahan  yang  terjadi  adalah  jauhnya  rute  yang  dilalui  oleh  angkutan  umum  dan mengakibatkan lamanya waktu yang ditempuh serta biaya yang dikeluarkan masyarakat tidak sedikit. Tujuan dari penelitian  ini  untuk  menyusun  rute  sistem  transportasi  umum  dikota  Medan  kedalam  sebuah  graf  dan  mencari solusi rute terdekatnya. Data yang digunakan adalah data rute perjalanan dan waktu tempuh angkutan umum dari Terminal Pinang Baris menuju Terminal Amplas. Hasil yang diperoleh dari sistem angkutan umum Kota Medan pada KPUM 64, RMC 120 dan U-MORINA 138 dapat direpresentasikan dalam graf. Hasil perhitungan jarak rute angkutan menggunakan Nearest Neighbor Method untuk KPUM 64 sebesar 22,9 km, RMC 120 sebesar 21,05 km dan  U-MORINA  120  sebesar  22,7  km.  Sedangkan  perhitungan  jarak  rute  angkutan  menggunakan Closest Neighbor Method untuk  KPUM 64 sebesar 42,3 km, RMC 120 sebesar 41,65 km dan U-MORINA 138 sebesar 44,7  km.  Dari  hasil  perhitungan  diperoleh Nearest  Neighbor  Method memiliki  hasil  perhitungan  lebih  kecil daripada  hasil  perhitungan Closest  Neighbor  Method. Dengan  adanya  penyusunan  sistem  rute  transfortasi  ini memberikan kemudahan bagi masyarakat kota Medan dalam memilih rute mana yang  paling cepat dan biaya yang murah.
Kata Kunci: Transportasi Umum, Rute Graf, Nearest Neighbor Method, Closed Insertion Method

## 1. PENDAHULUAN
Transportasi  merupakan  salah  satu  hal  yang sangat penting, karena manusia selalu membutuhkan transportasi  untuk  berpindah  dari  satu  tempat  ke tempat  lain,  untuk  melakukan  berbagai  aktivitas. Ada berbagai macam sarana transportasi umum yang digunakan.  Ada  yang  berupa  kendaraan  pribadi seperti mobil atau motor, metro, dan lain sebagainya (Haryono, 2006).
Sistem transportasi perjalanan bus adalah model jaringan.  Dikatakan  digambarkan  dengan  area sebagai  titik  dan  rute  yang  menghubungkan  area sebagai garis. Model perjalanan bus kota dari suatu terminal  ke  beberapa  pemberhentian  pada  rutenya secara  berurutan  dan  kembali  ke  terminal  semula tepat  satu  kali  dalam  teori  graf  garis  disebut  siklus Hamilton (Febrian, 2019).
Kota Medan merupakan salah satu kota besar di Indonesia  dengan  jumlah  penduduk  yang  sangat padat.  Selain  banyak  pendatang,  terutama  banyak mahasiswa  yang  merantau.  Dalam  hal  ini, pemerintah  Kota  Medan  berupaya  memperhatikan sistem transportasi yang aman, sekaligus mengurangi  kepadatan  kendaraan  pribadi  di  Kota Medan yang semakin padat kendaraan.
Teori  graf  juga  merupakan  salah  satu cabang  matematika  yang  masih  sangat  menarik untuk  dibahas  karena  teori-teorinya  masih  dapat diterapkan  hingga  saat  ini  dan  dapat  diterapkan untuk  memecahkan  masalah  dalam  kehidupan sehari-hari  (Chatrand,  1986).  Dengan  mempelajari dan  menganalisis  model  atau  formulasi,  teori  graf dapat  ditunjukkan  peran  dan  kegunaannya  dalam memecahkan  berbagai  masalah.  Masalah  yang dirumuskan  oleh  teori  graf  dibuat  sederhana,  yaitu aspek-aspek  yang  diperlukan  diambil  dan  aspek- aspek lainnya dihilangkan. Salah satu sistem tersebut adalah sistem transportasi kota, misalnya menentukan  rute  perjalanan  terpendek  dan  waktu tercepat  untuk  jarak  yang  harus  ditempuh.  Rute adalah  jarak  atau  arah  yang  harus  ditempuh  (Roza, 2013).
Dalam  penelitian  ini  rute  tersebut  akan menggambarkan langkah-langkah untuk menelusuri proses setting pada  sistem  transportasi  angkutan umum  Kota  Medan  yakni  dengan  mencari  jalur terpendek  dan  waktu  tercepat.  Dengan  demikian penelitian ini diharapkan dapat  menjadi solusi bagi pengguna kendaraan agar dapat mempercepat waktu tempuh dengan rute yang telah ditentukan.

## 2. TINJAUAN PUSTAKA
2.1 Model Transportasi Transportasi  merupakan  suatu  sistem  yang terdiri  dari  fasilitas-fasilitas  tertentu  beserta  suatu aliran dan sistem pengendalian yang memungkinkan orang  atau  barang  berpindah  dari  satu  tempat  ke tempat  lain  secara  efisien  setiap  saat  untuk mendukung kegiatan manusia (Hairulsyah, 2006).
2.2 Graf Graf G didefinisikan  sebagai  pasangan himpunan   , v e , dengan notasi
  , G v e  dimana v adalah  himpunan  tak  kosong  dari  simpul-simpul (verteks)  dan e adalah  himpunan  sisi (edge) yang menghubungkan  sepasang  simpul.  Himpunan e boleh kosong, artinya graf tidak mempunyai sisi-sisi yang  menghubungkan  antar  simpulnya  namun himpunan v tidak boleh kosong karena sebuah graf harus memiliki minimal satu buah simpul. Biasanya simpul  direpresentasikan  dengan  bilangan  asli 0,1, 2,..., n sedangkan sisi direpresentasikan dengan
1 2 3 , , ,..., n e e e e . (Wirdasari, 2011).
2.3. Keterhubungan
2.3.1. Walk Sebuah  jalan : W u v  pada  graf G adalah
barisan  berhingga 0 1 1 2 1 : , , , ,..., ,..., n n W u u e u e u e   . ,
n u v  berselang  seling  antara  simpul  dan  tepi, dimulai  dari  titik u dan  diakhiri  dengan  titik v , dimana 1 i i e u   untuk 1, 2, 3,..., i n  adalah  sisi dalam G . 0 u disebut titik awal, n u disebut titik akhir dan 1 2 1 , ,..., n u u u  disebut titik internal dan n adalah panjang W (Chatrand, 1986).
2.3.2. Trail
Lintasan u v  yang  semua  rusuknya  berbeda disebut  lintasan u v  .  Lintasan u v  pada  graf G adalah  lintasan  yang  tidak  mengulang  setiap  ruas (Chatrand, 1986).
2.3.3. Path Suatu  jalur u v  adalah  perjalanan u v  (lintasan u v  )  yamg  tidak  mengulangi  sebarang simpul (Chatrand, 1986). 2.3.4. Cycle
Sirkuit
  1 2 ,   ,...,   , 3 n v v v n  memiliki n titik dengan v i adalah  titik-titik  berbeda  untuk  1 i n   disebut cycle .  Jalan  tertutup (closed  trail) dan  tak trivial pada graf G disebut sirkuit G . Sirkuit (cycle) adalah  suatu walk tertutup  yang  tidak  mempunyai pengulangan verteks kecuali verteks awal dan akhir (Chatrand, 1986).
2.3.5. Terhubung
Terhubung  dua  simpul u dan  simpul v dikatakan terhubung jika ada  jalur dari u ke v . jika dua  simpul  terhubung  maka  pasti  simpul  pertama dapat dijangkau dari simpul kedua (Romelta, 2009). 2.3.6. Lintasan Terpendek Lintasan terpendek adalah lintasan yang dilalui dari satu simpul ke simpul lain dengan besaran atau nilai  pada  sisi  yang  bilangan  akhirnya  dari  simpul awal  sampai  simpul  akhir  paling  kecil  (Romelta, 2009).
2.4. Metode Penyelesaian Masalah Transportasi 2.4.1. Nearest Neighbor Method Metode ini mempunyai langkah-langkah (Febrian, 2019):
1) Andaikan  suatu  graf  memiliki  titik a .  Pilih sembarang  titik  sebagai  awalan  misalkan  titik a.
2) Pilih  sisi  yang  bersisian (incident) dengan ab yang  mempunyai  bobot  sisi  paling  kecil, Masukan sisi ab ke dalam lintasan. 3) Pilih sisi lain yang bersisian (incident) dengan b yang mempunyai bobot sisi paling kecil tetapi harus sesuai dengan aturan jika sisi yang akan dipilih  mengarah  ke  titik  yang  telah  dipilih, maka  eliminasi  sisi  yang  bersisian  dengan b yang mengarah ketitik tersebut, kemudian pilih sisi bersisian yang memiliki bobot paling kecil diantara yang belum terpilih.
4) Ulangi langkah 3 sampai semua n titik dipilih.. Sirkuit  Hamilton  akan  terpenuhi  jika  titik terakhir yang dipilih merupakan titik awal yang dipilih.
2.4.2. C losed Insertion Method Metode  ini  mempunyai  langkah-langkah (Abrori, 2010):
1. Ambil i x sebagai terminal (titik awal)
2. Pilih halte pertama yang paling dekat dengan
1 x yaitu j x 3. Pilih  halte  yang  terdekat  dengan 1 x dan j x yaitu k x untuk disisipan di antara 1 x dan j x
sehingga terbentuk sikel i j k i x x x x   
4. Seperti  langkah  3,  pilih  halte m x untuk disisipkan  maka  terdapat  tiga  kemungkinan sikel yang dapat terbentuk:
1
2
3 i j m k i i k m j i i j k m i S x x x x x S x x x x x S x x x x x
    
         
Perhitungan  pertambahan  bobot  terpendek misal jarak 1 2 x x  dilambangkan dengan 1,2 1,3 2,3 , , C a C b C c    maka maka total pertambahan jarak adalah 1,3 2,3 1,2
C C C b c a      (Wilson, 1990).

## 3. METODE PENELITIAN
Jenis  penelitian  yang  digunakan  adalah penelitian kualitatif-kuantitatif yakni berupa gambar rute  perjalanan  angkutan  umum  yang  telah dimisalkan  dalam  sebuah  graf    dan  berupa  waktu perjalanan  angkutan  umum  kota.  Data  yang diperlukan  untuk  memecahkan  persoalan  dengan cara  melakukan  wawancara langsung  kepada pihak yang  berwenang,  melakukan  pengamatan  dan pengukuran  waktu  secara  langsung.  Sedangkan analisa data yang digunakan adalah membuat model graf  dengan  menggunakan Nearest  Neighbor Method dan C losed Insertion Method.
4. HASIL PENELITIAN
4.1. Rute Angkutan Umum KPUM 64
1. Daerah Kerja Angkutan Umum KPUM 64
Gambar 1. Daerah kerja KPUM 64 Keterangan gambar: Verteks A = Terminal Pinang Baris Verteks B = Jl.SM Raja Verteks C = Jl.KH W. Hasyim Verteks D = Jl.TB. Simatupang Verteks E = Terminal Amplas Verteks F = Jl. Gajah Mada Verteks G = Jl. Gatot Subroto Verteks H = Jl. Iskandar Muda Verteks I = Jl. Patimura Verteks J = Jl. Mongonsidi Verteks K = Jl. Ir.Juanda Verteks L  = Jl. Hayam Wuruk
2. Pemecahan  Masalah  Rute  Angkutan  Umum KPUM 64
Gambar 2. Jarak area kerja angkutan umum KPUM 64  yang  dihitung  dengan Nearest Neighbor Method dan C losed Insertion Method
a. Nearest Neighbor Method
Berdasarkan  gambar  1,  solusi  rute  angkutan umum KPUM 64 adalah: A – D – G – C – F – H – L – I – J – K – B – E. Total bobot rute yang ditempuh adalah  0.1 + 1.1 + 5.8 + 0.6 + 0.45 + 0.6 + 1.4 + 0.45 +  1.4  +  1.9  +  9.1  =  22,9  km  perjalanan  mulai  dari titik A  (Terminal Pinang Baris).
b. C losed Insertion Method
Berdasarkan  gambar  1,  solusi  rute  angkutan umum  KPUM  64  yakni  dengan  memilih  titik  A untuk  disisipkan  di  antara  D  dan  G  sehingga diperoleh siklus: E – B – J – I – H – C – D – A – G
–  F  –  L  –  K  –  E.  Pertambahan  bobotnya  adalah ( ) ( ) ( ) 0.1 1.2 1.3 0 d D A d A G d D G         
km.  Karena  hasil  pertambahan  bobotnya  nol  maka bobot totalnya tidak berubah yaitu 42,3 km  dengan pemberangkatan dimulai dari titik E
4.2. Rute  Angkutan  Umum  Rahayu  Medan  Ceria (RMC 120)
1. Daerah Kerja Angkutan Umum RMC 120
Gambar 2. Daerah kerja RMC 120 Keterangan gambar: Verteks A = Terminal Pinang Baris Verteks B = Jl. Setia Budi Verteks C = Jl. Dr Mansyur Verteks D = Jl. Jamin Ginting Verteks E = Jl. SM. Raja Verteks F = Jl. TB. Simatupang Verteks G = Jl. Amal Verteks H = Jl. Merak Verteks I = Terminal Amplas Verteks J = Jl. AH.Nasution Verteks K = Jl. Kasuari
2. Pemecahan  Masalah  Rute  Angkutan  Umum RMC 120
Gambar 3. Jarak area kerja angkutan umum RMC 120  yang  dihitung  dengan Nearest Neighbor Method dan C losed Insertion Method
a. Nearest Neighbor Method
Berdasarkan  gambar  2,  solusi  rute  angkutan umum RMC 120 adalah: A – F – G – H – K – B – C – D – J – E – I. Total bobot rute yang ditempuh oleh angkutan umum ini 0.1 + 0.9 + 0.65 + 0.7 + 0.9 + 2 + 2.1 + 6.5 + 2.1 +
5.1 = 21.05 km dengan perjalanan dimulai dari titik A (Terminal Pinang Baris).
b. C losed Insertion Method
Berdasarkan  gambar  2,  solusi  rute  angkutan umum  RMC  120  yakni  dengan  memilih  titik  A dipilih untuk disisipkan di antara G dan F sehingga diperoleh siklus: I – J – C – K – H – G – F – A – B – D–E–I.
Pertambahan bobot adalah ( ) ( ) ( ) 0.8 0.1 0.9 0 d G A d A F d F G         
km.  Karena  hasil  dari  kenaikan  berat  adalah  nol, berat  total  tidak  berubah  yaitu  41,65  km  dengan pemberangkatan dimulai dari titik I.
4.3. Rute Angkutan Umum U–MORINA 138
1. Daerah  Kerja  Angkutan  Umum  U–MORINA
138
Gambar  4. Daerah kerja U–MORINA 138 Keterangan gambar: Verteks A = Terminal Pinang Baris Verteks B = Jl. Maulana Lubis Verteks C = Jl. Raden Saleh Verteks D = Jl. Iskandar Muda Verteks E = Jl. Gajah Mada Verteks F = Terminal Amplas Verteks G = Jl. TB. Simatupang Verteks H = Jl. Gatot Subroto Verteks I = Jl. Thamrin Verteks J = Jl. MT. Haryono Verteks K = Jl. St. Kreta Api Verteks L = Jl. Menteng VII Verteks M = Jl. Denai Verteks N = Jl. Sutrisno Verteks O = Jl. S. Parman
2. Pemecahan Masalah Rute Angkutan Umum U– MORINA 138
Gambar    5. Jarak  area  kerja  angkutan  umum  U– MORINA 138 dengan Nearest Neighbor Method dan C losed Insertion Method
a. Nearest NeighborMethod
Bedasarkan gambar 3, diperoleh solusi rutenya A – G – H – D – E – O – B – C – K – J – I – N – M –  L  –  F.  Total  bobot  rute  yang  ditempuh  oleh angkutan umum ini adalah 0.1 + 1.1 + 6 + 0.7 + 0.65 + 1.1 + 0.85 + 0.3 + 0.8 + 1 + 0.9 + 1.2 + 5.2 + 2.8 = 22.7  km  dengan  perjalanan  mulai  dari  titik  A  atau Terminal Pinang Baris
b. C losed Insertion Method
Berdasarkan  gambar  3,  solusi  rute  angkutan umum U–MORINA 138 yakni dengan memilih titik A  untuk  disisipkan  di  antara  H  dan  G  sehingga diperoleh siklus: F – M – I – K – B – E – H – A –G – D – O – C – J – N –  L –  F. Pertambahan bobot
( ) ( ) ( ) 0.8 0.1 0.9 0 d H A d A G d H G          km.  Karena  hasil  pertambahan  beratnya  nol  maka berat  totalnya  tidak  berubah  yaitu  44,7  km  dengan pemberangkatan dimulai dari titik F.

## 5. KESIMPULAN
Sistem  transportasi  Angkutan  Umum  Kota Medan yaitu Angkutan Umum KPUM 48, RMC 120 dan  U–MORINA  138  dapat  direpresentasikan  ke dalam teori graf dengan halte sebagai titik  (verteks) dan jalan yang menghubungkan kesetiap halte-halte tersebut sebagai garis ( edge ). Hasil perhitungan dan penentuan  rute  dengan  menggunakan Nearest NeighborMethod dan C losed Insertion Method dapat menghasilkan  rute  yang  berbeda  antara  rute angkutan  umum  KPUM  64,  RMC  120  dan  U– MORINA  138  yang  beroperasi  selama  ini.  Rute angkutan umum yang terpendek dengan menggunakan Nearest  Neighbor  Method pada  rute angkutan umum RMC 120 yaitu dengan jarak 21,05 km  dapat  dilihat  dari  segi  pertimbangan  jarak  dan jalan  yang  bisa  dilewati  oleh  kendaraan  pribadi seperti mobil.

## DAFTAR PUSTAKA
Abrori,  M.  (2010). Uji  Efisiensi  Jalur  Trans  Jogja Trayek 3A. Sosio Religia.
Chatrand,  L.  et.al.  (1986). Graphs  and  Digraphs Second  Edition .  California  a  Division  of Wadsworth.
Febrian,  D.  (2019). Aplikasi  Metode  Tetangga (Nearest  Neighbour  Algorithm)  Terdekat Untuk  Mencari  Rute  Terpendek  Perjalanan Wisata  Museum  Dan  Wisata  Religi  Di  Kota Medan. Jurnal  Karismatika  Unimed  (pp.  1- 13).
Hairulsyah. (2006). Kajian Tentang Transportasi di Kota  Medan  dan  Permasalahannya .  Jurnal Perencanaan  Dan  Pengembangan  Wilayah Wahana Hijau.
Haryono. (2006). Pemilihan Model Transportasi Di DKI  Jakarta  Dengan  Analisis  Kebijakan Proses  Hirarki  Analitik .  Jurnal  Teknik  Sipil Universitas Pelita Harapan.
Romelta,  E.  (2009). Metode  Pencarian  Lintasan Terpendek Dalam Graf . Bandung: ITB Press.
Roza,  I.,  Narwen,  Zulakmal.  (2013). Graf  Garis (Line Graph) Dari Graf Siklus, Graf Lengkap Dan  Graf  Bintang ,  Jurnal  Matematika UNAND  Fakultas  Matematika  Dan  Ilmu Pengetahuan Alam, Universitas Andalas (pp. 1-4).
Wilson,  R.J.  and  Watkin,  J.J.  (1990). Graph,  An Introductory  Approach .  Sinagpore:  John Wiley and Sons Inc.
Wirdasari, D. (2011). Teori Graf dan Implementasinya  dalam  Ilmu  Komputer ..
Jurnal Saintikom (pp. 23-34).