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

## PENENTUAN RUTE OPTIMAL PENDISTRIBUSIAN BARANG PADA PT. RAJAWALI NUSINDO CABANG PEMATANGSIANTAR DENGAN MENGGUNAKAN ALGORITMA BRANCH AND BOUND

## DETERMINATION OF THE OPTIMAL ROUTES OF GOODS DISTRIBUTION IN PT. RAJAWALI NUSINDO PEMATANGSIANTAR BRANCH USING BRANCH AND BOUND ALGORITHM

## RIFKA SAPRIANI GIRSANG¹, DEBORA EXAUDI SIRAIT², RANI FARIDA SINAGA³
¹²³Program Studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas HKBP Nommensen Pematangsiantar, Indonesia
Email : rifkagirsang13@gmail.com¹, debora.sirait@uhnp.ac.id², rani.sinaga@uhnp.ac.id³

## Abstrak
PT.  Rajawali  Nusindo  Cabang  Pematangsiantar  adalah  salah  satu  perusahaan  BUMN  yang  bergerak  di  bidang distribusi dan perdagangan obat-obatan, alat kesehatan dan penjualan umum. Pada saat mendistribusikan obat- obatan ke pelanggan rumah sakit dan pelanggan apotek yang terletak di kota Pematangsiantar perusahaan kurang memperhatikan  rute  dan  total  jarak  yang  dilalui. Travelling  Salesmen  Problem diilustrasikan  dengan  seorang salesmen yang mengantar barang ke berbagai tempat hanya sekali lalu kembali ke titik awal. Dalam menyelesaikan permasalahan Trvaelling Salesmen Problem salah satu algoritma pada matematika terapan yang dapat digunakan adalah  algoritma branch  and  bound .  Algoritma branch  and  bound berkerja  dengan    merepresentasikan  matriks jarak kedalam bentuk graf lalu mereduksi baris dan kolom matriks jarak  dan membentuk pohon ruang status. Total jarak tempuh yang biasa digunakan perusahaan  untuk pelanggan rumah sakit adalah 18,9 Km, waktu tempuh 28,5 menit  dengan biaya  bahan  bakar  Rp.  19.000 dan  pelanggan  apotek  19,97  Km,  waktu  tempuh  30 menit  dengan biaya bahan bakar Rp. 20.000 sedangkan menggunakan algoritma branch and bound diperoleh total  jarak tempuh pelanggan  rumah  sakit  sebesar  16,1  Km,  waktu  tempuh  24  menit  dengan  biaya  bahan  bakar  Rp.  16.000dan pelanggan  apotek  sebesar  14,07  Km,  waktu  tempuh  21  menit  dengan  biaya  bahan  bakar  Rp.14.000.  Maka diperoleh selisih total jarak, waktu tempuh dan biaya bahan bakar berturut turut sebesar untuk pelanggan rumah sakit sebesar 2,8 Km, 5 menit, Rp.3.0000 dan pelanggan apotek sebesar 5,9 Km, 9 menit, dan Rp. 6.000.
Kata Kunci : Travelling Salesmen Problem, Graf, Rute Terpendek, Algoritma Branch and Bound, Matematika

## Abstract
PT. Rajawali Nusindo Pematangsiantar Branch is a state-owned company engaged in the distribution and trading of medicines, medical devices and general sales. When distributing medicines to hospital customers and pharmacy customers located in Pematangsiantar city, the company pays little attention to the route and total distance traveled. The Traveling Salesmen Problem is illustrated with a salesman who delivers goods to various places only once and then  returns  to  the  starting  point.  In  solving  the  Trvaelling  Salesmen  Problem,  one  of  the  algorithms  in  applied mathematics  that  can  be  used  is  the  branch  and  bound  algorithm.  The  branch  and  bound  algorithm  works  by representing the distance matrix in the form of a graph and then reducing the rows and columns of the distance matrix and forming a status space tree. The total distance used by the company for hospital customers is 18.9 Km, travel time is 28.5 minutes and the fuel cost is Rp. 19,000 and 19,97 Km pharmacy customers, travel time is 30 minutes with a fuel cost of Rp. 20,000 while using the branch and bound algorithm, the total distance traveled by hospital customers is 16.1 Km, travel time is 24 minutes and fuel costs are Rp. 16,000 and pharmacy customers of 14.07 Km, travel time is 21 minutes and the fuel cost is Rp. 14,000. Then the difference in total distance, travel time and fuel costs is obtained respectively for home customers.
Key Words : Travelling Salesmen Problem , Graph,  Shortest route , Branch and Bound Algorithm, Mathematics

