Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 2, Juni  (2024), pp. 248-256

## Perhitungan Jarak Dalam Meminimalkan Biaya Perjalanan Menggunakan Algoritma Generate And Test
Padma Mike Putri M Universitas Negeri Padang, Indonesia E-mail: miekemadri90@gmail.com

## Abstract
Generate  and  Test  is  included  in  the  artificial  intelligence  section  where  the  search process must find a solution to the success of a system in producing value. Generate and test is a simple method in the heuristic search process. The way this algorithm works is like  a  combination  of  depth-first  search  and  backtracking  because  the  solution  must  be generated  completely  before  being  tested.  If  the  generation  of  a  solution  is  done systematically  and  follows  the  procedure,  it  will  find  the  solution.  The  problem  in  this research is determining a route that is difficult to detect because it has many paths to get to the final value, so an algorithm is needed to solve this problem so that the path to be taken has a smaller range and is able to manage time and costs. Based on the final results obtained,  3  paths  were  found  that  can  be  used  as  a  reference  in  saving  time  and  costs, including,  path  1  f  (E-F-L-R-U-Z)  =  9+6+13+16+13=57,  path  2.  f  (E-G-M-S-X-Z  = 7+5+ 11+19+12 =54 and path 3. f (E-H-N-T-Y-Z = 5+9+8+14+16=52. This algorithm can be used as a reference in determining travel routes and other measurement cases.
Keywords: heuristic  search,  generate  and  test,  traveling  saleman  problem,  route, alternative path

## Abstrak
Generate and Test termasuk kedalam bagian  artificial intelegence yang mana proses pencarian  harus  menemukan  solusi  keberhasilan  sebuah  system  dalam  menghasilkan nilai. Generate and test termasuk kedalam sebuah metode yang sederhana dalam proses pencarian  heuristic.  Cara  kerja  algoritma  ini  seperti  gabungan    dari  depth-first  search dengan  pelacakan  mundur  (backtracking)  karana  solusi  harus  dibangkitkan  secara lengkap  sebelum  dilakukan  test.Jika  pembangkitan  sebuah  solusi  dikerjakan  secara sistematis dan mengikuti prosedur akan  menghasilkan sebuah   solusinya. Permasalahan pada penelitian ini adalah penentuan rute yang sulit dideteksi karena memiliki jalur yang banyak  untuk  menuju  nilai  akhir  sehingga  dibutuhkan  sebuah  algoritma  dalam menyelesaikan  permasalahan  ini  sehingga  jalur  yang  akan  dilewati  memiliki  jangkauan yang lebih kecil serta mampu memanilisir waktu dan biaya. Berdasarkan hasil akhir yang diperoleh, ditemukan 3 Jalur yang bias dijadikan acuan dalam  pengehematan waktu dan biaya diantaranya , jalur 1. f (E-F-L-R-U-Z ) = 9+6+13+16+13=57, jalur 2. f (E-G-M-S- X-Z)  =  7+5+11+19+12  =54  dan  jalur  3.  f  (E-H-N-T-Y-Z)  =  5+9+8+14+16=52. Algoritma  ini  bisa  dijadikan  acuan  dalam  penentuan  rute  perjalanan  maupun    kasus pengukuran yang lainnya.
Kata Kunci: pencarian heuristik, generate and test, travelling saleman problem, Rute, Jalur alternative.

## 1. Pendahuluan
Pada  prinsipnya  teori  optimasi  matematis  terdiri  dari  tiga  pendekatan,  yaitu  metode klasik, algoritma evolusioner, dan metode hybrid. Pengoptimalan masalah pada dasarnya menentukan berbagai nilai variabel suatu fungsi menjadi maksimum atau minimal dengan memperhatikan  keterbatasan  yang  ada.  Salah  satu  bentuk  optimasi  Konsep  yang  terus berkembang adalah optimasi kombinatorial. Pengoptimalan ini merujuk ke kasus optimasi tertentu yang mengatur semua solusi yang mungkin dan layak bentuk diskrit [1]. Besarnya

## BRAHMANA: Jurnal Penerapan Kecerdasan Buatan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 2, Juni  (2024), pp. 248-256
kebutuhan  manusia  akan  informasi  juga  memicu  perkembangan  komputer  sebagai  alat bantu untuk mempermudah manusia dalam pengolahan data. Dalam pengembangan ilmu pengetahuan dan perkembangannya pada saat ini menjadikan informasi memiliki peranan yang  sangat  penting  dalam  usaha  menciptakan  kemajuan  disemua  bidang  kehidupan manusia.  Dengan  adanya  teknologi  informasi  telah  banyak  dirasakan  kemudahan  dalam mendapatkan informasi yang cepat, tepat dan akurat[2].
Hal  ini  diiringi  juga  dengan  semakin  berkembangnya  Teknologi  Informasi  yang dibutuhkan  oleh  pengguna  sehingga  mengakibatkan  munculnya  suatu  cabang  ilmu  baru dalam  teknologi  informasi,  yaitu  pencarian  informasi  (information  retrieval).  Sejalan dengan  perkembangan  teknologi,  maka  perkembangan  peralatan  juga  ikut  mengambil andil  yang  besar  untuk  mendukung  perkembangan  pertukaran  informasi  yang  semakin hari  semakin  canggih.  Hampir  semua  kecanggihan  teknologi  yang  memberikan kemudahan  kepada  user  dalam  menemukan  apa  yang  diinginkannya.  Salah  satu kemudahan yang diberikan adalah menyediakan fasilitas searching yang digunakan untuk memberikan  kemudahan  mendapatkan  lebih  banyak  informasi  yang  berbentuk  dokumen kebutuhan menjadi sangat penting dengan semakin mudahnya memperoleh informasi dari seluruh  dunia  sebagai  akibat  perkembangan  teknologi  informasi  dan  komunikasi  yang semakin  pesat  [3].  Menurut  penelitian  [4]  Metode  pencarian  heuristik  merupakan  salah satu  metode  yang  umumnya  digunakan  dalam  mencari  lintasan  terpendek,  salah satunya yaitu  metode  Hill  Climbing  di  mana  proses  pengujian  dilakukan  dengan  menggunakan fungsi heuristik. Permasalahan yang umumnya temui adalah pencarian lintasan terpendek untuk  menyelesaikan  masalah  jarak  dapat  di  ubah  menjadi  struktur  graph,  dimana  titik menyatakan  kota  dan  sisi  menyatakan  jalur  yang  menghubungkan  dua  buah  kota.  Dari logika  tersebut  sehingga  dapat  menemukan  lokasi  tujuan  serta  menghemat  biaya perjalanan. Keunggulan dari algoritma ini yaitu semua solusi yang mungkin akan peroleh kemudian diperiksa dari sisi kiri satu persatu, sehingga akan diperoleh solusi dengan hasil yang optimal.
Menurut  penelitian  [5]  lometer  [5].  Penentuan  rute  distribusi  untuk  meminimalkan biaya  menggunakan  saving  matrix,  telah  diterap-  kan  di  berbagai  contoh  kasus  untuk berbagai  sektor.  Penentuan  jadwal  pengiriman  dan  rute  yang  akan  dilewati  akan berpengaruh pada total jarak tempuh yang juga akan berpengaruh pada waktu tempuh dan biaya  transportasi  pada  proses  pengiriman.  Heuristik  adalah  teknik  yang  meningkatkan efisiensi  dalam  proses  pencarian,  namun  pada  akhirnya  biaya  kelengkapan.  Untuk mengukur kinerja metode pencarian, ada empat kriteria yang dapat digunakan (Coppin, 2004):
a) Kelengkapan: apakah metode menjamin ditemukannya  solusi jika solusi tersebut ada;
b) Kompleksitas waktu : berapa lama waktu yang dibutuhkan;
c) Kompleksitas ruang : berapa banyak memori yang dibutuhkan;
d) Optimalitas:  apakah  metode  menjamin  menemukan  solusi  terbaik  jika adabeberapa solusi berbeda [6].
Metode  Generate  and  Test  adalah  sebuah  metode  dari  beberapa  konsep  pencarian heuristik.  Menurut  Kusumadewi  (2003),  pada  prinsipnya  metode  ini  merupakan penggabungan  antara  depth-first  search  dengan  pelacakan  mundur  (backtracking)  yaitu bergerak ke belakang  menuju pada suatu keadaan awal. Nilai pengujian berupa jawaban „ya‟ atau „tidak‟ [7] [8].
Algoritma yang dihasilkan pada proses pengujian diantaranya:
1. Menghasilkan solusi yang mungkin (menghasilkan titik tertentu atau jalur tertentu dari awal negara).
2. Uji  apakah  simpul  tersebut  benar-benar  solusi  dengan  membandingkan  simpul tersebut atau simpul akhir dari a jalur yang dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi langkah pertama [9].

