## OPTIMALISASI PENCARIAN LINTASAN TRAVELING SALESMAN PROBLEM  MENGGUNAKAN ALGORITMA BACKTRACKING
Hari Murti 1 , Edy Supriyanto 2 , Sugiyamta 3
1,2,3 Program Studi Sistem Informasi, Universitas Stikubank email: 1 harimurti@edu.unisbank.ac.id, 2 edy_supriyanto@edu.unisbank.ac.id,
3 sugiyamtagik@edu.unisbank.ac.id

## Abstrak
Tujuan  pemecahan  masalah  penjual  atau  wira  niaga  keliling  ( traveling  salesman problem ,  TSP)  adalah  menentukan  lintasan  atau  rute  dengan  total  jarak  atau  biaya  yang paling  minimum.  Penelitian  ini  berkenaan  dengan  proses  optimalisasi  pencarian  alternatif lintasan atau rute pada masalah TSP. Penjual mencari rute atau lintasan untuk mengunjungi semua kota yang ada sebanyak satu kali kunjungan. Proses optimalisasi pencarian alternatif menggunakan algoritma backtracking.
Terdapat lima buah kasus TSP yang akan digunakan yaitu TSP1 memiliki 4 buah kota dengan 6 lintasan (jalur), TSP2 memiliki 5 buah kota dengan 10 lintasan, TSP3 memiliki 6 buah  kota  dengan  15  lintasan,  TSP4  memiliki  7  buah  kota  dengan  21  lintasan,  dan  TSP5 memiliki  8  buah  kota  dengan  28  lintasan.  Dari  hasil  pengujian  diperoleh  algoritma  runut- balik  (backtracking)  dapat  digunakan  untuk  menghasilkan  jumlah  alternatif  lintasan  yang lebih  sedikit  jika  dibandingkan  dengan  total  kombinasi  alternatif  lintasan.  Semakin  besar jumlah  node  (kota)  dan  jumlah  lintasan  (jalur)  maka  prosentase  pengurangan  variasi (alternatif) akan lintasan semakin besar.
Kata Kunci: traveling salesman problem , algoritma runut-balik, backtracking .

## 1. PENDAHULUAN

