## Faculty of Sains and Technology, Ibrahimy University
S4-Accredited : 85/M/KPT/2020 Journal page is available to : https://journal.ibrahimy.ac.id/index.php/JIMI

## PENERAPAN BAT ALGORITHM DALAM PENYELSAIAN KASUS TRAVELLING SALESMAN PROBLEM (TSP) PADA INTERNSHIP PROGRAM
Veri Julianto 1) , Hendrik Setyo Utomo 2) , Muhammad Rusyadi Arrahimi 3)
1,2,3 Teknologi Informasi, Politeknik Negeri Tanah Laut
email: 1 veri@politala.ac.id, 2 hendrik.tomo@politala.ac.id, 3 ahmadrusadi@politala.ac.id

## ARTICLE INFO

## ABSTRACT
Article History:
Recieved   :  02 November 2021 Revised   :  30 December 2021 Accepted   :  30 December 2021
Published  :  31 December 2021
This  optimization  is  an  optimization  case  that  organizes  all possible  and  feasible  solutions  in  discrete  form.  One  form  of combinatorial optimization that can be used as material in testing a method is the Traveling Salesman Problem (TSP). In this study, the bat  algorithm  will  be  used  to  find  the  optimum  value  in  TSP. Utilization of the Metaheuristic Algorithm through the concept of the Bat Algorithm is able to provide optimal results in searching for  the  shortest  distance  in  the  case  of  TSP.  Based  on  trials conducted using data on the location of student street vendors, the Bat Algortima is able to obtain the global minimum or the shortest distance when compared to the nearest neighbor method, Hungarian method, branch and bound method.
Keywords: Bat Algorithm Optimization TSP Metaheuristic Permutation IEEE style in citing this article: V. Julianto, H. S. Utomo, and M. R.  Arrahimi,  “Penerapan  Bat Algorithm  Dalam  Penyelsaian
Kasus Travelling Salesman Problem  (TSP)  Pada  Internship Program”, Jurnal.ilmiah.informatika,  vol.  6, no. 2, pp. 111-116, Dec. 2021.
© 2021 Jurnal Ilmiah Informatika (Scientific Informatics Journal) with CC BY NC licence