## BRAHMANA: Jurnal Penerapan Kecerdasan Buatan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 2, Juni  (2024), pp. 248-256
Di bawah ini adalah contoh kasus Generate and test dalam kasus Salesman Program. penjelasan  tentang  kombinasi  4  kota  dengan  masingmasing  kombinasi  diantaranya:  a) Tukar  Kota  1,2  (menukar  urutan  posisi  kota  ke-1  dengan  kota  ke-2).  b)  Tukar  Kota (menukar  urutan  posisi  kota  ke-2  dengan  kota  ke-3).  c)  Tukar  Kota  (tukar  urutan  posisi kota ke-3 dengan kota ke-4). d) Tukar Kota (menukar urutan posisi kota ke-4 dengan kota ke-1  e)  Tukar  Kota  2,4  (menukar  urutan  posisi  kota  ke-2  dengan  kota  ke-4).  f)  Tukar Kota1,3 (menukar urutan posisi kota ke-1 dengan kota ke-3) [10].
Gambar 1. Panjang Lintasan

## 2. Metodologi Penelitian
Dalam  menyelesaikan  hasil  penelitian  ini  diperlukan  sebuah  metodologi  penelitian agar  hasil  penelitian  ini  lebih  terarah.  Untuk  itu  diperlukan  proses  sistematis  agar penenelitian ini menhhasilkan sebuah nilai. Langkah langkah dalam penelitian ini yaitu:
Gambar 2. Metodologi Penelitian

