Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 3, Juli (2024), pp. 818-824

## Distribusi Produk Menggunakan Metode Travelling Salesman Problem (TSP) Dengan Konsep Algoritma Heuristik
Yendrizal
Teknik Komputer, Akademi Manajemen Informatika dan Komputer, Solok, Sumatra Barat, Indonesia E-mail: yendrizal70@gmail.com

## Abstract
Searching  for  solutions  in  determining  the  shortest  route  in  product  distribution  is often found in everyday life.  Solutions to solve problems can be designed in the form of diagrams  consisting  of  lines  and  central  points.  Examples  include  finding  the  shortest route  (Traveling  salesman  problem  (TSP).  The  concept  of  the  Traveling  Salesman Problem (TSP) is a classic problem of finding the shortest route that a salesman can take when want to visit several cities without having to visit the same city more than once. The problem that often occurs is that the delivery of goods must be on time to the destination, however,  because  the  locations  to  be  addressed  are  so  many  and  spread  across  each region,  it  makes  it  very  difficult  for  distributors  to  deliver.  goods  according  to  the specified time, the research objective is expected to be able to help distributors in finding the  smallest  route  for  delivering  goods  both  in  terms  of  time  and  saving  gasoline, providing  distribution  route  solution  options that  can  minimize delays in  goods delivery and optimize human resource transportation facilities. The Heuristic Algorithm produces the best solution to problems which are part of a more complex problem where delivery of orders from distributors to consumers is maximized. The final result of the TSP process is 240  CBDA=240.  This  method  can  help  in  finding  the  smallest  route  solution  in distributing goods so that it can be used as a reference to get the best results.
Keywords: Artificial intelligence; Searching; Route; (Traveling salesman problem (TSP); Heuristics; Solution

## Abstrak
Pencarian solusi dalam Penentuan rute terpendek dalam distribusi produk sering kali ditemukan dalam kehidupan sehari hari. Solusi dalam menyelesaikan permasalahan bisa dirancang dalam bentuk  diagram yang terdiri dari garis dan titik titik pusat, Contoh nya seperti  mencarian  rute  terpendek  (Travelling  salesman  problem  (TSP).  Permasalahan yang sering kali terjadi yaitu pengiriman barang yang harus tepat waktu sampai tujuan namun, karena lokasi yang akan dituju sangat banyak dan luas  ke masing masing daerah sangat memperlulit  para distributor dalam pengiriman barang sesuai dengan waktu yang telah ditentukan, Tujuan Penelitian yang diharapkan mampu membantu para distributor dalam  mencari  jalur  terkecil  dalam  pengantaran  barang  baik  dari  segi  waktu  maupun penghematan bensin, memberikan pilihan solusi rute distribusi yang dapat meminimalisir keterlambatan pengiriman barang dan mengoptimalkan sarana transportasi sumber daya manusia.  Algoritma  Heuristik  menghasilkan  solusi  terbaik  pada  permasalahan  yang merupakan  bagian  persoalan  yang  lebih  kompleks  dimana  pengiriman  pesanan  dari distributor ke konsumen menjadi lebih maksimal. Hasil akhir dari proses TSP yaitu  240 CBDA=240.  Metode  ini  dapat  memantu  dalam  menemukan  solusi  rute  terkecil  dalam pendistribusian barang sehingga bisa dijadikan acuan untuk mendapatkan hasil terbaik.
Kata  kunci: Kecerdasan  Buatan;  Searcing;  Rute;  (Travelling  salesman  problem (TSP); Heuristik; Solusi

## KESATRIA: Jurnal Penerapan Sistem Informasi (Komputer & Manajemen)

## 1. Pendahuluan
Travelling Salesman Problem (TSP) merupakan masalah klasik mencari rute terpendek yang  bisa  dilalui  salesman  ketika  ingin  mengunjungi  beberapa  kota  tanpa  harus mendatangi  kota  yang  sama  lebih  dari  satu  kali  [4].  Penyelesaian  eksak  untuk  masalah TSP  ini  mengharuskan  perhitungan  terhadap  semua  kemungkinan  rute  yang  dapat diperoleh,  kemudian  memilih  salah  satu  rute  yang  terpendek  [1].  TSP  merupakan  salah satu  permasalahan  kombiantorial  di  bidang  transfortasi  untuk  menemukan  suatu  rute perjalanan  terpendek  yang  dapat  di  tempuh  dari  titik  awal  keberangkatan  menuju  titik tujuan, serta meminimumkan biaya perjalanan dan waktu tempuh perjalanan [2]. Menurut Penelitian  yang  berjudul  [3]  Optimasi  Multiple  Travelling  Salesman  Problem  (M-TSP) Pada Penentuan Rute Optimal Penjemputan Penumpang Travel Menggunakan Algoritme Genetika yang menghasilkan penelitian alternatif solusi penyelesaian permasalahan kasus M-TSP  sehingga  dapat  menjadi  pertimbangan  untuk  bidang  usaha  yang  menerapkan metode  M-TSP  dalam  aktivitas  kerjanya,  salah  satunya  yaitu  jasa  perusahaan  travel  di kota Malang.
Berdasarkan  beberapa  kasus  dalam  Traveling  Salesperson  Problem,  maka  kasus tersebut  dapat  diselesaikan  dengan  beberapa  tipe  seperti:  1.  Exact  Solution,  yang merupakan  solusi  yang  dihasilkan  dengan  tipe  yang  optimal  pada  permasalahan  yang diberikan. Metode ini dibagi menjadi dua bagian yakni: a. Brute – Force Method Metode ini  merupakan  metode  dengan  memecahkan  masalah  tertentu  dengan  memeriksa  semua kemungkinan kasus dalam kategori lambat. b. Branch and Bound Metode ini merupakan suatu  algoritma  yang  digunakan  untuk  mencari  jalur/rute  terpendek.  Algoritma  ini  akan melakukan  perhitungan  secara  rekursif  yaitu  pemecahan  masalah  hingga  terkecil  serta algoritma  ini  juga  akan  melakukan  pencatatan  biaya  minimum  sehingga  dapat memperkirakan  nilai  yang  optimal  (Triyanto  et  al.,  2015)  [4].  2.  Approximate  Solution, yang  merupakan  suatu  pendekatan  untuk  menentukan  solusi  yang  tepat  pada  suatu permasalahan  yang  diberikan  serta  dapat  diperoleh  dari  algoritma  yang  didesain  untuk menyelesaikan  sebuah  permasalahan  secara  cepat  atau  juga  mencari  pendekatan  solusi jika  tidak  ditemukan.  Metode  ini  juga  menggunakan  dasar  intuisi  hingga  memperoleh solusi  secara  cepat,  namun  tidak  dapat  menjamin  solusi  yang  optimal.  Metode  ini  juga dibagi kedalam satu penyelesaian yang disebut Nearest Neighbor [5].
Menurut [6] Beberapa contoh masalah yang dapat diselesaikan dengan menggunakan pendekatan  TSP  adalah    1.  Pencarian  rute  bis  sekolah  untuk  mengantarkan  siswa  2. Pencarian  rute  truk  pengantar  parcel  3.  Pengambilan  tagihan  telepon.  Graf  digunakan untuk  mempresentasikan  suatu  objek  diskrit  dan  hubungan  antar  objek-objek  tersebut. Secara  visual,  suatu  objek  di  graf  direpresentasikan  dengan  sebuah  titik,  dan  suatu hubungan antar objek direpresentasikan dengan sebuah garis yang menghubungkan kedua titik. Graf bisa digunakan untuk  mepresentasikan berbagai hal, salah satu kegunaan graf adalah untuk mempresentasikan sebuah peta [7]. Masalah lintasan terpendek secara umum dijelaskan  menggunakan  konsep  graf  dapat  berupa  graf  berarah  atau  graf  tidak  berarah. Sisi  dalam  sebuah  graf  tidak  berarah  dapat  dianggap  memunginkan  perjalanan  di  kedua arah.  Sebaliknya,  sisi  dalam  graf  berarah  hanya  dapat  digunakan  untuk  satu  arah perjalanan.  Biasanya  dalam  menentukan  lintasan  terpendek  dengan  menggunakan  graf berbobot. Setiap sisi dalam graf berbobot terdapat suatu nilai atau bobot [8].
Menurut  Penelitian  [9][6],  Permasalahan  matematika  adalah  cikal  bakal  dari permasalahan  Travelling  Salesman  Problem  (TSP),  dikemukakan  oleh  matematikawan Irlandia  William  Rowan  Hamilton  dan  matematikawan  Inggris  Thomas  Penyngton  pada tahun  1800.  Matematikawan  Karl  Menger  di  Vienna  dan  Harvard  pada  tahun  1930 mempelajari pertama kali bentuk umum
Gambar 1. Rute terpendek
Algoritma yang bekerja berdasarkan heuristic dan metaheuristic dapat menjadi sebuah solusi  untuk  menyelesaikan  NP-Hard  Problem  dengan  waktu  perhitungan  yang  wajar ditunggu,  walaupun  solusi  yang  dihasilkan  belum  tentu  merupakan  solusi  yang  terbaik [10]. Algoritma Heuristik merupakan salah satu algoritma yang dapat menghasilkan solusi terbaik  dalam  suatu  permasalahan  dimana  permasalahan  tersebut  merupakan  irisan  atau bagian  dari  suatu  permasalahan  yang  tingkatannya  lebih  kompleks  sehingga  pengiriman pesanan  dari  produsen  ke  konsumen  menjadi  lebih  maksimal  [11].  Menurut  Penelitian [12],  Pengiriman  memiliki  beberapa  jasa  yang  salah  satunya  adalah  ekspedisi.  jasa tersebut  digunakan  untuk  mengirimkan  produk  atau  barang  dalam  kapasitas  sedang hingga kecil ke berbagai tempat tujuan. Kurir perusahaan ekspedisi sebagai ujung tombak pelayanan  sering  kali  mengalami  kesulitan  untuk  menentukan  rute  yang  akan  dilalui dalam  pengantaran  barang  karena  banyaknya  alamat  yang  menjadi  tujuannya,  untuk  itu diperlukan  suatu  sistem  yang  dapat  membantu  kurir  dalam  menentukan  rute  yang  akan dilaluinya  dalam  sekali  pengantaran  dan  dapat  menampilkan  hasil  pencarian  jarak  pada lebih dari satu titik tujuan yang telah diperoleh.
Penelitian  Yang  Berhubungan  Dengan  TSP  Seperti1.    Studi  Tentang  Travelling Salesman Dan Vehicle Routing Problem Dengan Time Windows (Sutapa Et Al., 2004). 2. Implementasi  Travelling  Salesman  Problem  (Tsp)  Dengan  Algoritma  Genetika Menggunakan  Peta  Leaflet  (Studi  Kasus  PT.  AMZ  Geoinfo  Solution  Surabaya)  [14]3. Penanganan  Fuzzy  Time  Window  Pada  Travelling  Salesman  Problem  (TSP)  Dengan Penerapan Algoritma Genetika (Yuliastuti Et Al., 2017) 4. Travelling Salesman Problem (Tsp)  Optimization  Seed  Distribution  Using  Genetic  Algorithm  (Wati  Et  Al.,  2022)  5. Implementasi  Algoritma  Cheapest  Insertion  Heuristic  (CIH)  Dalam  Penyelesaian Travelling  Salesman  Problem  (TSP)  (Utomo  Et  Al.,  2018)  6.  Penyelesaian  Multiple Travelling  Salesman  Problem  (Multi-Tsp)  Dengan  Metode  Order  Crossover  Dalam Algoritma  Genetika  (Studi  Kasus:  Data  Pelanggan  Agen  Surat  Kabar  Di  Kota Singkawang)  [18].  7.  Optimalisasi  Rute  Distribusi  Produk  Menggunakan  Metode Traveling Salesman Problem [19].

## 2. Metodologi Penelitian
Langkah langkah dalam menyelesaikan penelelitian ini diantaranya:
a) Menentukan  masing masing Jarak dan titik pada  TSP
b) Menghitung masing masing jarak dari satu titik ke titik yang lain yang mempunyai Goal akhir
c) Membuat proses perhitungan masing masing jarak
d) Menjumlahkan semuah jarak yang telah dirancang
e) Memilih solusi terbaik dengan melihat nilai terkecil dan memiliki Goal akhir.

