## RESEARCH ARTICLE

## Route  Determination  for  Distribution  by  Using  a Combination  of  Branch  and  Bound  Algorithm  and

## Cheapest Insertion Heuristic
Syamsuddin Mas’ud *
Department  of  Mathematics,  Faculty  of  Mathematics  and  Natural  Sciences, Universitas Negeri Makassar, Makassar, Indonesia
Abstract: This  paper  discusses  the  determination  of  the  LPG  Gas distribution  route  using  the  concept  of  the  Traveling  Salesman  Problem.  The research data is secondary data obtained from a previous study, where in that study,  the  generated  routes  had  different  starting  and  ending  points. However,  in  this  research,  the  sought-after  routes  are  those  with  the  same starting and ending points. Such routes are sought with the consideration that in  a  travel  route,  the  starting  and  ending  points  are  usually  the  same.  The Traveling  Salesman  Problem  method  used  in  determining  these  routes  is  the Branch and Bound algorithm combined with the Cheapest Insertion Heuristic. The distribution route obtained is v 1 – v 2 – v 6 – v 11 – v 10 – v 7 – v 9 – v 12 – v 13 – v 14 – v 13 – v 12 – v 9 – v 8 – v 4 – v 5 – v 4 – v 3 – v 2 – v 1 .
Keywords : Route, Distribution, Branch and Bound, Cheapest Insertion Heuristic

## 1. Pendahuluan
Penentuan  rute  seringkali  menjadi  topik  optimasi  yang  sering  dibahas  dalam  kaitannya dengan Traveling Salesman Problem. Secara umum ada, banyak algoritma yang dapat menjadi alternatif  pencarian  rute  terkait  Traveling  Salesman  Problem  (Taillard,  2023;  The  Traveling Salesman Problem, 2006). Salah satu yang paling sering digunakan adalah algoritma Dijkstra. Algoritma Dijkstra juga digunakan untuk pencarian rute terbaik pemadam kebakaran Kota Semarang  (Nggufron,  2019).  Terdapat  juga  pengembangan  algoritma  Dijkstra  yaitu algoritma  Weighted-Sum  Dijkstra  yang  penggunaannya  juga  untuk  penentuan  rute  terbaik (Widianto,  2021).  Algoritma  yang  sama,  yaitu  algoritma  Dijkstra  juga  digunakan  dalam menentukan solusi optimal pencarian jalur tercepat untuk mencari lokasi cafe di Bumiayu (Alifiani et al., 2021). Selain Dijkstra, terkadang juga digunakan Algoritma Prim. Algoritma Prim  digunakan  dalam  penentuan  lintasan  terpendek  dan  lintasan  tercepat  pada pendistribusian logistik Bulog Jawa Barat (Lusiani et al., 2020). Penerapan Minimum Spanning Tree  yaitu  algoritma  Prim  juga  digunakan  dalam  menentukan  rute  terpendek  distribusi naskah soal USBN di SMA Negeri se-Sleman (Rahmadi & Sandariria, 2023).
Selain algoritma Dijkstra dan Prim, dalam menyelesaikan permasalahan rute terkait Traveling Salesman Problem, terdapat juga algoritma Branch and Bound yang dapat dikatakan sebagai salah satu  pilihan  pertama.  Penerapan  algoritma  Branch  and  Bound  dalam  menentukan  jalur terpendek  untuk  melakukan pencarian penginapan dan hotel  di  Kota  Kendari  (Saputra  et al., n.d.). Optimalisasi rute distribusi produk menggunakan metode Traveling Salesman Problem yaitu  Branch  and  Bound  (Auliasari  et  al.,  2018).  Rute  pendistribusian  air  mineral  dalam kemasan  juga  menggunakan  algoritma  Branch  and  Bound  (Moriza  et  al.,  n.d.).  Penyelesaian
* Corresponding author: Syamsuddin Mas’ud, Mathematics, Mathematics and Natural Sciences, Universitas Negeri Makassar, Makassar, Indonesia
E-mail: syamsuddinm@unm.ac.id
Mas’ud, et.al., ARRUS Journal of Mathematics and Applied Science, Vol. 4, No.1 (2024) https://doi.org/10.35877/mathscience2636
asymmetric Travelling Salesman Problem juga dapat dilakukan dengan algoritma Branch and Bound (Nur & Rahadjeng, 2021).
Pada  penentuan  rute  menggunakan  algoritma  Dijkstra  ataupun  menggunakan  algoritma Prim,  umumnya  menghasilkan  rute  yang  titik  awal  dan  titik  akhirnya  tidak  sama.  Sebagai contoh, tulisan tentang pencarian rute terbaik pendistribusian BBM dari terminal BBM ke SPBU  wilayah  kota  medan  menggunakan  algoritma  Dijkstra  (Arif  &  Marbun,  2023)  dan tulisan  tentang  penentuan  rute  pendistribusian  gas  LPG  menggunakan  algoritma  Prim (Mas’ud,  2024) .  Meskipun  hasil  yang  diperoleh  pada  tulisan  pendisitribusian  dengan algoritma  Prim  ini (Mas’ud,  2024) lebih  optimal  (yakni  dengan  total  bobot  10,91) dibandingkan penggunaan algoritma Floyd Warshall dan algoritma Greedy (Ningrum et al., 2023)  (yakni  dengan  total  bobot  13.13),  namun  titik  awal  dan  titik  akhir  rute  tidak  sama. Tentu  saja  rute  yang  demikian  tidaklah  lazim  digunakan  karena  keumuman  dari pendistribusian, titik awal rute dan titik akhirnya adalah sama. Untuk itu, dalam penelitian ini, penulis akan mencari rute pendistribusian gas LPG dengan rute yang lazim yakni titik awal  dan  titik  akhir  rute  sama.  Penulis  memilih  algoritma  Branch  and  Bound  yang dikombinasikan  dengan  Cheapest  Insertion  Heuristic  untuk  mencari  rute  yang  diinginkan tersebut mengikuti apa yang telah dilakukan pada tulisan tentang penyelesaian asymmetric Travelling  Salesman  Problem  (Nur  &  Rahadjeng,  2021)  yang  berhasil  mendapatkan  rute perjalanan layanan jemput donasi LAZIS dengan titik awal dan titik akhir rute sama.

