Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 438 – 444 DOI : https://doi.org/10.36987/jpms.v8i2.3399

## TRAVELLING SALESMAN PROBLEM UNTUK OPTIMASI RUTE TERPENDEK MENGGUNAKAN PROGRAM DINAMIK

## TRAVELLING SALESMAN PROBLEM FOR OPTIMIZATION OF THE SHORTEST ROUTE USING DYNAMIC PROGRAM
JOY PUTRA SAGALA 1 , RANI F SINAGA 2 , LOLYTA D SIMBOLON 3
1 Program Studi  Matematika, Universitas HKBP Nommensen Pematangsiantar Jalan Sangnawaluh No. 4, Pematangsiantar email: sagalajoy2804@gmail.com.
2 Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas HKBP Nommensen Pematangsiantar Jalan Sangnawaluh No. 4, Pematangsiantar email: sinagaranii@gmail.com.
3 Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas HKBP Nommensen Pematangsiantar Jalan Sangnawaluh No. 4, Pematangsiantar email: lolyta.damora.ld@gmail.com.

## Abstrak
Tujuan dari penelitian ini adalah untuk menentukan rute dan biaya pick up barang yang optimal pada perusahaan  logistik  di  Pematangsiantar  dimana  ada  6  titik  rute  yang  akan  diteliti,  menjadikan  hasil penelitian sebagai pengambilan kebijakan perusahaan dalam menentukan rute yang akan digunakan. Metode penelitian yang digunakan peneliti mengunakan metode kuantitatif, analisis data menggunakan analisis Travelling  Salesman  Problem menggunakan  program  dinamik  dengan  model  matriks. Berdasarkan  hasil  penelitian  diketahui  bahwa  rute  terpendek  yang  didapat  yaitu  dimulai  dari  Siantar Martoba, kemudian ke Cabang Siantar, kemudian ke Siantar Selatan, kemudian ke Siantar Sitalasari, kemudian ke Siantar Marimbun, kemudian ke Siantar Barat, dan kembali ke Siantar Martoba dengan jarak sebesar 23,5 kilometer. Sedangkan waktu tercepat yang diperoleh untuk melewati semua titik yaitu 47 menit. Maka berdasarkan hasil optimal rute terpendek yang telah di dapat yaitu 23,5 km, maka bahan bakar yang digunakan  adalah sebanyak 2,9 liter solar dengan biaya sebesar Rp.19.720.
Kata kunci: Rute terpendek, Traveling Salesman Problem, Program dinamik

## Abstract
The purpose of this research is to determine the optimal route and cost of picking up goods for logistics companies in Pematangsiantar where there are 6 route points to be researched, making the research results as company policy making in determining the route to be used. The research method used by researchers  using  quantitative  methods,  data  analysis  using  Traveling  Salesman  Problem   using dynamic programs with matrix models. Based on the results of the study, it is known that the shortest route obtained is starting from Siantar Martoba, then to Siantar Branch, then to Siantar Selatan, then to Siantar Sitalasari, then to Siantar Marimbun, then to Siantar Barat, and back to Siantar Martoba with a distance of 23.5 kilometers. While the fastest time obtained to pass all points is 47 minutes. So based on the optimal results, the shortest route that has been obtained is 23.5 km, then the fuel used is 2.9 liters of diesel at a cost of Rp. 19,720.
Keywords: Shortest route, Traveling Salesman Problem, Dynamic Program