## 3. Hasil Dan Pembahasan
A. Analisa Pembahasan
Proses  penyelesaian General  And  Test (  Pembangkitan  dan  pengujian)  merupakan proses yang paling sederhana pada heuristic. Prinsip kerja pada metode ini menggunakan algoritma depth first search dengan system pelacakan mundur dengan ketentuan pencarian solusi  harus  lengkap  sebelum    dilakukan  pengujian test. Dalam  proses  pencarian pembangkitan  solusi  harus  dilakukan  secara  sistematis  maka  akan  mememukan  solusi namun jika proses permasalahan nya luas maka akan menemukan solusi yang lama serta membutuhkan waktu nya sangat panjang dalam menemukan solusi. Proses kerja penyelesaian Generate And Test
1. Bangkitkan kemungkinan solusi
2. Uji apakah solusi tersebut sesuai dengn kriteria yang digunakan
3. Jika  solusi  ditemukan  berhenti,  namun  jika  belum  ditemukan  solusi  ulangi langkah sampai menemukan solusi
Dibawah ini merupakan Sebuah Genere And test dalam pencarian rute terkecil
Gambar 3. Rute awal
Gambar 3 menjelaskan bahwa diketahui 21 Kota  yaitu, E F G H I J K L M N O P Q R S  T  U  V  W  X  Y  Z  jarak  masing  masing  kota  berbeda  beda  dapat  dilihat  pada  gambar diatas.  Pada  gambar  di  atas  tanda  panah  berfungsi  sebagai  petunjuk  arah    yang  bias dilewati.  Seseorang  ini  menjelajahi  suatu  kota  dengan  rute  Awal  kota  E  dan  kota  yang terakhir yang dikunjungi yaitu Kota Z. Permasalahan pada kasus ini yaitu jalur mana yang bias dilewati agar menghemat biaya tranportasi dalam perjalanan. Diketahui Keadaan awal = E Goal               = Z Solusi yang akan dicari yaitu  jalur dari kota A ke kota E, untuk mengelesaikan kasus ini menggunakan algoritma DFS. Untuk memperkecil biaya perjalanan dapat diselesaikan dengan  cara  menyelesaikan jalur  terpendek,  karena  yang  akan  diseselaikan jalur  terkecil maka  proses  yang  akan  dilaksanakan  yaitu  jarak  terpendek  dengan  melakukan  fungsi heuristic sebagai petunjuk arah yang akan dicari.

