Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 3, Juli (2024), pp. 975-980

## Penerapan Algoritma Genetika Untuk Mencari Optimasi Kasus TSP Pada 20 Gerai Indomart
Yerika Puspa Rosanti 1* , Iwel Triana 2 , Sigit Pancahayani 3 1,2,3 Institut Teknologi Bandung, Indonesia E-mail: 1 yerikapuspa@gmail.com, 2 iweltrianaa@gmail.com,
3 spancahayani@lecturer.itk.ac.id

## Abstract
In  the  delivery  of  a  package,  goods,  and  conducting  business,  location  is  a  crucial factor  to  manage.  A  common  issue  is  the  late  arrival  of  packages  because  delivery couriers cannot find the fastest or most efficient route. This study aims to apply a genetic algorithm to optimize the traveling salesman problem (TSP) for the distribution of goods to 20 Indomaret outlets in the Dago area of Bandung City. TSP is a classic optimization problem that seeks to find the shortest route that visits each city once and returns to the origin  city.  The  genetic  algorithm,  as  a  population-based  search  and  optimization method, is used due to its capability to find near-optimal solutions for complex and large problems.  This  algorithm  leverages  natural  selection  mechanisms  such  as  selection, crossover,  and  mutation  to  develop  solutions  from  one  generation  to  the  next.  Initial parameters  were  set  with  a  population  of  100  and  a  maximum  of  500  generations  to increase  the  variety  of  solutions  without  taking  too  much  time.  The  fitness  value  was obtained  by  taking  the  negative  of  the  total  distance  traveled,  and  after  the  iteration process,  an  optimal  result  with  a  fitness  value  of  -0.10  was  achieved.  It  only  took  50 seconds  to  run  500  generations  for  selecting  the  distribution  route  of  20  Indomaret outlets.
Keywords: genetic  algorithm,  travelling  salesman  problem,  fitness  score,  distance optimization

## Abstrak
Dalam  pengiriman  suatu  paket,  barang,  dan  dalam  melakukan  sebuah  bisnis,  lokasi merupakan  hal  yang  sangat  penting  untuk  dikendalikan.  Banyaknya  kasus  yang  sering ditemukan  adalah  kedatangan  paket  yang  terlambat  dikarenakan  kurir  barang  tidak dapat  menemukan jalur  yang  tercepat  atau  yang  paling  efisien.  Penelitian ini  bertujuan untuk menerapkan algoritma genetika untuk mencari optimasi kasus travelling salesman problem  (TSP)  pendistribusian  barang  pada  20  gerai  Indomaret  di  wilayah  Dago  Kota Bandung.  TSP  adalah  masalah  optimasi  klasik  yang  bertujuan  untuk  menemukan  rute terpendek  yang  mengunjungi  setiap  kota  sekali  dan  kembali  ke  kota  asal.  Algoritma genetika  sebagai  metode  pencarian  dan  optimasi  berbasis  populasi,  digunakan  karena kemampuannya dalam menemukan solusi mendekati optimal untuk masalah kompleks dan bersar.  Algoritma  ini  memanfaatkan  mekanisme  seleksi  alam  seperti  seleksi,  crossover, dan  mutasi  untuk  mengembangkan  solusi  dari  satu  generasi  ke  generasi  berikutnya. Parameter awal diatur yaitu populasi 100 dan maksimal generasi 500 untuk menambah variasi  solusi  tetapi  tidak  memakan  waktu  yang  terlalu  lama.  Nilai  fitness  diperoleh dengan negatif dari total jarak yang ditempuh dan setelah proses iterasi, diperoleh hasil yang  optimal  dengan  nilai  fitness  -0.10.  Hanya  dibutuhkan  waktu  50  detik  untuk menjalankan 500 buah generasi pada pemilihan jalur distribusi 20 gerai Indomaret.
Kata  kunci :  Algoritma  Genetika;  Traveling  Salesman  Problem;  Nilai  Fitness; Optimasi Jarak.