## Pendahuluan
Salah satu aktivitas perusahaan adalah mendistribusikan barang kepada tiap pelanggan. Barang yang  didistribusikan  oleh  PT.  Rajawali  Nusindo  yaitu  obat –  obatan,  alat  kesehatan,  dan  penjualan umum.  Barang  tersebut  didistribusikan  ke  rumah  sakit,  apotek,  toko  kelontong  dan  lain –  lain  yang terletak di daerah Pematangsiantar, Simalungun, Nias Barat, Nias Selatan, Nias Utara, Gunung Sitoli, Serdang  Bedagai,  Mandailing  Natal,  Padang  Lawas,  Padang  Sidimpuan,  Tapanuli  Selatan,  Tapanuli Utara,  Tapanuli  Tengah,    Humbang  Hasundutan,  Samosir,  dan  Toba.  Pada  pendistribusian  barang
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301
berupa obat, perusahaan melakukan pendataan terhadap pembelian yang dilakukan oleh pelanggan, lalu  mendistribusikannya  tanpa  mempertimbangkan  total  jarak  tempuh  yang  mengakibatkan  waktu distribusi menjadi kurang optimal dan biaya untuk bahan bakar saat pengantaran barang bertambah. Dan dalam proses sistem transportasi pengiriman produk tersebut, pemilihan rute tercepat merupakan hal yang penting. Karena dapat mengoptimalkan waktu pengiriman, dan juga berdampak kepada biaya bahan  bakar  saat  pengantaran  barang  berkurang.  Travelling  Salesman  Problem    bertujuan  untuk menentukan  rute  perjalanan  seorang  salesman.  Rute  ini  bermula  dari  asal  (kota),  lalu  mengunjungi sejumlah  kota  yang  ditentukan  hanya  sekali,  dan  kembali  ke  kota  asal    sehingga  total  jarak  yang ditempuh  oleh  salesmen  tersebut  optimal[1] . Graf  digunakan  untuk  memilih  lintasan  terpendek.  Dan setiap  jalurnya  memiliki  bobotnya  masing-masing  yang    menyatakan  jarak  antar  tempat,  waktu pengiriman, ongkos pengiriman dan lain sebagainya. Mencari lintasan terpendek tersebut dimulai dari simpul awal ke simpul tujuan, dan bertujuan untuk mendapatkan lintasan yang memiliki jumlah bobot yang minimum. Ada berbagai jenis grafik seperti graf sederhana, graf  tidak sederhana, graf  berarah, dan  graf  tidak  berarah.  Graf  adalah  struktur  diskrit  yang  terdiri  dari  sekumpulan  objek  yang  disebut simpul  dan  himpunan    sisi  yang  menghubungkan  simpul-simpul  tersebut.  Graf  digunakan  untuk mewakili objek-objek ini[2].
Travelling  Salesman  Problem dapat  dibagi  menjadi  dua  bagian: Symmetric  Traveling  Salesman Problem dan Asymmetric Traveling Salesman Problem . Dalam masalah Symmetric Traveling Salesman Problem , jarak dari kota A menuju kota B sama dengan jarak dari kota B menuju kota A. Akan tetapi pada masalah Asymmetric Traveling Salesman Problem , jarak  dari kota A menuju kota B tidak sama dengan  jarak  dari  kota  B  menuju  kota  A[3].Pada  penelitian  ini,  jenis TSP yang  digunakan  adalah Asymmetric Traveling Salesman Problem dimana jarak dari pelanggan A ke pelanggan B tidak sama dengan jarak dari pelanggan B ke pelanggan A. Dalam penelitian terdahulu tentang pencarian distribusi terpendek  menggunakan  algoritma  yang  ada,  algoritma Branch  and  Bound menghasilkan  rute  dan waktu yang lebih optimal dibandingkan dengan algoritma yang lain[4-7]. Algoritma branch and bound menggunakan  pendekatan  enumerasi  dengan  menonaktifkan  pencarian  yang  tidak  meyakinkan. Pencarian biaya minimum atau pencarian nilai minimum adalah teknik yang digunakan dalam algoritma branch and bound untuk menemukan solusi dengan menghitung nilai (biaya) setiap node. Node dengan nilai terendah memiliki probabilitas tertinggi untuk mencapai solusi[8].