## a.  Latar Belakang Masalah
Penelitian  ini  berkenaan  dengan  proses  optimalisasi  pencarian  alternatif  lintasan  atau  rute  pada masalah penjual atau wira niaga keliling ( traveling salesman problem , TSP). Wira niaga mencari rute atau  lintasan  untuk  mengunjungi  semua  kota  yang  ada  sebanyak  satu  kali  kunjungan.    Proses optimalisasi  pencarian  alternatif  menggunakan  algoritma backtracking .  Beberapa  penelitian  yang pernah dilakukan yang berhubungan dengan hal tersebut di atas, antara lain:
1) Penelitian  yang  dilakukan  oleh  Erdiwansyah  dan  Gani  (2016).  Masalah  optimasi  pada Traveling Salesman Problem (TSP) sangat terkenal dan telah menjadi standar untuk mencoba algoritma yang komputational. Traveling Salesman Problem merupakan sebuah permasalahan optimasi yang dapat diterapkan pada berbagai kegiatan seperti pendistribusian barang, pengambilan tagihan listirk dan penjadwalan.  Algoritma Local  Search merupakan  metode  pencarian  solusi  berdasarkan neighborhood dari  solusi  awal.  Metode  ini  dikenal  juga  dengan  nama iterative  improvement . Algoritma Population Based merupakan pencarian secara global. Hasil menunjukan algoritma local search lebih baik dari algoritma population based dalam pencarian nilai yang optimal.
2) Penelitian  yang  dilakukan  oleh  Widodo  dan  Mahmudy  (2010).  Pelancong  tidak  hanya  berfikir tentang  tempat  apa  yang  layak  dikunjungi  namun  juga  memikirkan  makanan  apa  yang  dapat dinikmati  beserta  keunikan  dan  kenyamanannya.  Perhatian  masyarakat  terhadap  wisata  kuliner mempengaruhi  kecenderungan  dan  gaya  dalam  berwisata.  Kondisi  ini  membawa  perubahan pertimbangan  seorang  pelancong  melakukan  pilihan  terhadap  tempat  kunjungan  wisata. Rekomendasi tentang faktor pilihan wisata, kesesuaian selera tempat makan, dan waktu perjalanan menjadi  hal  yang  penting.  Dalam  penelitian  ini  dilakukan  pendekatan  terhadap  masalah  tersebut dengan  menganalogikan  pada  kasus  pemilihan  rute  manakah  yang  memiliki  biaya  paling  murah untuk dilalui seorang pelancong yang harus mengunjungi sejumlah m daerah tujuan wisata (m > 1). Tiap daerah tujuan harus dikunjungi tepat satu kali dan kemudian kembali lagi ke tempat semula. Masalah  tersebut  sering  dikenal  dengan  nama Traveling  Salesman  Problem (TSP)  yaitu  masalah
kombinatorial yang solusi optimumnya didapat dengan cara mencoba semua kemungkinan sehingga memerlukan waktu komputasi yang cukup tinggi. Berbeda dengan fungsi TSP konvensional yang tujuannya  hanya  meminimalkan  jarak,  kasus  rekomendasi  ini  harus  mencocokkan  pilihan  wisata, kesesuaian  selera  tempat  makan,  dan  waktu  perjalanan.  Algoritma  Genetika  (GA)  terbukti  sesuai untuk menyelesaikan masalah multi obyektif, sehingga dapat diterapkan untuk sistem rekomendasi wisata kuliner metode crossover dengan satu titik potong dan mutasi dengan pergeseran gen pada GA mampu menyelesaikan masalah.
3) Penelitian yang dilakukan oleh Murti, Soelistijadi, dan Sugiyamto (2017). Permasalahan traveling salesman problem (TSP) adalah seorang penjual yang harus mengunjungi semua kota sebanyak satu sekali saja dimana dia harus mengawali dan mengakhiri perjalanan di kota yang sama. Tujuan TSP adalah menentukan lintasan atau rute dengan total jarak atau biaya yang paling minimum. Penelitian ini  bertujuan  untuk  mengetahui  kebutuhan  waktu  pada  proses  penyelesaian  TSP  menggunakan teknik pencarian buta dan pencarian terbimbing. Metode yang digunakan adalah pencarian melebar pertama ( breadth-first search ), pencarian mendalam pertama ( depth-first search ), pembangkitan dan pengujian ( generate and test ), dan pencarian terbaik pertama ( best first search ). Terdapat tiga buah ilustrasi kasus TSP yang digunakan yaitu TSP1 memiliki 4 buah kota dengan 6 jalan penghubung, TSP2 memiliki 5 buah kota dengan 10 jalan penghubung, dan TSP3 memiliki 8 buah kota dengan 28  jalan  penghubung.  Dari  hasil  pengujian  diperoleh  pencarian  mendalam  pertama  ( depth  first search )  membutuhkan  waktu  paling  sedikit  (tercepat)  apabila  dibandingkan  dengan  metode pencarian yang lain.
4) Penelitian yang berjudul “Perbandingan Algoritma Greedy, Algoritma Cheapest Insertion Heuristics dan Dynamic Programming Dalam Penyelesaian Travelling Salesman Problem” (Aristi, 2014). Pada penelitian  ini  dibandingkan  hasil  dari  perhitungan  menggunakan  algoritma greedy ,  algoritma cheapest insertion heuristics , dan dynamic programming , sehingga diketahui algoritma mana yang lebih  baik  untuk  menyelesaikan  kasus  TSP.  Hasil  penelitian  menunjukan  algoritma greedy lebih sederhana cara penyelesaiannya untuk jumlah kota yang masih sedikit sedangkan pada jumlah kota yang lebih banyak maka lebih baik menggunakan algoritma cheapest insertion heuristics . Melalui penelitian  ini  dapat  disimpulkan  jumlah  kota  yang  dikunjungi  berpengaruh  terhadap  pemilihan algoritma.
5) Penelitian oleh Fatmawati dan kawan-kawan pada tahun 2015 (Fatmawati, dkk., 2015). Tabu Search merupakan  salah  satu  metode  heuristik  yang  berbasis  pada  pencarian  lokal.  Proses  kinerjanya bergerak  dari  satu  solusi  ke  solusi  berikutnya  dengan  cara  memilih  solusi  terbaik.  Tujuan  utama metode  ini  adalah  mencegah  proses  pencarian  agar  tidak  melakukan  pencarian  ulang  pada  ruang solusi  yang  sudah  pernah  ditelusuri.  Metode  ini  menggunakan Tabu  List untuk  menyimpan sekumpulan solusi yang baru saja dievaluasi, hasilnya akan disesuaikan terlebih dahulu dengan isi pada Tabu List untuk melihat apakah solusi tersebut sudah ada atau tidak. Jika solusi tersebut sudah ada  maka  solusi  tersebut  tidak  akan  dievaluasi  lagi  pada  iterasi  berikutnya.  Pada  penelitian  ini, metode Tabu  Search diterapkan  untuk  menyelesaikan travelling  salesman  problem (TSP)  pada contoh kasus salesman PT. XX dalam mengatur rute perjalanannya.
6) Penelitian oleh Yunus, Helmi, dan Martha pada tahun 2015 (Yunus, dkk., 2015). Program Dinamis merupakan  salah  satu  metode  yang  dapat  digunakan  untuk  menyelesaikan  Traveling  Salesman Problem (TSP). Program Dinamis adalah metode penyelesaian dengan menguraikan solusi menjadi beberapa tahap atau iterasi sedemikian hingga solusi dari persoalan tersebut dapat dipandang sebagai serangkaian  keputusan  yang  saling  berkaitan.  Traveling  Salesman  Problem  adalah  membentuk sebuah  sirkuit  untuk  melewati  semua  simpul  dengan  total  bobot  dari  sisi  pembentuk  sirkuit minimum.  Penelitian  ini  mengkaji  penggunaan  Program  Dinamis  pada  penyelesaian  TSP  untuk menentukan sirkuit dengan bobot minimum dan melewati semua simpul dari graf. Berdasarkan arah dan bobotnya jika diambarkan dalam bentuk graf, TSP simetris merupakan jenis graf tidak berarah dan berbobot, sedangkan TSP asimetris adalah graf berarah dan berbobot. Penyelesaian TSP dapat menggunakan  Program  Dinamis  rekursif  maju  dan  rekursif  mundur  karena  mempunyai  solusi optimal yang sama. Hasil penyelesaian TSP menggunakan Program Dinamis dengan rekursif maju diperoleh berdasarkan solusi optimal dari iterasi ke-1 sampai iterasi ke-t.
Penelitian  yang  akan  dilakukan  oleh  penulis  adalah  melakukan  optimalisasi  pencarian  alternatif pada  lintasan traveling  salesman  problem (TSP).  Hal  ini  mengingat  penelitian  tentang  optimalisasi pencarian  alternatif  pada  lintasan  TSP  masih  belum  banyak  dilakukan.  Beberapa  contoh  kasus  TSP diperoleh dari data set (www.cc.gatech.edu/~bdilkina/CSE6140-2014fa/ProjectTSP.htm) dan buku teks (Russell dan Norvig, 2010; Kusumadewi dan Purnomo, 2005; Kusumadewi, 2003).