## 2. Metodologi Penelitian
Penelitian  ini  merupakan  penelitian  terapan  dengan  menggunakan  data  sekunder.  Data diperoleh  dari  tulisan  tentang  penentuan  rute  pendistribusian  gas  LPG  menggunakan algoritma  Floyd  Warshall  dan  algoritma  Greedy  (Ningrum  et  al.,  2023).  Data  tersebut meliputi  nama  lokasi,  jarak  antara  setiap  lokasi,  dan  waktu  perjalanannya  masing-masing. Penentuan rute yang diinginkan, dicari dengan menggunakan algoritma Branch and Bound dan Cheapest Insertion Heuristic yang dikombinasikan.
Penelitian  dimulai  dengan  mengumpulkan  data  yang  diperlukan  yakni  lokasi,  jarak,  dan waktu perjalanan dari tulisan tentang rute pendistribusian gas LPG (Mas’ud, 2024; Ningrum et  al.,  2023).  Selanjutnya  menggunakan  algoritma  Branch  and  Bound  dan  Cheapest  Insertion Heuristic  yang  dikombinasikan  (Nur  &  Rahadjeng,  2021)  untuk  menetukan  rute  yang diinginkan.  Berikut  ini  diberikan  langkah-langkah  dari  algoritma  Branch  and  Bound  dan Cheapest Insertion Heuristic yang dikombinasikan (Nur & Rahadjeng, 2021):
1) Menentukan matriks ( 𝐶 𝑖𝑗 ) berukuran n x n, dengan n adalah banyaknya titik yang akan dikunjungi. Matriks berisikan elemen jarak dari titik i ke titik j. Inisiasikan jarak dari titik i ke titik i dengan nilai ~ (tak hingga).
2) Identifikasi nilai terkecil pada tiap baris matriks dan kurangkan tiap baris dengan nilai terkecil yang telah teridentifikasi sebelumnya.
3) Kemudian  identifikasikan  nilai  terkecil  pada  tiap  kolom  matriks  dan  kurangkan  tiap olom dengan nilai terkecil yang telah teridentifikasi sebelumnya.
4) Jumlahkan  semua  nilai  terkecil  baris  dan  nilai  terkecil  kolom  pada  langkah  2  dan  3 sehingga dihasilkan nilai batas simpul akar C(R).
5) Rute dimulai dari titik awal dan dihubungkan dengan titik akhir.
6) Membuat subtur antara 2 titik. Subtur adalah rute perjalanan dari titik asal dan berakhir di titik asal dengan mengunjungi titik-titik yang hendak dituju.
7) Mengganti salah satu rute dengan kombinasi antar 2 titik, contohnya menyisipkan titik k yang belum termasuk anggota subtur pada rute (i,j) sehingga menjadi rute (i,k) dan rute (k,j), dengan hasil kombinasi adalah pilihan rute terkecil. Subtur terbaru menjadi:
C(R)+C(i,k)+C(k,j)-C(i,j)
C(R): nilai simpul akar, C(i,k): jarak dari titik i ke titik k, C(k,j): jarak dari titik k ke titik j,
Mas’ud, et.al., ARRUS Journal of Mathematics and Applied Science, Vol. 4, No.1 (2024) https://doi.org/10.35877/mathscience2636
C(i,j): jarak dari titik i ke titik j.
8) Ulangi langkah ke-7 hingga semua titik masuk dalam subtur, dan STOP.
3. Hasil dan Pembahasan
Terlebih dahulu, berikut disajikan data (Ningrum et al., 2023) yang diperlukan, yaitu lokasi pendistribusian dan representasi titiknya masing-masing dalam titik graf, pada Tabel 1.
Tabel 1. Daftar Lokasi Pendistribusian dan Representasi Titiknya
No  Lokasi Pendistribusian Representasi Titik pada Graf 1 PT Rama Manggala Gas v 1 2 PT Mayangkara LPG v 2 3 Jl Galunggung RT 03 RW 02 Sukorejo, Sukorejo v 3 4 Jl Mayang Tengah RT 02 RW 05 Sukorejo, Sukorejo v 4 5 Jl Mayang Tengah RT 03 RW 05 Sukorejo, Sukorejo v 5 6 Jl. Bakung Sukorejo, Sukorejo v 6 7 Jl Kaliporong, Pakunden, Sukorejo v 7 8 Jl. Bengawan Solo, Pakunden, Sukorejo v 8 9 PT Hari Putra Santosa Jaya SPBU no 54.66103 v 9 10  Jl. Mawar, Sukorejo, Sukorejo v 10 11  Toko Buwana v 11 12  Jl. Jati GG 1 No 27 RT 02 RW 12, Sukorejo, Sukorejo v 12 13  Jl. Jati No 65 RT 04 RW 12, Sukorejo, Sukorejo v 13 14  Jl. Jati RT 02 RW 14, Sukorejo, Sukorejo v14
Selanjutnya, dengan sumber  data  yang  sama  (Ningrum  et  al., 2023), berikut disajikan data jarak dan waktu tempuh antar titik graf dinyatakan pada Tabel 2.
Tabel 2. Jarak dan Waktu Tempuh Antar Lokasi Pasangan Titik Jarak (km) Waktu Tempuh (menit) 𝑣 1 − 𝑣 2 2,7 6 𝑣 2 − 𝑣 3 2,1 7 𝑣 2 − 𝑣 6 3,2 8 𝑣 2 − 𝑣 7 3 7 𝑣 2 − 𝑣 8 2,6 7 𝑣 3 − 𝑣 4 0,65 3 𝑣 4 − 𝑣 5 0,12 1 𝑣 3 − 𝑣 8 0,9 3 𝑣 5 − 𝑣 6 0,26 1 𝑣 5 − 𝑣 10 0,26 2 𝑣 6 − 𝑣 7 0,6 2 𝑣 7 − 𝑣 8 1,2 2 𝑣 8 − 𝑣 9 1,2 4 𝑣 8 − 𝑣 4 0,6 2 𝑣 7 − 𝑣 9 0,8 3 𝑣 7 − 𝑣 10 1,12 5 𝑣 7 − 𝑣 11 1,32 6 𝑣 11 − 𝑣 6 0,72 4 𝑣 6 − 𝑣 9 1,4 5 𝑣 9 − 𝑣 10 1,5 5 𝑣 4 − 𝑣 10 0,14 1
Mas’ud, et.al., ARRUS Journal of Mathematics and Applied Science, Vol. 4, No.1 (2024) https://doi.org/10.35877/mathscience2636
Pasangan Titik Jarak (km) Waktu Tempuh (menit) 𝑣 10 − 𝑣 11 0,2 1 𝑣 11 − 𝑣 12 1,2 4 𝑣 9 − 𝑣 12 1,2 5 𝑣 12 − 𝑣 13 0,35 1 𝑣 13 − 𝑣 14 0,6 1
Pencarian  rute  pendistribusian  gas  LPG  dilakukan  dengan  menjadikan  v 1 (PT  Rama Manggala  Gas)  sebagai  titik  awal  sekaligus  titik  akhir  pendistribusian  dengan  bentuk  graf (Mas’ud, 2024) disajikan pada Gambar 1.
Gambar 1. Graf Pendistribusian Gas LPG Tabel 3. Matriks Jarak antar Titik-Titik Graf
v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12 v 2 ~ 2.10 ~ ~ 3.20 3.00 2.60 ~ ~ ~ ~ v 3 2.10 ~ 0.65 ~ ~ ~ 0.90 ~ ~ ~ ~ v 4 ~ 0.65 ~ 0.12 ~ ~ 0.60 ~ 0.14 ~ ~ v 5 ~ ~ 0.12 ~ 0.26 ~ ~ ~ 0.26 ~ ~ v 6 3.20 ~ ~ 0.26 ~ 0.60 ~ 1.40 ~ 0.72 ~ v 7 3.00 ~ ~ ~ 0.60 ~ 1.20 0.80 1.12 1.32 ~ v 8 2.60 0.90 0.60 ~ ~ 1.20 ~ 1.20 ~ ~ ~ v 9 ~ ~ ~ ~ 1.40 0.80 1.20 ~ 1.50 ~ 1.20 v 10 ~ ~ 0.14 0.26 ~ 1.12 ~ 1.50 ~ 0.20 ~ v 11 ~ ~ ~ ~ 0.72 1.32 ~ ~ 0.20 ~ 1.20 v 12 ~ ~ ~ ~ ~ ~ ~ 1.20 ~ 1.20 ~
Berdasarkan Gambar 1 maka pencarian rute dilakukan dengan terlebih dahulu mengabaikan titik v 1 , v 13 , dan v 14 . Hal ini dilakukan karena rute pada titik tersebut tunggal sehingga jelas bahwa  rute  pada  sisi  yang  bersesuaian  dengan  ketiga  titik  mesti  dilalui  2  kali  sehingga algoritma diterapkan pada titik-titik selain ketiga titik tersebut. Setelah hasil rute diperoleh dari  algoritma,  kembali  dilakukan  penambahan  rute  yang  melibatkan  ketiga  titik  tersebut. Berikut  ini  akan  diberikan  langkah  demi  langkah  pencarian  rute  pendistribusian  dengan menggunakan  algoritma  Branch  and  Bound  dan  Cheapest  Insertion  Heuristic  yang dikombinasikan.
v 1 v 2 v 8 v 9 v 6 v 5 v 3 v 4 v 10 v 11 v 12 v 13 v14 v 7 2,7 2,6 1,2 1,2 0,35 0,6 1,2 0,2 0,14 0,65 2,1 0,9 0,6 0,26 0,72 1,5 1,4 0,8 1,12 0,26 0,12 0,6 3 3,2 1,32 1,2
Terlebih dahulu akan ditentukan matriks (C ij ) berukuran 11 x 11. Diperoleh matriks dalam bentuk Tabel 3.
Langkah  selanjutnya  yaitu  mengidentifikasi  nilai  terkecil  pada  tiap  baris  matriks  dan kurangkan tiap baris dengan nilai terkecil yang telah teridentifikasi sebelumnya berdasarkan data pada Tabel 3. Hasil yang diperoleh disajikan pada Tabel 4.
Tabel 4. Matriks Hasil Pengurangan Baris dari Matriks Jarak
v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12 v 2 ~ 0.00 ~ ~ 1.10 0.90 0.50 ~ ~ ~ ~ v 3 1.45 ~ 0.00 ~ ~ ~ 0.25 ~ ~ ~ ~ v 4 ~ 0.53 ~ 0.00 ~ ~ 0.48 ~ 0.02 ~ ~ v 5 ~ ~ 0.00 ~ 0.14 ~ ~ ~ 0.14 ~ ~ v 6 2.94 ~ ~ 0.00 ~ 0.34 ~ 1.14 ~ 0.46 ~ v 7 2.40 ~ ~ ~ 0.00 ~ 0.60 0.20 0.52 0.72 ~ v 8 2.00 0.30 0.00 ~ ~ 0.60 ~ 0.60 ~ ~ ~ v 9 ~ ~ ~ ~ 0.60 0.00 0.40 ~ 0.70 ~ 0.40 v 10 ~ ~ 0.00 0.12 ~ 0.98 ~ 1.36 ~ 0.06 ~ v 11 ~ ~ ~ ~ 0.52 1.12 ~ ~ 0.00 ~ 1.00 v 12 ~ ~ ~ ~ ~ ~ ~ 0.00 ~ 0.00 ~
Langkah  selanjutnya  yaitu  mengidentifikasi  nilai  terkecil  pada  tiap  kolom  matriks  dan kurangkan  tiap  kolom  dengan  nilai  terkecil  yang  telah  teridentifikasi  sebelumnya berdasarkan data pada Tabel 4. Hasil yang diperoleh disajikan pada Tabel 5.
Tabel 5. Matriks Hasil Pengurangan Kolom dari Matriks pada Tabel 4
v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12 v 2 ~ 0.00 ~ ~ 1.10 0.90 0.25 ~ ~ ~ ~ v 3 0.00 ~ 0.00 ~ ~ ~ 0.00 ~ ~ ~ ~ v 4 ~ 0.53 ~ 0.00 ~ ~ 0.23 ~ 0.02 ~ ~ v 5 ~ ~ 0.00 ~ 0.14 ~ ~ ~ 0.14 ~ ~ v 6 1.49 ~ ~ 0.00 ~ 0.34 ~ 1.14 ~ 0.46 ~ v 7 0.95 ~ ~ ~ 0.00 ~ 0.35 0.20 0.52 0.72 ~ v 8 0.55 0.30 0.00 ~ ~ 0.60 ~ 0.60 ~ ~ ~ v 9 ~ ~ ~ ~ 0.60 0.00 0.15 ~ 0.70 ~ 0.00 v 10 ~ ~ 0.00 0.12 ~ 0.98 ~ 1.36 ~ 0.06 ~ v 11 ~ ~ ~ ~ 0.52 1.12 ~ ~ 0.00 ~ 0.60 v 12 ~ ~ ~ ~ ~ ~ ~ 0.00 ~ 0.00 ~
Langkah selanjutnya yaitu jumlahkan semua nilai terkecil baris dan nilai terkecil kolom pada 2  langkah  sebelumnya,  sehingga  dihasilkan  C(R)  =  8.89  sebagai  nilai  batas  simpul  akar. Karena  titik  v 1 adalah  titik  awal  rute  dan  sekaligus  termasuk  titik  yang  diabaikan,  maka algoritma  dijalankan  dengan  menganggap  v 2 sebagai  titik  awal  dan  titik  akhir  pengganti. Alasan pemilihan v 2 adalah karena hanya titik ini yang bertetangga langsung dengan v 1 .
Langkah  selanjutnya,  setelah  menetapkan  v 2 sebagai  titik  awal  sekaligus  titik  akhir  untuk menjalankan algoritma, yaitu menetapkan subtur  antara  2  titik, dipilih  (v 2 ,v 3 )-(v 3 ,v 2 ) sebagai subtur awal. Dibentuk tabel untuk mengumpulkan hasil penyisipan titik-titik lain ke dalam setiap sisi subtur awal.
Berdasarkan  Tabel  6,  diperoleh  bahwa  bobot  terkecil  yakni  ketika  v8  yang  disisipkan sehingga  subtur  yang  baru  adalah  (v 2 ,v 8 )-(v 8 ,v 3 )-(v 3 ,v 2 ).  Karena  itu,  nilai  C(R)  menjadi  9.44
Mas’ud, et.al., ARRUS Journal of Mathematics and Applied Science, Vol. 4, No.1 (2024) https://doi.org/10.35877/mathscience2636
untuk  langkah  selanjutnya  dan  dilakukan  penyisipan  titik  pada  subtur  baru  (v 2 ,v 8 )-(v 8 ,v 3 )- (v 3 ,v 2 ). Proses dilanjutkan secara terus menerus sehingga diperoleh Tabel 7.
Tabel 6. Penyisipan pada Subtur Pertama Sisi Awal Sisi hasil sisipan Penambahan bobot sisipan Total bobot subtur (v 2 ,v 3 ) (v 2 ,v 4 )-(v 4 ,v 3 ) C(R)+C(v 2 ,v 4 )+C(v 4 ,v 3 )-C(v 2 ,v 3 ) ~ (v 2 ,v 3 ) (v 2 ,v 5 )-(v 5 ,v 3 ) C(R)+C(v 2 ,v 5 )+C(v 5 ,v 3 )-C(v 2 ,v 3 ) ~ (v 2 ,v 3 ) (v 2 ,v 6 )-(v 6 ,v 3 ) C(R)+C(v 2 ,v 6 )+C(v 6 ,v 3 )-C(v 2 ,v 3 ) ~ (v 2 ,v 3 ) (v 2 ,v 7 )-(v 7 ,v 3 ) C(R)+C(v 2 ,v 7 )+C(v 7 ,v 3 )-C(v2,v3) ~ (v 2 ,v 3 ) (v 2 ,v 8 )-(v 8 ,v 3 ) C(R)+C(v 2 ,v 8 )+C(v 8 ,v 3 )-C(v 2 ,v 3 ) 9.44 (v 2 ,v 3 ) (v 2 ,v 9 )-(v 9 ,v 3 ) C(R)+C(v 2 ,v 9 )+C(v 9 ,v 3 )-C(v 2 ,v 3 ) ~ (v 2 ,v 3 ) (v 2 ,v 10 )-(v 10 ,v 3 ) C(R)+C(v 2 ,v 10 )+C(v 10 ,v 3 )-C(v 2 ,v 3 ) ~ (v 2 ,v 3 ) (v 2 ,v 11 )-(v 11 ,v 3 ) C(R)+C(v 2 ,v 11 )+C(v 11 ,v 3 )-C(v 2 ,v 3 ) ~
(v 2 ,v 3 ) (v 2 ,v 12 )-(v 12 ,v 3 ) C(R)+C(v 2 ,v 12 )+C(v 12 ,v 3 )-C(v 2 ,v 3 ) ~ Tabel 7. Penyisipan pada Subtur Kedua Sisi Awal Sisi hasil sisipan Penambahan bobot sisipan Total bobot subtur (v 2 ,v 6 ) (v 2 ,v 5 )-(v 5 ,v 6 ) C(R)+C(v 2 ,v 5 )+C(v 5 ,v 6 )-C(v 2 ,v 6 ) ~
(v 2 ,v 6 ) (v 2 ,v 10 )-(v 10 ,v 6 ) C(R)+C(v 2 ,v 10 )+C(v 10 ,v 6 )-C(v 2 ,v 6 ) ~
(v 2 ,v 6 ) (v 2 ,v 12 )-(v 12 ,v 6 ) C(R)+C(v 2 ,v 12 )+C(v 12 ,v 6 )-C(v 2 ,v 6 ) ~
(v 6 ,v 11 ) (v 6 ,v 5 )-(v 5 ,v 11 ) C(R)+C(v 6 ,v 5 )+C(v 5 ,v 11 )-C(v 6 ,v 11 ) ~
(v 6 ,v 11 ) (v 6 ,v 10 )-(v 10 ,v 11 ) C(R)+C(v 6 ,v 10 )+C(v 10 ,v 11 )-C(v 6 ,v 11 ) ~
(v 6 ,v 11 ) (v 6 ,v 12 )-(v 12 ,v 11 ) C(R)+C(v 6 ,v 12 )+C(v 12 ,v 11 )-C(v 6 ,v 11 ) ~
(v 11 ,v 7 )
(v 11 ,v 5 )-(v 5 ,v 7 ) C(R)+C(v 11 ,v 5 )+C(v 5 ,v 7 )-C(v 11 ,v 7 ) ~
(v 11 ,v 7 ) (v 11 ,v 10 )-(v 10 ,v 7 )
C(R)+C(v 11 ,v 10 )+C(v 10 ,v 7 )-C(v 11 ,v 7 ) 12.31
(v 11 ,v 7 ) (v 11 ,v 12 )-(v 12 ,v 7 )
C(R)+C(v 11 ,v 12 )+C(v 12 ,v 7 )-C(v 11 ,v 7 ) ~
(v 7 ,v 9 ) (v 7 ,v 5 )-(v 5 ,v 9 ) C(R)+C(v 7 ,v 5 )+C(v 5 ,v 9 )-C(v 7 ,v 9 ) ~
(v 7 ,v 9 ) (v 7 ,v 10 )-(v 10 ,v 9 ) C(R)+C(v 7 ,v 10 )+C(v 10 ,v 9 )-C(v 7 ,v 9 ) 14.13
(v 7 ,v 9 ) (v 7 ,v 12 )-(v 12 ,v 9 ) C(R)+C(v 7 ,v 12 )+C(v 12 ,v 9 )-C(v 7 ,v 9 ) ~
(v 9 ,v 8 ) (v 9 ,v 5 )-(v 5 ,v 8 ) C(R)+C(v 9 ,v 5 )+C(v 5 ,v 8 )-C(v 9 ,v 8 ) ~
(v 9 ,v 8 ) (v 9 ,v 10 )-(v 10 ,v 8 ) C(R)+C(v 9 ,v 10 )+C(v 10 ,v 8 )-C(v 9 ,v 8 ) ~
(v 9 ,v 8 ) (v 9 ,v 12 )-(v 12 ,v 8 ) C(R)+C(v 9 ,v 12 )+C(v 12 ,v 8 )-C(v 9 ,v 8 ) ~
(v 8 ,v 4 ) (v 8 ,v 5 )-(v 5 ,v 4 ) C(R)+C(v 8 ,v 5 )+C(v 5 ,v 4 )-C(v 8 ,v 4 ) ~
(v 8 ,v 4 ) (v 8 ,v 10 )-(v 10 ,v 4 ) C(R)+C(v 8 ,v 10 )+C(v 10 ,v 4 )-C(v 8 ,v 4 ) ~
(v 8 ,v 4 ) (v 8 ,v 12 )-(v 12 ,v 4 ) C(R)+C(v 8 ,v 12 )+C(v 12 ,v 4 )-C(v 8 ,v 4 ) ~
(v 4 ,v 3 ) (v 4 ,v 5 )-(v 5 ,v 3 ) C(R)+C(v 4 ,v 5 )+C(v 5 ,v 3 )-C(v 4 ,v 3 ) ~
(v 4 ,v 3 ) (v 4 ,v 10 )-(v 10 ,v 3 ) C(R)+C(v 4 ,v 10 )+C(v 10 ,v 3 )-C(v 4 ,v 3 ) ~
(v 4 ,v 3 ) (v 4 ,v 12 )-(v 12 ,v 3 ) C(R)+C(v 4 ,v 12 )+C(v 12 ,v 3 )-C(v 4 ,v 3 ) ~
(v 3 ,v 2 ) (v 3 ,v 5 )-(v 5 ,v 2 ) C(R)+C(v 3 ,v 5 )+C(v 5 ,v 2 )-C(v 3 ,v 2 )
~
(v 3 ,v 2 ) (v 3 ,v 10 )-(v 10 ,v 2 ) C(R)+C(v 3 ,v 10 )+C(v 10 ,v 2 )-C(v 3 ,v 2 )
~
(v 3 ,v 2 ) (v 3 ,v 12 )-(v 12 ,v 2 ) C(R)+C(v 3 ,v 12 )+C(v 12 ,v 2 )-C(v 3 ,v 2 ) ~
Berdasarkan  Tabel  7,  diperoleh  bahwa  bobot  terkecil  yakni  ketika  v10  yang  disisipkan sehingga subtur yang baru adalah (v 2 ,v 6 )-(v 6 ,v 11 )-(v 11 ,v 10 )-(v 10 ,v 7 )-(v 7 ,v 9 )-(v 9 ,v 8 )-(v 8 ,v 4 )-(v 4 ,v 3 )-(v 3 ,v 2 ). Karena  itu  nilai  C(R)  menjadi  12.45  untuk  langkah  selanjutnya  dan  dilakukan  penyisipan titik pada subtur baru (v 2 ,v 6 )-(v 6 ,v 11 )-(v 11 ,v 10 )-(v 10 ,v 7 )-(v 7 ,v 9 )-(v 9 ,v 8 )-(v 8 ,v 4 )-(v 4 ,v 3 )-(v 3 ,v 2 ). Penyisipan pada subtur baru ini tidak menghasilkan subtur lagi sehingga disimpulkan bahwa rute inilah
Mas’ud, et.al., ARRUS Journal of Mathematics and Applied Science, Vol. 4, No.1 (2024) https://doi.org/10.35877/mathscience2636
rute  yang  diinginkan.  Adapun  titik  v 5 dan  v 12 yang  belum  masuk  pada  subtur  akan ditambahkan dengan memilih  sisi  berbobot paling  minimal. Setelah itu titik  v 1 ,  v 13 , dan v14 juga ditambahkan dengan memilih sisi berbobot paling minimal, sehingga diperoleh rute v 1 – v 2 – v 6 – v 11 – v 10 – v 7 – v 9 – v 12 – v 13 – v14 – v 13 – v 12 – v 9 – v 8 – v 4 – v 5 – v 4 – v 3 – v 2 – v 1 . Rute ini merupakan  rute  yang  lebih  lazim  untuk  digunakan  dalam  melakukan  pendistribusian  gas LPG  dibandingkan  dengan  rute  yang  diperoleh  pada  penelitian  menggunakan  algoritma Prim (Mas’ud,  2024) dan  menggunakan  algoritma  algoritma  Floyd  Warshall  maupun algoritma Greedy (Ningrum et al., 2023) sebelumnya. Hal ini karena dengan menggunakan Algoritma  Branch  and  Bound  dan  Cheapest  Insertion  Heuristic  yang  dikombinasikan,  diperoleh rute dengan titik awal dan titik akhir yang sama.