## 1. PENDAHULUAN
Secara  matematis  teori  optimasi  yang berkembang berdasarkan matematis terbagai menjadi tiga metode yaitu metode klasik,  algoritma  evolusioner  dan  metode hybrid. Salah satu bentuk konsep optimasi yang berkembang yaitu optimasi kombinatorial.  Optimasi  ini  merupakan kasus  optimasi  yang  mengatur  semua
solusi  yang  mungkin  dan  layak  dalam bentuk diskrit.
Salah satu bentuk optimasi kombinatorial  yang  dapat  dijadikan sebagai  bahan  dalam  menguji  suatu metode  yaitu  Travelling  Salesman  Problem (TSP). Adapun proses optimisasi pada TSP yaitu menemukan rute perjalanan seorang salesman  yang  dimulai  dari  satu  lokasi awal  ke  beberapa  lokasi  yang  telah
ditentukan,  setelah  itu  kembali  ke  lokasi asal  sedemikian rupa  sehingga jarak  total yang ditempuh minimum dan setiap kota dikunjungi  tepat  satu  kali.  Tujuan  yang diharapkan  adalah  menentukan  panjang sirkuit  terbaik  dengan  jarak  total  atau biaya yang paling minimum [1].
Salah  satu  metode  yang  digunakan untuk  menyelesaikan  TSP  yaitu  dengan menggunakan konsep pendekatan melalui metaheuristik. Algoritma ini dapat diklasifikasikan ke dalam empat kategori: pencarian  local  (local  search),  kecerdasan swarm  (swarm  intelligence),  evolusioner, dan algoritma hibrida [2]. Pada penelitian [1]  menerapkan  konsep  evolusioner dengan  menggunakan  algortima  genetika dalam  menyelesaikan  TSP  melalui  proses pengujian  yang  menggunakan order crossover dan inversion mutation dilakukan pengulangan proses sebanyak 8 kali.  Pada  penelitian  lain  TSP  berhasil diselesaikan dengan mengkombinasi agoritma  Firefly  Algorithm-Tabu  Search pada berbagai dataset yang disediakan [3]. Algoritma PSO juga berhasil dimodifikasi untuk menyelesaikan TSP melelui konsep diskrit [4]. Algoritma diskrit penyerbukan bunga (Discrete Flower Pollination Algorithm) dalam menyelesaikan
permasalahan  simetrik  TSP  juga  telah berhasil diaplikasikan [5]. Berdasarkan hal tersebut  maka  sudah  banyak  algoritma metaheuristik  yang  sudah  digunakan dalam optimasi TSP.
Salah satu metode yang akan diterapkan  pada  penelitian  ini  adalah  Bat Algorithm  (Algoritma  Kelelawar)  sebagai metode  metaheuristik  yang  berdasarkan konsep  bio-inspired  dan  diciptakan  oleh Xin‐She  Yang.  Metode ini  diinspirasi  dari tingkah  laku  terbang  kelelawar  dalam menemukan  mangsa  dan  menghindari rintangan.  Algoritma  kelelawar  sangat bagus dalam menyelesaikan permasalahan kontinyu  dan  dikrit  [6].  Pada  penelitian sebelumnya  algoritma  kelelawar  ini
digunakan  oleh  [6]  dalam  menyelesaikan permaslahan multiobjektif dengan menggabungkannya dengan konsep evolusi.  Pada  [7]  berhasil  mengabungkan metode  ini  dengan  memperbaiki  pada proses  eksploitasi  dengan  menggunakan Levy Flight Trajectory.  Akan  tetapi  metode hybrid  ini  belum  diterapkan  dalam mengoptimasi  permasalahan  diskrit  yaitu TSP.
Pada penelitian ini akan menggunakan algortima  kelelawar  yang  digunakan untuk  mencari  nilai  optimum  dalam TSP. TSP yang digunakan dengan menggunkaan  prinsip  ATSP  (Asymmetric Traveling  Salesman  Problem).  Algoritma kelelawar  akan  dibandingkan  dengan beberapa  metode  lain  yang  juga  pernah digunakan sebagai penyelesaian TSP. Pada kasus  ini  akan  menggunakan  beberapa kota  atau  perusahaan  tempat  mahasiswa Politeknik  Negeri  Tanah  Laut  yang melakukan internship program.