## b.  Perumusan Masalah
Penelitian  ini  berkenaan  dengan  proses  optimalisasi  pencarian  alternatif  lintasan  atau  rute  pada masalah penjual atau wira niaga keliling ( traveling salesman problem , TSP). Wira niaga mencari rute atau  lintasan  untuk  mengunjungi  semua  kota  yang  ada  sebanyak  satu  kali  kunjungan.  Proses optimalisasi pencarian alternatif menggunakan algoritma backtracking.

## c.   Batasan Masalah
Terdapat  lima  buah  kasus traveling  salesman  problem (TSP)  yang  akan  digunakan  yaitu  TSP1 memiliki 4 buah kota dengan 6 lintasan (jalur), TSP2 memiliki 5 buah kota dengan 10 lintasan, TSP3 memiliki 6 buah kota dengan 15 lintasan, TSP4 memiliki 7 buah kota dengan 21 lintasan, dan TSP5 memiliki 8 buah kota dengan 28 lintasan.

## 2. TUJUAN DAN MANFAAT PE NELITIAN

## a. Tujuan dan Manfaat Penelitian
Tujuan  penelitian  ini  yaitu  untuk  memperoleh  alternatif  lintasan  pada  proses  penyelesaian traveling salesman problem (TSP) dan optimalisasi pencarian alternatif pada lintasan tersebut. Manfaat dari  penelitian  ini  adalah  menghasilkan  alternatif  lintasan  yang  optimal  pada  penyelesaian  beberapa kasus TSP.

