Go-Integratif : Jurnal Teknik Sistem dan Industri  Vol. 01, No.01, (November 2020) 69–79
Penentuan Rute Distribusi Menggunakan Model Integer Linear Programming dengan Metode Branch and Bound
Gratia Melina Sari, Rainisa Maini Heryanto * , Santoso Program Studi Teknik Industri, Universitas Kristen Maranatha Jl. Prof. drg. Surya Sumantri MPH No. 65, Bandung 40164

## Abstrak
Biaya  distribusi  merupakan  biaya  yang  dapat  diminimalisasi  perusahaan.  Biaya  distribusi dalam jaringan distribusi memiliki kontribusi 10% sampai 20% dari biaya akhir barang. Salah satu  cara  untuk  meminimalisasi  biaya  distribusi  adalah  menentukan  rute  distribusi  yang optimal  yang  memberikan  total  biaya  minimum.  Penelitian  ini  membahas  penentuan  rute distribusi  menggunakan  model Integer  Linear  Programming untuk  menyelesaikan  masalah Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). Metode yang digunakan untuk  memecahkan  masalah  adalah Branch  and  Bound dengan  bantuan  MATLAB.  Model matematis yang digunakan adalah model matematis total biaya perjalanan. Studi kasus yang digunakan dalam perhitungan adalah PT XYZ, perusahaan manufaktur cat yang melakukan pendistribusian  produk  dari  gudang  ke  konsumen.  Saat  ini,  kebijakan  pemesanan  dan pengiriman perusahaan membuat biaya distribusi tidak efisien dan terjadi gagal pengiriman. Penelitian  ini  memberikan  2  skenario  usulan  pengiriman.  Pada  skenario  1,  pengiriman dilakukan  sesuai  dengan  kebijakan pada perusahaan saat ini dengan mencari biaya optimal. Pada  skenario  2,  permintaan  akan  dikumpulkan  pada  hari  Jumat  dan  pengiriman  akan dilakukan pada minggu berikutnya. Dari hasil perhitungan didapatkan total biaya per bulan pada rute aktual perusahaan adalah Rp. 1.349.053,49 sedangkan skenario 1 memberikan hasil Rp.  1.067.207,73  (penghematan  20,89%)  dan  skenario  2  memberikan  hasil  Rp.  602.105,21 (penghematan 55,37%).
Kata kunci: Biaya; Branch  and Bound ; CVRPTW; Distribusi ; Integer Linear Programming ; Rute

## Abstract
Distribution costs are costs that could be minimized by the company. Distribution cost in distribution network contributes 10% to 20% of the final cost of products. One of the ways to minimize distribution costs is to determine the optimal distribution route that provides minimum total costs. This research study about route determination using integer linear programming  model  in  solving  the  problem  of  CVRPTW.  Method  that  used  to  solve  the problem is Branch and Bound with the support of MATLAB software. The mathematical model  used  was  total  travelling  cost.  Case  study  in  this  research  is  PT  XYZ,  a  paint manufacturing  company  that  distributes  product  from  warehouse  to  several  customers. Currently, order and delivery company’s policies make inefficiency in distribution costs and delivery  failures  occur.  This  study  gives  2  proposed  delivery  scenario.  In  first  scenario , delivery was carried out according to the current system policies in the company by looking for optimal costs. In second scenario, demand was collected on Friday and deliveries were made at the following week. From the calculation results, the total cost per month generated
by  the  actual  route  is  IDR.  1,349,053.49,  first  scenario  is  IDR.  1,067,207.73  (20.89% saving), and second scenario is IDR. 602,105.21 (55.37% saving).
Keywords: Branch  and  Bound;  Cost;  CVRPTW;  Distribution;  Integer  Linear  Programming; Route