## Metode Penelitian
Pada penelitian ini jenis penelitian yang diguanakan adalah penelitian kuantitatif. Metode penelitian kuantitatif  adalah  jenis  penelitian  spesifikasinya  sistematis,  dipikirkan  dengan  baik  dan  terstruktur dengan  jelas  dari  pembentukan  sampai  desain  penelitiannya.  Data  yang  digunakan  adalah  data pelanggan rumah sakit dan pelanggan apotek di PT. Rajawali Nusindo Cabang Pematangisantar, rute yang digunakan oleh perusahaan saat mengantarkan barang ke tiap pelanggan rumah sakit dan apotek, dan  kecepatan  yang  diguanakan  oleh  pengantar  barang  yaitu  40  Km/Jam.Untuk  menghasilkan  rute terpendek  sehingga  diperoleh  waktu  tempuh  dan  bahan  bakar  yang  optimal  digunakan  metode Travelling Salesmen Problem dengan algoritma branch and bound . Ada pun tahapan penyelesaiannya yaitu sebagai berikut :
1.  Mempersiapkan data yang akan diolah.
2.  Membentuk data berupa jarak yang diperoleh dari Google Maps kedalam bentuk matriks.
3.  Merepresentasikan matriks kedalam bentuk graf.
4.  Menentukan total jarak tempuh dari rute  yang digunakan perusahaan saat pengantaran barang ke pelanggan rumah sakit dan pelanggan apotek.
5.  Mengolah data matriks dengan algoritma branch and bound , dengan melakukan reduksi baris dan kolom sampai diperoleh rute dengan total jarak yang paling minimum.
6.  Menentukan rute tercepat, total jarak dari rute tersebut, waktu dan bahan bakar yang digunakan untuk menempuh rute tercepat.
7.  Menentukan perbandingan antara rute, total jarak, waktu tempuh dan penggunaan bahan bakar yang digunakan perusahaan dengan rute optimal, waktu tempuh dan penggunaan bahan bakar yang diperoleh dengan menggunakan algoritma branch and bound .
8.  Data telah selesai diolah dengan algoritma branch and bound .
Hasil Penelitian dan Pembahasan Algoritma Branch and Bound
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301
Penyelesaian permasalahan Travelling Salesmen Problem pasti membutuhkan sebuah algoritma, salah satu algoritma yang dapat digunakan adalah algoritma branch and bound. Algoritma Branch and Bound merupakan  algoritma  yang  membagi  permasalahan  menjadi  sub  masalah  lebih  kecil  yang mengarah ke solusi dengan pencabangan (branching) dan melakukan pembatasan (bounding) untuk mencapai  solusi  optimasi[9].  Pada  intinya  algoritma Branch  and  Bound adalah  pendekatan  untuk “mencabangkan dan membatasi”. Pencabangan (branching) adalah proses membentuk permasalahan kedalam bentuk struktur pohon pencarian (search tree) yang berguna untuk membangun semua cabang pohon menuju solusi, sedangkan pada proses pembatasan dilakukan dengan menghitung estimasi nilai (cost) simpul  dengan  memperhatikan  batas  atas (upper  bound) dan  batas  bawah (lower  bound). Misakan 𝑐(𝑖) merupakan  nilai  estimasi  lintasana  minimum  dari  simpul 𝑖 kesimpul  tujuan,  maka 𝑐(𝑖) menyatakan  batas (bound) pencarian  solusi  dari  simpul 𝑖 .  Sehingga  terdapat  fungsi  heuritsik  utuk menghitung nilai estimasi sebagai berikut:
𝑐(𝑖) = 𝑓(𝑖) + 𝑔(𝑖)
dengan : 𝑐(𝑖) = nilai simpul 𝑖
𝑓(𝑖) = nilai lintasan dari simpul awal ke simpul 𝑖
𝑔(𝑖) = nilai untuk mencapai simpul tujuan dari simpul 𝑖
Pada permasalahan yang lebih kompleks, digambarkan dengan matriks tereduksi dari matriks jarak antar titik yang dibentuk dari graf G. Matriks tereduksi adalah matriks yang tiap kolom dan tiap barisnya mengandung paling sedikit satu buah angka 0 dan elemen-elemen lainnya bernilai non-negatif[10].
Dari  data  yang  diperoleh,  akan  dicari  rute  pengantaran  barang  yang  optimal  dari  PT.  Rajawali Nusindo ke pelanggan rumah sakit dan pelanggan apotek menggunakan algoritma branch and bound dengan tahapan sebagai berikut :

## Pelanggan Rumah Sakit
Gambar Graf
Keterangan gambar :
1 = PT. Rajawali Nusindo Cabang Pematangsiantar
6 = Rumah Sakit Harapan
2 = Dinas Kesehatan Kota Pematangsiantar
7 = Rumah Sakit Tiara
3 = Rumah Sakit Vita Insani
8 = Rumah Sakit Tentara 4 = Rumah Sakit Horas Insani 9 = Rumah Sakit Rasyida
5 = Rumah Sakit Djasamen Saragih