## 2. KAJIAN LITERATUR DAN PEGEMBANGAN HIPOTESIS
Konsep dasar pengembangan Algoritma Kelelawar yaitu: a. Semua kelelawar menggunakan
kemampuan ekolokasi untuk
mengetahui  jarak,  mereka  juga  dapat membedakan  antara  mangsa  dan benda-benda di sekitar mereka
b. Kelelawar terbang secara acak  dengan kecepatan 𝐯 𝐢 dan  dengan  posisi 𝐱 𝐢 dengan  frekuensi  tetap 𝑓 𝑚𝑖𝑛 ,  dengan variasi  panjang  gelombang 𝜆 dan kenyaringan 𝐴 0 saat mencari mangsa. c. Mereka secara otomatis dapat menyesuaikan  panjang  geombang  dari sinyal  yang  merka  pancarkan  dan menyesuaikan  tingkat  sinyal 𝑟  ∈ [0,1] , dan tergantung pada target mereka.
d. Tingkat  kekerasan  suara  diasumsikan bervariasi dari 𝐴 𝑚𝑖𝑛 hingga 𝐴 0 .
Dalam  jurnal  yang  ditulis  oleh  Yang (2010)  membahas  mengenai  pergerakan
kelelawar  dalam  menghasilkan  sebuah algoritma sehingga dapat dijadikan sebagai  metode  pencarian  solusi  suatu fungsi  objektif.  Pada  jurnal  tersebut dikatakan  bahwa  kelelawar  terbang dengan  kecepatan 𝐯 𝐢 pada  posisi 𝐱 𝐢 di ruang pencarian pada dimensi d . Posisi ( 𝐱 𝐢 𝐭 ) dan kecepatan ( 𝐯 𝐢 𝐭 ) yang baru pada waktu t diberikan oleh : 𝑓 𝑖 = 𝑓 𝑚𝑖𝑛 + (𝑓 𝑚𝑎𝑥 − 𝑓 𝑚𝑖𝑛 )𝛽, (1)
𝒗 𝒊 𝒕 = 𝒗 𝒊 𝒕−𝟏 + (𝒙 𝒊 𝒕 − 𝒙 ∗ )𝑓 𝑖 , (2)
𝒙 𝒊 𝒕 = 𝒙 𝒊 𝒕−𝟏 + 𝒗 𝒊 𝒕 , (3)
dengan β ∈ [0,1] merupakan  vektor  acak dari distribusi uniform dan 𝐱 ∗ merupakan solusi  global  terbaik  yang  diperoleh dengan  membandingkan  dengan  seluruh solusi diantara 𝑛 kelelawar.
Dalam  pencarian  lokal,  setiap  satu solusi  didapatkan  diantara  solusi  terbaik saat  itu.  Solusi  yang  baru  untuk  setiap kelelawar  dibangkitkan  secara  lokal menggunakan random walk.
𝒙 𝒃𝒂𝒓𝒖 = 𝒙 𝒍𝒂𝒎𝒂 + 𝜖𝐴 𝑡 , (4)
Dengan 𝜖 ∈ [−1,1] merupakan  suatu bilangan  acak  dan 𝐴 𝑡 = ⟨𝐴 𝑖 𝑡 ⟩ adalah  rata- rata  dari  tingkat  Kekerasan  suara  dari seluruh  kelelawar  pada  waktu 𝑡 .  Pada penelitian  ini  random  walk  yaitu  sebagai berikut :
𝒙 𝒃𝒂𝒓𝒖 = 𝒙 𝒍𝒂𝒎𝒂 + 𝑐 ∙ 𝑟𝑎𝑛𝑑 ∙ (𝒙 ∗ − 𝒙 𝒍𝒂𝒎𝒂 ) (5)
Dengan 𝐱 ∗ adalah 𝐱 terbaik  sekarang untuk  kelelawar  ke-i  dan  nilai 𝑐 adalah konstanta positif . Sedangkan 𝑟𝑎𝑛𝑑 ∈ [0,1] merupakan bilangan acak.
Tingkat  kekerasan 𝐴 𝑖 dan  laju  emisi gelombang suara 𝑟 𝑖 harus diperbaharui di setiap  iterasi.  Tingkat  kekerasan  suara biasanya  menurun  seiring  kelelawar menemukan  mangsanya  sementara  laju emisi gelombang suara meningkat. 𝐴 dapat bervariasi  dari 𝐴 0 = 1 hingga 𝐴 𝑚𝑖𝑛 = 0 . Untuk  setiap  iterasi,  maka 𝐴 𝑖 dan 𝑟 𝑖 diperbaharui dengan formula berikut :
𝐴 𝑖 𝑡+1 = 𝛼𝐴 𝑖 𝑡 ,   𝑟 𝑖 𝑡+1
= 𝑟 𝑖 0 [1 − exp(−𝛾𝑡)], (6)
dengan 0 < 𝛼 < 1 dan 𝛾 > 0 . untuk 𝑡 → ∞ kita perhatikan bahwa :
𝐴 𝑖 𝑡 → 0,      dan         𝑟 𝑖 𝑡 → 𝑟 𝑖 0 .