## 3. Hasil Dan Pembahasan

## 3.1. Analisa Data
Langkah  pertama  dalam  menyelesaikan  kasus  TSP  yaitu  menganalisa  data  yang digunkan  harus jelas  dan  benar  karena  semuanya  saling  berkaitan.  Data  yang  digunakan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 5, No. 3, Juli (2024), pp. 818-824
dikelompokkan  dalam  grap  yang  saling  terhubung.  Masing  masing  grap  memiliki  nilai sehingga bisa dihitung dari beberapa titik yang terhubung. Diketahui  4 Titik yang akan dihubungkan dengan nilai jarak masing masing yaitu AB=100, AC=95, AD=75, BC=85, BD=80 CD=90. Bangkitkan semua solusi  yang mungkin adalah n! = 4! = 24. Tujuannya agar dapat mencari solusii rute terpendek.Rute dikatakan valid apabila jalur yang dilalui tidak  berjarak  0.  Jika  rute  valid,  maka  jarak  dihitung  kemudian  dibandingkan  untuk mendapatkan jarak  yang  sangat  optimal.  Data  yang  diperoleh  dapat  dilihat  pada gambar dibawah ini
Gambar 2. Data TSP
Pada  Gambar  2  diketahui  4  Kota  yaitu  kota  A,B,C  dan  D  dan  jarak  masing  masing antar kota berbeda beda. Pada gambar diatas menjelaskan bahwa anak panah merupakan penghunung  antar  kota  yang  lainnya.  Untuk  menyelesaikan  kasus  ini  diperlukan  proses penyelesaian  dalam  memcari  solusi  terbaik  untuk  memperoleh  hasil  akhir.  Nilai  masing masing jarak antar jalur diantaranya:
Permasalahan dalam menyelesaikan kasus ini Keadaan Awal = ABCD Goal = ABCD Jarak masing masing Sudut AB=100; AC=95; AD=75; BC=85; BD=80; CD=90 Proses  yang diperoleh terdapat 24  Lintasan bisa dilihat pada Tabel 1 ini.
Tabel 1. Proses Iterasi
Pada Tabel 1 menjelaskan bahwa 4 Titik yang diketahui menghasilkan lintasan 24 yng mana  masing  masing  lintasan  memiliki  nilai  hitung  yang  berbeda.  Pada  proses  lintasan pertama  diperoleh  nilai  275  dan  pada  proses  kedua  diperoleh  nilai  265,  maka  untuk pencarian  selanjutnya  265  menjadi  acuan,  jika  pada  nomor  tiga  dan  nomor  selanjutnya memiliki nilai lebih kecil,maka nilai yang lebih kecil tersebut dijadikan nilai selanjutnya.