## Pendahuluan
Kegiatan  distribusi  menjadi  salah  satu  hal  yang  harus  diperhatikan  oleh  perusahaan karena  kegiatan  ini  dapat  mempengaruhi  biaya  akhir  barang.  Biaya  distribusi  dalam jaringan distribusi memiliki kontribusi 10% sampai 20% dari biaya akhir barang [1]. Oleh karena itu, biaya distribusi harus dapat diminimalisasi oleh perusahaan. Faktor-faktor yang  mempengaruhi  kegiatan  distribusi  dapat  berupa  kapasitas  yang  tersedia, banyaknya  permintaan  konsumen,  dan ketepatan waktu  distribusi.  Kegiatan distribusi juga dapat mempengaruhi kepuasan konsumen. Setiap konsumen berharap barang yang dipesan bisa sampai dengan tepat waktu, kondisi barang yang baik, dan jumlahnya sesuai dengan pesanan. Proses distribusi memiliki peran penting dalam sebuah jaringan bisnis, baik itu untuk konsumen maupun untuk kepentingan perusahaan [2].
Salah  satu  cara  yang  dapat  dilakukan  untuk  meminimalisasi  biaya  distribusi  adalah penentuan  rute  distribusi  yang  optimal.  Penentuan  rute  distribusi  akan  menentukan lamanya waktu yang diperlukan dan biaya yang harus dikeluarkan perusahaan [3]. Studi kasus yang digunakan dalam penelitian ini adalah PT XYZ, perusahaan manufaktur yang bergerak di bidang paint industry and chemical construction . Dalam kegiatan distribusi, perusahaan melakukan  pendistribusian  barang  dari gudang  bahan jadi (gudang pusat) ke beberapa lokasi tujuan seperti retailer , distributor, dan industri property .
Pada  saat  ini,  waktu  kegiatan  distribusi  belum  sesuai  dengan  harapan  perusahaan, dimana perusahaan menginginkan waktu pengiriman barang sesuai dengan waktu yang dialokasikan  dan  tidak  ada  yang  gagal  kirim.  Perusahaan  pernah  mengalami  masalah gagal  kirim  karena  konsumen  yang  dituju  sudah  tutup.  Selain  itu,  kebijakan  yang diterapkan perusahaan saat ini membuat biaya distribusi menjadi kurang efisien karena dalam satu minggu, konsumen yang sama dapat dikunjungi lebih dari satu kali oleh supir jika  konsumen  tersebut  sering  melakukan  pemesanan.  Metode  penentuan  rute  pada perusahaan  juga  masih  bersifat  impulsif  karena  rute  pengiriman  barang  saat  ini ditentukan sesuai dengan keinginan supir.

## Studi Pustaka

## Supply Chain Management (SCM)
SCM merupakan pengelolaan rantai siklus yang lengkap mulai dari bahan mentah dari berbagai supplier , dilanjutkan dengan kegiatan operasional di perusahaan, dan berlanjut dengan pendistribusian hingga sampai ke tangan konsumen [4]. Supply chain melibatkan seluruh bagian, baik secara langsung atau tidak langsung, untuk memenuhi permintaan konsumen.  Rantai  pasokan  tidak  hanya  berkaitan  dengan  manufaktur  dan  pemasok, tetapi juga melibatkan transportasi, gudang, retailer , dan pelanggan itu sendiri. Tujuan dari supply  chain yaitu  untuk  memaksimalkan  keseluruhan  nilai.  Keseluruhan value supply  chain tersebut  adalah  perbedaan  di  antara  nilai  dari  produk  akhir  terhadap pelanggan  dan  upaya  rantai  pasokan  dalam  memenuhi  permintaan  [5].  Distribusi merupakan suatu proses penyampaian barang atau jasa dari produsen ke konsumen dan
para  pemakai,  sewaktu  dan  dimana  barang  atau  jasa  tersebut  diperlukan. Agar  suatu kegiatan  penyaluran  barang  dapat  berjalan  dengan  baik,  maka  para  pemakai  saluran pemasaran harus mampu melakukan sejumlah tugas penting, yaitu; penelitian, promosi, kontak, penyelarasan, negoisasi, distribusi fisik, pembiayaan, dan pengambilan resiko [6].

## Vehicle Routing Problem (VRP)
VRP  pertama  kali  diperkenalkan  oleh  Dantzig  dan  Ramser  [7]  dan  semenjak  itu  telah dipelajari secara  luas. VRP sebenarnya merupakan perkembangan atau perluasan dari Travelling  Salesman  Problem (TSP).  VRP  merupakan  sebuah  cara  pencarian  atas penggunaan  yang  efisien  dari  sejumlah  kendaraan  yang  harus  melakukan  perjalanan untuk  mengunjungi  sejumlah  tempat  untuk  mengantar  dan  menjemput  orang  atau barang. Tujuan umum dari VRP yaitu mengantarkan barang kepada pelanggan dengan biaya minimum melalui rute kendaraan yang berangkat dari depot dan kembali ke depot. Pada umumnya fungsi tujuan dari permasalahan VRP adalah meminimalisasi total jarak yang  ditempuh  oleh  kendaraan  serta  meminimalisasi  jumlah  kendaraan  yang  akan digunakan. Selain itu, fungsi tujuan lain yang dapat ditambahkan yaitu seperti rentang waktu penyelesaian antar kendaraan, ataupun jenis fungsi tujuan lain sesuai kebutuhan dan karakteristik dari masing-masing permasalahan [8].
Terdapat beberapa jenis VRP yang tergantung pada jumlah faktor pembatas dan tujuan yang  akan  dicapai.  Pembatas  yang  paling  umum  digunakan  yaitu  jarak  dan  waktu. Berdasarkan  faktor  pembatasnya,  VRP  terbagi  menjadi  beberapa  jenis,  di  antaranya adalah Capacited  Vehicle  Routing  Problem (CVRP)  dimana  kendaraan  yang  memiliki keterbatasan  daya  angkut  (kapasitas) barang yang  harus  diantarkan  ke  suatu  tempat. Jenis  lain  dari  VRP  adalah Vehicle  Routing  Problem  with  Time  Windows (VRPTW) dimana setiap konsumen yang dilayani oleh kendaraan memiliki batas waktu menerima pelayanan.  Kombinasi  dari  CVRP  dan  VRPTW  adalah Capacitated  Vehicle  Routing Problem with Time Windows (CVRPTW) yang bertujuan untuk membentuk rute optimal untuk memenuhi permintaan konsumen yang dilakukan secara delivery dengan kendala kapasitas dan time windows .
Ada beberapa metode yang dapat digunakan untuk memecahkan masalah VRP yaitu metode eksak, metode heuristik, dan metode metaheuristik [9]. Ketiga metode mempunyai pendekatan yang berbeda  dalam  pencarian solusi. Metode eksak adalah metode yang mencari solusi dari seluruh ruang solusi yang ada sehingga dapat memberikan solusi yang optimal. Metode heuristik akan menyelesaikan masalah yang didasarkan pada  konsep trial and  error tetapi mengikuti langkah-langkah yang disusun secara sistematis untuk menghasilkan solusi.

