Jurnal Ilmiah Matematika dan Pendidikan Matematika (JMP) Vol. 16 No. 1, Juni 2024, hal. 19-28 ISSN (Cetak) : 2085-1456; ISSN ( Online ) : 2550-0422

## PENERAPAN MULTIPLE TRAVELING SALESMAN PROBLEM PADA OPTIMASI PENDISTRIBUSIAN

## Maya Widyastiti*
Program Studi Matematika, FMIPA, Universitas Pakuan maya.widyastiti@unpak.ac.id

## Amar Sumarsa
Program Studi Matematika, FMIPA, Universitas Pakuan

## Alfina Yulia Permana
Program Studi Matematika, FMIPA, Universitas Pakuan
ABSTRACT. Distribution  is  one  of  the  important  activities  in  sending  goods  from producers  to  consumers.  This  research  was  applied  to  PT.  Kobe  Boga  Utama,  Depok Branch.  This  company  distributed  products  to  333  outlets  in  2  weeks  from  Monday  to Saturday.  On  certain  days,  the  company  visited  more  than  one  trip,  requiring  several salesmen.  The  distribution  problem  can  be  formed  as  a  Multiple  Traveling  Salesman Problem and modeled as an Integer Linear Programming problem. This research aims to determine  the  optimal  route  with  the  shortest  distance  using  the  Branch  and  Bound method. The research results show that the salesman has to cover a minimum distance is 732.83  km  in  odd  weeks  with  149  outlets  to  visit.  The  number  of  trips  taken  is  7  trips, consisting  of  1  trip  on  Monday,  Thursday,  and  Friday,  and  2  trips  on  Wednesday  and Thursday. On even weeks, a salesman must visit 184 outlets with a minimum distance is 1292.3  km, consisting  of  1  trip  on  Tuesday,  Thursday,  Friday,  and  Saturday,  2  trips  on Wednesday,  and  3  trips  on  Monday.  The  total  minimum  distance  is  2025.09  km.  The optimization  result  is  about  359.97 km  (49.12%)  for odd  weeks  and  506.61  km (39.2%) for even weeks.
Keywords :  Distribution,  Muliple  Traveling  Salesman  Problem,  Branch  and  Bound Method
ABSTRAK. Pendistribusian merupakan salah satu kegiatan penting dalam mengirimkan barang dari produsen ke konsumen. Penelitian ini diterapkan pada PT. Kobe Boga Utama Cabang Depok. Perusahaan ini mendistribusikan produk ke 333 outlet dalam 2 pekan dari hari Senin hingga Sabtu. Pada hari tertentu, perusahaan mengunjungi lebih dari satu trip sehingga  membutuhkan  beberapa  salesman.  Masalah  pendistribusian  dapat  dibentuk sebagai Multiple Traveling  Salesman  Problem dan  dimodelkan  sebagai  masalah Integer Linear  Programming .  Penelitian  ini  bertujuan  untuk  menentukan  rute  optimal  dengan jarak  tempuh  terpendek  menggunakan  metode Branch  and  Bound .  Hasil  penelitian menunjukkan bahwa pada pekan ganjil, salesman harus menempuh jarak minimal sebesar 732.83  km  dengan  outlet  yang  harus  dikunjungi  sebanyak  149.  Banyaknya  trip  yang dilalui sebanyak 7 trip, yang terdiri dari 1 trip pada hari Senin, Kamis, dan Jumat, serta 2 trip  untuk  hari  Rabu  dan  Kamis.  Pada  pekan  genap,  salesman  harus  mengunjungi  184 outlet dengan total jarak  minimum  sebesar 1292.3 km, yang terdiri dari 1 trip pada hari Selasa,  Kamis,  Jumat,  dan  Sabtu,  2  trip  untuk  hari  Rabu,  dan  3  trip  untuk  hari  Senin.
Total jarak tempuh minimum sebesar 2025.09 km. Hasil optimal dari pekan ganjil sebesar 359.97 km (49.12%) dan untuk pekan genap sebesar 506.61 km (39.2%).
Kata Kunci :   distribusi, Integer  Linear  Programming ,  Metode Branch  and  Bound , Multiple Traveling Salesman Problem