## 1. Pendahuluan
Traveling  Salesman  Problem (TSP)  merupakan  sebuah  permasalahan  optimasi  yang dapat  diterapkan  pada  berbagai  kegiatan  seperti  routing  dan  penjadwalan  produksi  [1]. Masalah  optimasi  TSP  telah  menjadi  standar  untuk  mencoba  algoritma  yang komputasional  [2,3,4].  Pokok  permasalahan  dari  TSP  adalah  seorang  salesman  harus mengunjungi sejumlah kota yang diketahui jaraknya satu dengan yang lainnya [5]. Semua kota yang ada harus dikunjungi dan kota tersebut hanya boleh dikunjungi tepat satu kali [6,7].
Distribusi  merupakan  penyaluran  suatu  produk  dari  pihak  produsen  ke  pihak konsumen  [8].  Setiap  bisnis  memprioritaskan  kemudahan  pelanggan  untuk  membeli produk yang diperlukan untuk menyenangkan pelanggan mereka. Rute yang dipilih sistem distribusi adalah faktor kunci dalam menghitung jarak tempuh yang dibutuhkan dan biaya yang  terkait.  Jika  rute  yang  dipilih  sudah  optimal,  maka  sistem  distribusi  akan  lebih efektif  dan  efisien  karena  akan  menempuh  rute  dengan  jarak  sependek  mungkin, meminimalkan  faktor-faktor  yang  berhubungan  dengan  jarak  [3].  Manajemen  lokasi sangat penting saat mengirimkan paket, barang, atau menjalankan bisnis. Paket sering kali terlambat datang karena kurir tidak dapat menemukan rute tercepat atau paling efisien.
Dalam  kasus  ini  penulis  membuat  sebuah  alternatif  mencari  optimasi jalur  terpendek menggunakan metode algoritma genetika pada 20 gerai Indomaret di wilayah Dago, Kota Bandung.  Gerai  Indomaret  ditempatkan  di  lokasi-lokasi  strategis  sehingga  mudah dijangkau.  Gerai  Indomaret  dengan  mudah  dapat  ditemukan  di  berbagai  kawasan perumahan, perkantoran, niaga, wisata, apartemen dan fasilitas umum yang menyediakan produk food,  nonfood,  general  merchandise dan fresh  product untuk  memenuhi kebutuhan sehari- hari konsumen.
Berdasarkan  penelitian  yang  dilakukan  oleh  Ina  [9]  dalam  mengatasi  masalah  TSP pada perabot keliling di kota Kupang, didapatkan jadwal perjalanan tetap dan pasti untuk saudagar perabot keliling Kota Kupang serta jadwal tersendiri yang berisi jalur perjalanan titik  kelurahan  beserta  titik  tempuhnya.    Metode  penelitian  ini  dapat  memberikan wawasan tentang  penggunaan  algoritma  genetika  dan  pemilihan  parameter  optimal  yang relevan dengan penelitian penulis.
Berikutnya penelitian berjudul optimasi travelling Salesman problem dengan algoritma genetika pada kasus pendistribusian barang PT. Pos Indonesia di kota Bandar Lampung. Penelitian  ini  mencoba  mengoptimasi  rute  distribusi  barang  menggunakan  algoritma genetika,  relevan  dengan  upaya  penulis  untuk  mengoptimasi  rute  pengiriman  kurir ekspedisi.  Hasil  dan  pengalaman  dari  penelitian  ini  dapat  memberikan  perspektif tambahan tentang penggunaan algoritma genetika dalam masalah TSP [10].
Berdasarkan  permasalahan  yang  telah  diuraikan,  maka  diperlukan  solusi  yang  tepat untuk  memecahkan  masalah  tersebut.  Penelitian  ini  bertujuan  untuk  menerapkan algoritma  genetika  untuk  optimisasi  travelling  salesman  problem  pada  kasus pendistribusian barang pada gerai Indomaret di wilayah Dago Kota Bandung. Dalam hal pengerjaannya dibantu dengan bahasa pemrograman Phyton.

## 2. Metodologi Penelitian
Penelitian  ini  diawali  dengan  pengumpulan  data  gerai  indomaret  di  area  sekitar wilayah  Dago,  Kota  Bandung.  Data  tersebut  memuat  20  gerai  indomaret  beserta  lokasi berupa  titik  koordinat  yang  diperoleh  dari google  maps .  Selanjutnya,  diasumsikan  gerai indomaret  sebagai  titik  dan  jalan  yang  menghubungkan  antar  indomaret  sebagai  sisi. Bobot dari sisi yang dimaksud adalah jarak terpendek dari kedua titik ujung sisi tersebut. Kemudian,  digunakan  algoritma  genetika  untuk  menentukan  jarak  yang  paling  optimal dalam pendistribusian barang.
Skema penyelesaian permasalahan distribusi ini ditampilkan pada bagan alir berikut:
Gambar 1. Diagram Alir Algoritma Genetika

