p-ISSN : 2528-3561 e-ISSN : 2541-1934

## Perbandingan Pendekatan Breadth First Search, Depth First Search dan Best First Search Pada Pencarian Rute Menggunakan Metode Branch and Bound
Ryano Alderio 1* , Rianita Puspa Sari 2
1,2 Teknik Industri, Fakultas Teknik Universitas Singaperbangsa Karawang, Indonesia * Koresponden email : 1910631140142@student.unsika.ac.id
Diterima: 25 Juli 2023 Disetujui: 4 Agustus 2023

## Abstract
A Travelling Salesman often encounters a problem where they have to find the shortest route that can be passed when they want to visit several places without having to go to the same place more than once. So, it is necessary to find the shortest route that is  useful for efficient distribution. The Travelling Salesman Problem is solved using the branch and bound method with three different approaches: Breadth First Search, Depth  First  Search,  and  Best  First  Search.  These  three  approaches  will  be  compared  regarding  their effectiveness and efficiency. The case study used is a team of cigarette product sellers in the Kuningan area who  will  distribute  their  products  to  four  villages.  The  route  currently  in  use  is  from  Warehouse  → Karangmangu Village → Jalaksana Village → Peusing Village → Sidamulya Village → Warehouse with a distance of 19,8 km. The result of this study obtained the shortest route with the path from Warehouse → Karangmangu Village → Sidamulya Village → Peusing Village → Jalaksana Village → Warehouse with a  distance  of  19,7  km.  And  the  comparison  result  obtained  is  that  The  Breadth  First  Search  approach requires  more  calculations  with  28  calculations,  while  The  Depth  First  Search  approach  requires  25 calculations, and The Best First Search approach requires 23 calculations.
Keywords: travelling salesman problem, branch and bound, breadth-first search, depth first search, best first search

## Abstrak
Seorang Travelling Salesman seringkali menjumpai permasalahan yang dimana mereka harus mencari rute terpendek yang bisa dilalui ketika ingin mengunjungi beberapa tempat tanpa harus mendatangi tempat yang sama  lebih  dari  satu  kali.  Maka  perlu  dilakukan  pencarian  rute  terpendek  yang  berguna  untuk pendistribusian yang efisien. Pemecahan Travelling Salesman Problem ini dilakukan dengan menggunakan metode Branch and Bound dengan tiga pendekatan yang berbeda yaitu Breadth First Search , Depth First Search , dan Best First Search . Ketiga pendekatan ini akan dilakukan perbandingan mengenai efektivitas dan efisiensinya. Studi kasus yang dipakai adalah tim sales produk rokok di wilayah Kuningan yang akan mendistribusikan  produknya  ke  empat  desa. Rute  yang  saat  ini  digunakan  adalah  rute  Gudang  →  Desa Karangmangu → Desa Jalaksana → Desa Peusing → Desa Sidamulya → Gudang dengan jarak 19,8 km. Hasil  penelitian  ini  didapatkan  rute  terpendek  dengan  jalur  Gudang  →  Desa  Karangmangu  →  Desa Sidamulya → Desa Peusing → Desa Jalaksana → Gudang dengan jarak 19,7 km. Dan hasil perbandingan yang didapat adalah pendekatan Breadth First Search memerlukan perhitungan lebih banyak dengan 28 kali perhitungan, sedangkan untuk pendekatan Depth First Search membutuhkan 25 kali perhitungan, dan untuk pendekatan Best First Search membutuhkan 23 kali perhitungan.
Kata  Kunci:  travelling  salesman  problem;  branch  and bound;  breadth-first  search;  depth  first  search; best first search