## Linear Programming dan Branch and Bound
Linear  programming merupakan  teknik  optimisasi  yang  digunakan  dalam  pemecahan masalah  dalam  mengalokasikan  variabel-variabel  untuk  mencapai  fungsi  tujuan (minimum/maksimum).  Dalam  model linear  programming dikenal  dua  macam  fungsi, yaitu  fungsi  objektif  ( objective  function )  dan  fungsi  kendala  ( constraint  function ).  Pada model linear programming terdapat bentuk model yang lebih khusus seperti integer linear programming yang merupakan sebuah model pemrograman linear bilangan bulat yang dapat menghasilkan solusi dengan nilai-nilai baik integer maupun non-integer .
Metode Branch and Bound pertama kali diperkenalkan oleh Land dan Doig (1960).  Ide dasarnya  adalah  untuk  membagi  daerah  solusi feasible menjadi  daerah  solusi feasible yang lebih kecil. Metode Branch and bound merupakan suatu algoritma yang digunakan
dalam  permasalahan  optimisasi.  Pencarian  solusi  pada  algoritma  ini  dimulai  dengan menjabarkan  kandidat  solusi  yang  akan  dicabangkan  menggunakan  pohon  pencarian ( search  tree) dimana  setiap  simpul  menggambarkan  kemungkinan  solusi.  Simpul  yang lebih  kecil  ini  kemudian  dapat  dievaluasi  secara  sistematis  sampai  solusi  terbaik ditemukan.

## Metode Penelitian
Dalam penelitian ini, model matematis yang digunakan mengacu pada referensi tentang VRP dan penerapan model matematis dalam industri [10] dengan dilakukannya beberapa modifikasi yaitu penambahan indeks periode dan beberapa fungsi lain. Model matematis dibuat  dengan  mengidentifikasi  faktor  apa  saja  yang  berpengaruh  terhadap  variabel keputusan.
Beberapa asumsi yang digunakan dalam membuat model permasalahan CVRPTW, yaitu jika  jumlah  permintaan  pada  suatu  periode  melebihi  kapasitas  kendaraan,  maka kelebihannya  akan  dikirimkan  pada  kendaraan  berikutnya,  jika  waktu  tempuh  pada suatu periode melebihi waktu tutup konsumen, maka pengiriman akan dilakukan dengan beberapa  kendaraan,  tingkat  kemacetan  untuk  setiap  periode  diasumsikan  sama sehingga waktu tempuh untuk setiap periode sama, dan kegiatan istirahat dilakukan di tempat yang searah dengan tempat tujuan berikutnya.

## Indeks, Parameter, dan Variabel Keputusan
Indeks: i = node (posisi) awal j = node (posisi) tujuan k = kendaraan
p
= periode pengiriman
Parameter: N = total lokasi yang diteliti (pusat dan konsumen)
K
= total jumlah kendaraan yang tersedia
P
= total periode pengiriman d ij = jarak yang ditempuh dari node i ke j cb = biaya bahan bakar
ck
= konsumsi bahan bakar kendaraan
cl 0j = biaya tol dari gudang ke konsumen awal cl i0 = biaya tol dari konsumen akhir ke gudang M ip = jumlah permintaan di node i pada periode ke p Y ikp =   1, jika node i dilayani oleh kendaraan k pada periode p 0, jika node i tidak dilayani oleh kendaraan k pada periode p Q kp = kapasitas kendaraan k pada periode p SS ikp = waktu node i mulai dilayani oleh kendaraan k pada periode p a = jam buka perusahaan b = jam tutup perusahaan AT ikp = waktu kendaraan k sampai ke node i pada periode p AT jkp = waktu kendaraan k sampai ke node j pada periode p ST ikp = waktu pelayanan (unloading) di node i oleh kendaraan k pada periode p m = bilangan bulat besar TW kp = jam kerja tersedia pada kendaraan k untuk periode p