## 3. Hasil Dan Pembahasan
Pada penelitian ini, dari Google Maps penulis menggunakan parameter titik sebanyak 20 toko Indomaret yang berada di daerah Dago dan sekitarnya. Koordinat posisi masing- masing Indomaret dituangkan pada plot dengan menggunakan Python.
Gambar 2. Plot 20 gerai Indomart

## 3.1. Inisiasi parameter awal
Nilai populasi dengan yang digunakan adalah 100 sehingga dapat memberikan variasi genetik yang cukup. Populasi yang lebih besar cenderung menghasilkan solusi yang lebih baik  karena  banyak  variasi  genetik,  tetapi  juga  memerlukan  banyak  sumber  daya komputasi. Begitu pula dengan pemilihan jumlah generasi 500 supaya dapat memberikan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 3, Juli (2024), pp. 975-980
cukup pilihan untuk algoritma  mengeksplorasi ruang pencarian solusi yang efektif tetapi tidak menghabiskan waktu yang terlalu lama.

## 3.2. Perhitungan nilai fitness
Nilai fitness function ditentukan sebagai parameter penentuan baik atau tidaknya suatu individu  dalam  algoritma  genetika.  Nilai  fitness  ditentukan  sebagai  parameter  yang menentukan  nilai  optimum  dalam  masalah  optimasi  [11].  Mula-mula  dilakukan perhitungan  matriks  jarak  antara  semua  pasangan  kota  berdasarkan  koordinat  kota  yang diberikan. Hal ini menghasilkan matriks 2D yang berisi jarak antara setiap pasangan kota. Selanjutnya  dalam  fungsi  fitness,  dilakukan  penghitungan  total  jarak  tempuh  untuk  rute yang  ditempuh  oleh  individu  dengan  menjumlahkan  jarak  antar  kota  secara  berurutan. Barulah  setelah  itu  fitness  dihitung  sebagai  negatif  dari  total  jarak,  sehingga  mencari solusi  dengan  jarak  terpendek  (nilai  fitness  yang  lebih  tinggi  menunjukkan  solusi  yang lebih baik). Berikut adalah grafik perubahan nilai fitness dari penelitian ini.
Gambar 3. Perubahan Nilai Fitness pada Maksimal 500 generasi
Dari Gambar 3, didapatkan bahwa nilai fitness paling optimal berada pada nilai jarak - 0.10 jika digunakan maksimal 500 generasi.

## 3.3. Proses seleksi, kali silang, dan mutasi
Pewarisan  sifat  dari  individu  terbaik  perlu  dijaga  di  setiap  generasi.  Elitisme memungkinkan  sekumpulan  individu  terbaik  untuk  diduplikat  dari  induk  ke  keturunan berikutnya.  Dalam  penelitian  ini,  duplikat  tidak  dilakukan  pada  sekumpulan  individu terbaik,  melainkan  pada  individu  terbaik  dengan  tetap  menjaga  keberagaman  populasi. Penentuan banyaknya duplikat untuk meningkatkan kinerja AG diuji pada masalah fungsi nonlinear dua peubah.
Pada tahapan kali silang ( crossover ), dilakukan terlebih dahulu pemisahan bagian head dan  tail  dari  individu  yaitu  mother_head,  mother_tail,  serta  father_tail.  Kemudian dibuatlah  mapping  yang  berisi  pemetaan  gen  dalam  father_tail  dan  mother_tail.  Hal  ini bertujuan  untuk  memastikan  bahwa  tidak  ada  duplikat  gen  dalam  bagian  kepala (mother_head) yang akan digabungkan dengan father_tail. Barulah selanjutnya dilakukan perulangan  untuk  memeriksa  dan  memperbaiki  gen  dalam  mother_head.  Jika  ada duplikasi  gen  dari  father_tail,  gen  tersebut  diganti  dengan  gen  yang  dipetakan  dari mother_tail.  Setelah  memastikan  tidak  ada  duplikasi  gen,  bagian  mother_head digabungkan  dengan  father_tail  untuk  menghasilkan  keturunan  (offspring)  yakni  berupa rute yang valid untuk permasalahan ini.
Sedangkan fungsi mutasi yang dilakukan disini digunakan untuk  memilih dua indeks acak  dari  keturunan  (offspring)  dengan  parameter  yang  membatasi  agar  indeks  yang dipilih tidak saling tergantikan. Nilai gen pada dua indeks yang dipilih (offspring A dan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 3, Juli (2024), pp. 975-980
B)  ditukar.  Hal  ini  dilakukan  untuk  menyimulasikan  proses  mutasi,  dimana  dua  gen dipertukarkan nilainya.