## 1. PENDAHULUAN
Pendistribusian  merupakan  salah  satu  kegiatan  penting  untuk  semua  jenis industri  maupun  pelayanan.  Distribusi  adalah  proses  penyaluran  produk  dan  jasa dari  produsen  ke  konsumen.  Kegiatan  ini  bertujuan  untuk  pemerataan  produk  di suatu  daerah  sehingga  konsumen  dapat  mengonsumsi  atau  menggunakan  produk atau layanan yang diberikan dengan cepat, tepat dan kondisi yang baik. Selain itu, kegiatan distribusi menjadi upaya untuk menjaga stabilitas perusahaan. Pada saat ini,  banyak  perusahaan  besar  ataupun  perusahaan  berkembang  yang  harus mendistribusikan  barang  ke  banyak  konsumen.  Pendistribusian  ini  dilakukan harus  diimbangi  dengan  penentuan  rute  yang  tepat  sehingga  proses  distribusi menjadi  optimal.  Banyak  sekali  rute  yang  dapat  dipilih  oleh  perusahaan  dalam proses  pendistribusian.  Hal  ini  mengakibatkan  jarak  tempuh,  biaya  atau  waktu yang  dibutuhkan  berbeda-beda  pula.  Untuk  itu,  dibutuhkan  suatu  metode  yang dapat  menganalisa  proses  pendistribusian  produk  sehingga  dapat  meminimalkan jarak, biaya, waktu dan tenaga yang harus dikeluarkan.
Dalam  masalah  seperti  ini,  dapat  dilakukan  suatu  pendekatan  penyelesaian masalah  pendistribusian,  yaitu  dengan Traveling  Salesman  Problem (TSP).  TSP adalah penentuan rute optimal dimana terdapat satu salesman dari satu tempat asal yang  harus  mengunjungi  sejumlah  tempat  tujuan  sebanyak  tepat  satu  kali, kemudian  kembali  ke  tempat  asal  dengan  jarak  yang  minimum.  Dalam  TSP, salesman  tersebut  tidak  boleh  kembali  ke  tempat  asal  sebelum  semua  tempat selesai dikunjungi. Tujuan dari TSP adalah meminimumkan jarak total rute yang dikunjungi dalam satu perjalanan.
Masalah  TSP  telah  banyak  dikembangkan  antara  lain  Saputra  (2022) menggunakan Traveling  Salesman  Problem dalam  distribusi  kurir  JNE,  Rohman (2020)  menerapkan Traveling  Salesman  Problem pada  kasus  pendistribusian barang  PT.  Pos  Indonesia  di  Kota  Bandar  Lampung,  Amozhita  (2019)
Penerapan Multiple Traveling Salesman Problem
menyelesaikan Traveling  Salesman  Problem yang  diterapkan  di  PT.  Es  Malindo Boyolali dan Candrawati (2018) menerapkan TSP pada rute paket wisata di Bali.
PT.  Kobe  Boga  Utama  Cabang  Kota  Depok  merupakan  salah  satu perusahaan  yang  memproduksi  bumbu  siap  pakai.  Perusahaan  ini  umumnya melakukan  pendistribusian  ke  beberapa  outlet  yang  tersebar  di  Kota  Bogor, Jakarta,  Bekasi  dan  Depok.  Saat  ini,  untuk  mendistribusikan  produk  di  wilayah Depok,  perusahaan  harus  mengunjungi  sebanyak  333  outlet  dalam  2  pekan  dari hari  Senin  hingga  Sabtu  menggunakan  1  kendaraan  atau  1  kurir.  Model pendistribusian  ini  merupakan  model Traveling  Salesman  Problem ,  yaitu  proses penentuan  rute  hanya  menggunakan  satu  kendaraan.  Akan  tetapi,  dalam pelaksanaannya, perusahaan harus mengunjungi lebih dari satu trip pada hari-hari tertentu sehingga membutuhkan beberapa salesman. Kasus ini merupakan variasi dari masalah TSP yang disebut multi Traveling Salesman Problem (M-TSP). M-
TSP  merupakan  model  penyelesaian  dari  suatu  permasalahan  yang  dapat digunakan agar mampu memilih rute terpendek yang harus dilewati oleh beberapa kurir  dan  kurir  tersebut  harus  dimulai  dari  lokasi  awal  untuk  mengunjungi beberapa  lokasi  tepat  satu  kali  dan  akan  kembali  ke  lokasi  awal.  Variasi  lainnya dari  masalah  TSP  telah  banyak  dilakukan,  antara  lain  Sumarsa  (2023)  meneliti masalah  TSP  dengan Time  Windows , Asymmetric TSP  dikembangkan  oleh
Santosa (2017), dan Multiple TSP diteliti oleh Karimah (2017).
Dalam  proses  distribusi  pada  kasus  M-TSP  ini,  perusahaan  belum  bisa menentukan cara  yang pasti untuk meminimumkan total jarak tempuh untuk 351 outlet tersebut. Untuk mengatasi masalah tersebut, maka salesman dituntut untuk meminimumkan jarak rute sehingga rute yang dihasilkan dapat seefisien mungkin. Tujuan  penelitian  ini  adalah  menentukan  rute  optimal  dalam  pendistribusian produk  agar  total  jarak  tempuh  kendaraan  dapat  minimum  sehingga  proses pendistribusian  menjadi  efektif.  Masalah  ini  dibentuk  dalam Traveling  Salesman Problem dan  dimodelkan  dalam  masalah Integer  Linear  Programming .  Metode yang  digunakan  adalah Branch  and  Bound .  Selain  dengan  menggunakan  metode
Branch  and  Bound ,  beberapa  metode  dalam  menyelesaikan  TSP  sudah  banyak dikembangkan,  antara  lain  oleh  Pitaloka  (2022)  menyelesakan  masalah  TSP
dengan  algoritma  genetika,  Nurlaelasari  (2018)  menerapkan  TSP  dengan algoritma Ant Colony Optimization , Simbolon (2017) menggunakan metode Tabu Search dalam menyelesaikan TSP, dan Hidayati (2019) TSP diselesaikan dengan menggunakan metode Simulated Annealing .