## Variabel Keputusan:
X ijkp =    1, jika kendaraan k dibebankan dari node i ke j pada periode p 0, jika kendaraan k tidak dibebankan dari node i ke j pada periode p
Persamaan Matematis Fungsi Tujuan dan Fungsi Pembatas
0 0 0 0 1 1 ( ) * * * N N K P ij ijkp j i i j k p j i F X Min d X cb ck cl cl      
                               
 * X ijkp (1)
Persamaan  1  menunjukkan  fungsi  tujuan  dari  penelitian  ini  yaitu  menentukan  rute distribusi  barang  yang  menghasilkan  biaya  terkecil.  Adapun  komponen  biaya  yang digunakan  yaitu  biaya  perjalanan  yang  berhubungan  dengan  jarak  tempuh  dan  biaya bahan  bakar  kendaraan  dalam  pendistribusian  barang,  serta  biaya  tol  dari  gudang  ke konsumen pertama dan dari konsumen terakhir ke gudang.
Fungsi pembatas ditentukan sebagai berikut:
1. Total  jumlah  barang  yang  dibawa  tidak  melebihi  kapasitas  kendaraan  ditunjukkan pada persamaan 2 berikut ini:
1 * N ip ikp kp i M Y Q
   , untuk k = {1, …, 3} ; p = {1, 2, …, 17} (2)
2. Jumlah  kendaraan  yang  berangkat  dan  kembali  ke  pusat  (node  0)  tidak  melebihi jumlah kendaraan yang tersedia ditunjukkan pada persamaan 3 berikut ini:
1 K ikp k Y K    , untuk i = 0 ; p = {1, 2, ..., 17}
(3)
3. Setiap  kendaraan  hanya  bisa  mengunjungi  node  (konsumen)  satu  kali  ditunjukkan pada persaman 4 berikut ini:
1 1 K ikp k Y    , untuk i = {1, 2, ..., 45} ; p = {1, 2, …, 17} (4)
4. Pengaturan time windows ditunjukkan pada persamaan 5 sampai dengan persamaan 10 berikut ini:
Waktu memulai pelayanan (SS ikp ) lebih besar dari jam buka perusahaan (a) dan lebih kecil dari jam tutup perusahaan (b) untuk semua node dan periode.
a ≤ SS ikp ≤ b , untuk i = {1, 2, ..., 45}; k = {1, ..., 3}; p = {1, 2, ..., 17} (5) Waktu sampai di node ke-i (AT ikp ) lebih besar dari jam buka konsumen (a) untuk semua kendaraan dan periode
AT ikp ≥ a , untuk i = {1, 2, ..., 45}; k = {1, …, 3}; p = {1, 2, ..., 17} (6)
Waktu memulai pelayanan (SS ikp ) sama dengan waktu sampai di node i (AT ikp ) untuk semua konsumen, kendaraan dan periode.
SS ikp = AT ikp , untuk i = {1, 2, ..., 45}; k = {1, ..., 3}; p = {1, 2, ..., 17} (7)
Waktu sampai di node j (node berikutnya) adalah penjumlahan dari waktu  awal buka toko (a) dengan lamanya waktu perjalanan dari pusat ke node j (T ijkp ). AT jkp = a + T ijkp – m* (1 – X ijkp ) , untuk i = {1, 2, ..., 45}; k = {1, ..., 3};
p = {1, 2, ..., 17}
(8)
Waktu sampai di node j (node berikutnya) adalah penjumlahan dari waktu dimulainya pelayanan di node i (SS ikp ) dan lamanya waktu pelayanan/unloading (ST ikp ) dengan lamanya waktu perjalanan dari node i (node awal) ke node j (T ijkp ). AT jkp = SS ikp + ST ikp + T ijkp – M* (1 – X ijkp ) , untuk i = {1, 2, …, 45};
j = {0, 1, …, 45}; k = {1, …, 3}; p = {1, 2, …, 17}; j≠i (9)
Total waktu pendistribusian tidak boleh melebihi waktu tutup toko J kp ≤ TW kp , untuk k= {1, ..., 3}; p = {1, 2, …, 17} (10)
5. Y ikp adalah  bilangan  biner  yang  menunjukkan  pembebanan  kendaraan  terhadap konsumen seperti ditunjukkan pada persamaan 11 berikut ini:
Y ikp ϵ {0,1}, untuk i = {0, 1, ..., 45}; k = {1, ..., 3}; p = {1, 2, ..., 17} (11)
Pengolahan  model  matematis  menggunakan software MATLAB  R2019a.  Dalam pengolahan  data  ini  dibutuhkan  data-data  seperti  data  jarak,  jumlah  permintaan, lamanya  waktu  pelayanan,  jam  kerja  yang  tersedia,  waktu  buka  dan  waktu  tutup konsumen, biaya tol, biaya bahan bakar per liter dan biaya konsumsi bahan bakar untuk kendaraan.  Model  tersebut  dijalankan  dengan spesifikasi  laptop  yang  digunakan yaitu sebagai berikut :
Operating System : Windows 10 Pro (64 bit) Processor : Intel Core i5-7200U CPU up to 3,16 Hz RAM : 4,00 GB HDD : 1 TB
Sebelum  dilakukan  perhitungan, software MATLAB  divalidasi  dengan  menggunakan kasus  sederhana  yang  dihitung  secara  manual.  Validasi  dilakukan  untuk  mengetahui apakah coding yang  telah  dibuat  sudah  sesuai  dengan  perhitungan.  Kasus  sederhana yang digunakan terdiri dari 1 gudang (G) dan 3 toko (A, B, dan C) menggunakan metode branch and bound dengan search tree yang  dapat  dilihat  pada Gambar 1. Simpul yang lebih kecil dievaluasi secara sistematis sampai solusi terbaik ditemukan.