## Matriks Jarak Pelanggan Rumah Sakit
Jarak antar pelanggan di representasikan kedalam matriks 𝑀 9×9 dimana elemen 𝑀 𝑖𝑗 adalah jarak dari i ke j, sedangkan i dan j titik pada graf. Matriks ini merupakan matriks asimetris karena jarak dari i ke j tidak sama dengan jarak j ke i.
Gambar 1. Graf Pelanggan Rumah
Sakit
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301

## Hasil Pengolahan Dengan Algoritma Branch and Bound
Dalam penyelesaian menggunakan algoritma branch and bound terlebih dahulu melakukan reduksi matriks ketetanggaan yang memuat jarak antar tiap pelanggan. Reduksi baris dilakukan dengan cara mengurangkan semua elemen pada baris tertentu sehingga terdapat setidaknya satu nilai 0 pada baris tersebut .
1 2 3 4 5 6 7 8 9 1 0 3,4 3,7 0,8 3,5 5,6 5,2 5,5 6,4 2 3,6 0 0,55  2,8 0,1 2,8 1,8 2 2,6 3 3,1  0,65 0 2,3  0,75  3,2 2,4 2,7 3,3 4 0,8 2,6 2,9 0 2,7 4,8 4,4 4,7 4,9 5 3,6 0,8 0,55  2,8 0 2,8 1,7 2 2,6 6 5,9 2,9 3,2 5 3 0 2,2 1,9 3,6 7 5,1 2,4 2 4,2 2,5 2,2 0 0,9 1,3 8 5,3 2,6 2,3 4,5 2,7 1,9 0,9 0 1,9 9 5,8 3 2,6 4,9 3,1 3,2 1,3 1,9 0
Reduksi  baris  dilakukan  dengan  mengurangi  seluruh  elemen  pada  baris  tertentu  sehingga  setiap elemen memiliki setidaknya satu nilai 0 pada baris tersebut .
1 2 3 4 5
6 7 8 9 1 0 2,6 2,9 0 2,7 4,8 4,4 4,7 5,6 2 3,5 0 0,45 2,7 0 2,7 1,7 1,9 2,5 3 2,45 0 0 1,65  0,1  2,55  1,75  2,05  2,65 4 0 1,8 2,1 0 1,9 4 3,6 3,9 4,1 5 3,05  0,25 0 2,25 0 2,25  1,15  1,45  2,05 6 4 1 1,3 3,1 1,1 0 0,3 0 1,7 7 4,2 1,5 1,1 3,3 1,6 1,3 0 0 0,4 8 4,4 1,7 1,4 3,6 1,8 1 0 0 1 9 4,5 1,7 1,3 3,6 1,8 1,9 0 0,6 0
Tabel  matriks  dihasilkan  dari  pengurangan  tiap  baris  dengan  nilai  terkecil  pada  elemen  baris tersebut. Baris ke-1 dikurangi dengan 0,8 , baris ke-2 dikurangi dengan 0,1, baris ke-1 dikurangi dengan 0,65, baris ke-4 dikurangi dengan 0,8, baris ke-5 dikurangi dengan 0,55, baris ke-6 dikurangi dengan 1,9, baris ke-7 dikurangi dengan 0,9, baris ke-8 dikurangi dengan 0,9 dan baris ke-9 dikurangi dengan 1,3.Reduksi kolom dilakukan dengan cara mengurangi seluruh elemen pada kolom tertentu sehingga terdapat setidaknya satu nilai 0 pada baris tersebut.
Tabel 1 Tabel Matriks Jarak Pelanggan Rumah Sakit
Tabel 2. Tabel Hasil Reduksi Baris Matriks
Gambar 2. Matriks Jarak Pelanggan Rumah Sakit
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301
Rifka Sapriani Girsang, Debora Exaudi Sirait, Rani Farida Sinaga Penentuan Rute Optimal Pendistribuasian Barang pada PT. Rajawali Nusindo Cabang Pematangsiantar dengan Menggunakan Algoritma Branch and Bound
1 2 3 4 5 6 7 8 9 1 0 2,6 2,9 0 2,7 3,8 4,4 4,7 5,2 2 3,5 0 0,45 2,7 0 1,7 1,7 1,9 2,1 3 2,45 0 0 1,65  0,1  1,55  1,75  2,05  2,25 4 0 1,8 2,1 0 1,9 3 3,6 3,9 3,7 5 3,05  0,25 0 2,25 0 1,25  1,15  1,45  1,65 6 4 1 1,3 3,1 1,1 0 0,3 0 1,3 7 4,2 1,5 1,1 3,3 1,6 0,3 0 0 0 8 4,4 1,7 1,4 3,6 1,8 0 0 0 0,6 9 4,5 1,7 1,3 3,6 1,8 0,9 0 0,6 0
Matriks  diatas  diperoleh  dari  pengurangan  tiap  kolom  dengan  nilai  terkecil  pada  elemen  kolom tersebut.  Kolom  ke-6  dikurangi  dengan  1, dan  kolom  ke-9  dikurangi  dengan  0,4.  Selanjutnya  proses reduksi  akan  menghasilkan  nilai  batas  simpul  akar  atau ĉ(𝑟𝑜𝑜𝑡) yang  dihasilkan  dari  penjumlahan elemen pengurangan pada proses reduksi. Maka,
ĉ(𝑟𝑜𝑜𝑡) = 0,8 + 0,1 + 0,65 + 0,8 + 0,55 + 1,9 + 0,9 + 0,9 + 1,3 + 1 + 0,4 = 9,3
Kemudian, dihitung simpul-simpul lain pada pohon ruang status dengan proses reduksi matriks pada tiap ekspansi titiknya maka akan mengahasilkan pohon ruang status sebagai berikut:
Tabel 3. Tabel Hasil Reduksi Kolom Matriks
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301
Maka didapatkan rute optimal pada pelanggan rumah sakit adalah PT. Rajawali Nusindo Cabang Pematangsiantar-Rumah  Sakit  Horas  Insani-Dinas  Kesehatan  Kota  Pematangsiantar-Rumah  Sakit Djasamen  Saragih-Rumah  Sakit  Harapan-Rumah  Sakit  Tentara-Rumah  Sakit  Tiara-Rumah  Sakit Rasyida-Rumah  Sakit  Vita  Insani  lalu  kemudian  berakhir  di  PT.  Rajawali  Nusindo  Cabang Pematangsiantar dengan total jarak 16,1 Km