## 3.2. Pengelompokan Rute
Dibawah ini merupan  proses masing masing Lintasan
Gambar 3. Proses Lintasan
Hasil TSP yang diperoleh dengan nilai 75+80+85=240 CBDA=240 dengan Metode ini dapat memantu dalam menemukan solusi rute terpendek memberikan solusi optimal.

## KESATRIA: Jurnal Penerapan Sistem Informasi (Komputer & Manajemen)

## 4. Kesimpulan
Berdasarkan  hasil  akhir  yang  diperoleh  maka  penelitian  ini  dapat  menghasilkan kesimpuan diantaranya:
1. Penentuan  Rute  terpendek  pada    pengukuran  jarak  dapat  diselesaikan menggunakan metode Travelling Salesman Problem. Proses TSP mampu bekerja dalam  menyelesaikan  permasalahan  dengan  heuristic  nilai  yang  berbeda  beda, sehingga  dibutuhkan  proses  perhitungan  berkali  kali  dan  bervariasi  agar menghasilkan nilai yang lebih optimal
2. Semakin  banyak  perhitungan  nilai  yang  digunakan  maka  akan  semakin  besar peluang untuk mendapatkan nilai jarak terkecil sehingga mampu dijadikan ajuan dalam  penentuan  rute  arah  yang  mana  akan  dituju  sehingga  bisa  meminilisir waktu,jarak dan minyak yang digunakan.
3. Hasil  nilai  akhir  terpendek  yang  diperoleh  yaitu  75+80+85=240  CBDA=240. Pengujian  dan  hasil  perhitungan  masih  terdapat  kukurangan  yaitu  apabila pengujian  nilai  salah  perhitungan  maka  hasil  pencarian  akan  salah,  sebaiknya dilengkapi dengan Aplikasi pendeteksi secara langsung.