## 2. HASIL DAN PEMBAHASAN

## 2.1  Data
Data yang digunakan merupakan data outlet pengiriman produk PT. Kobe Boga  Utama  Cabang  Depok  untuk  pengiriman  setiap  harinya  dalam  dua  pekan. Pengiriman  dilakukan  pada  hari  Senin  hingga  Sabtu.  Data  jarak  diperoleh menggunakan bantuan google maps untuk menentukan jarak dari depot (PT. Kobe Boga  Utama  Cabang  Depok)  ke  beberapa  outlet  lainnya.  Data  banyaknya  outlet dan  banyaknya  trip  yang  harus  dikunjungi  setiap  harinya  pada  pekan  ganjil  dan genap terdapat pada Tabel 1.
Tabel 1. Banyaknya Outlet dan Trip yang Dikunjungi Banyak Outlet Banyak Trip Ganjil Genap Ganjil Genap Senin 22 40 1 3 Selasa 37 43 2 1 Rabu 48 44 2 2 Kamis 21 17 1 1 Jumat 21 21 1 1 Sabtu 0 19 0 1 Total 149 184 7 9

## 2.2 Formulasi Matematika
Formulasi matematika untuk masalah tersebut :
a. Indeks
indeks pekan ( = 1 untuk pekan ganjil dan = 2 untuk pekan genap),
indeks  hari  ( untuk  Senin,  Selasa,  Rabu,  Kamis,  Jumat,  dan,
Sabtu secara berurutan),
indeks outlet ( ;
Penerapan Multiple Traveling Salesman Problem
b. Parameter
:  jarak dari outlet ke outlet (satuan: kilometer),
: variabel tambahan untuk menghindari terjadi subroute pada outlet i ;
c. Variabel Keputusan
{
d. Fungsi Tujuan

## ∑ ∑ ∑ ∑
e. Fungsi Objektif
1. Setiap outlet hanya dilayani satu kali
∑ ∑ ∑ ∑ ∑ ∑ 2. Memastikan tidak adanya subtour pada rute yang dihasilkan ; ;
3. Kendala tambahan
,
4. Kendala binary
;
;

## 2.3  Pembahasan
Berdasarkan  formulasi  matematika  yang  telah  dibentuk  kemudian diselesaikan dengan bantuan program LINGO 11.0 menggunakan metode Branch and Bound . Rute yang diperoleh beserta jarak tempuh untuk setiap hari di pekan ganjil dan genap dapat dilihat pada Tabel 2 dan Tabel 3.
Tabel 2. Rute Pendistribusian Pekan Ganjil Hari Rute Jarak Senin 1-10-22-8-2-14-18-7-15-11-4-16-20-13-21-12-3-17-23-5-19-9- 6-1 103.94 Selasa (1) 1-9-14-11-4-16-15-19-17-12-3-7-2-18-8-13-10-5-6-1 85.24 Selasa (2) 1-20-14-18-19-17-106-12-3-11-15-8-2-5-9-16-7-13-4-1 91.44 Rabu (1) 1-11-10-23-13-20-14-3-5-12-27-19-4-6-26-22-15-25-7-24-16-8- 18-9-2-17-21-1 64.22 Rabu (2) 1-10-7-15-20-2-6-22-19-8-17-4-16-9-5-23-12-13-3-11-14-18- 21-1 57.98 Kamis 1-22-5-19-13-10-11-7-2-21-16-4-15-14-3-9-18-12-17-6-20-8-1 165.07 Jumat 1-20-17-14-9-10-4-16-7-15-21-11-13-8-19-22-12-3-18-6-2-5-1 164.94 Total 732.83
Berdasarkan  Tabel  2,  dapat  dilihat  bahwa  pada  pekan  ganjil,  PT  Kobe Boga Utama Cabang Depok harus mengirimkan produknya ke 7 trip dalam 5 hari pengiriman,  yaitu  dari  Senin  hingga  Jumat.  Pada  hari  Senin,  PT  Kobe  Boga Utama menempuh jarak 103.94 km untuk mendistribusikan produknya. Pada hari Selasa, PT. Kobe Boga Utama mengirimkan produknya ke 2 trip (Selasa (1) dan Selasa (2)) dengan jarak 85.24 km dan 91.44 km. Begitu juga pada hari Rabu, PT. Kobe  Boga  Utama  mengirimkan  produknya  ke  2  trip  (Rabu  (1)  dan  Rabu  (2)), dengan  jarak  masing-masing  sebesar  64.22  km  dan  57.98  km.  Pada  hari  Kamis, total jarak pendistribusian sebesar 165.07 km dan hari Jumat sebesar 164.94 km. Total jarak tempuh pada pekan ganjil adalah 732.83 km.
Tabel 3. Rute Pendistribusian Pekan Genap Hari Rute Jarak Senin (1) 1-7-21-2-11-15-9-19-4-22-3-17-10-5-12-6-13-18-8-14-20-16-1 169.89 Senin (2) 1-9-7-4-13-12-3-6-11-5-15-18-20-19-17-16-14-8-2-10-1 191.36 Senin (3) 1-3-22-7-10-18-23-20-13-6-11-8-15-12-4-21-14-17-5-19-16-2- 9-1 57.3 Selasa 1-7-21-2-11-15-9-19-4-22-3-17-10-5-12-6-12-18-8-14-20-16-1 281.11 Rabu (1) 1-9-19-7-21-20-5-4-18-11-10-8-15-12-22-13-6-3-23-14-2-16- 17-1 101.88 Rabu (2) 1-19-21-20-12-14-16-23-9-7-11-17-4-3-6-18-15-10-8-5-22-13- 2-1 107.62 Kamis 1-13-11-2-7-5-14-10-15-16-4-8-12-6-3-9-1 22.16 Jumat 1-9-12-7-8-5-10-19-2-21-3-18-6-4-11-15-20-14-13-17-16-22-1 191.54 Sabtu 1-3-10-19-14-6-18-16-9-20-2-11-17-15-4-7-12-8-13-5-1 169.4 Total 1292.3
Penerapan Multiple Traveling Salesman Problem
Rute pendistribusian pekan genap menghasilkan 9 trip dengan rincian 3 trip pada hari Senin (Senin (1), Senin (2), dan Senin (3)), 2 trip pada hari Rabu (Rabu (1)  dan  Rabu  (2),  serta  1  trip  pada  hari  lainnya,  yaitu  Selasa,  Kamis,  Jumat  dan Sabtu.  Total  jarak  tempuh  yang  diperoleh  pada  pekan  genap  sebesar  1292.3  km, dengan rincian Senin (1) sebesar 169.89 km, Senin (2) sebesar 191.36 km, Senin (3) sebesar 57.3 km, Selasa sebesar 281.11 km, Rabu (1) sebesar 101.88 km, Rabu (2)  sebesar  107.62  km,  Kamis  sebesar  22.16  km,  Jumat  sebesar  191.54  km,  dan Sabtu sebesar 169.4 km.

## 2.4 Perbandingan Jarak Sebelum dan Usulan
Untuk  memperoleh  jarak  tempuh  yang  optimal  bagi  PT.  Kobe  Boga  Utama Cabang  Depok,  maka  dilakukan  perbandingan  antara  rute  awal  dan  rute  usulan dengan  menggunakan  model  ILP.  Berikut  merupakan  perbandingan  hasil  jarak tempuh antara rute awal dan rute usulan model ILP dapat dilihat pada Tabel 4.
Tabel 4. Perbandingan Jarak Rute Awal dan Usulan Rute Awal Usulan Persentase 1 2 1 2 1 2 Senin 173.88 586.75 103.94 418.55 67.28% 146.77% Selasa 271.55 326.94 176.68 281.11 53.69% 16.3% Rabu 224.46 343.25 122.2 209.5 83.68% 127.84% Kamis 218,41 40.1 165.07 22.16 32.31% 80.95% Jumat 204.5 249.14 164.94 191.54 23.98% 30.07% Sabtu 0 252.69 0 169.4 0 49.17% Total 1092.8 1798.9 732.83 1292.3 49.12% 39.2%
Dari tabel di atas dapat dilihat bahwa untuk pengolahan jarak dengan model ILP  menghasilkan  jarak  yang  lebih  baik  dibandingkan  dengan  rute  awal.  Hal  ini dapat  dilihat  dari  selisih  jarak  pada  pekan  ganjil  sebesar  359.97  dan  pada  pekan genap  sebesar  506.61  atau  sebesar  49.12%  untuk  pekan  ganjil  dan  39.2%  untuk pekan genap.

## 3. KESIMPULAN DAN SARAN
Masalah  pendistribuan  produk  dari  PT.  Kobe  Boga  Utama  Cabang  Depok dapat  diformulasikan  sebagai  bentuk Multiple Traveling  Salesman  Problem (M-
TSP).  Masalah  ini  dimodelkan  dalam  bentuk Integer  Linear  Programming dan diselesaikan  dengan  menggunakan  metode Branch  and  Bound .  Hasil  yang diperoleh  menunjukkan  bahwa  pada  pekan  ganjil,  kurir  harus  mengunjungi  149 outlet dengan jarak tempuh minimum sebesar 732.83 km, sedangkan pada pekan genap,  kurir  harus  mengunjungi  184  outlet  dengan  total  jarak  tempuh  terpendek sebesar  1292.3  km.  Berdasarkan  hasil  yang  diperoleh  tersebut  menunjukkan adanya penghematan jarak sebesar 359.97 km untuk pekan ganjil dan 506.61 km untuk  pekan  genap,  dengan  persentase  penghematan  di  pekan  ganjil  sebesar 49.12% dan 39.2% di pekan genap.

## UCAPAN TERIMA KASIH
Ucapan  terima  kasih  penulis  sampaikan  kepada  Yayasan  Pakuan  Siliwangi  atas Hibah Internal 2023, Lembaga Penelitian dan Pengabdian Masyarakat Universitas Pakuan,  PT.  Kobe  Boga  Utama  Cabang  Depok,  serta  seluruh  pihak  yang  telah membantu terlaksananya penelitian ini.

## DAFTAR PUSTAKA
Amozhita,  K.  K.,  Suyitno,  A.,  Mashuri, Menyelesaikan  Travelling  Salesman
Problem dengan Metode Dua Sisi Optimal  pada  PT.  Es Malindo Boyolali , UJM Unnes Journaf of Mathematics, 8 (1) (2019), 20-29.
Candrawati,  L.  G.  A.,  Kadyanan,  G.  A.  G.  A., Optimasi  Traveling  Salesman Problem  (TSP)  Untuk  Rute  Paket  Wisata  di  Bali  dengan  Algoritma Genetika , Jurnal Ilmu Komputer, 10 (1) (2018), 27-32.
Hidayati,  R.,  Guntoro,  I.,  Junianti,  S., Penggunaan  Metode  Simulated  Annealing untuk  Penyelesaian  Traveling  Salesman  Problem, CESS  (Journal  of Computer Engineering System and Science), 4 (2) (2019), 217-221.
Karimah,  S.,  Widodo,  A.  W.,  Cholissodin  I., Optimasi  Multiple  Travelling Salesman  Problem  pada  Pendistribusian  Air  Minum  Menggunakan Algoritme Genetika (Studi Kasus: UD. Tosa Malang) , Jurnal Pengembangan
Teknologi Informasi dan Ilmu Komputer, 1 (9) (2017), 849-858.
Penerapan Multiple Traveling Salesman Problem
Nurlaelasari,  E.,  Supriyadi,  Lenggana,  U.  T., Penerapan  Algoritma  Any  Colony Optimization  Menentukan  Nilai  Optimal  dalam  Memilih  Objek  Wisata Berbasis Android, Jurnal Simetris, 9 (1) (2018), 287-298.
Pitaloka,  D.  K.,  Koesdijarto,  R., Implementasi  Travelling  Salesman  Problem (TSP) dengan Algoritma Genetika menggunakan Peta  Leaflet  (Studi Kasus PT.  AMZ  Geoinfo  Solution  Surabaya) ,  Senakama:  Prosiding  Seminar Nasional  Karya  Mahasiswa  2022 , Universitas  17  Agustus  1945,  Surabaya, 2022, 767-776.
Rohman,  S.,  Zakaria,  L.,  Asmiati,  Nuryaman,  A., Optimasi  Travelling  Salesman Problem  dengan  Algoritma  Genetika  pada  Kasus  Pendistribusian  Barang PT. Pos Indonesia di Kota Bandar Lampung, Jurnal Matematika Integratif,
16 (1) (2020), 61-73.
Santosa,  I.  B.  D.  A.  N., Penyelesaian  Kasus  Asymmetric  Traveling  Salesman Problem untuk Meminimasi Jarak Tempuh dengan Menggunakan Algoritma Elephant Herding Optimization , [Skripsi] Universitas Katolik Parahyangan,
2017.
Saputra,  D.  W., Optimalisasi  Rute  Distribusi  Kurir  Menggunakan  Metode Traveling  Salesman  Problem  (Studi  Kasus:  JNE  Balige), G-Tech:  Jurnal Teknologi Terapan, 6 (2) (2022), 159-165.
Simbolon,  J.  P.,  Zarlis,  M., Penyelesaian  Masalah  TSP  pada  Rute  Kunjungan ATM  dengan  Pendekatan  Heuristic  (Tabu  Search), Jurnal  Riset  Sistem Informasi dan Teknik Informatika (JURASIK), 2 (1) (2017), 13-28.
Sumarsa, A., Widyastiti, M., Penerapan  Traveling Salesman Problem  with Time Windows  pada  Pendistribusian  Produk, Prosiding  Seminar  Nasional Pendidikan Matematika 2022 , Universitas Pattimura, Ambon, 2023, 1-6.