## Gambar 1. Search tree
Dari perhitungan manual didapatkan biaya distribusi paling murah adalah Rp. 26.542,78 dengan rute G-A-C-B-G. Data yang sama dimasukkan ke dalam software MATLAB dan didapatkan hasil yang dapat dilihat pada Gambar 2.
1 2 3 4 5 6 GA 9,8 km GB 4,8 km GC 9 km 7 8 9 10 AB
5,5 km AC
3,2 km BA 5,3 km BC 4 km CA 3,3 km CB 3,7 km 11 12 13 14 15 16 17 18 19 20 21 22 BC 4 km CB 3,7 km
AC 3,2 km CA 3,3 km AB 5,5 km BA 5,3 km CG 8,7 km BG 4,6 km CG 8,7 km AG 10,4 km BG 4,6 km AG 10,4 km G-A-B-C-G 28 km G-A-C-B-G 21,3 km G-B-A-C-G 22 km G-B-C-A-G 22,5 km G-C-A-B-G 22,4 km G-C-B-A-G 28,4 km
Hasil perhitungan manual dan software memberikan hasil yang sama, dengan demikian software dapat dikatakan valid untuk digunakan pada kasus yang lebih kompleks pada penelitian ini.
Gambar 2. Output MATLAB
Pada  penelitian  ini,  terdapat  dua  skenario  yang  diusulkan,  skenario  pertama  yaitu pengiriman  sesuai  dengan  sistem  aktual  dimana  pada  skenario  1  tersebut  dilakukan pencarian  total  jarak,  waktu  tempuh,  dan  biaya  yang  optimalnya,  sedangkan  pada skenario kedua yaitu mengusulkan untuk mengelompokkan konsumen menjadi beberapa cluster dengan  menggunakan saving  matrix  [11] serta  melakukan  pengiriman  sesuai dengan cluster dengan  data-data  permintaan  yang  masuk  pada  hari  Senin-Jumat  dan akan  dikumpulkan  pada  hari  Jumat  untuk  dilakukan  pengelompokkan  pengirimannya sesuai  dengan  kode  setiap  toko  pada  minggu  berikutnya.  Hal  tersebut  dilakukan  agar mempermudah  supir  dalam  melakukan  kegiatan  distribusi  yang  sesuai  dengan cluster nya.

## Hasil dan Pembahasan
Metode  penentuan  rute  yang  dilakukan  perusahaan  saat  ini  masih  bersifat  impulsif sehingga  waktu  tempuh  dan  jarak  diperkirakan  masih  dapat  diperbaiki.  Dengan menggunakan metode penentuan saat ini, perusahaan terkadang masih mengalami gagal kirim  karena  kegiatan  distribusi  melebihi  waktu  jam  tutup  konsumen.  Kebijakan pemesanan yang diterapkan perusahaan saat ini masih belum efisien, dimana pesanan konsumen dikumpulkan pada hari yang sama. Perusahaan melakukan pengiriman sehari setelah konsumen melakukan pemesanan. Dalam pandangan perusahaan, jika konsumen yang sama memesan beberapa kali dalam periode satu minggu maka perusahaan harus bisa  melayani  permintaan  konsumen  dengan  mengirimkan  produk  di  hari  berikutnya lebih dari satu kali pengiriman walaupun jumlah pesanan konsumen tidak banyak. Hal ini  membuat  biaya  distribusi  yang  dikeluarkan  oleh  perusahaan  menjadi  tidak  efisien. Hasil perhitungan biaya operasional distribusi aktual, skenario 1, dan skenario 2 selama 1 bulan dapat dilihat pada Tabel 1.