## 1. Pendahuluan
Salesman adalah  orang  yang  melakukan  penawaran,  pemasaran,  distribusi,  dan  penjualan  sebuah produk  secara  langsung  pada  konsumen  agar  tertarik  untuk  membelinya  yang  berarti  salesman  sebagai perantara  pemesanan  barang. Salesman harus  memiliki  kepribadian  yang  pandai  dalam  mempengaruhi orang lain, yang artinya salesman harus mampu menggerakkan pelanggan untuk membeli produk/jasa yang ditawarkannya. Seringkali seorang salesman mengalami masalah yang dimana salesman harus mencari rute terpendek dari satu tempat ke tempat lain tanpa harus memutar atau mengunjungi kota dua kali. Tujuannya yaitu mencari jalur perjalanan ke semua kota dengan meminimumkan bobot total. Penerapan yang dibahas pada jurnal ini adalah untuk menentukan rute terpendek guna meminimasi biaya transportasi. Salah satu
p-ISSN : 2528-3561 e-ISSN : 2541-1934
cara  penyelesaian travelling  salesman  problem adalah  dengan  menggunakan  metode branch  and  bound yang  dimana branch  and  bound ini  merupakan  metode  yang  sistematis  dan  logis  dalam  menyelesaikan beragamnya permasalahan optimasi seperti optimasi kombinatorial dan diskrit [1].
Ada  beberapa  pendekatan  yang  bisa  digunakan  pada  metode branch  and  bound untuk  mengatasi permasalahan travelling  salesman ini.  Pada  penelitian  sebelumnya  yang  dilakukan  oleh  [2],  pendekatan yang digunakan adalah pendekatan Breadth First Search (BFS). Lalu pada penelitian yang dilakukan [3], pendekatan  yang  digunakan  adalah  pendekatan Depth  First  Search (DFS).  Dan  pada  penelitian  yang dilakukan oleh [4], pendekatan yang digunakan adalah pendekatan Best First Search (BeFS). Operation research atau penelitian operasional dapat dilihat dari  aspek ilmu dan aspek seni. Pada aspek ilmu terdapat pada tersedianya teknik-teknik algoritma serta matematis untuk pengambilan keputusan yang  tepat  dan  pemecahan  masalah.  Sedangkan,  aspek  seni  karena  keberhasilan  dalam  semua  tahapan dalam menindaklanjuti pemecahan masalah dari sebuah model matematis, yang tergantung dari kreativitas dan kemampuan pribadi pembuat keputusan. Tahapan dalam melakukan sebuah studi penelitian operasional dimulai  dari  mendefinisikan  suatu  permasalahan,  mengembangkan  model,  memecahkan  modelnya, menguji keabsahannya, kemudian pengimplementasian dari hasil akhirnya [5]. Dapat disimpulkan bahwa operation  research atau  penelitian  operasional  merupakan  sebuah  teknik  matematis  untuk  menarik  atau mendapatkan  keputusan  optimal  suatu  masalah.  Adapun  tahapannya  meliputi  mendefinisikan  suatu permasalahan,  mengembangkan  model,  memecahkan  modelnya,  menguji  keabsahannya,  kemudian pengimplementasian dari hasil akhirnya.
Travelling  Salesman  Problem (TSP)  merupakan  suatu  permasalahan  yang  dimana  penjual ( salesman ) harus berkunjung ke sejumlah kota/tempat untuk menjual produknya. Tiap kota/tempat hanya bisa dikunjungi sekali dan apabila telah berkunjung ke semua kota/tempat tersebut, maka harus kembali ke kota/tempat  awal  ia  berasal.  Untuk  mengefisiensikan  biaya,  waktu,  dan  tenaga,  maka  perlu  dicari  jalur optimal  untuk  melakukan  perjalanan  tersebut  [6].  Permasalahan  ini dikenal  juga  sebagai  permasalahan optimasi  klasik  dan  bersifat Non  Deterministic  Polynimial-time Complete (NPC),  yang  artinya  harus mencoba semua kemungkinan rute yang ada untuk mendapatkan rute yang paling optimal. Persoalan ini melibatkan  seorang  penjual  keliling  atau  “ Travelling  Salesman ” yang  harus  berkunjung  ke  semua  kota masing-masing satu kali dalam sebuah sirkuit yang kemudian kembali ke tempat awal ia memulai sehingga bisa dikatakan perjalanan yang sempurna.
Branch  and  Bound merupakan  salah  satu  metode  untuk  mendapatkan variable keputusan  yang berbentuk integer dan merupakan metode paling umum untuk mengatasi masalah optimasi integer . Prinsip utama dalam penggunaan metode ini yaitu strategi untuk melakukan “pencabangan dan pembatasan”  [7]. Cara  kerja  pada  metode  ini  adalah  dengan  melakukan  pencabangan  pada variable keputusan  yang  tidak mempunyai penyelesaian yang bulat, pencabangan ini terus dilakukan sampai memperoleh penyelesaian yang bulat sehingga seluruh variabel keputusan akan menghasilkan nilai yang bulat serta akan mendapatkan keuntungan yang maksimal untuk perusahaan [8]. Metode ini didasarkan pada gagasan bahwa himpunan- himpunan dibagi menjadi dua sub himpunan terpisah pada setiap langkah proses branching . Selanjutnya, satu  sub  set  berisi  jalur  antara  dua  kota  yang  terpilih  dan  sub  set  lainnya  tidak.  Untuk  masing-masing himpunan bagian ini, batasan bawah ( bound) dihitung untuk durasi atau biaya. Akhirnya, himpunan bagian yang  melebihi  estimasi bound bawah  dihilangkan  [9].  Metode  ini  akan  memberikan  batasan  pada penyelesaian optimal, kemudian didapatkan bilangan pecahan dengan cara dibuatkannya branch (cabang) bawah  dan  atas  pada  tiap-tiap  variabel  keputusan  yang  memiliki nilai  pecahan  supaya  menjadi  bilangan yang bulat sehingga tiap pembatas akan menghasilkan branch baru serta membentuk sebuah search tree (pohon pencarian) yang bisa diselesaikan.
Adapun langkah-langkah dalam melakukan metode ini yaitu sebagai berikut:
a. Mengatasi permasalahan program linear menggunakan cara simplex biasa.
b. Melihat  solusi  optimumnya.  Apabila variable basis  yang  diinginkan  bulat  adalah  benar  bulat,  bisa disimpulkan bahwa solusi optimum yang bulat telah dicapai.
c. Nilai  dari  solusi  pecahan  yang  sesuai  dicabangkan  pada  sub-bab  masalah,  bertujuan  agar menghilangkannya solusi kontinu yang solusi bulatnya tidak terpenuhi.
d. Pada tiap sub-bab permasalahan, nilai pada solusi optimum kontinu fungsi tujuan akan dijadikan bound atas dan solusi bulat yang terbaik dijadikan bound bawah. Pada awalnya ini merupakan solusi kontinu yang kurang dari bound bawah dan tidak diikutsertakan dalam analisa setelahnya. Sebuah solusi bulat yang layak ialah solusi yang lebih baik atau sama baik dari bound atas pada tiap sub-masalah yang dicari.  Apabila  solusi  tersebut  didapatkan,  maka  sub-masalah  dengan bound atas  terbaiklah  yang terpilih untuk dilakukan pencabangan. Kemudian kembali lagi pada langkah 3.
p-ISSN : 2528-3561 e-ISSN : 2541-1934
BFS ( Breadth  First  Search )  merupakan  cara  penelusuran  suatu  graf  dengan  arah  penelusurannya yang  mengutamakan  ke  arah  lebar  (samping)  graf  tersebut  [10].  Pendekatan  ini  dilakukan  secara menyamping yang dimana kota (titik) yang akan dibangkitkan lebih dulu adalah tetangga dari titik awal tersebut [11].
DFS ( Depth  First  Search )  merupakan  sebuah  pencarian uninformed yang  cara  kerjanya  dengan memperluas simpul pada anak pertama dari  pohon pencarian yang muncul, dengan demikian akan lebih dalam dan lebih sama node tujuan yang ditemukan atau hingga ditemukannya node yang tidak beranak, lalu dilanjutkan pencarian backtracks , dan kembali menuju node terbaru yang belum selesai dijelajah [12]. Jika belum ditemukannya solusi pada pencarian tersebut, maka perlu kembali ke simpul sebelumnya untuk dilakukan penelusuran dan dilanjut ke simpul tetangga. Ulangi terus proses ini sampai solusi ditemukan [13].
BeFS ( Best-First  Search )  adalah  metode  yang  dilakukan  dengan  cara  dibangkitkannya  simpul selanjutnya dari sebuah simpul yang terbaik diantara seluruh simpul level terdalam ( leaf nodes ) yang pernah dibangkitkan [14]. Pendekatan ini merupakan gabungan dari metode Breath-First Search dan Depth-First Search yang  mengambil  masing-masing  kelebihannya.  Tiap  langkah  pada  proses  BeFS,  simpul-simpul akan  dipilih  dengan diterapkannya  fungsi heuristik  pada  tiap  simpul yang  terpilih  dengan  digunakannya aturan-aturan  tertentu  agar  didapatkan  penggantinya  dan  pencarian  diperbolehkan  untuk  mengunjungi simpul-simpul yang lebih rendah apabila simpul yang lebih tinggi mempunyai nilai heuristik lebih buruk [13].
Oleh  sebab  itu,  penulis  akan  melakukan  perbandingan  antara  pendekatan Breadth  First  Search , Depth First Search , dan Best First Search yang digunakan metode Branch and Bound pada penyelesaian Travelling  Salesman  Problem. Alasan  lainnya  adalah  karena  dari  ketiga  pendekatan  tersebut  saling berkaitan yang dimana Best First Search adalah kombinasi antara BFS dan DFS yang mengambil masing- masing kelebihan dari keduanya [15]. Studi kasus yang digunakan adalah perjalanan yang dilakukan Tim Sales produk rokok di wilayah Kuningan yang berasal dari salah satu gudang penyimpanan produk rokok yang  mendistribusikan  produknya  ke  beberapa  tempat  pada  4  desa  yang  berbeda,  yaitu  Desa  Jalaksana, Desa Sidamulya, Desa Karangmangu, dan Desa Peusing.