## 3. TINJAUAN PUSTAKA

## a.   Pencarian dan Pencocokan
Masalah  pencarian  merupakan  pencarian  solusi  yang  direncanakan  yang  mencari  lintasan  dari keadaan  awal  atau  keadaan  sekarang  sampai  dengan  keadaan  tujuan.  Pencarian  adalah  suatu  proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan ( state space ). Ruang  keadaan  merupakan  suatu  ruang  yang  berisi  semua  keadaan  yang  mungkin.  Kondisi  suatu pencarian meliputi:
1) Keadaan awal atau keadaan sekarang.
2) Keadaan tujuan atau sasaran yang ingin dicapai.
3) Biaya atau nilai yang diperoleh dari solusi.
Solusi  adalah  suatu  lintasan  dari  keadaan  awal  sampai  keadaan  tujuan  (Desiani  dan  Arhami,  2006). Proses pencarian solusi dapat dilakukan dengan cara sebagai berikut:
1) Memeriksa keadaan awal atau keadaan sekarang.
2) Mengeksekusi aksi yang dibolehkan dan berpindah ke keadaan berikutnya (keadaan baru).
3) Memeriksa  keadaan  baru.  Jika  keadaan  baru  bukan  solusi  maka  keadaan  baru  menjadi  keadaan sekarang dan kembali ke proses a, jika sebaliknya yaitu keadaan baru merupakan solusi maka proses pencarian selesai.
Proses di atas dikerjakan sampai dengan solusi ditemukan atau ruang keadaan telah dieksekusi semua. Kesuksesan dalam pencarian dan pencocokan ( search and matching ) akan menentukan tingkat keberhasilan sistem yeng bekerja berdasarkan kecerdasan buatan. Terdapat dua kelompok utama teknik pencarian  dan  pencocokan,  yaitu  pencarian  buta  ( blind  search )  dan  pencarian  terbimbing  ( heuristic search ) (K usumadewi, 2003).
b.  Pencarian mendalam pertama (depth-first search)
Metode pencarian buta akan mencari semua kemungkinan penyelesaian yang dimiliki. Salah satu metode  pencarian  buta  ( blind  search )  yaitu  Pencarian  mendalam  pertama  ( depth-first  search )  . Pencarian ini dimulai dari node akar dan dilanjutkan ke tingkat  yang lebih tinggi. Proses ini diulang
sampai  dengan  ditemukan  solusi.  Keuntungan  metode  ini  adalah  membutuhkan  memori  yang  relatif lebih kecil apabila dibandingkan dengan metode Pencarian melebar pertama. Disini hanya node-node pada lintasan yang aktif yang disimpan. Pada metode ini dimungkinkan untuk menemukan solusi tanpa harus menguji semua node (Kusumadewi, 2003).
Pada kasus terbaik, metode ini akan mencapai tujuan pada tingkat pertama, sehingga dibutuhkan waktu  pencarian  yang  cukup  singkat.  Pada  kasus  terburuk,  metode  ini  akan  mencapai  tujuan  pada tingkat terakhir dengan node terakhir.

## c.   Traveling Salesman Problem (TSP)
Studi  kasus traveling  salesman  problem (TSP)  dapat  diilustrasikan  seorang  penjual  yang  harus mengunjungi  seluruh  kota  dimana  masing-masing  kota  dikunjungi  sebanyak  satu  kali.  Dia  harus mengawali dan mengakhiri perjalanan di kota yang sama. Tujuan TSP adalah menentukan lintasan atau rute yang ditempuh penjual agar memperoleh total jarak atau biaya paling minimum.

## 1 Gambar 3.1 Ilustrasi denah kasus TSP
Pada Gambar 3.1. dapat dilihat sebuah ilustrasi denah kasus TSP, terdapat empat buah kota yaitu A, B, C, dan D, masing-masing dengan jarak tempuh diantara keempat kota tersebut.