## 3.4. Proses iterasi untuk mendapatkan solusi optimal
Selanjutnya adalah melakukan iterasi melalui setiap ggenerasi dalam range 500 seperti yang  sudah  diatur  sebelumnya.  Hingga  pada  akhir  evolusi,  Gambar  lintasan  paling optimal dari algoritma genetika ini ditampilkan sebagai berikut.
Gambar 4. Lintasan Optimal TSP pada 20 gerai Indomart

## 4.  Kesimpulan
Algoritma  genetika  dapat  diimplementasikan  untuk  menyelesaikan  ukuran  jarak  atau masalah TSP yang optimal. Pada penelitian ini, diatur populasi 100 dan maksimal generai adalah  500.  Ternyata,  hanya  dibutuhkan  waktu  sekitar  50  detik  saja  untuk  menjalankan 500  buah  generasi  pada  pemilihan  jalur  distribusi  20  gerai  Indomart.  Serta  didapatkan nilai fitness score sebesar  -0.10. Nilai optimal parameter algoritma genetika dipengaruhi oleh  perbedaan  nilai  yang  digunakan.  untuk  pengembangan  penelitian  mencari  rute tercepat selanjutnya, dapat dilakukan dengan menambahkan beberapa faktor seperti data terkait  kepadatan  lalu  lintas,  serta  jumlah  dan  frekuensi  lampu  merah  pada  jalan  yang dilewati yang mempengaruhi waktu tempuh perjalanan secara nyata.

## Daftar Pustaka
[1] Gutin,  G.,  Punen,  A.  P.  “The  Traveling  Salesman  Problem  and  Its  Variations”, Springer Science and Business Media, 2006.
[2] JianChen  Zhang.  “Comparison  of  various  algorithms  based  on  TSP  Solving”, Journal of Physics: Conference Series, 2021.
[3] Luailiyatuzzahrok. “Penggunaan Algoritma Genetika dalam Penyelesaian Masalah Traveling  Salesman  Problem  pada  Pendistribusian  Tabung  Liquified  Petroleum Gas”. Skripsi Universitas Lampung, Indonesia, 2023.
[4] Steeb, W. “The Nonlinear Workbook 5th Edition”, World Scientific Publishing Co. Pte. Ltd, USA, 2011.
[5] Applegate, D. L., Chvatal, V., Bixby, R. E., Cook, W. J. “The Traveling Salesman Problem: A Computational Study”, Princeton University Press. USA, 2007.
[6] Mubarok,  Aldhiqo  Y.,  dan  Chotijah,  U.  “Penerapan  Algoritma  Genetika  untuk Mencari  Optimasi  Kombinasi  Jalur  Terpendek  dalam  Kasus  Travelling  Salesman Problem”, Jurnal Teknologi Terpadu, Vol. 7, pp. 77-82, 2021.
[7] Pesant,  G.,  Gendreau,  M.,  Potvin,  J.,  Rousseau,  J.  “An  Exact  Constraint    Logic Programming  Algorithm  for  The  Travelling  Salesman  Problem  with  Time Windows”, Transportation Science, Vol. 32, pp. 12-29, 1998.
[8] Suryanto,  M.  H.  “Sistem  Operasional  Manajemen  Distribusi”,  PT.  Grasindo, Jakarta, 2016.
[9] Ina,  W.  T.,  Manu,  S.  O.,    dan  Matahhine,  T.  Y.  “Penerapan  Algoritma  Genetika pada Travelling Salesman Problem (TSP) (Studi Kasus: Pedagang Perabot Keliling di Kota Kupang)”, Jurnal Media Elektro, Vol. 8, pp. 53-58, 2019.
[10] Rohman,  S.,  Zakaria,  L.,  Asmiati,  A.,  dan  Nuryaman,  A.  “Optimisasi  Travelling Salesman Problem dengan Algoritma Genetika pada Kasus Pendistribusian Barang PT.  Pos  Indonesia  di  Kota  Bandar  Lampung”,  Jurnal  Matematika  Integratif,  Vol. 16, pp.61-73.
[11] Ramdhani,  S.,  Mauliana,  P.,    Wiguna,  W.,    Hunaifi,  N.,  dan  Firmansyah,  R. “Sistem  Penjadwalan  Antrian  Service  Mobil  Toyota  Menggunakan  Algoritma Genetika di Auto2000 Pasteur”, Jurnal Infotronik, Vol. 7, pp. 1, 2022.