## Pendahuluan
Kegiatan untuk mengirimkan barang dari suatu lokasi ke lokasi lain dalam sebuah tempat tentunya memerlukan efisiensi waktu dan biaya yang baik. Efisiensi  yang baik adalah permasalahan optimasi, dimana  harus  adanya  penentuan  akan  pemilihan  nilai  maksimum  atau  minimum  untuk  kasus  yang bersangkutan.
Travelling  Salesman  Problem (TSP)  adalah  permasalahan  umum  dalam  optimasi  kombinatorial dimana seorang salesman harus mengujungi sejumlah N kota, disyartakan setiap kota hanya dikunjungi sekali. Salesman ini harus memilih rute sehingga jarak total yang dia tempuh minimum  [1]. Traveling Salesman  Problem (TSP)  diilustrasikan  sebagai  perjalanan  salesman  untuk  menentukan  jalan  yang ditempuh dari suatu simpul untuk melewati semua simpul dan kembali kesimpul awal, dengan ketentuan setiap  simpul  hanya  boleh  dilewati  dalam  satu  kali  perjalanan  [2].  Penentuan  lintasan  dan meminimumkan  biaya  merupakan  salah  satu  masalah  yang  dihadapi  dalam  perusahaan.  Penentuan
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 438 – 444 DOI : https://doi.org/10.36987/jpms.v8i2.3399
lintasan  terpendek  pada Traveling  Salesman  Problem (TSP)  adalah  salah  satu  masalah  dari  graph, bagaimana  membentuk  sebuah  sirkuit  minimum.  Bobot  pada  sisi  yang  menghubungkan  sepasang simpul merepresentasikan waktu, biaya, dan jarak. Banyak penelitian telah mengembangkan algoritma untuk menyelesaikan masalah Traveling Salesman Problem (TSP). Traveling Salesman Problem (TSP) dapat dengan mudah diubah dalam bentuk network problem dengan  formulasi  yang  serupa  dengan  model  rute  terpendek  [3].  Konsumen  yang  dikunjungi diidentifikasikan sebagai simpul-simpul (node) dari jaringan.  Persoalan Travelling Salesman Problem (TSP)  adalah  persoalan  optimasi  yang  dinyatakan  sebagai  mencari  rute  perjalanan  termurah  untuk mengunjungi node (konsumen), dimana setiap konsumen dikunjungi secara pasti satu kali.
Pada persoalan TSP ini, jika setiap simpul mempunyai sisi ke simpul  yang lain, maka graf yang merepresentasikannya  adalah  graf  lengkap  berbobot.  Pada  sembarang  graf  lengkap  dengan 𝑛 buah simpul (𝑚 > 2) ,  jumlah  sirkuit  hamilton  yang  berbeda  adalah (𝑛−1) 2 ! .  Rumus  ini  dihasilkan  dari kenyataan  bahwa  dimulai  dari  sembarang  simpul  dipunyai 𝑛 − 1 buah  sisi  untuk  dipilih  dari  simpul pertama 𝑛 − 2 sisi dari simpul kedua, 𝑛 = 3 dari simpul ketiga, dan seterusnya. Ini adalah pilihan yang independen,  sehingga  dapat  diperoleh (𝑛 − 1)! pilihan.  Jumlah  itu  harus  dibagi  2,  karena  tiap  sirkuit Hamilton terhitung 2 kali, sehingga semuanya ada (𝑛−1) 2 ! buah sirkuit hamilton.
Berdasarkan arah dan bobot pada sisi suatu graf , masalah penentuan lintasan terpendek pada TSP dapat dibedakan menjadi 3 yaitu:
1. TSP euclidean merupakan masalah penentuan lintasan terpendek pada 𝑹 𝒏 . 2. TSP simetris merupakan jenis graf tidak berarah tetapi mempunyai bobot atau bobot dari simpul 𝑖 ke simpul 𝑗 sama dengan bobot dari simpul 𝑗 ke simpul 𝑖 . 3. TSP asimetris merupakan jenis graf berarah dan berbobot atau bobot dari simpul 𝑖 ke simpul 𝑗 tidak sama dengan jarak dari simpul 𝑗 ke simpul  . Dimana pada penelitian ini TSP yang akan dibahas adalah TSP asimetris .
Program  dinamik  adalah  salah  satu  teknik  matematika  yang  digunakan  untuk  mengoptimalkan proses pengambilan keputusan secara bertahap sedemikian rupa sehingga solusi dari persoalan dapat dipandang dari serangkaian ketetapan yang saling berkaitan [4]. Akan tetapi program dinamik adalah suatu  tipe  pendekatan  umum  dalam  pemecahan  masalah  dan  persamaan-persamaan  tertentu  yang digunakan harus dibuat sesuai dengan situasi yang sifatnya individual [5]. Dalam teknik ini, keputusan yang  menyangkut  suatu  persoalan  dioptimalkan  secara  bertahap.  Jadi,  inti  dari  teknik  insi  ialah membagi satu persoalan atas beberapa bagian persoalan yang disebut tahap, kemudian memecahkan tiap tahap dengan mengoptimalkan keputusan atas tiap tahap sampai seluruh persoalan terpecahkan.
Langkah penyelesaian program dinamik perhitungan rekursif maju dimulai dari iterasi ke-1 sampai iterasi  ke- 𝑛 ,  dan  penyelesaian  program  dinamik  perhitungan  rekursif  mundur  yaitu  dari  iterasi  ke- 𝑛 sampai  iterasi  ke-1.  Aplikasi  program  dinamik  banyak  digunakan  untuk  menyelesaikan  masalah optimasi,  pada  penelitian  ini  akan  dibahas  pengggunaan  program  dinamik  dalam  menentukan  rute terpendek pada permasalahan Traveling Salesman Problem (TSP) dengan perhitungan rekursif maju. Salah satu perusahaan logistik di Pematangsiantar memiliki beberapa cabang yang dibagi pada 6 dari 8 kecamatan yang ada di pematangsiantar yaitu Siantar Barat, Siantar Marimbun, Siantar Martoba, Siantar Selatan, Siantar Sitalasari, Siantar Timur.