## d.  Algoritma Backtracking
Algoritma  runut-balik  ( backtracking )  pertama  kali  diperkenalkan  oleh  D.H  Lehmer  pada  tahun 1950.  Algoritma  ini  cukup  handal  digunakan  untuk  beberapa  penyelesaian  masalah  dan  untuk memberikan kecerdasan buatan dalam game. Algoritma runut-balik  berbasis pada pencarian mendalam pertama ( depth-first search , DFS). Aturan pencariannya akan mengikut kepada aturan pencarian DFS yaitu dengan mencari solusi dari akar ke daun dengan pencarian mendalam.
Algoritma  ini  secara  sistematis  akan  mencari  solusi  berdasarkan  ruang  solusi  yang  ada  secara sistematis  namun  tidak  semua  ruang  solusi  akan  diperiksa,  hanya  pencarian  yang  mengarah  kepada solusi  yang  akan  diproses.  Untuk  memfasilitasi  pencarian  ini,  maka  ruang  solusi  diorganisasikan  ke dalam struktur pohon. Lintasan dari akar ke daun menyatakan solusi yang mungkin (Paliyus, R., dkk., 2015).

## 4. METODOLOGI PENELITIAN

## a.   Metode Penelitian
Pada penelitian ini menggunakan metode penelitian studi pustaka. Studi pustaka bahan referensi meliputi  pencarian  buta  ( blind  search )  dengan  metode  pencarian  mendalam  pertama  ( depth-first search )  serta  algoritma  runut-balik  ( backtracking )  untuk  penyelesaian  persoalan traveling  salesman problem (TSP).

## 5.  HASIL DAN ANALISA

## a.   Ilustrasi kasus TSP
Pada penelitian ini menggunakan lima buah ilustrasi kasus TSP seperti dapat dilihat pada Gambar 5.1, Gambar 5.2, Gambar 5.3, Gambar 5.4, dan Gambar 5.5. Pada TSP1 memiliki 4 buah kota dengan 6 lintasan (jalur), TSP2 memiliki 5 buah kota dengan 10 lintasan, TSP3 memiliki 6 buah kota dengan
15 lintasan, TSP4 memiliki 7 buah kota dengan 21 lintasan, dan TSP5 memiliki 8 buah kota dengan 28 lintasan. Rangkuman lima buah kasus TSP ini dapat dilihat pada Tabel 1.
Gambar 5.1 Ilustrasi kasus TSP1
Gambar 5.2 Ilustrasi kasus TSP2
Gambar 5.3 Ilustrasi kasus TSP3

## Gambar 5.4 Ilustrasi kasus TSP4

## Gambar 5.5 Ilustrasi kasus TSP5
Tabel 5.1 Rangkuman lima buah kasus TSP
Pada  Tabel  5.2.  dapat  dilihat  seluruh  alternatif  lintasan  yang  memungkinkan  beserta  panjang lintasan  untuk  menyelesaikan  kasus  TSP1  seperti  pada  Gambar  5.1.  Diperoleh  sebanyak  24  buah alternatif lintasan yang merupakan kombinasi dari urutan kunjungan ke kota A, B, C, dan D. Panjang lintasan terpilih yang terkecil adalah 12 dengan urutan lintasan terpilih adalah ACBD atau DBCA. Dua lintasan  tersebut  dapat  dipilih  salah  satunya  sebagai  solusi  dari  kasus  TSP  karena  memiliki  panjang lintasan terkecil yang sama.
Tabel 5.2 Alternatif Lintasan Traveling Salesman Problem studi kasus TSP1
Pencarian ke  Lintasan Panjang Lintasan Lintasan Terplih Panjang Lintasan Terpilih 1 ABCD 19 ABCD 19 2 ABDC 18 ABDC 18 3 ACBD 12 ACBD 12
4 ACDB 13 ACBD 12 5 ADBC 16 ACBD 12 6 ADCB 18 ACBD 12 7 BACD 17 ACBD 12 8 BADC 21 ACBD 12 9 BCAD 15 ACBD 12 10 BCDA 18 ACBD 12 11 BDAC 14 ACBD 12 12 BDCA 13 ACBD 12 13 CABD 15 ACBD 12 14 CADB 14 ACBD 12 15 CBAD 20 ACBD 12 16 CBDA 16 ACBD 12 17 CDAB 21 ACBD 12 18 CDBA 18 ACBD 12 19 DABC 20 ACBD 12 20 DACB 15 ACBD 12 21 DBAC 15 ACBD 12 22 DBCA 12 ACBD atau DBCA 12 23 DCAB 17 ACBD atau DBCA 12 24 DCBA 19 ACBD atau DBCA 12