## Waktu Tempuh
Waktu  tempuh  adalah  waktu  yang  diperlukan  oleh  kendaraan  untuk  mengantarkan    barang  ke pelanggan.  Digunakan  kecepatan  kendaraan  40km/jam.  Rumus  untuk  menghitung  waktu  tempuh sebagai berikut:
Waktu Tempuh = 𝑑𝑖𝑗 𝑣 × 60 menit
= 16,1 40 𝑘𝑚/𝑗𝑎𝑚 × 60 menit = 24,15 menit

## Bahan Bakar
Bahan bakar yang digunakan oleh kendaraan pengantar barang adalah jenis bahan bakar pertalite dimana  1  liter  pertalite  bisa  menempuh  jarak  10  km.  Harga  1  liter  pertalite  adalah  Rp.10.000.  Maka banyaknya bahan bakar yang digunakan saat pengantaran barang yaitu sebegai berikut : Bahan bakar yang digunakan 1,61 liter maka biaya bahan bakarnya sebesar Rp.16.100.

## Pelanggan Apotek Gambar Graf
Keterengan Gambar: 1 = PT. Rajawali Nusindo Cabang Pematangsiantar
9 = Apotek Pemuda
2 = Apotek Bersama
10 = Apotek Care
3 = Apotek Sinta Farma 2
11 = Apotek Bersatu
4 = Apotek Rama
12 = Apotek Plus+
5 = Apotek THS
13 = Apotek Megumi
6 = Apotek Salido
14 = Apotek Makmur
7 = Apotek Sejahtera
15 = Apotek KF85
8 = Apotek Matahari
Gambar 3. Pohon Ruang Status Pelanggan Rumah Sakit
Gambar 4. Graf Pelanggan Apotek
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301

## Matriks Jarak Pelanggan Apotek
Jarak antar pelanggan di representasikan kedalam matriks 𝑀 15×15 dimana elemen 𝑀 𝑖𝑗 adalah jarak dari i ke j, sedangkan i dan j titik pada graf. Matriks ini merupakan matriks asimetris karena jarak dari i ke j tidak sama dengan jarak j ke i.