## 2. Metode Penelitian

## Pengumpulan Data
Pengambilan  data  dilakukan  dengan  mewawancarai  narasumber  yang  bekerja  sebagai Promotion Representative di tempat pendistribusian produk rokok tersebut yang bernama Agus Mukhlas Sugiarto dan didapatkan data tempat yang akan disinggahi pada hari Jumat yang ditunjukkan pada Tabel 1 .
Tabel 1 . Tujuan dan jarak antar titik Tempat O A B C D O - 3.9 5.4 3.6 7.4 A 3.9 - 3.2 2.9 3.6 B 5.4 3.2 - 4.3 4.3 C 3.6 2.9 4.3 - 6.4 D 7.4 3.6 4.3 6.4 - Sumber: Data Peneliti (2023)
Gambar 1 . Posisi masing-masing titik Sumber: Peneliti (2023)
Pada Tabel  1 berisikan  tempat  yang  akan dituju  serta  jarak  antar  tempatnya  dan pada Gambar 1 merupakan posisi tiap-tiap tempat. Untuk satuan jarak yang digunakan adalah kilometer (km) yang diukur dengan bantuan Google Map dan untuk keterangan simbol tujuan ada pada keterangan berikut ini:
O B A C D
p-ISSN : 2528-3561 e-ISSN : 2541-1934
O  : Gudang A  : Desa Jalaksana B  : Desa Sidamulya C  : Desa Karangmangu D  : Desa Peusing
Rute yang digunakan saat ini dimulai dari Gudang → Desa Karangmangu → Desa Jalaksana → Desa Peusing → Desa Sidamulya → Gudang dengan total jarak 19,8 km.
Gambar 2 . Rute yang digunakan saat ini Sumber: Peneliti (2023)
Alasan mereka memilih rute tersebut karena jalur tersebut seperti melingkar sehingga mereka pikir dengan membuat jalur yang melingkar atau seperti berkeliling, serta tidak membuat jalur atau garis yang saling memotong satu sama lain akan didapati rute yang lebih pendek.