## 4. Kesimpulan
Penentuan  rute  menggunakan  Algoritma  Branch  and  Bound  dan  Cheapest  Insertion  Heuristic yang  dikombinasikan,  menghasilkan  rute  yang  lazim  dalam  rute  pendistribusian  yaitu dengan titik awal dan titik akhir rute yang sama. Adapun rute yang diperoleh yaitu v 1 – v 2 – v 6 – v 11 – v 10 – v 7 – v 9 – v 12 – v 13 – v14 – v 13 – v 12 – v 9 – v 8 – v 4 – v 5 – v 4 – v 3 – v 2 – v 1 atau PT Rama Manggala Gas - PT Mayangkara LPG - Jl. Bakung Sukorejo, Sukorejo - Toko Buwana - Jl. Mawar, Sukorejo, Sukorejo  -  Jl  Kaliporong, Pakunden, Sukorejo  -  PT  Hari  Putra  Santosa Jaya SPBU no 54.66103 - Jl. Jati GG 1 No 27 RT 02 RW 12, Sukorejo, Sukorejo - Jl. Jati No 65 RT 04 RW 12, Sukorejo, Sukorejo - Jl. Jati RT 02 RW 14, Sukorejo, Sukorejo - Jl. Jati No 65 RT 04 RW 12, Sukorejo, Sukorejo - Jl. Jati No 65 RT 04 RW 12, Sukorejo, Sukorejo - PT Hari Putra Santosa Jaya SPBU no 54.66103 - Jl. Bengawan Solo, Pakunden, Sukorejo - Jl  Mayang  Tengah RT  02  RW  05  Sukorejo,  Sukorejo  -  Jl  Mayang  Tengah  RT  03  RW  05 Sukorejo, Sukorejo - Jl Mayang Tengah RT 02 RW 05 Sukorejo, Sukorejo - Jl Galunggung RT 03 RW 02 Sukorejo, Sukorejo - PT Mayangkara LPG - PT Rama Manggala Gas.