## Hasil Pengolahan Dengan Algoritma Branch and Bound
Dalam  penyelesaian  menggunakan  algoritma Branch  and  Bound terlebih  dahulu  melakukan reduksi matriks ketetanggaan yang memuat jarak antar tiap pelanggan. Reduksi baris dilakukan dengan cara mengurangi  seluruh  elemen  pada  baris  tertentu  sehingga  terdapat setidaknya  satu  nilai  0  pada baris tersebut .
Tabel  matriks  diatas  diperoleh  dari    pengurangan  tiap  baris  dengan  nilai  terkecil  pada  elemen  baris tersebut. Baris ke-1 dikurangi dengan 2,3 , baris ke-2 dikurangi dengan 0,6, baris ke-3 dikurangi dengan 0,01, baris ke-4 dikurangi dengan 1,1, baris ke-5 dikurangi dengan 0,5, baris ke-6 dikurangi dengan 0,4, baris ke-7 dikurangi dengan 0,15, baris ke-8 dikurangi dengan 0,2 dan baris ke-9 dikurangi dengan 0,35, baris ke-10 dikurangi dengan 1,2, baris ke-11 dikurangi dengan 0,35, baris ke-12 dikurangi dengan 0,3, baris ke-13 dikurangi dengan 1,2, baris ke-14 dikurangi dengan 1,2, baris ke-15 dikurangi dengan 0,4. Maka, dihasilkan matriks dibawah ini :
Tabel 4. Tabel Matriks Jarak Pelanggan Apotek
Tabel 5. Tabel Hasil Reduksi Baris Matriks
Gambar 5. Matriks Jarak Pelanggan Apotek
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301
Tiap kolom dikurangkan dengan nilai terkecil pada elemen kolom tersebut. Kolom ke-1 dikurangkan dengan  1,2,  kolom  ke-10  dikurangi  dengan  0,1,  kolom  ke-12  dikurangi  dengan  0,01.  Maka,  akan dihasilkan matriks dibawah ini :
Proses reduksi selanjutnya akan dihasilkan nilai batas simpul akar atau ĉ(𝑟𝑜𝑜𝑡) yang diperoleh dari proses penjumlahan dan pengurangan elemen pada proses reduksi. Maka,dihasilkan nilai simpul akar sebagai berikut : ĉ(𝑟𝑜𝑜𝑡) = 10,26 + 1,31 = 11,57
Kemudian,  dihitung  simpul-simpul  lain  pada  pohon  ruang  status  dengan  melakukan  reduksi baris dan reduksi kolom maka akan mengahasilkan pohon ruang status sebagai berikut :
Tabel 6. Tabel Hasil Reduksi Kolom Matriks
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301
Maka  didapatkan  rute  optimal  pada  pelanggan  apotek  adalah  PT.  Rajawali  Nusindo  Cabang Pematangsiantar-Apotek Rama-Apotek Pemuda-Apotek Sejahtera-Apotek Bersama-Apotek Matahari- Apotek  Plus-Apotek  Bersatu-Apotek  KF85-Apotek  Sinta  Farma  2-Apotek  Salido-Apotek  THS-Apotek Megumi-Apotek Makmur-Apotek Care lalu kembali ke PT. Rajawali Nusindo Cabang Pematangsiantar dengan total jarak 14,07 Km

## Waktu Tempuh
Waktu  tempuh  adalah  waktu  yang  diperlukan  oleh  kendaraan  untuk  mengantarkan    barang  ke pelanggan.  Digunakan  kecepatan  kendaraan  40km/jam.  Rumus  untuk  menghitung  waktu  tempuh sebagai berikut:
Waktu Tempuh = 𝑑𝑖𝑗 𝑣 × 60 menit = 14,07 40 𝑘𝑚/𝑗𝑎𝑚 × 60 menit = 21,105 menit

## Bahan Bakar
Bahan bakar yang digunakan oleh kendaraan pengantar barang adalah jenis bahan bakar pertalite dimana  1  liter  pertalite  bisa  menempuh  jarak  10  km.  Harga  1  liter  pertalite  adalah  Rp.10.000.  Maka banyaknya bahan bakar yang digunakan saat pengantaran barang yaitu sebegai berikut : Bahan bakar yang digunakan 1,407 liter maka biaya bahan bakarnya sebesar Rp.14.070.
Maka, dari diperoleh hasil pengoptimalan sebagai berikut :
Setelah menggunakan algoritma branch and bound rute yang diperoleh  menghasilkan  total jarak yang  lebih kecil dibandingkan dengan total jarak jika menggunakan rute yang biasa digunakan oleh perusahaan. Maka perbandingan menggunakan  rute perusahaan  dengan rute yang diperoleh dari algoritma branch and bound terdapat pada tabel dibawah ini :
Gambar 6. Pohon Ruang Status Pelanggan Apotek
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301

## Pelanggan Rumah Sakit
Pada  tabel  dibawah  ini,  terdapat  hasil  dari  pengolahan  rute  yang  digunakan  perusahaan  saat mengantarkan barang berupa obat-obatan ke pelanggan rumah sakit dan rute yang diperoleh setelah menggunakan algoritma branch and bound.
Rute Total Jarak Waktu Tempuh Penggunaan Bahan Bakar Biaya Bahan Bakar Rute Perusahaan 1,4,2,5,7,6,9, 8,7,3,1 18,9 Km 28,5 menit 1,9 Liter Rp. 19.000 Rute Optimal Branch and Bound 1,4,2,5,6,8,7, 9,3,1 16,1 Km 24 menit 1,61 Liter Rp. 16.100