## Penerapan Metode Branch and Bound
Perhitungan  dilakukan  secara  manual  dengan  cara  menghitung bound tiap  titik/tempat  sepanjang jalur.  Perhitungan  dilakukan  mulai  dari  level  pertama  hingga  level  terakhir  yang  dimana  level  terakhir merupakan  level  yang  akan  mendapatkan  total bound pada  sebuah  rute/jalur.  Perhitungan  ini  dilakukan untuk mencari total bound terkecil diantara semua rute yang ada.
Perhitungan  level  1  dilakukan  dengan  cara  memasukan  data  ke  tabel  perhitungan,  lalu  cari  jarak terkecil  pada  tiap  barisnya  sehingga  total  dari  jarak  terkecil  tersebut  akan  didapatkan bound sebagai pembatas. Pada level ini hanya terdapat 1 kali perhitungan karena hanya menghitung bound dari tempat awal keberangkatan, yaitu dari Gudang.
Tabel 2 . Perhitungan level 1 Jarak B v 1 M 3.9 5.4 3.6 7.4 3.6 v 2 3.9 M 3.2 2.9 3.6 2.9 v 3 5.4 3.2 M 4.3 4.3 3.2 v 4 3.6 2.9 4.3 M 6.4 2.9 v 5 7.4 3.6 4.3 6.4 M 3.6 Total 16.2 Sumber: Data Peneliti (2023)
Simbol B merupakan bound dan simbol v merupakan suatu perjalanan. Bound yang didapat adalah 16,2 sehingga bound pada cabang selanjutnya tidak akan kurang dari 16,2.
Dilanjutkan pada perhitungan level 2 dengan cara  memasukkan data ke tabel perhitungan dan cari jarak  terkecil  pada  tiap  barisnya  untuk  mendapatkan bound. Setelah  dari  Gudang,  ada  4  pilihan  untuk dijadikan tujuan pertama. Oleh karena itu, bound pada v 1 akan diisi dengan jarak tujuan selanjutnya yang akan  dituju.  Kemudian  hilangkan  nilai  pada  kolom  tempat  yang  akan  dituju,  nilai  pada  baris  tempat sebelumnya, dan juga nilai dari tempat tujuan selanjutnya menuju tempat awal. Sebagai contoh, perhitungan pertama yang dilakukan dari Gudang ke Jalaksana (O → A).
Pada perhitungannya, bound pada v 1 diisi dengan jarak O → A (3,9), lalu hilangkan nilai pada kolom A (karena titik A tidak akan dilewati kembali), nilai pada baris O (karena sudah terisi dengan v 1 ), dan juga jarak A → O (karena setelah ke A, tidak akan mungkin menuju ke O).
O B A C D
p-ISSN : 2528-3561 e-ISSN : 2541-1934
Tabel 3 . Perhitungan level 2 Jarak B v 1 3.9 v 2 - - 3.2 2.9 3.6 2.9 v 3 5.4 - M 4.3 4.3 4.3 v 4 3.6 - 4.3 M 6.4 3.6 v 5 7.4 - 4.3 6.4 M 4.3 Total 19 Sumber: Data Peneliti (2023)
Didapatlah bound pada perjalanan O → A dengan total bound 19. Lanjutkan perhitungan seperti ini pada tujuan yang lainnya dengan cara yang sama dan didaptkan hasil bound pada tiap perhitungan di level 2. B OA = 19 B OB = 18 B OC = 16,5 B OD = 20 Sebagai contoh, peneliti menggunakan bound terkecil yaitu 16,5 yang merupakan jalur O → C untuk dilanjutkan perhitungannya ke level 3 agar dijadikan contoh perhitungan pada level tersebut.
Perhitungan level 3 sama seperti perhitungan level 2, hanya saja menggunakan tabel lanjutan yang terpilih pada level 2. Dalam kasus ini menggunakan tabel perhitungan B OC yang sudah terpilih sebelumnya. Sebagai contoh, perhitungan pertama dilakukan dengan jalur O → C → A.
Tabel 4 . Perhitungan level 3 Jarak B v 1 3.6 v 2 2.9 v 3 - - 3.2 - 3.6 3.2 v 4 5.4 - M - 4.3 4.3 v 5 7.4 - 4.3 - M 4.3 Total 18.3 Sumber: Data Peneliti (2023)
Lanjutkan perhitungan seperti ini pada tujuan yang lainnya dengan cara yang sama. Sebagai contoh, peneliti menggunakan jalur O → C → A dengan bound 18,3 untuk dilanjutkan perhitungannya ke level 4 agar dijadikan contoh perhitungan pada level tersebut.
Perhitungan pada level 4 sama saja seperti perhitungan sebelumnya, tabel perhitungan yang dipilih adalah tabel perhitungan B OCA . Dalam kasus ini, level 4 merupakan level terakhir sehingga akan didapatkan jalur  dari  awal  keberangkatan  hingga  kembali  ke  tempat  awal  keberangkatan  dan  juga  didapatkan  total bound pada jalur tersebut. Sebagai contoh, perhitungan dilakukan dengan jalur O → C → A → B → D → O.
Tabel 5 . Perhitungan level 4 Jarak B v 1 3.6 v 2 2.9 v 3 3.2
v 4 - - - - 4.3 4.3 v 5 7.4 - -
- M 7.3 Total 21.4
Sumber: Data Peneliti (2023)
Lanjutkan  perhitungan  seperti  ini  pada  tujuan  yang  lainnya  dengan  cara  yang  sama.  Pada  level terakhir, bound yang didapat merupakan total bound (TB) pada jalur tersebut. Untuk mencari total bound terkecil, lakukan kembali perhitungan pada rute yang lain baik pada level 2, level 3, maupun level 4 hingga didapat total bound terkecil.
p-ISSN : 2528-3561 e-ISSN : 2541-1934