## Tabel 1. Biaya operasional distribusi aktual
No Total drop point Total muatan (Kg) Rute aktual Jarak
tempuh (Km) Waktu tempuh & pelayanan (menit) Total biaya 1 8 530 G-C7-C9-C6-C10-D8-D15-A7-G 88,30 207,68 81.724,29 Rp 2 5 363 G-D2-A5-A6-A1-B9-G 85,40 156,86 83.335,84 Rp 3 6 416 G-D11-D10-D9-D6-A6-B8-G 84,60 183,08 82.676,96 Rp 4 7 378 G-D2-D14-D1-C10-C9-C2-B4-G 104,00 187,72 98.654,89 Rp 5 8 362 G-D6-D14-D1-C11-C8-B1-B6-A9-G 90,90 202,22 87.865,66 Rp 6 6 487 G-C1-D6-C5-C10-A6-B5-A8-A10-G 90,50 172,22 85.536,22 Rp 7 5 424 G-A8-A10-B7-C10-D15-G 74,80 154,87 74.605,63 Rp 8 9 639 G-C11-C3-C10-C4-C8-D2-B4-A10-G 102,20 222,71 95.172,40 Rp 9 7 411 G-D8-D5-C10-C1-B8-A4-A10-G 93,60 192,94 91.089,40 Rp 10 3 520 G-D13-A6-B8-G 52,20 108,36 55.992,16 Rp 11 7 405 G-C11-C5-C9-D2-A8-A7-A3-G 97,10 184,94 90.972,01 Rp 12 4 360 G-C7-D4-B5-A3-G 63,30 121,93 63.134,18 Rp 13 5 309 G-D13-C1-A10-A6-A2-G 60,40 137,21 62.745,72 Rp 14 5 343 G-D2-A2-B2-B3-B8-G 80,51 148,50 79.308,41 Rp 15 1 200 G-D2-G 60,30 66,61 62.663,36 Rp 16 4 481 G-D2-D8-C8-A2-G 72,30 129,10 72.546,62 Rp 17 7 382 G-A9-A4-A6-C10-D3-D12-D5-G 82,60 176,65 81.029,75 Rp 1.383,01 2.753,59 1.349.053,49 Rp Total
Tabel 2. Biaya operasional distribusi skenario 1
No Total drop point Total muatan (Kg)
Rute optimisasi Jarak tempuh optimisasi
(Km) Waktu tempuh optimisasi (menit) Biaya optimisasi 1 8 530 G-A10-A7-D15-D8-C6-C7-C10-C9-G 66,7 181,66 65.934,43 Rp 2 5 363 G-A5-B9-D2-A1-A6-G 45,4 129,34 50.391,65 Rp 3 6 416 G-B8-D6-D11-D10-D9-A6-G 50,3 151,06 54.427,31 Rp 4 7 378 G-B4-C10-C9-D1-D2-D14-G 67,3 166,2 68.428,59 Rp 5 8 362 G-B1-B6-C8-C11-D1-D6-D14-A9-G 62,9 168,2 64.804,73 Rp 4 137 G-C5-C10-A6-A8-G 45,5 137,37 48.474,01 Rp 4 350 G-C1-D6-B5-A10-G 61,4 165 61.569,33 Rp 7 3 313 G-D15-B7-C10-G 57,5 99,19 58.357,27 Rp 8 9 639 G-B4-A7-A10-D2-C8-C11-C10-C4-C3-G 67,8 263,68 66.840,40 Rp 9 7 411 G-C1-C10-B8-D8-D5-A10-A4-G 68,1 174,92 67.087,48 Rp 10 3 520 G-B8-D13-A6-G 38,3 103,37 44.544,06 Rp 11 7 405 G-C5-C9-C11-D2-A3-A7-A8-G 66,9 159,92 64.099,15 Rp 12 4 360 G-C7-B5-D4-A3-G 58,9 117,91 59.510,32 Rp 13 5 309 G-C1-D13-A2-A10-A6-G 43,2 127,19 46.579,72 Rp 14 5 343 G-B3-B8-B2-D2-A2-G 52,4 130,48 56.156,88 Rp 15 1 200 G-D2-G 60,3 66,60 62.663,36 Rp 16 4 481 G-A2-D2-D8-C8-G 57,2 123,07 58.110,19 Rp 17 7 382 G-C10-D3-D5-D12-A9-A4-A6-G 70,7 168,63 69.228,85 Rp 1.040,8 2.496,42 1.067.207,73 Rp
Total 6

