PENERAPAN ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM (TSP)  (STUDI KASUS: PEDAGANG PERABOT KELILING DI KOTA KUPANG)
Wenefrida T. Ina 1 , Sarlince Manu 2 Thomas Yohanis Mattahine 3
1,2,3 Jurusan Teknik Elektro, Fakultas Sains dan Teknik, Universitas Nusa Cendana Kupang Email: wenefrida150477@gmail.com Email: vonnyoctaviana@gmail.com Email: thomasmattahine@gmail.com

## ABSTRACT
Traveling Salesman Problem (TSP) is one of the optimization problems that occur in everyday life. The problem in the TSP case is how to build the shortest route the salesman will take. This case modeling will be applied to a mobile furniture trader in Kupang City using the genetic algorithm method. Currently, selling furniture is still carried out in the old way where the location  is  uncertain,  so  it  cannot  be  decided  that  the  resulting  travel  route  is  optimal.  This  algorithm  follows  the  genetic process of biological chromosomes based on Charles Darwin's theory of evolution. In this research, ten urban village points were taken as samples for a merchant's travel schedule. As a result, the genetic algorithm can provide the optimal solution for the traveling furniture merchant case study. Apart from that,  it can provide a fixed itinerary, itinerary of travel routes, and mileage. Furthermore, the random numbers used in crossing over are the largest and smallest random numbers. The smallest random number has a positive effect on the fitness value, so it uses a small random number during crossing over. Keywords: TSP, Genetic Algorithm, Furniture Trader.

## ABSTRAK
Travelling  Salesman  Problem  (TSP)  merupakan  salah  satu  permasalahan  optimasi  yang  terjadi  di  kehidupan  sehari-hari. Permasalahan pada kasus TSP adalah bagaimana membangun rute terpendek yang akan dilalui salesman. Pemodelan kasus ini  akan  diterapkan  pada  pedagang  perabot  keliling  di  Kota  Kupang  dengan  metode  algoritma  genetika.  Saat  ini  proses penjualan  perabot  masih  dilakukan  dengan  cara  lama  dimana  lokasi  yang  dipakai  tidak  menentu,  sehingga  belum  dapat diputuskan bahwa rute perjalanan yang dihasilkan sudah optimal.    Algoritma ini mengikuti proses genetik dari kromosom – kromosom biologi yang berdasar pada teori evolusi Charles Darwin. Dalam penelitian ini diambil 10 titik kelurahan sebagai sampel untuk jadwal perjalanan seorang pedagang.  Hasilnya algoritma genetika dapat memberikan solusi yang optimal untuk studi kasus pedagang perabot keliling. Selain itu,  dapat memberikan jadwal perjalanan yang tetap, jadwal rute perjalanan dan jarak tempuh. Selanjutnya, angka acak yang dipakai dalam proses pindah silang adalah angka acak terbesar dan terkecil. Angka  acak  terkecil  berpengaruh  positif  terhadap  nilai  fitness  sehingga  menggunakan  angka  acak  yang  kecil  saat  proses pindah silang
Kata kunci: TSP, Algoritma Genetika, Pedagang Perabot Keliling.

## 1. PENDAHULUAN
Traveling  Salesman  Problem (TSP)  merupakan permasalahan  di  mana  seorang salesman harus mengunjungi semua kota, di mana setiap kota hanya dikunjungi sekali dan harus dimulai dari dan kembali ke  kota  asalnya.  Kasus  TSP  salah  satu  contohnya adalah pedagang perabot keliling. Pedagang perabot keliling merupakan penyambung antara produsen dan konsumen,  keberadaan  pedagang  perabot  keliling sangat membantu ibu rumah tangga khususnya untuk mendapatkan  perabot  rumah  tangga.  Algoritma
genetika  ( Genetic  Algorithms,  GAs )  merupakan  tipe EA  ( Evolutionary  Algorithms )  yang  paling  popular. Algoritma  genetika  berkembang  seiring  dengan perkembangan teknologi informasi yang sangat pesat karena kemampuannya untuk menyelesaikan berbagai masalah kompleks [1-3]. Untuk membantu para  pedagang  memperoleh  rute  perjalanan  yang optimal  maka  akan  diterapkan  algoritma  genetika untuk  TSP  dengan  studi  kasus  pedagang  perabot keliling [4, 5]. Untuk menerapkan algoritma genetika dalam penyelesaian masalah rute paling optimal dari pedagang  perabot  keliling  dan  memberikan  jadwal
perjalanan  kepada  pedagang  serta  mengetahui pengaruh bilangan acak pada proses pindah silang.

## 2. METODE PENELITIAN

## 2.1 Teori Graf
Graf  digunakan  untuk  merepresentasikan  objek- obyek  diskrit  dan  hubungan  diantara  objek-obyek tersebut.  Representasi  visual  dari  graf  dinyatakan dengan  noktah,  bulatan  atau  titik  sedangkan hubungan  antar  objek  dinyatakan  dengan  garis. Menurut catatan sejarah, masalah jembatan
Konigsberg  adalah  masalah  yang  pertama  kali menggunakan Graf (Tahun
1736). Graf dikelompokkan  menjadi  beberapa  kategori  (jenis) bergantung  pada  sudut  pandang  pengelompokannya graf  dapat  dipandang  berdasarkan  ada  tidaknya  sisi ganda  atau  sisi  kalang,  berdasarkan  jumlah  simpul atau berdasarkan orientasi arah pada sisi.