## b.  Optimalisasi pencarian alternatif lintasan
Hasil optimalisasi pencarian alternatif lintasan atau rute pada Gambar 5.1 atau studi kasus TSP1 dapat  dilihat  pada  Tabel  5.3.  Terdapat  12  alternatif  lintasan  yang  berbeda  dari  sebelumnya  yaitu sebanyak  24  alternatif  lintasan,  sehingga  variasi  lintasan  berkurang  sebesar  50%.  Prosentase  ini diperoleh dari:
= (total kombinasi alternatif lintasan - jumlah alternatif lintasan hasil optimalisasi ) / total kombinasi alternatif lintasan * 100%
= (24 – 12) / 24 * 100%
= 50%
Tabel 5.3. Hasil optimalisasi pencarian alternatif lintasan untuk studi kasus TSP1
Nomor Pencarian ke n (pada tabel 1) Lintasan Panjang Lintasan Lintasan Terpilih Panjang Lintasan Terpilih 1 1 ABCD 19 ABCD 19 2 2 ABDC 18 ABDC 18 3 3 ACBD 12 ACBD 12 4 4 ACDB 13 ACBD 12 5 5 ADBC 16 ACBD 12 6 6 ADCB 18 ACBD 12 7 7 BACD 17 ACBD 12 8 8 BADC 21 ACBD 12 9 9 BCAD 15 ACBD 12 10 11 BDAC 14 ACBD 12 11 13 CABD 15 ACBD 12 12 15 CBAD 20 ACBD 12
Pada Gambar 5.2 atau studi kasus  TSP2 terdapat 120 buah alternatif lintasan  yang merupakan kombinasi  dari  kunjungan  ke  kota  A,  B,  C, D, dan  E.  Seluruh  kombinasi  lintasan  dapat dilihat  pada Tabel 5.4. Hasil optimalisasi pencarian alternatif lintasan atau rute pada Gambar 5.2 dapat dilihat pada
Tabel  5.5.  Terdapat  10  alternatif  lintasan  yang  berbeda  dari  sebelumnya  sebanyak  120  alternatif lintasan, sehingga variasi lintasan berkurang sebesar 91,66%. Prosentase ini diperoleh dari: =   (total kombinasi alternatif lintasan - jumlah alternatif lintasan hasil optimalisasi ) / total kombinasi alternatif lintasan * 100%
=   (120 – 10) / 120 * 100% =   91,66%
Panjang lintasan terpilih yang terkecil adalah 8 dengan urutan lintasan terpilih adalah AEDBC atau ACBDE. Dua lintasan tersebut dapat dipilih salah satunya sebagai solusi dari kasus TSP karena memiliki panjang lintasan terkecil yang sama.
Tabel 5.4 Seluruh kombinasi lintasan untuk studi kasus TSP2
Tabel 5.5. Hasil optimalisasi pencarian alternatif lintasan untuk studi kasus TSP2
Nomor  Lintasan Panjang Lintasan Lintasan Terpilih Panjang Lintasan Terpilih 1 AEDBC 8 AEDBC 8 2 ACBDE 8 AEDBC atau ACBDE 8 3 BDECA 10 AEDBC atau ACBDE 8 4 BDEAC 9 AEDBC atau ACBDE 8 5 CBDAE 11 AEDBC atau ACBDE 8 6 CBAED 11 AEDBC atau ACBDE 8 7 DBCAE 9 AEDBC atau ACBDE 8 8 DBCEA 10 AEDBC atau ACBDE 8 9 EDBAC 10 AEDBC atau ACBDE 8 10 EDCBA 11 AEDBC atau ACBDE 8
Panjang lintasan pada kasus TSP5 dapat dilihat pada Tabel 5.6, terdapat dua puluh delapan lintasan yang menghubungakan delapan kota. Pada Tabel 5.7 dapat dilihat rekapitulasi prosentase pengurangan variasi (alternatif) lintasan untuk seluruh kasus TSP.  Dari hasil pengujian diperoleh algoritma runut- balik ( backtracking ) dapat digunakan untuk menghasilkan jumlah alternatif lintasan yang lebih sedikit jika dibandingkan dengan  total  kombinasi alternatif lintasan. Untuk seluruh kombinasi lintasan pada kasus TSP5 dapat dilihat pada Tabel 5.8.
Tabel 5.6. Panjang Lintasan setiap kota pada TSP5
Nomor  Kota Asal  Kota Tujuan  Panjang Lintasan 1 A B 6 2 A C 4 3 A D 9 4 A E 9 5 A F 5 6 A G 5 7 A H 8 8 B C 7 9 B D 7 10 B E 6 11 B F 9 12 B G 9 13 B H 3 14 C D 9 15 C E 4 16 C F 3 17 C G 7 18 C H 6 19 D E 9 20 D F 9 21 D G 3 22 D H 9 23 E F 4 24 E G 3 25 E H 4 26 F G 5 27 F H 3