## Tabel 3. Biaya operasional distribusi skenario 2
No Total drop point Total muatan (Kg) Rute optimisasi Jarak tempuh optimisasi (Km) Waktu tempuh optimisasi (menit) Biaya optimisasi 1 8 541 G-A5-A10-A8-A1-A7-A11-A9-A6-G 38,80 163,52 44.955,86 Rp 2 6 461 G-B5-B1-B9-B6-B7-G 39,61 151,64 45.622,98 Rp 3 7 434 G-C7-C8-C5-C9-C6-C1-C4-G 49,80 150,78 50.015,51 Rp 4 10 1100 G-D11-D8-D12-D6-D1-D2-D16-D10-D9-D15-G 53,70 232,17 57.227,57 Rp 5 7 725 G-A10-A3-A11-A7-A8-A4-A6-G 39,40 158,69 45.450,02 Rp 6 5 751 G-B2-B5-B9-B6-B8-G 36,61 153,12 43.152,00 Rp 7 7 621 G-C7-C8-C5-C9-C6-C3-C2-G 51,40 155,39 51.333,28 Rp 8 6 551 G-D14-D16-D8-D2-D5-D4-G 60,10 157,52 62.498,64 Rp 9 5 460 G-A4-A9-A11-A2-A6-G 36,80 119,64 43.308,65 Rp 10 4 205 G-B2-B4-B9-B3-G 37,20 100,46 43.638,09 Rp 11 2 225 G-C8-C6-G 48,90 81,89 49.274,27 Rp 12 6 825 G-D13-D5-D8-D3-D2-D14-G 63,90 166,56 65.628,34 Rp 556,22 1.791 602.105,21 Rp Total
Dari  hasil  biaya  aktual  dan  usulan  yang  telah  diolah  didapatkan  masing-masing  total biaya yang berbeda. Berikut merupakan perbandingan total biaya aktual dengan usulan yang dapat dilihat pada Tabel 4.
Tabel 4. Perbandingan total biaya aktual dan usulan Total biaya Aktual 1.349.053,49 Rp Skenario 1 1.067.207,73 Rp Skenario 2 602.105,21 Rp
Total biaya yang  dihasilkan rute aktual sebesar Rp.  1.349.053,49 per bulan, skenario 1 sebesar  Rp.  1.067.207,73  per  bulan,  dan  skenario  2  adalah  sebesar  Rp.  602.105,21  per bulan. Total penghematan biaya yang dihasilkan skenario 1 sebesar 20,89% dan skenario 2  sebesar  55,37%.  Pada  kasus  ini,  jika  perusahaan  ingin  tetap  menerapkan  kebijakan pemesanan  sebelumnya,  maka  skenario  1  memiliki  biaya  yang  lebih  kecil.  Jika perusahaan ingin kebijakan pemesanannya diubah, maka skenario 2 memiliki biaya yang lebih  kecil.  Selain  meminimalisasi  biaya,  pada  skenario  1  juga  meminimalisasi  jarak sebesar  342,21  km  atau  24,74%,  serta  dalam  segi  waktu  dapat  diminimalisasi  sebesar 257,17 menit atau 9,34%. Skenario 2 juga meminimalisasi jarak sebesar 826,79 km atau 59,78%, serta dalam segi waktu dapat diminimalisasi sebesar 962,21 menit atau 34,94%.
Pada skenario 2 terdapat perubahan kebijakan pemesanan dan pengiriman yaitu dengan melakukan  pengumpulan  pesanan  konsumen  terlebih  dahulu,  yang  melakukan pemesanan  dari  hari  Senin  sampai  Jumat.  Pesanan  tersebut  dikumpulkan  pada  hari Jumat  dan  akan  dikirim  pada  hari  Senin  sampai  Kamis  minggu  berikutnya, penggambaran  skenario  dapat  dilihat  pada  Gambar  3.  Pada  skenario  2  ini,  kegiatan pengiriman dilakukan sesuai dengan cluster sehingga jarak antar konsumen lebih dekat. Pertimbangan yang  harus  dilakukan  dalam menerapkan  skenario  2  ini  adalah penalty pesanan konsumen yang diterima dimana pengirimannya harus mundur beberapa hari, selain  itu  perlu  dipertimbangkan  juga  adanya lost  sales karena  adanya  kemungkinan konsumen berpindah ke pesaing.
Dalam  penerapan  skenario  2  ini  diperlukan  negosisasi  dengan  konsumen  dan  dengan adanya  perubahan  kebijakan  ini  perlu  dilakukan benefit  sharing bagi  perusahaan  dan konsumen.  Kebijakan  usulan  memungkinkan  biaya  distribusi  menjadi  lebih  murah,
sehingga keuntungan yang didapat oleh perusahaan meningkat. Di sisi lain mungkin saja konsumen harus menunggu lama. Hal tersebut dapat diatasi dengan melakukan benefit sharing misalnya  dengan  memberikan  potongan  harga  sesuai  dengan  hari pengirimannya.  Tetapi  dengan  diterapkan  perubahan  kebijakan  juga  memungkinkan adanya  ancaman  bagi  perusahaan  karena  kompetitor  memiliki  kesempatan  untuk menguasai pasar karena kompetitor tersebut mungkin bisa melakukan pengiriman yang lebih cepat.
Minggu 1
Minggu 2 Minggu 4 Minggu 3
Sn Sl, Rb, Km, Jm
Sn Sl, Rb, Km, Jm Sn Sl, Rb, Km, Jm
Sn Sl, Rb, Km, Jm
Pemesanan
Pengiriman
Gambar 3. Pemesanan dan pengiriman skenario 2