## 3. HASIL DAN PEMBAHASAN

## 3.1. Pembuatan Aplikasi
Implementasi  sistem  merupakan  tahap  perubahan spesifikasi sistem ke dalam bentuk aplikasi. Halaman utama  atau  home  merupakan  halaman  awal  dari sistem  yang  menampilkan  aplikasi,  profil,  tentang aplikasi dan keluar.
Pada  menu  aplikasi  berisi  aplikasi  TSP  akan  dilakukan proses  perhitungan  menggunakan  algoritma  genetika dengan menentukan terlebih dahulu 10 titik kelurahan yang akan dilalui oleh seorang pedagang perabot keliling.

## 3.2 Pengujian dan Hasil
.  Adapun  langkah-langkahnya  adalah  sebagai berikut:
1. Setelah  memilih  titik  awal  dan  juga  titik  pada proses sebelumnya proses perhitungan dapat diakses dengan  menekan  tombol  ‘perhitungan  algoritma genetika’  yang  ada  pada  form  aplikasi  TSP  dengan algoritma genetika.
Gambar 4. Perhitungan Algoritma Genetika
2. Proses selanjutnya adalah membangkitkan populasi  awal  yang  berbentuk  beberapa  kromosom dengan  menekan  tombol  ‘generate  populasi’,  yang berfungsi untuk membangkitkan kromosom awal dari kelurahan-kelurahan yang telah dipilih.
Gambar 1.Tampilan Awal Aplikasi
Gambar 2. Sub Menu Aplikasi
Gambar 3. Daftar 10 Kelurahan yang dipilih
Gambar 5. Populasi Awal yang dibangkitkan
Setelah memperoleh beberapa kromosom awal, akan dilakukan proses perhitungan dengan cara memasukkan  setiap  kromosom  ke  dalam  ‘proses perhitungan nilai fitness awal’.
3. Proses  menghitung  nilai  fitness  dan  juga  nilai invers  dari  fitness  (1/F)  dari  setiap  kromosom  yang ada.  Hasil  dari  proses  akan  ditampilkan  pada  tabel nilai fitness (F) dan tabel nilai invers fitness (Qi) yang berada  di  samping  setiap  kromosom  pada  program yang ada. Proses perhitungan nilai fitness ini sangat penting  karena  dapat  menjadi  ukuran  baik  tidaknya suatu solusi yang didapatkan.
Gambar 7. perhitungan nilai fitness.
4. Setelah  proses  perhitungan  nilai  fitness,  proses selanjutnya adalah menghitung probabilitas dan nilai kumulatif  dari  setiap  probabilitas.  Perhitungan  ini perlu  dilakukan  karena  saat  akan  dilakukan  proses pindah  silang  akan  diambil  kromosom  dengan  nilai probabilitas terbesar dan perhitungan nilai kumulatif sendiri akan berfungsi sebagai interval dari nilai acak yang akan dibangkitkan pada roulette-wheel.
Gambar 8. Proses Perhitungan Probabilitas.
5. Melakukan  seleksi roulette-wheel dengan menekan tombol ‘seleksi roulette-wheel ’, seleksi ini digunakan  untuk  membangkitkan  bilangan  acak  R antara 0-1 dengan syarat C [i-1] < R [i] < C [i] . Dimana C i merupakan  interval  yang  akan  dipakai  untuk membangkitkan bilangan acak 0 – 1.
Gambar 9. Seleksi Roulette-Wheel
6. Setelah  itu  bilangan  acak  yang  diperoleh  akan dipakai  untuk  mengurutkan  kromosom  dari  nilai terendah  sampai  nilai  tertinggi.  Dengan  langkah memasukkan  bilangan  acak  yang  diperoleh  serta populasi  dan  nilai  fitnessnya  kedalam  sebuah data grid view untuk diurutkan. Terdapat dua tipe bilangan acak yang akan dipakai yaitu bilangan acak kecil (1- 5) dan bilangan acak besar (6-9).
Gambar 10. Mengisi Data ke data grid view
Gambar 6. Proses Perhitungan
7. Pindah
silang
merupakan
proses mengkombinasikan dua kromosom untuk memperoleh  kromosom  baru  yang  diharapkan mempunyai  nilai  fitness  lebih  baik  dari  kromosom sebelumnya.  Dalam  studi  kasus  ini  akan  dipakai metode one-cut-point-crossover.