## Daftar Pustaka
[1] D.  T.  Wiyanti,  “Algoritma  Optimasi  Untuk  Penyelesaian  Travelling  Salesman Problem,” J. Transform. , Vol. 11, No. 1, P. 1, 2013, Doi: 10.26623/Transformatika.V11i1.76.
[2] Zulkarnaen  Zulkarnaen  And  Muhammad  Azmi,  “Implementasi  Algoritma  I-Sos Dalam  Penyelesaian  Traveling  Salesman  Problem  (Tsp),” Tek.  Teknol.  Inf.  Dan Multimed. , Vol. 2, No. 1, Pp. 1–7, 2021, Doi: 10.46764/Teknimedia.V2i1.29.
[3] P. M. R. Raditya And C. Dewi, “Optimasi Multiple Travelling Salesman Problem (  M-Tsp  )  Pada  Penentuan  Rute  Optimal  Penjemputan  Penumpang  Travel Menggunakan Algoritme Genetika,” J. Pengemb. Teknol. Inf. Dan Ilmu Komput. , Vol. 2, No. 10, Pp. 3560–3568, 2018.
[4] C. Sitompul And O. M. Horas, “A Vehicle Routing Problem With Time Windows Subject To The Constraint Of Vehicles And Good’s Dimensions,” Int. J. Technol. , Vol. 12, No. 4, Pp. 865–875, 2021, Doi: 10.14716/Ijtech.V12i4.4294.
[5] D.  Wawan  Saputra,  “Optimalisasi  Rute  Distribusi  Kurir  Menggunakan  Metode Traveling  Salesman  Problem  (Studi  Kasus:  Jne  Balige),” G-Tech  J.  Teknol. Terap. , Vol. 6, No. 2, Pp. 159–165, 2022, Doi: 10.33379/Gtech.V6i2.1577.
[6] 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.
[7] R.  N.  B.  Sitepua  And  G.  N.  A.  C.  Putra,  “Penentuan  Rute  Terpendek Menggunakan  Algoritma  A  Star,” J.  Nas.  Teknol.  Inf.  Dan  Apl. ,  Vol.  1,  No. November, Pp. 431–440, 2022.
[8] K. K. Amozhita, A. Suyitno, And Mashuri, “Menyelesaikan Travelling Salesman Problem (Tsp) Dengan Metode Dua Sisi Optimal Pada Pt. Es Malindo Boyolali,” Unnes J. Math. , Vol. 8, No. 1, Pp. 20–29, 2019.
[9] L. G. A. Candrawati And I. G. A. G. A. Kadyanan, “Optimasi Traveling Salesman Problem (Tsp) Untuk Rute Paket Wisata Di Bali Dengan Algoritma Genetika,” J. Ilm. Komput. , Vol. 10, No. 1, Pp. 27–32, 2017.
[10] E.  Sanggala,  “Penyelesaian  Travelling  Salesman  Problem  (Tsp)Dengan Evolutionary  Algorithm  &  Excel  Solver(Studi  Kasus:  Ak-47-Tsp  Instance),” J. Inov. Tek. Ind. , Vol. 2, No. 2, Pp. 47–62, 2023.
[11] Indah  Setyorini,  “15-Article  Text-117-1-10-20210105,” J.  Ilm.  Mat.  Dan Pendidik. , Vol. 1, No. 1, Pp. 14–18, 2020.
[12] G.  Muhamad  Adzaky,  O.  Traveling  Salesman  Problem,  And  R.  Wahid  Saleh
Insani,  “Optimasi  Traveling  Salesman  Problem  (Tsp)  Menggunakan  Algoritma Genetika Dan Google Maps Api Untuk Kurir Ekspedisi Pada J&T Paris 2 Berbasis Web Gis,” Inser. Inf. Syst. Emerg. Technol. J. , Vol. 4, No. 2, P. 119, 2023.
[13] I.  N.  Sutapa,  I.  G.  A.  Widyadana,  And  C.  Christine,  “Studi  Tentang  Travelling Salesman  Dan  Vehicle  Routing  Problem  Dengan  Time  Windows,” J.  Tek.  Ind. , Vol. 5, No. 2, Pp. 81–89, 2004, Doi: 10.9744/Jti.5.2.81-89.
[14] D. K. Pitaloka And R. Koesdijarto, “Implementasi Travelling Salesman Problem (Tsp)  Dengan  Algoritma  Genetika  Menggunakan  Peta  Leaflet  (Studi  Kasus  Pt. Amz Geoinfo Solution Surabaya),” Pros.  Senakama ,  Vol.  1,  No.  September,  Pp. 767–776, 2022.
[15] G.  E.  Yuliastuti,  W.  F.  Mahmudy,  And  A.  M.  Rizki,  “Penanganan  Fuzzy  Time Window  Pada  Travelling  Salesman  Problem  (Tsp)  Dengan  Penerapan  Algoritma Genetika,” Matics , Vol. 9, No. 1, P. 38, 2017, Doi: 10.18860/Mat.V9i1.4072.
[16] V. Wati, Y. Yuliana, P. Paradise, And K. Kusrini, “Travelling Salesman Problem (Tsp)  Optimization  Seed  Dis-Tribution  Using  Genetic  Algorithm,” Jurteksi (Jurnal  Teknol.  Dan  Sist.  Informasi) ,  Vol.  8,  No.  3,  Pp.  359–368,  2022,  Doi: 10.33330/Jurteksi.V8i3.1738.
[17] R.  G.  Utomo,  D.  S.  Maylawati,  And  C.  N.  Alam,  “Implementasi  Algoritma Cheapest  Insertion  Heuristic  (Cih)  Dalam  Penyelesaian  Travelling  Salesman Problem  (Tsp),” J.  Online  Inform. ,  Vol.  3,  No.  1,  P.  61,  2018,  Doi: 10.15575/Join.V3i1.218.
[18] S. W. H. Yudhi, “Penyelesaian Multiple Travelling Salesman Problem (Multi-Tsp) Dengan  Metode  Order  Crossover  Dalam  Algoritma  Genetika  (Studi  Kasus:  Data Pelanggan  Agen  Surat  Kabar  Di  Kota  Singkawang),” Bimaster    Bul.  Ilm.  Mat.
Stat. Dan Ter. , Vol. 8, No. 2, Pp. 157–166, 2019, Doi: 10.26418/Bbimst.V8i2.31310.
[19] K.  Auliasari,  M.  Kertaningtyas,  And  D.  W.  L.  Basuki,  “Optimalisasi  Rute Distribusi Produk Menggunakan Metode Traveling Salesman Problem,” J.  Sains,
Teknol. Dan Ind. , Vol. 16, No. 1, P. 15, 2018, Doi: 10.24014/Sitekin.V16i1.6109.