## B. Proses Penyelesaian
Iterasi -1
1. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang dilewati (E-F-L-R- U-Z )
= 9+6+13+16+13. f (E-F-L-R-U-Z ) = 9+6+13+16+13=57. Uji kriteria yang digunakan Jalur  dilewati  (E-F-L-R-U-Z  )  =  9+6+13+16+13=57  merupakan  jalur  pertama maka jalur pertama yang disimpan yaitu f (E-F-L-R-U-Z ) = 9+6+13+16+13=57
2. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang dilewati E-F-L-R- U-W-Z =  9+6+13+16+10+5.
f (E-F-L-R-U-W-Z) = 9+6+13+16+10+5=59.

## BRAHMANA: Jurnal Penerapan Kecerdasan Buatan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 2, Juni  (2024), pp. 248-256
Jalur dilewati (E-F-L-R-U-Z ) = 9+6+13+16+13=57 merupakan jalur selanjutnya jalur yang disimpan yaitu f (E-F-L-R-U-Z ) = 9+6+13+16+13=57 < f (E-F-L-R- U-W-Z) = 9+6+13+16+10+5=59.
3. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang dilewati E-F-L-R- U-W-X-Z =  9+6+13+16+10+9+12.
f (E-F-L-R-U-W-Z) = 9+6+13+16+10+9+12 =75. Jalur  dilewati  (E-F-L-R-U-Z  )  =  9+6+13+16+10+9+12  =75  jalur  selanjutnya maka jalur yang disimpan yaitu f (E-F-L-R-U-Z ) = 9+6+13+16+13=57 < f (E-F- L-R-U-W-X-Z)=  9+6+13+16+10+9+12 =75.
4. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang dilewati E-F-G-M- S-X-Z =  9+7+5+11+19+12.
f (E-F-G-M-S-X-Z) =  9+7+5+11+19+12 =63. Jalur dilewati E-F-G-M-S-X-Z =  9+7+5+11+19+12 =63. Jalur selanjutnya  yang disimpan yaitu f (E-F-L-R-U-Z ) = 9+6+13+16+13=57 f (E-F-L-R-U-W-X-Z< f (E-F-G-M-S-X-Z) =  9+7+5+11+19+12 =63.
5. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang dilewati E-F-G-H- N-T-Y-Z =  9+7+8+9+8+14+16.
f (E-F-G-H-N-T-Y-Z =  9+7+8+9+8+14+16) =71. Jalur dilewati E-F-G-M-S-X-Z =  9+7+5+11+19+12 =63. Jalur yang disimpan selanjutnya yaitu f f (E-F-L-R-U-Z ) = 9+6+13+16+13=57 < f (E-F-G-H-N-T-Y-Z =  9+7+8+9+8+14+16) =71.
6. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang dilewati E-F-G-H-I- P-U-Y-Z = 9+7+8+5+10+13+15+16.
f E-F-G-H-I-P-U-Y-Z = 9+7+8+5+10+13+15+16=83. Jalur dilewati E-F-G-M-S-X-Z =  9+7+5+11+19+12 =63. jalur selanjutnya yang disimpan yaitu f f (E-F-L-R-U-Z ) = 9+6+13+16+13=57< f E-F-G-H-I-P-U-Y-Z = 9+7+8+5+10+13+15+16=83.
7. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang E-F-G-H-I-J-Q-U- Y-Z= 9+7+8+5+10+12+14+15+16.
E-F-G-H-I-J-Q-U-Y-Z= 9+7+8+5+10+12+14+15+16=96. Jalur dilewati E-F-G-H-I-J-Q-U-Y-Z= 9+7+8+5+10+12+14+15+16=96. Jalur  selanjutnya  yang  disimpan  disimpan  yaitu f (E-F-L-R-U-Z  )  = 9+6+13+16+13=57 < f ( E-F-G-H-I-J-Q-U-Y-Z= 9+7+8+5+10+12+14+15+16=96.
8. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang E-F-G-H-I-J-K-Q-
U-Y-Z =9+7+8+5+10+12+7+14+15+16.
E-F-G-H-I-J-K-Q-U-Y-Z =9+7+8+5+10+12+7+14+15+16=112. Jalur dilewati E-F-G-M-S-X-Z =  9+7+5+11+19+12 =63. jalur selanjutnya yang disimpan yaitu f (E-F-L-R-U-Z ) = 9+6+13+16+13=57< f
(E-F-G-H-I-J-K-Q-U-Y-Z =9+7+8+5+10+12+7+14+15+16=112.
9. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  yang  E-G-M-S-X-Z  = 7+5+11+19+12.
E-G-M-S-X-Z = 7+5+11+19+12 =54. Jalur dilewati E-G-M-S-X-Z = 7+5+11+19+12 =54. selanjutnya Jalur yang disimpan yaitu f (E-G-M-S-X-Z = 7+5+11+19+12 =54 < f (E-F-L-R-U-Z ) = 9+6+13+16+13=57.
10. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang E-G-H-N-T-Y-Z = 7+8+9+8+14+16. E-G-H-N-T-Y-Z = 7+8+9+8+14+16 =62. Jalur dilewati E-G-H-N-T-Y-Z = 7+8+9+8+14+16 =62. selanjutnya  maka  jalur  yang  disimpan  yaitu f (E-G-M-S-X-Z  =  7+5+11+19+12 =54 < f( E-G-H-N-T-Y-Z = 7+8+9+8+14+16 =62.

## BRAHMANA: Jurnal Penerapan Kecerdasan Buatan
11. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang A-G-H-I-P-U-Y-Z =7+8+9+10+13+5+6. A-G-H-I-P-U-Y-Z =7+8+9+10+13+5+6= 68. Jalur dilewati A-G-H-I-P-U-Y-Z =7+8+9+10+13+5+6= 68. akan jalur selanjutnya maka jalur pertama yang disimpan yaitu f (E-G-M-S-X-Z = 7+5+11+19+12 =54 < f( A-G-H-I-P-U-Y-Z =7+8+9+10+13+5+6= 68. 12. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang E-G-H-I-P-U-Y-Z =7+8+9+10+12+14+15+16. E-G-H-I-P-U-Y-Z =7+8+9+10+12+14+15+16=91. Jalur  dilewati  E-G-H-I-P-U-Y-Z  =7+8+9+10+12+14+15+16=91akan  jalur selanjutnya jalur yang disimpan yaitu f (E-G-M-S-X-Z = 7+5+11+19+12 =54 < f( E-G-H-I-P-U-Y-Z =7+8+9+10+12+14+15+16=91. 13. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang E-G-H-I-J-K-Q-U- Y-Z = 7+8+9+10+12+7+14+15+16. E-G-H-I-J-K-Q-U-Y-Z = 7+8+9+10+12+7+14+15+16=98. Jalur  dilewati  E-G-H-I-J-K-Q-U-Y-Z  =  7+8+9+10+12+7+14+15+16=98  jalur selanjutnya  maka  jalur  yang  disimpan  yaitu f (E-G-M-S-X-Z  =  7+5+11+19+12 =54 < f( E-G-H-I-J-K-Q-U-Y-Z = 7+8+9+10+12+7+14+15+16=98. 14. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  yang  E-H-N-T-Y-Z  = 5+9+8+14+16=52. E-H-N-T-Y-Z = 5+9+8+14+16=52. Jalur dilewati E-H-N-T-Y-Z = 5+9+8+14+16=52. selanjutnya  maka  jalur    yang  disimpan  yaitu f (E-H-N-T-Y-Z  = 5+9+8+14+16=52 < f (E-G-M-S-X-Z = 7+5+11+19+12 =54. 15. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  yang  E-H-I-P-U-Y-Z  = 5+5+10+13+15+16. E-H-I-P-U-Y-Z = 5+5+10+13+15+16 =64. Jalur dilewati E-H-I-P-U-Y-Z = 5+5+10+13+15+16 =64. jalur  selanjutnya  maka  jalur  yang  disimpan  yaitu f (E-H-N-T-Y-Z  = 5+9+8+14+16=52 < f (E-H-I-P-U-Y-Z = 5+5+10+13+15+16 =64. 16. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang E-H-I-J-Q-V-Y-Z = 5+5+10+12+4+16+15. E-H-I-J-Q-V-Y-Z = 5+5+10+12+4+16+15=67. Jalur  dilewati    E-H-I-J-Q-V-Y-Z  =  5+5+10+12+4+16+15=67  selanjutnya  maka jalur yang disimpan yaitu f (E-H-N-T-Y-Z = 5+9+8+14+16=52 < f ( E-H-I-J-Q-V-Y-Z = 5+5+10+12+4+16+15=67. 17. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang E-H-I-J-K-Q-V-Y- Z = 5+5+10+12+17+14+15+16.
E-H-I-J-K-Q-V-Y-Z = 5+5+10+12+17+14+15+16=84.
Jalur dilewati E-H-I-J-K-Q-V-Y-Z  = 5+5+10+12+17+14+15+16=84jalur
selanjutnya maka jalur  yang disimpan yaitu f (E-H-N-T-Y-Z = 5+9+8+14+16=52
< f (E-H-I-J-K-Q-V-Y-Z <5+5+10+12+17+14+15+16=84.
18. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  yang  E-I-P-U-Y-Z= 8+10+13+15+15=62. E-I-P-U-Y-Z= 8+10+13+15+15=62. Jalur  dilewati  E-I-P-U-Y-Z=  8+10+13+15+15=62  jalur  selanjutnya  maka  jalur yang disimpan yaitu f (E-H-I-J-K-Q-V-Y-Z < E-I-P-U-Y-Z=
8+10+13+15+15=62.
19. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  yang    E-I-J-Q-U-Y  –Z =8+10+12+14+15+16. E-I-J-Q-U-Y –Z =8+10+12+14+15+16=75. Jalur dilewati E-I-J-Q-U-Y –Z =8+10+12+14+15+16=75. jalur selanjutnya maka jalur yang disimpan yaitu f (E-H-I-J-K-Q-V-Y-Z <

## BRAHMANA: Jurnal Penerapan Kecerdasan Buatan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 2, Juni  (2024), pp. 248-256
E-I-J-Q-U-Y –Z =8+10+12+14+15+16=75.
20. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  E-I-J-K-Q-U-Y-Z  = 8+10+12+7+14+15+16.
E-I-J-K-Q-U-Y-Z = 8+10+12+7+14+15+16=82.
Jalur  dilewati  E-I-J-K-Q-U-Y-Z  =  8+10+12+7+14+15+16=82  jalur  selanjutnya maka  jalur  yang  disimpan  yaitu f (E-H-I-J-K-Q-V-Y-Z  <  E-I-J-K-Q-U-Y-Z  = 8+10+12+7+14+15+16=82.

## C. Hasil Pencarian Rute
Setelah dihitung dari 20 jalur maka diperoleh 3 jalur  yang bisadijadikan ajuan dalam perjalanan diantaranya:
1. Hitung  semua nilai menggunakan algoritma DFS. Jalur yang dilewati (E-F-L-R- U-Z ) = 9+6+13+16+13 f (E-F-L-R-U-Z ) = 9+6+13+16+13=57 Uji kriteria yang digunakan Jalur  dilewati  (E-F-L-R-U-Z  )  =  9+6+13+16+13=57  merupakan  jalur  pertama maka jalur pertama yang disimpan yaitu f (E-F-L-R-U-Z ) = 9+6+13+16+13=57
Gambar 4. Hasil Rute 1
2. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  yang  E-G-M-S-X-Z  = 7+5+11+19+12 E-G-M-S-X-Z = 7+5+11+19+12 =54 Jalur dilewati E-G-M-S-X-Z = 7+5+11+19+12 =54 selanjutnya Jalur yang disimpan yaitu f (E-G-M-S-X-Z = 7+5+11+19+12 =54 < f (E-F-L-R-U-Z ) = 9+6+13+16+13=57
Gambar 5. Hasil Rute 2
3. Hitung    semua  nilai  menggunakan  algoritma  DFS.  Jalur  yang  E-H-N-T-Y-Z  = 5+9+8+14+16=52 E-H-N-T-Y-Z = 5+9+8+14+16=52 Jalur dilewati E-H-N-T-Y-Z = 5+9+8+14+16=52 selanjutnya  maka  jalur    yang  disimpan  yaitu f (E-H-N-T-Y-Z  = 5+9+8+14+16=52 < f (E-G-M-S-X-Z = 7+5+11+19+12 =54
Gambar 6. Hasil Rute 3
Hasil  akhir  yang  diperoleh  dari  masing  masing  pencarian  ditemukan  3  Rute  terpendek yang  bisa  acuan  dalam  mencari  solosi  jalur  1 f (E-F-L-R-U-Z  )  =  9+6+13+16+13=57, jalur  2. f (E-G-M-S-X-Z  =  7+5+11+19+12  =54  dan  jalur  3. f (E-H-N-T-Y-Z  = 5+9+8+14+16=52.  Algoritma  ini  bisa  dijadikan  acuan  dalam  penentuan  rute  perjalanan maupu kasus pengukuran yang lainnya.

## 4. Kesimpulan
Berdasarkan  dari  pembahasan  yang  telah  diuraikan,  maka  ditarik  kesimpulan  bahwa algoritma  generate  and  test  mampu  di  implementasikan  pada  penentuan  rute  terpendek karena  dapat  mencari  solusi  terkecil  sehingga  dapat  meminilisir  biaya  dan  waktu  dalam menemukan  solusi  Akhir.  Terdapat  3  jalur  rute    yang  bisa    dijadikan  acuan  dalam pengehematan  waktu  dan  biaya  diantaranya  ,  jalur  1 f (E-F-L-R-U-Z  )  = 9+6+13+16+13=57, jalur 2. f (E-G-M-S-X-Z = 7+5+11+19+12 =54 dan jalur 3. f (E-H-N- T-Y-Z = 5+9+8+14+16=52. Penelitian ini bisa dijadikan sebagai panduan dalam mencari solusi  dalam  penentuan  rute  terkecil  sehingga  dan  dapat  di  implemetasikan  untuk kehidupan sehari hari.

## Daftar Pustaka
[1] A. W. Aranski,  “Optimization of The Smallest  Road Using The Traveling Salesman  Problem  (TSP)  Method,” Int.  J.  Inf.  Syst.  Technol.  Akreditasi , vol. 6, no. 158, pp. 159–166, 2022.
[2] S.  B.  Christian  and  R.  Fajriah,  “Aplikasi  Sistem  Informasi  Inventaris Perusahaan Untuk Mendukung Manajemen Procurement,” JUST IT  J. Sist. Informasi,  Teknol.  Inf.  dan  Komput. ,  vol.  11,  no.  1,  p.  62,  2020,  doi: 10.24853/justit.11.1.62-71.
[3] W.  L.  Putri  and  N.  Jarti,  “Algoritma  General  and  Test  Menggunakan Metode  Depth  First  Search  Dalam  Penentuan  Jalur  Rute  Terpendek,” Brahmana J. Penerapan Kecerdasan … , vol. 4, no. 2, pp. 154–163, 2023.
[4] E.  V.  Dangkua,  V.  Gunawan,  and  K.  Adi,  “Penerapan  Metode  Hill Climbing  Pada  Sistem  Informasi  Geografis  Untuk  Mencari  Lintasan Terpendek,” J.  Sist.  Inf.  Bisnis ,  vol.  5,  no.  1,  pp.  19–25,  2015,  doi: 10.21456/vol5iss1pp19-25.
[5] D.  Mahrizon,  “Meminimalkan  Biaya  Transportasi  Penentuan  Rute Terpendek Pengiriman Barang Menggunakan Metode Generate And Test,” vol. 8, no. 1, pp. 23–28, 2023.
[6] P.  M.  P.  M,  “Search  Optimization  of  The  Shortest  Route  Using  the Generate And Test Algorithm,” Int. J. Inf. Syst. Technol. , vol. 6, no. 1, pp. 25–32, 2022.
[7] R.  Rahmadi,  “Implementasi  Metode  Generate  and  Test  Dalam Menyelesaikan  Travelling  Salesman  Problem  Menggunakan  Robot Bersensor,” Semin. Nas. , vol. 2010, no. Snati, pp. 29–34, 2010.
[8] A.  W.  Aranski,  “Depth  First  Search  Algorithm  In  Solving  the  Shortest Route  Using  the  Concept  of  Generate  and  Test,” IJISTECH  (International J. Inf. Syst. … , vol. 6, no. 158, pp. 353–360, 2022.
[9] S. Silvilestari, “Utilization of The Generate and Test Algorithm In Shortest Route  Search  Case,” IJISTECH  (International  J.  Inf.  Syst.  … ,  vol.  5,  no. 158, pp. 541–547, 2022.
[10]  A.  Maulana,  “Pemanfaatan  Algoritma  Generate  and  Test  Dalam  Kasus Travelling Salesman Problem Pencarian Jalur Terpendek,” J. Sist. Komput. dan Inform. , vol. 3, no. 2, p. 128, 2021, doi: 10.30865/json.v3i2.3617.