## 3. METODE PENELITIAN
TSP merupakan
salah satu permasalahan  optimasi  kombinatorial. Permasalahan  matematika  tentang  TSP dikemukan pada tahun 1800 oleh matematikawan  Irlandia,  Willian  Rowan Hamilton  dan  matematikawan  Inggris Thomas  Penyngton.  TSP  merupakan sekumpulan  kota  dan  biaya  perjalanan (atau  jarak) yang  diberikan antar  masing- masing  pasangan  kota  yang  digunakan untuk menemukan jalan terbaik kunjungan ke semua kota dan kembali ke titik  awal  dalam  upaya  meminimalkan biaya atau jarak perjalanan.
Apa yang dilakukan dalam TSP adalah membentuk  sebuah  tour.  Operator  yang bisa digunakan untuk masalah TSP adalah pencarian  urutan  semua  lokasi  untuk memilih lokasi yang belum pernah terpilih satu  demi  satu  sehingga  dihasilkan  satu rute  kunjungan  yang  lengkap  dari  lokasi awal kemudian mengunjungi semua lokasi yang  lain  tepat  satu  kali  dan  akhirnya kembali  ke  lokasi  awal.  Sehingga  dengan definisi  tersebut  dapat  dikatakan  bahwa konsep permasalahan TSP memiliki aturan sebagai berikut:
a. Harus  mengunjungi  setiap  kota  tepat satu kali, tidak boleh kurang ataupun lebih.
b. Semua  kota  harus  dikunjungi  dalam satu kali perjalanan (tour).
c. Dimulai  dan diakhiri  pada kota  yang sama.
TSP  dapat  dimodelkan  sebagai  graf terhubung  lengkap  dalam  dimensi 𝐷 ruang euclidian, terdiri dari titik dari graf tersebut,  sisi  graf  dan  jarak/bobot  graf
tersebut.  Dalam  matematika  dapat  di definisikan sebagai himpunan sebuah kota sejumlah 𝑛 yang  didefinisikan  sebagai {𝑐 1 , 𝑐 2 , … , 𝑐 𝑛 } .  Permutasi  dari  kota  ini didefinisikan 𝜋 1 , 𝜋 2 , … , 𝜋 𝑛 ,  dimana 𝜋 𝑖 = {𝑐 1 , 𝑐 2 , … , 𝑐 𝑛 } . Sehingga untuk
meminimalkan 𝑓(𝜋) penjumlahan seluruh jarak  euclidian 𝑑 antara  setiap  kota  di seperti berikut :
𝑓(𝜋) = ∑ 𝑑 𝜋(𝑖)𝜋(𝑖+1) + 𝑑 𝜋(𝑛)𝜋(1) 𝑛−1 𝑖=1 (7)
Rumus  jarak  Euclidian 𝑑, antara  dua kota dengan koordinat (𝑥 1 , 𝑦 1 ) dan (𝑥 2 , 𝑦 2 ) yaitu :
𝑑 = √(𝑥 1 − 𝑥 2 ) 2 + (𝑦 1 − 𝑦 2 ) 2 (8)