## References
Alifiani,  I.,  Abdillah,  M.  A.,  &  Saliha,  I.  (2021).  Solusi  Optimal  Pencarian  Jalur  Tercepat Menggunakan Algoritma Dijkstra Untuk Mencari Lokasi Cafe Di Bumiayu.  Jurnal Derivat:
Jurnal Matematika dan Pendidikan Matematika, 8(2), 140 – 148.
https://doi.org/10.31316/j.derivat.v8i2.1899
Arif, M., & Marbun, J. P. (2023). Pencarian Rute Terbaik Pendistribusian BBM dari Terminal BBM ke  SPBU  Wilayah  Kota  Medan  Menggunakan  Algoritma  Dijkstra  dengan  Logika  Fuzzy sebagai Penentu Bobot pada Graf.  FARABI: Jurnal Matematika dan Pendidikan Matematika, 6(1), 10 – 19. https://doi.org/10.47662/farabi.v6i1.428
Auliasari,  K.,  Kertaningtyas,  M.,  &  Basuki,  D.  W.  L.  (2018).  Optimalisasi  Rute  Distribusi  Produk Menggunakan Metode Traveling Salesman Problem. Jurnal Sains, Teknologi dan Industri, 16(1), 15. https://doi.org/10.24014/sitekin.v16i1.6109
Lusiani, A., Sartika, E., Binarto, A., & Habinuddin, E. (2020). Compatible Graphs on Traffic Lights Waiting  Time  Optimization:  Proceedings  of  the  International  Seminar  of  Science  and  Applied Technology (ISSAT 2020). International Seminar of Science and Applied Technology (ISSAT 2020), Bandung, Indonesia. https://doi.org/10.2991/aer.k.201221.077
Mas’ud,  S.  (2024). Penentuan  Rute  Pendistribusian  Gas  LPG  Menggunakan  Algoritma  Prim  dengan Optimalisasi Melalui Pergantian Sisi. 7.
Moriza,  D.,  Adiyanto,  H.,  &  Nurdiansyah,  Y.  (n.d.).  Rute  Pendistribusian  Air  Mineral  dalam  Kemasan Menggunakan Metode Nearest Neighbour dan Branch and Bound di PT. Agronesia BMC.
Nggufron, N. (2019). Pencarian Rute Terbaik Pemadam Kebakaran Kota Semarang Menggunakan Algoritma Dijkstra dengan Logika Fuzzy sebagai Penentu Bobot pada Graf.
Ningrum,  E.  R.,  Sanwidi,  A.,  Akbarita,  R.,  &  Qomaruddin,  M.  N.  H.  (2023).  Optimasi  Rute Pendistribusian Gas Elpiji Menggunakan Algoritma Floyd Warshall Dan Algoritma Greedy.
Jurnal Ilmiah Matematika dan Terapan, 20(1), 1 – 14.
https://doi.org/10.22487/2540766X.2023.v20.i1.15568
Mas’ud, et.al., ARRUS Journal of Mathematics and Applied Science, Vol. 4, No.1 (2024) https://doi.org/10.35877/mathscience2636
Nur,  M.  A.  S.,  &  Rahadjeng,  B.  (2021).  Kombinasi  Algoritma  Branch  and  Bound  dan  Cheapest
Insertion  Heuristic  dalam  Menyelesaikan  Asymmetric  Travelling  Salesman  Problem. MATHunesa: Jurnal Ilmiah Matematika, 9(2), 351 – 358.
https://doi.org/10.26740/mathunesa.v9n2.p351-358
Rahmadi,  D.,  &  Sandariria,  H.  (2023).  Penerapan  Minimum  Spanning  Tree  dalam  Menentukan  Rute Terpendek Distribusi Naskah Soal USBN di SMA Negeri se- Sleman.
Saputra, R. H., Nangi, J., & Aksara, L. B. (n.d.). Penerapan Algoritma Branch and Bound dalam Menentukan Jalur Terpendek untuk Melakukan Pencarian Penginapan dan Hotel Di Kota Kendari.
Taillard,  É.  D.  (2023).  Design  of  Heuristic  Algorithms  for  Hard  Optimization:  With  Python  Codes  for  the Travelling Salesman Problem. Springer International Publishing. https://doi.org/10.1007/978- 3-031-13714-3
The traveling salesman problem: A computational study. (2006). Princeton university press.
Widianto,  T.  (2021).  Optimalisasi  Metode  Weighted-Sum  Dijkstra  Algorithm  untuk  Menentukan Rute  Terbaik  yang  Sesuai  dengan  Kebutuhan.  Jurnal  CoreIT:  Jurnal  Hasil  Penelitian  Ilmu Komputer dan Teknologi Informasi, 7(1), 13. https://doi.org/10.24014/coreit.v7i1.11625