## Tabel 5.7 Rekapitulasi prosentase pengurangan variasi (alternatif) lintasan
Tabel 5.8 Seluruh kombinasi lintasan untuk studi kasus TSP5

## 6.  KESIMPULAN DAN SARAN

## a.   Kesimpulan
Dari  hasil  pengujian  diperoleh  algoritma  runut-balik  ( backtracking )  dapat  digunakan  untuk menghasilkan jumlah alternatif lintasan yang lebih sedikit jika dibandingkan dengan total kombinasi alternatif  lintasan.  Semakin  besar  jumlah node (kota)  dan  jumlah  lintasan  (jalur)  maka  prosentase pengurangan variasi (alternatif) akan lintasan semakin besar.

## b.   Saran
Saran  untuk  penelitian  selanjutnya  adalah  menambah  variasi  jumlah node (kota)  dan  jumlah lintasan (jalur) serta menampilkan visualisasi rute yang dipilih.

## DAFTAR PUSTAKA
[1] Aristi,  G.,  2014,  Perbandingan  Algoritma  Greedy,  Algoritma  Cheapest  Insertion  Heuristics  dan Dynamic  Programming  Dalam  Penyelesaian  Travelling  Salesman  Problem,  Jurnal  Paradigma, Vol. XVI, No. 2, Hal. 52 - 58, September 2014.
[2] Desiani, A. dan Arhami, M., 2006, Konsep Kecerdasan Buatan, Penerbit Andi, Yogyakarta.
[3] Erdiwansyah,  Gani,  T.  A.,  2016,  Analisis  Perbandingan  Metode  Local  Search  dan  Population Based  Dalam  Algoritma  Berevolusi  untuk  Penyelesaian  Travelling  Salesman  Problem  (TSP), Jurnal Serambi Engineering, Volume I, Nomor 1, Hal. 111, Agustus 2016.
[4] Fatmawati, Prihandono, B., Noviani, E., 2015, Penyelesaian Travelling Salesman Problem Dengan Metode Tabu Search, Buletin Ilmiah Mat. Stat. Dan Terapannya (Bimaster), Vol. 04, No.1, hal 17 – 24, (2015).
[5] Kusumadewi, S., 2003, Artificial Intelligence (Teknik dan Aplikasinya), Graha Ilmu, Yogyakarta.
[6] Kusumadewi, S. dan Purnomo, H., 2005, Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik, Graha Ilmu, Y ogyakarta.
[7] Murti, H., Soelistijadi, R., Sugiyamto, 2017, Analisa Kebutuhan Waktu pada Proses Penyelesaian Traveling  Salesman  Problem,  Prosiding  SINTAK  2017  Hal.  74  -  78,  Universitas  Stikubank Semarang.
[8] Paliyus,  R.,  Muhammad  Danial,  M.,  Udjulawa,  D.,,  2015,  Implementasi  Backtracking  Dalam Permainan Cari Kata untuk Mengenalkan Nama dan Fungsi Anggota Tubuh, http://eprints.mdp.ac.id/1681/ , STMIK MDP GI Palembang.
[9] Russell, S., Norvig, P., 2010, Artificial Intelligence A Modern Approach Third Edition, Pearson, USA.
[10] Widodo, A.W., Mahmudy, W.F., 2010, Penerapan Algoritma Genetika pada Sistem Rekomendasi Wisata Kuliner, Jurnal Ilmiah KURSOR Vol. 5, No. 4, hlm. 205-211, Juli 2010.
[11] Yunus,  H.,  Helmi,  Martha,  S.,  2015,  Metode  Program  Dinamis  pada  Penyelesaian  Traveling Salesman Problem, Buletin Ilmiah Mat. Stat. dan Terapannya, Volume 04, No. 3 (2015), hal 329 – 336.
[12] https://visualgo.net/bn/tsp