## Pelanggan Apotek
Pada  tabel  dibawah  ini,  terdapat  hasil  dari  pengolahan  rute  yang  digunakan  perusahaan  saat mengantarkan  barang  berupa  obat-obatan  ke  pelanggan  apotek  dan  rute  yang  diperoleh  setelah menggunakan algoritma branch and bound.
Rute Total Jarak Waktu Tempuh Pengguna an Bahan Bakar Biaya Bahan Bakar Rute Perusahaan 1,4,9,7,2,15,3,6,5,10,13, 14,11,8,12,1 19,97 Km 30 menit 2 Liter Rp. 20.000 Rute Optimal Branch and Bound 1,4,9,7,2,8,12,11,15,3,6, 5,13,14,10,1 14,07 Km 21 menit 1,407 Liter Rp. 14.070
Diperoleh total jarak rute yang dihasilkan melalui perhitungan dengan algoritma branch and bound lebih  kecil  atau  lebih  optimal    dibandingankan  dengan  total  jarak  rute  perusahaan.  Waktu pendistribusian  yang  digunakan  dalam  penelitian  ini  adalah  waktu  perjalanan  yang  dibutuhkan  oleh karyawan pengantar barang saat mengantarkan barang ke rumah sakit ataupun apotik yang berada di kota  Pematangsiantar.  Untuk  menentukan  waktu  pendistribusian  adalah  dengan  rumus  waktu  sama dengan total jarak dibagi dengan kecepatan kendaraan yang digunakan oleh pengantar barang. Dalam waktu  pengantar  barang  juga  menjadi  lebih  optimal  apabila  menggunakan  rute  yang  di  peroleh  dari perhitungan algoritma branch and bound. Jika rute yang digunakan saat pengantaran barang optimal maka, waktu tempuh, banyaknya penggunaan bahan bakar dan biaya bahan bakar yang dikeluarkan akan berkurang.
Rute  optimal  yang  diperoleh  dalam  pengantaran  barang  kepada  pelanggan  rumah  sakit  adalah sebagai  berikut  diawali  keberangkatan  dari  PT.  Rajawali  Nusindo  Cabang  Pematangsiantar-Rumah Sakit  Horas  Insani-Dinas  Kesehatan  Kota  Pematangsiantar-Rumah  Sakit  Djasamen  Saragih-Rumah Sakit Harapan-Rumah Sakit Tentara-Rumah Sakit Tiara-Rumah Sakit Rasyida-Rumah Sakit Vita Insani lalu kemudian berakhir di PT. Rajawali Nusindo Cabang Pematangsiantar. Rute optimal yang diperoleh dalam pengantaran barang kepada pelanggan apotek adalah sebagai berikut dimulai dari PT. Rajawali Nusindo Cabang Pematangsiantar-Apotek Rama-Apotek Pemuda-Apotek Sejahtera-Apotek Bersama- Apotek  Matahari-Apotek  Plus-Apotek  Bersatu-Apotek  KF85-Apotek  Sinta  Farma  2-  Apotek  Salido- Apotek  THS-Apotek  Megumi-Apotek  Makmur-Apotek  Care  lalu  kembali  ke  PT.  Rajawali  Nusindo Cabang  Pematangsiantar.  Sesuai  dengan  permasalahan Travelling  Salesmen  Problem dimana perjalanan diawali dari suatu tempat lalu mengunjungi beberapa tempat lainnya tepat sekali kemudian diakhir akan kembali ke tempat awal.
Tabel 7. Tabel Hasil Rute Perusahaan Dengan Rute Optimal Untuk Pelanggan Rumah Sakit
Tabel 8. Tabel Hasil Rute Perusahaan Dengan Rute Optimal Untuk Pelanggan Apotek
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585 Hal : 416 – 426 DOI : https://doi.org/10.36987/jpms.v8i2.3301
Rifka Sapriani Girsang, Debora Exaudi Sirait, Rani Farida Sinaga Penentuan Rute Optimal Pendistribuasian Barang pada PT. Rajawali Nusindo Cabang Pematangsiantar dengan Menggunakan Algoritma Branch and Bound