## 3. Hasil dan Pembahasan
Perhitungan Travelling  Salesman  Problem dilakukan  menggunakan  metode Branch  and  Bound , tentunya menggunakan tiga pendekatan yang berbeda, yaitu Breadth First Search , Depth First Search , dan Best First Search . Tujuan perhitungan ini adalah untuk mendapatkan total bound terbaik diantara semua rute yang ada sehingga akan didapatkan rute terpendek.

## Breadth First Search
Gambar 3 . Perhitungan pendekatan breadth first search Sumber: Data Peneliti (2023)
Terlihat  pada  perhitungan Breadth  First  Search diatas,  dibutuhkan  28  kali  perhitungan  untuk mendapatkan total bound terbaik dan hasil akhir total bound yang didapat sebesar 19,7 dengan rute O → A → D → B → C → O dan juga kebalikannya.

## Depth First Search
Gambar 4 . Perhitungan pendekatan depth first search Sumber: Data Peneliti (2023)
Terlihat  pada  perhitungan Depth  First  Search diatas,  dibutuhkan  25  kali  perhitungan  untuk mendapatkan total bound terbaik dan hasil akhir total bound yang didapat sebesar 19,7 dengan rute O → A → D → B → C → O dan juga kebalikannya.
O B : 16,2 B B : 18 A B : 19 D B : 20 C B : 16,5 B B : 21,4 D B : 19,7 C B : 19,7 A B : 21,5 D B : 19,1 C B : 19,8 B B : 18,3 A B : 18,3 D B : 20 A B : 21,8 C B : 23,1 B B : 20,7 DCO B : 21,4 CDO B : 25,2 DBO B : 22,9 BDO B : 22,8 CBO B : 23,6 BCO B : 19,7 CAO B : 22,9 ACO B : 19,8 DBO B : 19,8 BDO B : 21,4 DAO B : 19,7 ADO B : 22,1 TB 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 TB 2 TB 3 TB 4 Lvl 1 Lvl 2 Lvl 3 Lvl 4 O B : 16,2 B B : 18 A B : 19 D B : 20 C B : 16,5 B B : 21,4 D B : 19,7 C B : 19,7 A B : 21,5 D B : 19,1 C B : 19,8 B B : 18,3 A B : 18,3 D B : 20 DCO B : 21,4 CDO B : 25,2 DBO B : 22,9 BDO B : 22,8 CBO B : 23,6 BCO B : 19,7 CAO B : 22,9 ACO B : 19,8 DBO B : 19,8 BDO B : 21,4 DAO B : 19,7 ADO B : 22,1 TB 1 1 11 17 25 2 5 8 12 13 14 18 21 24 3 4 6 7 9 10 15 16 19 20 22 23 TB 2 TB 3 TB 4 Lvl 1 Lvl 2 Lvl 3 Lvl 4
p-ISSN : 2528-3561 e-ISSN : 2541-1934