## Metode Penelitian
Contoh penerapan program dinamik pada permasalahan lintasan terpendek, misalkan suatu hari diadakan perjalanan ke suatu kota ke arah barat. Perjalanan berantai merupakan satu - satunya cara yang  ada  pada  transportasi  umum  untuk  mengadakan  perjalanan  dari  Timur  menuju  ke  arah  Barat. Pada peta digambarkan jalur perjalanan yang ada. Dari peta tersebut diketahui juga bermacam - macam jalur perjalanan berantai yang ada seperti pada gambar berikut.
Dengan  menggunakan  pendekatan  program  dinamik  pada  masalah  ini  hanya  tedapat  3 kemungkinan  lintasan  yang  harus  dilalui  dari  simpul  1  ke  simpul  10  yaitu  melalui  simpul  2,  3  dan  4.
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 438 – 444 DOI : https://doi.org/10.36987/jpms.v8i2.3399
Misalkan bobot minimum dari simpul 2 ke 10 dengan S 2 , bobot minimum dari simpul 3 ke 10 dengan S 3 dan bobot minimum dari simpul 4 ke 10 dengan S 4 . Oleh karena itu:
𝑆 1 = 𝑚𝑖𝑛 [ 2 + 𝑆 2 5 + 𝑆 3 1 + 𝑆 4 ]
di mana S 1 merupakan bobot minimum dari simpul 1 ke 10. Karena nilai S 2 , S 3 dan S 4 tidak diketahui pada awalnya, maka nilai S 2 dapat dihitung jika diketahui nilai S 5 dan S 6 (nilai minimum dari simpul 5 dan 6 ke simpul 10), oleh karena itu nilai S 2 , S 3 , dan S 4 sebagai berikut:
𝑆 2 = 𝑚𝑖𝑛 [ 10 + 𝑆 5 12 + 𝑆 6 ] 𝑆 3 = 𝑚𝑖𝑛 [ 5 + 𝑆 5 10 + 𝑆 6 7 + 𝑆 7 ] 𝑆 4 = 𝑚𝑖𝑛 [ 15 + 𝑆 6 13 + 𝑆 7 ]
Nilai S 5 , S 6 , dan S 7 bergantung pada S 8 dan S 9 . Pada simpul 8 dan 9 lintasan menuju simpul 10 hanya terdapat satu jalan, maka nilai S 8 dan S 9 diketahui. Dengan bekerja mundur dari simpul 8 dan 9 ke simpul 1, berikut beberapa perhitungan yang diperlukan:
𝑆 8 = 1, 𝑆 9 = 4
𝑆 5 = 𝑚𝑖𝑛 [ 7 + 𝑆 8 5 + 𝑆 9 ] = 𝑚𝑖𝑛 [ 8 9 ] = 8 𝑆 6 = 𝑚𝑖𝑛 [ 3 + 𝑆 8 4 + 𝑆 9 ] = 𝑚𝑖𝑛 [ 4 8 ] = 4 𝑆 7 = 𝑚𝑖𝑛 [ 7 + 𝑆 8 1 + 𝑆 9 ] = 𝑚𝑖𝑛 [ 8 5 ] = 5 𝑆 2 = 𝑚𝑖𝑛 [ 10 + 𝑆 5 12 + 𝑆 6 ] = 𝑚𝑖𝑛 [ 18 16 ] = 16
𝑆 3 = 𝑚𝑖𝑛 [ 5 + 𝑆 5 10 + 𝑆 6 7 + 𝑆 7 ] = 𝑚𝑖𝑛 [ 13 14 12 ] = 12
𝑆 4 = 𝑚𝑖𝑛 [ 15 + 𝑆 6 13 + 𝑆 7 ] = 𝑚𝑖𝑛 [ 19 18 ] = 18
𝑆 1 = 𝑚𝑖𝑛 [ 2 + 𝑆 2 5 + 𝑆 3 1 + 𝑆 4 ] = 𝑚𝑖𝑛 [ 18 17 19 ] = 17
Sehingga diperoleh lintasan terpendek dari simpul 1 ke simpul 10 atau dari timur ke barat adalah 1→3→7→9→10 dengan bobot minimum yaitu 17.
Penyelesaian  masalah  perjalanan  salesman  menggunakan  program  dinamik  dimulai  dengan meng input jumlah simpul dari graf dimisalkan sebagai 𝑁 dan bobot sisi dari simpul 𝑖 ke simpul 𝑗 . Jika ditentukan 1 sebagai simpul awal, maka penentuan lintasan terpendek menggunakan program dinamik rekursif maju yaitu dari iterasi ke-1 sampai iterasi ke-( 𝑁 = 1). Diberikan 𝑁 𝑗 = {2,3, . . . , 𝑗 = 1, 𝑗 + 1, . . . 𝑁} dan 𝑆 adalah  himpunan  bagian  dari 𝑁 𝑗 yang  berisikan 𝑖 anggota. Didefinsikan fungsi nilai optimal 𝑓 𝑖 (𝑗, 𝑆) sebagai panjang lintasan terpendek dari kota 1 ke kota 𝑗 melalui  himpunan 𝑖 kota-kota  perantara 𝑆 (  variabel 𝑖 menunjukkan  jumlah  kota  pada 𝑆 )  dan 𝑑 𝑖𝑗 menyatakan jarak ( atau waktu tempuh, biaya dan sebagainya ) dari simpul 𝑖 ke simpul 𝑗 . Maka langkah- langkah penyelsaian TSP dengan program dinamik rekursif maju adalah sebagai berikut :
1. Tentukan  jarak/waktu  terpendek  dari  simpul  1  ke  simpul 𝑗 tanpa  melalui  simpul  lain  dengan persamaan:
𝑓 0 (𝑗, _) = 𝑑 1𝑗 2. Hitung 𝑓(𝑗, 𝑆) untuk |𝑆| = 1 kemudian  dapat  diperoleh  untuk |𝑆| = 2 sampai |𝑆| = 𝑁 − 2 ,  dengan persamaan :
𝑓 𝑖 (𝑗, 𝑆) = min 𝑘∈𝑆 [𝑓 𝑖−1 (𝑘, 𝑆 − {𝑘} + 𝑑 𝑘𝑗 ]
dengan 𝑖 = 1,2, . . . , 𝑁 − 2; 𝑗 ≠ 1; 𝑆 ⊆ 𝑁 𝑗
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 438 – 444 DOI : https://doi.org/10.36987/jpms.v8i2.3399
3. Solusi optimal untuk penyelesaian masalah traveling salesman problem adalah : min 𝑗=2,3,...𝑛 [𝑓 𝑁−2 (𝑗, 𝑁 𝑗 ) + 𝑑 𝑗1 ]
Secara intuitif hubungan rekursif penyelesaian TSP dengan program dinamik yaitu sebagai berikut: anggap bahwa akan dihitung 𝑓 𝑖 (𝑗, 𝑆) , dimana lintasan terpendek dari simpul 1 ke simpul 𝑗 melewati 𝑆 yang memiliki simpul 𝑘 ( himpunan bagian dari 𝑆 . Karena simpul 𝑆 − {𝑘} harus dikunjungi dalam urutan yang optimal, panjang dari lintasan ini adalah 𝑓 𝑖−1 (𝑘, 𝑆 − {𝑘}) + 𝑑 𝑘𝑗 . Selanjutnya terdapat aturan dalam pemilihan simpul 𝑘 secara optimal ( bebas memilih simpul 𝑘 ) hal ini jelas bahwa 𝑓 𝑖 (𝑗, 𝑆) diberikan dengan rumus 1.
Oleh karena itu, untuk menghitung panjang dari lintasan terpendek, dimulai dengan menghitung 𝑓 𝑖 (𝑗, 𝑆) (untuk setiap 𝑗, 𝑆 pasang dari  nilai 𝑓 0 . Kemudian hitung 𝑓 2 (𝑗, 𝑆) (untuk setiap 𝑗, 𝑆 pasang ) dari nilai 𝑓 1 .  Kemudian  dilanjutnya  dengan  cara  yang  sama  sampai 𝑓 𝑁−2 (𝑗, 𝑁 𝑗 ) telah  dihitung  untuk  setiap simpul 𝑗 . Panjang dari lintasan terpendeknya diberikan pada rumus 3, karena beberapa simpul 𝑗 harus menjadi simpul terakhir yang dikunjungi sebelum kembali ke simpul 1.

## Hasil Penelitian dan Pembahasan
Perusahaan  logistik  di  Pematangsiantar  memliki  titik  wilayah  pada  setiap  kecamatan  .Wilayah tersebut  terdiri  dari  6  dari  8  kecamatan  meliputi  :  Siantar  Barat,  Siantar  Marimbun,  Siantar  Martoba, Siantar  Selatan,  Siantar  Sitalasari,  Siantar  Timur.  Proses  pick  up  barang  perusahaan  logistik Pematangsiantar ini berpusat di kecamatan Siantar Martoba.
Data jarak dan waktu berdasarkan Google Maps
Tabel 1. Jarak dan Waktu dari kec Siantar Martoba (Pusat Pick Up barang)  ke setiap lokasi
No. Lokasi Jarak (km) Waktu (menit) (detik) 1 Kantor Cabang 7,0 Kilometer 13 Menit (780 detik) 2 Siantar Barat 7,8 Kilometer 16 Menit (960 detik) 3 Siantar Selatan 8,2 Kilometer 16 Menit (960 detik) 4 Siantar Marimbun 10 Kilometer 20 Menit (1200 detik) 5 Siantar Sitalasari 10 Kilometer 19 Menit (1140 detik) Tabel 2. Jarak dan Waktu dari kantor Cabang  ke setiap titik kecamatan No. Lokasi Jarak (km) Waktu (menit) (detik) 1 Siantar Martoba 6,3 Kilometer 12 Menit (720 detik) 2 Siantar Barat 1,4 Kilometer 4 Menit (240 detik) 3 Siantar Selatan 2,5 Kilometer 6 Menit (360 detik) 4 Siantar Marimbun 4,4 Kilometer 9 Menit (540 detik) 5 Siantar Sitalasari 3,7 Kilometer 9 Menit (540 detik)
Tabel 3. Jarak dan Waktu dari kec Siantar Barat ke setiap lokasi
No. Lokasi Jarak (km) Waktu (menit) (detik)
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 438 – 444 DOI : https://doi.org/10.36987/jpms.v8i2.3399
1 Siantar Martoba 7,5  Kilometer 15  Menit (900 detik) 2 Cabang 1,2 Kilometer 3  Menit (180 detik) 3 Siantar Selatan 1,5 Kilometer 4 Menit (360 detik) 4 Siantar Marimbun 3,2  Kilometer 7 Menit (420 detik) 5 Siantar Sitalasari 2,3 Kilometer 6  Menit (360 detik)
Tabel 4. Jarak dan Waktu dari kec Siantar Selatan  ke setiap lokasi
No. Lokasi Jarak (km) Waktu (menit) (detik) 1 Siantar Martoba 8,7  Kilometer 17  Menit (1020 detik) 2 Cabang 2,4  Kilometer 5  Menit (300 detik) 3 Siantar Barat 1,5 Kilometer 4 Menit (360 detik) 4 Siantar Marimbun 2,4  Kilometer 5 Menit (300 detik) 5 Siantar Sitalasari 2,9 Kilometer 7  Menit (420 detik) Tabel 5. Jarak dan Waktu dari kec Siantar Marimbun  ke setiap lokasi No. Lokasi Jarak (km) Waktu (menit) (detik) 1 Siantar Martoba 11,0  Kilometer 20  Menit (1200 detik) 2 Cabang 4,3 Kilometer 9  Menit (540 detik) 3 Siantar Barat 3,4  Kilometer 7 Menit (420 detik) 4 Siantar Selatan 2,8  Kilometer 6 Menit (360 detik) 5 Siantar Sitalasari 2,0 Kilometer 5 Menit (300 detik)
Tabel 6. Jarak dan Waktu dari kec Siantar Sitalasari ke setiap lokasi
No. Lokasi Jarak (km) Waktu (menit) (detik) 1 Siantar Martoba 10,0  Kilometer 19  Menit (1140 detik) 2 Cabang 3,5 Kilometer 9  Menit (540 detik) 3 Siantar Barat 2,3  Kilometer 6  Menit (360 detik) 4 Siantar Selatan 3,3  Kilometer 8 Menit (480 detik) 5 Siantar Marimbun 2 Kilometer 5  Menit (300 detik)

## Hasil perhitungan jarak
Menghitung bobot dari simpul awal atau simpul 𝑖 ke simpul 𝑗 , untuk 𝑖𝜖𝑠 dan 𝑖 ≠ 𝑦 dengan |𝑆| = 5 .
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 438 – 444 DOI : https://doi.org/10.36987/jpms.v8i2.3399
𝑓 𝐸 (𝑆, 𝑗) = min 𝑖𝜖𝑠 {𝑅 𝑖𝑗 + 𝑓 𝐷 (𝑆 − {𝑗}𝑗)}
𝑓 𝑍 [{𝐴, 𝐵, 𝐶, 𝐷, 𝐸}𝑍] =    𝑅 𝐴𝑍 + 𝑓 𝐷 ({𝐵, 𝐶, 𝐷, 𝐸}𝐴) ; 𝑅 𝐵𝑍 +   𝑓 𝐷 ({𝐴, 𝐶, 𝐷, 𝐸}𝐵) ; 𝑅 𝐶𝑍 + 𝑓 𝐷 ({𝐴, 𝐵, 𝐶, 𝐷}𝐸) ; 𝑅 𝐷𝑍 +   𝑓 𝐷 ({𝐴, 𝐵, 𝐶, 𝐸}𝐷); 𝑅 𝐸𝑍 + 𝑓 𝐷 ({𝐴, 𝐵, 𝐶, 𝐷}𝐸) = 𝑚𝑖𝑛 [6,3 + 17,2    7,5 + 16,2   8,7 + 16,9   11 + 15,1  10 + 14,3] = 𝑚𝑖𝑛 [23,5   23,7   25,6   26,1  24,3] = 23,5
solusi yaitu dari simpul A ke Z dengan bobot 23,5 km.
Berdasarkan hasil optimal iterasi ke-1 sampai iterasi ke-6 yaitu diperoleh lintasan terpendek dari titik Z ke titik B dengan jarak 7,8 km, dari B ke titik C dengan jarak 1,5 km,dari titik C ke titik D dengan jarak  2,4  km,  dari  titik  D  ke  titik  E  dengan  jarak  2  km,  dari  titik  E  titik  A  dengan  jarak  3,5,dari  titik  A kemudian kembali ke titik Z dengan jarak 6,3 km . Maka total jarak yang dilalui yaitu 7,8 + 1,5 + 2,4 + 2 + 3,5 + 6,3 = 23,5 km.

## Hasil perhitungan waktu
Menghitung bobot dari simpul awal atau simpul 𝑖 ke simpul 𝑗 , untuk 𝑖𝜖𝑠 dan 𝑖 ≠ 𝑦 dengan |𝑆| = 5 . 𝑓 𝐸 (𝑆, 𝑗) = min 𝑖𝜖𝑠 {𝑅 𝑖𝑗 + 𝑓 𝐷 (𝑆 − {𝑗}𝑗)}
𝑓 𝑍 [{𝐴, 𝐵, 𝐶, 𝐷, 𝐸}𝑍] =    𝑅 𝐴𝑍 + 𝑓 𝐷 ({𝐵, 𝐶, 𝐷, 𝐸}𝐴) ; 𝑅 𝐵𝑍 +   𝑓 𝐷 ({𝐴, 𝐶, 𝐷, 𝐸}𝐵) ; 𝑅 𝐶𝑍 + 𝑓 𝐷 ({𝐴, 𝐵, 𝐶, 𝐷}𝐸) ; 𝑅 𝐷𝑍 +   𝑓 𝐷 ({𝐴, 𝐵, 𝐶, 𝐸}𝐷); 𝑅 𝐸𝑍 + 𝑓 𝐷 ({𝐴, 𝐵, 𝐶, 𝐷}𝐸) = 𝑚𝑖𝑛 [12 + 35    15 + 35   17 + 34   20 + 35  19 + 33] = 𝑚𝑖𝑛 [47   50   51   55  52] = 47
Solusinya yaitu dari A ke Z dengan bobot 47.
Berdasarkan hasil optimal iterasi ke-1 sampai iterasi ke-6 yaitu diperoleh lintasan terpendek dari titik Z ke titik C dengan waktu 16 menit,dari titik C ke  titik D dengan waktu 5 menit, dari titik D ke titik E dengan waktu 5 menit, dari titik E ke titik B dengan waktu 6 menit , dari titik B ke titik A dengan waktu 3 menit , dari titik A kemudian kembali ke titik Z dengan waktu 12 menit. Maka total waktu yang dilalui yaitu 16 + 5 + 5 + 6 + 3 + 12 = 47 menit .

## Perhitungan biaya
Pada  perusahaan  logistik  di  Pematangsiantar  dalam  proses pick  up barang  menggunakan kendaraan mobil box colt diesel (euro-2) dengan perkiraan perbandingan bahan bakar  1 : 8 atau 1 liter bahan bakar dapat di gunakan untuk menempuh jarak 8 km. Hasil wawancara dengan salesman (kurir). Berdasarkan hasil optimal rute terpendek yang telah di dapat yaitu 23,5 km, maka pada proses pick up barang jarak yang di tempuh sejauh 23,5 km.
Maka konsumsi bahan bakar untuk menempuh jarak 23,5 km yaitu:
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 438 – 444 DOI : https://doi.org/10.36987/jpms.v8i2.3399
Jarak yang di tempuh
𝑘𝑒𝑚𝑎𝑚𝑝𝑢𝑎𝑛 𝑘𝑒𝑛𝑑𝑎𝑟𝑎𝑎𝑛 / 𝑙𝑖𝑡𝑒𝑟 = 23,5 𝑘𝑚 8 = 2,9 Liter
Maka konsumsi bahan bakar untuk menempuh 23,5 km sebanyak 2,9 liter  solar. Jika di konversikan ke Rupiah dengan harga 1 liter solar Rp.6800 yaitu 2,9 x Rp.6800 = Rp.19.720.

## Kesimpulan
Berdasarkan hasil dan pembahasan yang di peroleh dari pengolahan data dengan penyelesaian Travelling  Salesman  Problem  (TSP) dengan  program  dinamik  dan  penggunaan  aplikasi  Excel  solver memberikan  rute  yang  optimal    waktu  terpendek  yaitu  :  Z  -  C  -  D  -  E  -  B  -  A –  Z  dengan  jarak 23,1 Km dengan waktu 47 menit dan Total Biaya penggunaan bahan bakar solar sebesar 23,1 km : 8 km = 2,8875 liter; 2,8875 liter  x  Rp 6.800 = Rp 19.635 Rute yang dilalui dimulai dari Siantar Martoba, kemudian ke Siantar Selatan, kemudian ke Siantar Marimbun, kemudian ke Siantar Sitalasari, kemudian ke Siantar Barat, kemudian ke Siantar Cabang , dan kembali ke Siantar Martoba. Rute di atas adalah rute  yang  optimal  karena  rute  harus  di  mulai  dari  Gudang  lalu  kembali  lagi  ke  gudang  perusahaan logistik

## Daftar  Pustaka
[1] Santosa,  B.  (2017). Pengantar  Metaheuristik:  Implementasi  dengan  Matlab (Vol.  1).  ITS  Tekno Sains.
[2]  Yunus, H., & Helmi, S. M. (2015) Metode Program Dinamis Pada Penyelesaian Traveling Salesman Problem . Bimaster Buletin Ilmiah Matematika, Statistika dan Terapannya, 4(03).
[3]    Utomo, H. T., Pulungan, M. H., & Santoso, E. S. M. (2004). Minimasi Biaya Distribusi Tempe Dengan Menggunakan      Metode Travelling Salesman Problem (TSP)(Studi Analisa Usaha Kecil Hikma Sanan â€“Malang). Jurnal Teknologi Pertanian , 5 (2).
[4]   Ningtyas, D. K., Evania, V., & Ernastuti, E. (2008, August). Evaluasi Kinerja Algoritma Traveling Salesman  Problem dengan  Teknik  Pemrograman  Dinamik.  In Proceeding, Seminar  Ilmiah Nasional Komputer dan Sistem Intelijen (KOMMIT 2008). Gunadarma University.
[5]    Rangkuti, A. (2014). Penerapan Model Dinamik Probabilistik pada Produksi Kendaraan Bermotor dalam Negeri Tahun 2009-2013. Jurnal Matematika, Statistika dan Komputasi, 11(1), 8-16.