## Kesimpulan
Berdasarkan  hasil  penelitian  dan  pembahasan,  maka  kesimpulan  yang  didapatkan  adalah  sebagai berikut :
1.  Rute  optimal  yang  diperoleh  untuk  pengantaran  barang  kepada  pelanggan  rumah  sakit  adalah sebagai berikut diawali keberangkatan dari PT. Rajawali Nusindo Cabang Pematangsiantar-Rumah Sakit  Horas  Insani-Dinas  Kesehatan  Kota  Pematangsiantar-Rumah  Sakit  Djasamen  Saragih- Rumah  Sakit  Harapan-Rumah  Sakit  Tentara-Rumah  Sakit  Tiara-Rumah  Sakit  Rasyida-Rumah Sakit Vita Insani lalu kemudian berakhir di PT. Rajawali Nusindo Cabang Pematangsiantar. Rute optimal untuk pengantaran barang kepada pelanggan apotek adalah sebagai berikut dimulai dari PT. Rajawali Nusindo Cabang Pematangsiantar-Apotek Rama-Apotek Pemuda-Apotek Sejahtera- Apotek Bersama-Apotek Matahari-Apotek Plus-Apotek Bersatu-Apotek KF85-Apotek Sinta Farma 2-Apotek  Salido-Apotek  THS-Apotek  Megumi-Apotek  Makmur-Apotek  Care  lalu  kembali  ke  PT. Rajawali Nusindo Cabang Pematangsiantar.
2.  Total jarak tempuh rute perusahaan untuk pelanggan rumah sakit 18,9 Km sedangkan rute optimal 16,1 Km selisih yang diperoleh 2,8 Km. Untuk pelanggan apotek total jarak tempuh rute perusahaan 19,97 Km sedangkan rute optimal 14,07 Km selisih yang diperoleh 5,9 Km.
3.  Untuk  menempuh  total  jarak  rute  perusahaan  untuk  pelanggan  rumah  sakit  diperlukan  waktu 29 menit, sedangkan rute optimal dibutuhkan waktu 24 menit, maka selisih waktunya adalah 5 menit. Untuk menempuh total jarak rute perusahaan untuk pelanggan apotek diperlukan waktu 30 menit, sedangkan rute optimal dibutuhkan waktu 21 menit, maka selisih waktunya adalah 9 menit.
4.  Untuk menempuh total jarak rute perusahaan pelanggan rumah sakit dibutuhkan 1,9 liter dengan harga  Rp. 19.000,  sedangkan  rute  optimal  dibutuhkan  1,61  liter  dengan  harga  Rp.  16.100  maka selisihnya  adalah  Rp.  3.000  untuk  setiap  pengantaran.  Untuk  pelanggan  apotek  dengan  rute perusahaan dibutuhkan 2 liter dengan harga Rp. 20.000 sedangkan rute optimal dibutuhkan 14,07 liter dengan harga Rp. 14.070 maka selisihnya adalah Rp. 6.000 untuk setiap pengantaran.

## Daftar Pustaka
[1] Gutin, G  & Punnen, A.  2004, The Traveling Salesman Problem and Its Variations . Kluwer Academic Publisher, London, Inggris.
[2] Wijaya, A. 2009. Matematika Diskrit . Bandung : Politeknik Telkom
[3] Greco, Frederio. 2008. Travelling Salesmen Problem . Rijeka: InTech.
[4] Desparaja, C., Gumelar, R.F. and Anggraeni, N.F. (2020) ‘Pendistribusian Produk Kartu Seluler untuk Alternatif Rute Terpendek Menggunakan Metode Branch and Bound di PT. T’, Jurnal Teknik: Media Pengembangan Ilmu dan Aplikasi Teknik , 19(1), p. 40. doi:10.26874/jt.vol19no01.145.
[5] Ichwani, M.R. and Suyitno, A. (2019) ‘Penggunaan Algoritma Branch and Bound Pada OptimasiRute Pendistribusian Air Minum Dalam’, Joournal of Mathematics , 4(1), pp. 30 –37
[6] Moriza, D., Adiyanto, H. and Nurdiansyah, Y. (2016) ‘Rute Pendistribusian Air Mineral Dalam Kemasan Menggunakan Metode Nearest Neighbour dan Branch and Bound Di PT Agronesia BMC’, Reka Integra Itenas , 4(2), pp. 195 –205. Available at: https://ejurnal.itenas.ac.id/index.php/rekaintegra/article/view/1101.
[7] Mursy, A.A.L. et al. (2019) ‘Menentukan Rute Terpendek Pendistribusian Bahan Bangunan oleh PT. Sadar Jaya Manunggal Mataram Menggunakan Algoritma Branch and Bound’, Eigen Mathematics Journal , 2(1), pp. 54 –60. doi:10.29303/emj.v1i1.24.
[8] Eko Budi Purwanto. 2008. Perancangan dan Analisis Algoritma . Yogyakarta: Graha Ilmu.
[9] Margiyani, S. et al. (2014) ‘Aplikasi Algoritma Branch and Bound Untuk Optimasi Jalur Pemadam Kebakaran Kota Yogyakarta’, 3(1), pp. 59–66.
[10] Ichwani, M.R. and Suyitno, A. (2019) ‘Penggunaan Algoritma Branch and Bound Pada Optimasi Rute Pendistribusian Air Minum Dalam’, Joournal of Mathematics , 4(1), pp. 30 –37.