## Best First Search
Gambar 5 . Perhitungan pendekatan best first search Sumber: Data Peneliti (2023)
Terlihat  pada  perhitungan Best  First  Search diatas,  dibutuhkan  23  kali  perhitungan  untuk mendapatkan total bound terbaik dan hasil akhir total bound yang didapat sebesar 19,7 dengan rute O → C → B → D → A → O dan juga kebalikannya.

## Pembahasan
Pada ketiga perhitungan diatas, hasil akhir total bound yang didapat sama besar dengan nilai 19,7 dan hasil akhir yang didapat sama-sama didapatkan pada TB 4. Tetapi perbedaan yang didapatkan terletak pada banyaknya perhitungan yang dilakukan.
Untuk  mendapatkan  total bound terbaik,  pendekatan Breadth  First  Search membutuhkan  28  kali perhitungan, sedangkan untuk pendekatan Depth First Search membutuhkan 25 kali perhitungan, dan untuk pendekatan Best First Search membutuhkan 23 kali perhitungan. Breadth First Search memerlukan perhitungan yang lebih banyak karena sifat pendekatan ini yang harus  melakukan  perhitungan  dengan  arah  melebar  yang  artinya  perhitungan  mengutamakan  titik  yang bertetangga dengan titik awal sebelum melakukan perhitungan ke dalam. Depth First Search melakukan perhitungan yang mengutamakan titik ke dalam daripada titik yang bertetangga untuk segera mencari total bound terlebih  dahulu  sebagai  patokan  total bound selanjutnya  dan  kecepatan  menemukan  hasil  akhir dipengaruhi  oleh  keberuntungan  yang  tergantung  dimana  letak  total bound terbaik  berada,  ketika  total bound terbaik didapat pada total bound pertama maka perhitungan yang dilakukan pun tidak akan banyak dan begitu pun sebaliknya. Best First Search melakukan perhitungan dengan mencari bound terbaik pada tiap  level  untuk  dilakukan  perhitungan  selanjutnya  pada  titik  dengan bound terpendek  tersebut  dan mengeliminasi bound yang lebih besar.
Setelah dilakukan perhitungan secara menyeluruh, maka didapatlah hasil dengan total bound terkecil dengan nilai 19,7 dan didapatlah rute terpendek dengan jalur O → C → B → D → A → O atau sebaliknya.
Gambar 5 . Hasil rute terpendek yang didapat Sumber: Data Peneliti (2023)
Maka  diperoleh  rute  terpendek  studi  kasus  ini  adalah  Gudang  →  Desa  Karangmangu  →  Desa Sidamulya → Desa Peusing → Desa Jalaksana → Gudang ataupun sebaliknya dengan total jarak 19,7 km.