## Kesimpulan
Metode  yang  diusulkan  untuk  memperbaiki  masalah  rute  pengiriman  saat  ini  adalah menggunakan  model Integer Linear Programming yang  diolah  menggunakan  metode Branch and Bound dengan bantuan software MATLAB (skenario 1). Model ini digunakan untuk mencari total biaya yang  optimal yang bisa dikeluarkan oleh perusahaan dalam melakukan kegiatan distribusi.
Dalam  studi  kasus,  diusulkan  agar  perusahaan  mengubah  kebijakan  pemesanan  dan pengiriman  dimana  pemesanan  dilakukan  dengan  mengumpulkan  semua  permintaan konsumen selama hari Senin sampai Jumat terlebih dahulu, agar konsumen yang sama yang telah melakukan pemesanan beberapa kali bisa digabungkan pengirimannya. Data- data  permintaan  yang  masuk  pada  hari  Senin  sampai  Jumat  akan  dikumpulkan  pada hari Jumat untuk dilakukan  pengelompokan pengirimannya sesuai dengan kode setiap toko pada minggu berikutnya (skenario 2).
Manfaat dan kelebihan dari metode penentuan rute usulan bagi perusahaan adalah total biaya yang dihasilkan pada skenario 1 dan 2 lebih murah. Selain meminimalisasi biaya, usulan pada skenario 1 juga meminimalisasi jarak dan waktu .

## Daftar Pustaka
[1]  P. Toth and D. Vigo, "An overview of vehicle routing problems," in The vehicle routing problem , ed: SIAM, 2002, pp. 1-26.
[2]  R.  Yohanes,  Santoso,  and  R.  M.  Heryanto,  "Penentuan  Rute  Distribusi  yang Mempertimbangkan  Multi  Trips,  Time  Window,  Simultaneous  Pickup  Delivery dengan Menggunakan Algoritma Sequential Insertion," in Seminar Nasional Teknik Indutri, Universitas Gadjah Mada , 2020.
[3]  Y.  Stephanie,  Santoso,  and  R.  M.  Heryanto,  "Determination  of  Distribution  Route using Linear Programming Model (Case Study at Washing Jeans Company)," in 2019 1st International  Conference on Engineering  and  Management in Industrial System (ICOEMIS 2019) , 2019.
[4]  S. Chopra, P. Meindl, and D. V. Kalra, Supply chain management: strategy, planning, and operation vol. 232: Pearson Boston, MA, 2013.
Go-Integratif : Jurnal Teknik Sistem dan Industri  Vol. 01, No. 01, (November 2020) 69–79
[5]  I.  N.  Pujawan  and  Mahendrawathi, Supply  Chain  Management ,  3  ed.  Yogyakarta: Andi, 2017.
[6]  P.  Kotler, Manajemen  Pemasaran  (Analisis,  Perencanaan,  Implementasi  dan Pengendalian) : Erlangga, 1993.
[7]  G.  B.  Dantzig  and  J.  H.  Ramser,  "The  truck  dispatching  problem," Management science, vol. 6, pp. 80-91, 1959.
[8]  R.  Prana,  "Aplikasi  kombinatorial  pada  vehicle  routing  problem," Jurnal  Teknik Informatika ITB, 2007.
[9]  K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, "The vehicle routing problem: State of the art classification and review," Computers & Industrial Engineering, vol. 99, pp. 300-313, 2016.
[10] P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications , Second ed.: SIAM, 2014.
[11] G.  M. Sari, "Laporan Kerja Praktek Magang  Bagian Transportasi Rute di PT XYZ- Bandung," Universitas Kristen Maranatha, Bandung, 2018.