## Gambar 11. Pindah Silang
8. Proses untuk mendapatkan kromosom baru yang pertama  (kromosom  anak  [1])  adalah  dengan  cara melakukan  pindah  silang  pada  kromosom  induk terpilih  pertama  (kromosom  [1])  dan  kromosom induk terpilih kedua (kromosom [2]). Cara ini dapat dilakukan  dengan  cara  menekan  tombol  “proses  1” yang ada pada form pindah silang.
Gambar 12. Mengisi GenAawal
Gambar 13. Hasil dari Proses Pindah Silang (Angka Acak Terkecil)
Gambar 14. Hasil dari Proses Pindah Silang (Angka Acak Terbesar)
9. Setelah  melakukan  proses  pindah  silang  dapat dilanjutkan  dengan  proses  mutasi  dalam  proses  ini akan dihitung nilai fitness dari pindah silang dengan angka acak yang kecil dan juga angka acak yang besar untuk  dapat  dilihat  pengaruh  penggunaan  besar  – kecilnya angka acak yang dipakai pada proses pindah silang ini.
Gambar 15. Perhitungan Nilai Fitness Setelah Pindah Silang (Angka Kecil)

## Gambar 16. Perhitungan Nilai Fitness setelah Pindah Silang (Angka Besar)
10. Setelah  memperoleh  hasil  dari  pindah  silang akan  dilakukan  proses  mutasi.  Metode  mutasi  yang dipakai adalah reciprocal exchange mutation, dimana metode  ini  bekerja  dengan  memilih  dua  posisi
( exchange point / XP) secara acak kemudian menukar kedua  posisi  tersebut.  Proses  ini  dimulai  dengan menghitung  nilai  fitness  dari  ke-enam  kromosom yang akan dipakai dalam proses mutasi, perhitungan nilai fitness ini berfungsi sebagai pembanding antara nilai  fitness  sebelum  dilakukan  mutasi  dan  setelah dilakukan mutasi.
Gambar 17. Menghitung Nilai Fitness Sebelum Proses Mutasi
Gambar 18. Memilih Titik yang Ditukar
Gambar 19. Hasil dari Proses Pertukaran Titik
Setelah  dilakukan  proses  ini,  nilai  fitness  akan kembali dihitung untuk dapat membandingkan antara nilai fitness sebelumnya dan nilai fitness terbaru yang merupakan hasil mutasi.
Gambar 20. Menghitung Nilai Fitness setelah Proses Mutasi.
11. Setelah memperoleh jalur dari hasil perhitungan dengan  algoritma  genetika  akan  dibuatkan  jadwal perjalanan  untuk  pedagang  perabot  keliling  di  Kota Kupang. Proses ini berfungsi untuk membuat jadwal perjalanan  bagi  pedagang  perabot  keliling.  Proses pembuatan  jadwal  sendiri  dapat  dilakukan  melalui aplikasi yang telah dibuat.
Gambar 21. Kromosom Baru.
Gambar 22. Proses Pembuatan Jadwal Perjalanan (1)
Gambar 23. Proses Pembuatan Jadwal Perjalanan (2)

## Gambar 24. Hasil Pembuatan Jadwal
Jadwal  dari  aplikasi  yang  ada  dapat  dibuat  dalam bentuk  dokumen  untuk  mempermudah  bila  ingin mencetak jadwal yang telah dibuat. Proses pembuatan dokumen  dapat  dilakukan  dengan  menekan  tombol “cetak”  pada form jadwal  yang  ada  pada  aplikasi. Hasil  dari  proses  menekan  tombol  cetak  sendiri berupa word document untuk lebih mudah saat ingin dicetak ataupun disimpan dalam suatu perangkat.
Gambar 25. Jadwal yang Dihasilkan Berbentuk

## Dokumen

## 4. KESIMPULAN
Berdasarkan  penelitian  yang  dilakukan  dapat disimpulkan bahwa:
1. Jadwal yang diperoleh dari hasil penelitian ini dapat  dipakai  untuk  menentukan  lokasi penjualan antara hari senin hingga hari sabtu.
2. Rute yang dihasilkan sangat bergantung pada bilangan  acak  yang  dihasilkan  pada  proses pindah silang dan pertukaran titik pada proses mutasi.
3. Pemilihan  bilangan  acak  pada  proses  pindah silang  dapat  berpengaruh  terhadap  jadwal yang dihasilkan.

## DAFTAR PUSTAKA
[1] Andri., Suyandi, WinWin, 20”Aplikasi Travelling Salesman  Problem  dengan  Metode  Artificial Bee Colony,” Jurnal STMIK Mikroskil , Medan, 2013
[2]  Ina,  Wenefrida  Tulit,  “Penerapan  Algoritma Genetika  Pada  Persoalan  Kurir  TIKI,”  Jurnal Universitas Nusa Cendana , Kupang, 2012.
[3]  Mahmudy,  Wayan  Firdaus,  “Optimasi  Multi Travelling  Salesman  Problem  Menggunakan Algoritma Genetika,” Jurnal Universitas Brawijaya , Malang. 2008.
[4]  Suprayogi,  Dwi  Aries,  “Penerapan  Algoritma Genetika  Travelling  Salesman  Problem  with Time  window:  studi  kasus  antar  jemput laundry,” Jurnal Universitas Brawijaya , Malang. 2008.
[5] Sutojo, T, Edy Mulyanto dan Vincent Suhartono, “Kecerdasan Buatan, “Yogyakarta: Andi, 2010.