## 4. Kesimpulan
Dari  analisis  dan  perhitungan  yang  telah  dilakukan,  bisa  disimpulkan  bahwa  pada  penyelesaian Travelling  Salesman  Problem menggunakan  metode Branch  and  Bound pada  ketiga  pendekatan  yang
O B A C D O B : 16,2 B B : 18 A B : 19 D B : 20 C B : 16,5 B B : 21,4 D B : 19,7 C B : 19,7 A B : 21,5 D B : 19,1 C B : 19,8 B B : 18,3 A B : 18,3 D B : 20 DCO B : 21,4 CDO B : 25,2 DBO B : 22,9 BDO B : 22,8 CBO B : 23,6 BCO B : 19,7 CAO B : 22,9 ACO B : 19,8 DBO B : 19,8 BDO B : 21,4 DAO B : 19,7 ADO B : 22,1 TB 1 1 11 17 25 2 5 8 12 13 14 18 21 24 3 4 6 7 9 10 15 16 19 20 22 23 TB 2 TB 3 TB 4 Lvl 1 Lvl 2 Lvl 3 Lvl 4
p-ISSN : 2528-3561 e-ISSN : 2541-1934
dibahas  memiliki  sedikit  perbedaan.  Untuk  mendapatkan  total bound terbaik,  pendekatan Breadth  First Search membutuhkan 28 kali perhitungan, sedangkan untuk pendekatan Depth First Search membutuhkan 25 kali perhitungan, dan untuk pendekatan Best First Search membutuhkan 23 kali perhitungan. Walaupun hasil yang didapat pada ketiga pendekatan tersebut sama. Hasil rute terpendek yang didapat dari Travelling Salesman Problem pada studi kasus ini adalah Gudang → Desa Karangmangu → Desa Sidamulya → Desa Peusing → Desa Jalaksana → Gudang atau sebaliknya dengan total jarak 19,7 km.
Breadth  First  Search memerlukan  perhitungan  yang  lebih  lama  dan  banyak  untuk  mencari  total bound terbaik, pendekatan ini lebih cocok apabila ingin mencari berapa kemungkinan rute yang bisa dilalui. Kecepatan Depth First Search tergantung pada letak total bound terbaik berada, apabila secara kebetulan total bound terbaik terletak pada TB pertama maka bisa saja pendekatan ini lebih cepat daripada pendekatan yang  lain  dan  begitu  pun  sebaliknya. Best  First  Search adalah  pendekatan  yang  paling  aman  dan  lebih disarankan karena pendekatan ini yang lebih mengutamakan bound terkecil untuk melakukan perhitungan selanjutnya  yang  bisa  dipastikan  akan  lebih  cepat  dari Breadth  First  Search dan  juga  mempunyai kemungkinan yang lebih besar untuk lebih cepat dari Depth First Search .