## 4. HASIL DAN PEMBAHASAN
Pada  tahap  pembahasan  artikel  ini akan menggunakan kasus data yaitu letak perusahaan yang akan dilakukan
monitoring  pada  sistem  Praktek  Kerja Lapangan  di  Politeknik  Negeri  Tanah Laut.  Kota  yang  akan  diambil  yaitu sebanyak  8  perusahaan  maka  akan dilakukan
perhitungan dengan mengguanakan Algortima Kelelawar dalam menentukan rute optimumnya. Sebanyak 8 perusahaan itu diantaranya yaitu:
1  =  Politeknik Negeri Tanah Laut
2  =  CV Boston
3  =  PT. Astra Isuzu
4  =  BPS Kalimantan Selatan
5  =  PT. Indofood Sukses Makmur
6  =  PT. Taspen
7  =  Air Nav Indonesia
8  =  PT. Sumber Alfaria Trijaya, Tbk Jarak  dalam  satuan  kilometer  antara perusahaan satu dengan perusahaan yang lain  digambarkan  dengan  matrik  jarak yaitu:
Tabel 1. Matrik Ketetanggaan 0 47 43 49 24 58 44 26 47 0 17 6 23 44 5 21 43 17 0 16 17 15 9 19 49 6 16 0 21 32 8 18 24 23 17 21 0 30 29 4 58 44 15 32 30 0 35 33 44 5 9 8 29 35 0 26
26 21 19 18 4 33 26 0 Penerapan  algortima  keleawar  dalam meyelesaikan TSP yaitu dengan memberikan perubahan dengan
melakukan  modifikasi  dalam  proses iterasinya.  Berikut  ini  adalah  algortma yang digunakan :
Algoritma  1:  Pseudocode  Improvisasi Algoritma Kelelawar
definisikan fungsi objektif 𝒇(𝒙); inisialisasi populasi kelelawar 𝑿 = 𝒙 𝟏 , 𝒙 𝟐 , … , 𝒙 𝒏 ; for setiap kelelawar 𝒙 𝒊 pada populasi do inisialisasi sinyal 𝒓 𝒊 , velocity 𝒗 𝒊 dan kekerasan 𝑨 𝒊 end
while ( 𝒕 < 𝒊𝒕𝒆𝒓𝒂𝒔𝒊 𝒎𝒂𝒌𝒔𝒊𝒎𝒖𝒎 ) for each bat 𝒙 𝒊 in the population do bangkitkan solusi baru; if ( 𝒓𝒂𝒏𝒅 > 𝒓 𝒊 ) pilih solusi diantara solusi terbaik ( 𝒙 ′ ) end if 𝒓𝒂𝒏𝒅 > 𝒓 𝒊 then Pilih salah satau solusi terbaik; Bangkitkan kelelawar terbaru 𝒙 ′′ Menggunakan nilai random tentukan uritan posisi if 𝒇(𝒙") < 𝒇(𝒙′) then 𝒙 𝒊 = 𝒙 𝒊 "
if rand< 𝒂 𝒊 and f( 𝒙 𝒊 )<f( 𝒙 ∗ ) then terima solusi baru; increase 𝒓 𝒊 and reduce 𝑨 𝒊 ; end end end while
Dengan menggunakan algoritma nearest  neighbor  method,  Hungarian  method, branch  and  bound  method  didapatkan  hasil yang sama dan hanya mampu menghasilkan rute yaitu sebagai berikut:
1  5  4  2  7  3  6  8  1
Dengan  total  jarak  yaitu  139  km. Dengan menggunakan algortima kelelawar  maka  didapatkan  hasil  yang mampu lepas dari local minimum yaitu di 139 dan mampu mendapatkan rute global minimum yaitu
1  5  6  3  7  2  4  8  1
Dengan  totoal  jarak  yaitu  133  km. Berikut  ini  adalah  rute  yang  dihasilkan algoritma kelelawar :
Politeknik  Negeri  Tanah  Laut  PT. Indofood Sukses Makmur  PT. Taspen  PT.  Astra  Isuzu  Air  Nav  Indonesia  CV  Boston  BPS  Kalimantan  Selatan  PT.  Sumber  Alfaria  Politeknik  Negeri Tanah Laut.
Total rute = 24+30+15+9+5+6+18+26 =133.
Berdasarkan
hasil
percobaan didapatkan bahwa ruter terpendek dalam melakukan  proses  perjalanan  monitoring atau  kunjungan  perusahaan  PKL  dimulai dari  Politeknik  Negeri  Tanah  Laut kebeberapa  perusahaan  dan  kembali  lagi ke  Politeknik  Negeri  Tanah  Laut  yaitu sejauh  133  Km.  dengan  melalui  beberapa kota yang sudah di tentukan.
Pada  peneilitian  ini  jumlah  populasi yang digunakan oleh Algortima Kelelawar dalam  melakukan  pencarian  solusi  yaitu sebesar  20  populasi.  Dengan  iterasi maksimum  <  100  iterasi.  Beberapa parameter pada natural Algoritma Kelelawar tidak digunakan seperti frekuensi.  Pada  kasus  ini  juga  dilakukan perbandingan dengan pencarian TSP yaitu dengan  menggunkan  beberapa  algoritma seperti  nearest  neighbor  method,  Hungarian method, branch and bound method didapatkan hasil yang kurang optimal jika dibandingkan  dengan  pencarian  dengan menggunakan algoritma Kelawar.
Nilai  Optimum  untuk  ketiga  metode tersebut  terjebak  pada  local  minimum yaitu pada rute  1  5  4  2  7  3  6  8     dengan total jarak yaitu
139 km.
Sehingga  dalam  proses  pencarian  TSP dengan  konsep  ATSP  yaitu  perjalanan dilakukan dalam start awal dengan konsep sirkuit  Hamilton  melalui  beberapa  kota tepat sekali dan kembali lagi ke kota awal dapat menggunakan Algoritma Kelelawar sebagai alternatif dalam menyelesaikannya.  Perlunya  modifikasi lagi  pada  tahap  local  search  dengan menggunakan  konsep  swap  yang  lain untuk  mendambah  optimum  dalam pencarian kota yang cukup besar dimensinya.

## 5. UCAPAN TERIMA KASIH
Terimaksih  kepada  Politeknik  Negeri Tanah  Laut  yang  telah  mendanai  proses penelitian  melalui  program  PD3  Politala dengan dana DIPA.

## 6. KESIMPULAN
Berdasarkan  hasil  peneliian  ini  maka dapat disimpulkan pemanfaatan Algorima Metaheuristik  melalui  konsep  Algortima Kelelawar mampu memberikan hasil yang optimal dalam melakukan pencarian jarak terpendek dalam kasus TSP jika
dibandingkan  dnegan  nearest  neighbor method, Hungarian method, branch and bound method.  Dengan  proses  komputasi  yang lebih  efektif  maka  proses  pencarian  nilai optimum terasa leih cepat. Pada penelitian ini  juga  perlu  dikembangkan  dengan konsep pertukaran posisi indifidu dengan menggunakan  konsep  local  search  yang lebih powerfull seperti 2-opt, 3-opt atau k- opt.

## 7. REFERENSI
[1]  S.  Rohman,  L.  Zakaria,  A.  Asmiati, and  A.  Nuryaman,  “Optimisasi Travelling Salesman Problem dengan Algoritma  Genetika  pada  Kasus Pendistribusian  Barang  PT.  Pos Indonesia di Kota Bandar Lampung,” J. Mat. Integr., vol. 16, no. 1, p. 61, 2020, doi: 10.24198/jmi.v16.n1.27804.61-73.
[2]  M.  Iqbal,  M.  Zarlis,  T.  Tulus,  and  H. Mawengkang,  “Model  Pendekatan Metaheuristik  Dalam  Penyelesaian optimisasi  Kombinatorial,”  Semin. Nas. Teknol. Komput. Sains, vol. 1, no. 1, pp. 92–97, 2020.
[3]  R.  Naufal,  “Implementasi  Firefly Algorithm  -  Tabu  Search  Untuk
Penyelesaian Traveling Salesman Problem,” vol. 2, no. 1, pp. 42–48, 2017.
[4]  E. F. G. Goldbarg, G. R. De Souza, and M.  C.  Goldbarg,  “Particle  swarm  for the traveling salesman problem,” Lect. Notes  Comput.  Sci.  (including  Subser. Lect.  Notes  Artif.  Intell.  Lect.  Notes Bioinformatics),  vol.  3906  LNCS,  no. September,  pp.  99–110,  2006,  doi: 10.1007/11730095_9.
[5]  R. Strange, A. Y. Yang, and L. Cheng,
“Discrete Flower Pollination
Algorithm for Solving the Symmetric Travelling  Salesman  Problem,”  2019 IEEE  Symp.  Ser.  Comput.  Intell.  SSCI 2019,  pp.  2130–2137,  2019,  doi: 10.1109/SSCI44817.2019.9002797.
[6]  V.  Julianto,  “Penerapan  Hybrid  Bat Algorithm ( BA ) dengan Differential Evolution ( DE ) untuk Mengoptimasi Model Multiobjektif,” vol. 2, pp. 130– 135, 2016.
[7]  V. Julianto, D. Jurusan, T. Informatika, P.  Negeri,  and  T.  Laut,  “Optimasi Model  Multiobjektif  Menggunakan Gabungan Algoritma Kelelawar Dengan  Differential  Evolution  (  De  ) Dan Levy Flight,” vol. 2017, pp. 159–
164, 2017.