## 5. Referensi
[1]   N.  Nurjanah  and  Nabila,  "Pengoptimalan  Rute  dalam  Pendistribusian  Roti  di  PT.  Daisei  Log Indonesia  Hub  Cikarang  Menggunakan  Metode  Travelling  Salesman  Problem  (TSP)  Branch  and Bound," Jurnal Logistik Bisnis, vol. 09, pp. 55-67, 2019.
[2]   Y. D. Prasetyo, "Penyelesaian Travelling Salesman Problem Dengan Algoritma Branch And Bound," Jurnal Mathematics Paedagogic, vol. 1, pp. 162-168, 2017.
[3]   Rismayani  and  Ardimansyah,  "Aplikasi  Berbasis  Mobile  untuk  Pencarian  Rute  Angkutan  Umum Kota Makassar Menggunakan Algoritma Depth First Search," Jurnal Pekommas, vol. 18, pp. 171- 180, 2015.
[4]   Y.  Afero,  "Algoritma  Best  First  Search  Menentukan  Lintasan  Jalur  Terpendek  pada  Kota  Wisata Bukittinggi," Journal Of Information System And Informatics Engineering, vol. 5, pp. 138-145, 2021.
[5]   H. A. Taha, Operations Research: An Introduction , New York: Pearson Pretince Hall, 2007.
[6]   I.  Sutoyo,  "Penerapan  Algoritma  Nearest  Neighbour  untuk  Menyelesaikan  Travelling  Salesman Problem," Paradigma, vol. 20, pp. 101-106, 2018.
[7]   N.  F.  A.  Muzzaki  and  Y.  P.  Astuti,  "Optimasi  Produksi  Gerabah  dengan  Metode  Round  Off  dan Branch and Bound Terhadap UKM Dewi Sri Teracotta," Jurnal MATHunesa, vol. 9, pp. 251-259, 2021.
[8]   Y. N. Firdaus, "Implementasi Algoritma Branch and Bound dalam Penentuan Jumlah Produksi untuk Memaksimalkan Keuntungan," STRING (Satuan Tulisan Riset dan Inovasi Teknologi), vol. 4, pp. 65- 70, 2019.
[9]   M. Mataija, M. R. Segic and F. Kozic, "Solving The Travelling Salesman Problem Using The Branch and Bound Method," Zbornik Veleučilišta u Rijeci, vol. 4, pp. 259-270, 2016.
[10]  C.  Liman,  Desain  dan  Analisis  Algoritma  Breadth  First  Search  sebagai  Metode  Penyelesaian Permasalahan  Pencarian  Cycle  Graf:  Studi  Kasus  SPOJ  284099  -  ADA  and  CYCLE,  Surabaya: Institut Teknologi Sepuluh November, 2018.
[11]  K.  Auliasari,  M.  Kertaningtyas  and  D.  W.  L.  Basuki,  "Optimalisasi  Rute  Distribusi  Produk Menggunakan Metode Traveling Salesman Problem," Jurnal Sains, Teknologi, dan Industri, vol. 16, pp. 15-23, 2018.
[12]  A. Y. Prasetyo, "Penerapan Algoritma Depth First Search (DFS) pada Aplikasi Game Traffic Puzzle," Jurnal Informatika STMIK Tulus Cendikia, vol. 8, pp. 33-41, 2021.
[13]  S. Kusumadewi, Artificial Intelligence (Teknik dan Aplikasinya) , Yogyakarta: Graha Ilmu, 2003.
[14]  R. Apriandi, T. Rismawan and D. M. Midyanti, "Penerapan metode Best First Search (BFS) untuk pencarian  lokasi  spbu  terdekat  menggunakan  arduino  berbasis  android," Jurnal  Coding  Sistem Komputer Untan, vol. 6, pp. 1-11, 2018.
[15]  L.  I.  Liana,  "Implementasi  Algoritma  Best  First  Search  untuk  Aplikasi  Mesin  Pencari  Handphone pada E-Commerse (Apenphone)," Journal of Informatics and Computer Science (JINACS), vol. 2, pp. 67-73, 2020.