Penerapan Min Plus Algebra Pada Penentuan Rute Tercepat Distribusi Susu
Vivi Suwanti 1 , Pohet Bintoto 2 , Riski Nur Istiqomah Dinullah 3
1 Universitas Kanjuruhan Malang, vivi_devbatghost@unikama.ac.id
2 Universitas Kanjuruhan Malang, pohet_bintoto@unikama.ac.id
3 Universitas Kanjuruhan Malang, ky2_zahra@unikama.ac.id

## Abstrak
Penelitian  ini  bertujuan  untuk  mencari  rute  tercepat  yang  bisa  ditempuh untuk  mendistribusikan  susu  dari  produsen  di  daerah  Kepanjen  Malang  ke Pabrik  pengolah  di  daerah  Tanggulangin  dengan  menggunakan  algoritma Min   Plus   Algebra .   Metode   penelitian   yang   digunakan   adalah   kualitatif deskriptif. Tahap penelitian yang dilakukan meliputi 1) observasi lapangan, 2) pembuatan  prototipe  program  Matlab Min plus  algebra ,  3) perhitungan  rute tercepat  menggunakan  program  Matlab,   dan  4)  analisis  data.  Dari  hasil penelitian  didapat digraf searah yang terdiri dari 10 titik sebagai representasi rute  pengiriman.  Dengan  menggunakan  prototipe  program  Matlab  didapat jalur  yang  tercepat  yang  dapat  dilalui  adalah  produsen  –  jalan  Raya  Kebon Agung  – Gadang  –  jalur  Arjosari  – jalur  jalan  Raya  Malang  Pandaan  lanjut tol – pabrik pengolah dengan waktu tempuh 134 menit.
Katakunci: min plus algebra, distribusi, tercepat

## 1  PENDAHULUAN
Distribusi susu merupakan salah satu aspek penting dalam rantai industri penghasil  dan  pengolah  susu.  Tingkat    ketepatan  waktu  dalam  perjalanan harus  selalu  diperhatikan  untuk  menjaga  kualitas  susu  yang  dikirimkan. Oleh karena itu dibutuhkan metode pencarian jalur terpendek untuk efisiensi proses perjalanan.
J. Math. and Its Appl. E-ISSN: 2579-8936 P-ISSN: 1829-605X Vol. 14, No. 2, Desember 2017, 103-112
Pada  matematika,  telah  banyak  ditemukan  algoritma-algoritma  untuk mencari  jalur  terpendek.  Salah  satunya  adalah  dengan  menggunakan min plus  algebra. Secara  umum  aljabar  min-plus  analog  dengan  aljabar  max- plus, atau dapat dikatakan kedua struktur aljabarnya isomorfis. [1]
Definisi  1.1 Diberikan } { :     R R dengan R adalah  himpunan semua bilangan  real  dan   :  .  Pada  R didefinisikan  operasi  berikut:
) , min( b a b a   dan b a b a    , untuk setiap  R b a  , . [1]
 R adalah  semiring  idempotem  komutatif  dengan  elemen  identitas terhadap  adalah 0 dan elemen identitas terhadap  adalah   :  .
Definisi  1.2 Suatu jaringan lintasan searah S adalah suatu graf berarah berbobot  terhubung  kuat  taksiklik  S  =  (V,  A),  dengan  V  =  {1,  2,  ,  ...  ,  n} yang memenuhi kondisi: jika (i, j)  A, maka i < j. [1]
Dalam  jaringan  lintasan  searah  ini,  titik  menyatakan  persimpangan, arc/garis menyatakan suatu jalan , sedangkan bobot busur menyatakan jarak, sehingga bobot dalam jaringan selalu positif.
Teorema 1.1 Diberikan suatu jaringan lintasan searah dengan n titik dan
A adalah matriks bobot graf berarah dengan entri        j i j i j i j i a ij titik ke hubung tidak ter atau titik jika , titik ke terhubung dan titik jika arc, bobot .  Vektor  saat-mulai paling awal titik i dapat dilalui diberikan oleh e e b A x   * dimana 1 *      n A A E A  ,  dengan E  matriks  berordo n×n dengan entri        j i j i e ij jika , jika 0, dan   T e b    0  . Lebih lanjut
e n x merupakan waktu minimal untuk melintasi jaringan. [1]
Teorema 1.2 Diberikan suatu jaringan lintasan searah dengan n titik dan A  adalah  matriks  bobot  graf  berarah  berbobot  jaringan  tersebut.  Vektor saat-penyelesaian  paling  lambat  titik  diberikan  oleh
    1 1 * b A x T   
dimana   T e n x b      1 [1]
Definisi    1.3 Suatu  jalan A j i  ) , ( dalam  jaringan  lintasan  searah  S
disebut jalan terpendek jika 1 1 dan j e j i e i x x x x   [1]
Berdasarkan  [3], min  plus  algebra selalu  benar  secara  matematis  untuk perhitungan  jarak  terpendek  serta  mudah  diterapkan  baik  secara  manual maupun  bahasa  pemrograman.  Pada  penelitian  ini,  istilah  jarak  terpendek diganti  dengan  rute  tercepat  dengan  pertimbangan  bahwa  pada  praktik distribusi, jalan dengan jarak yang lebih pendek belum tentu dapat ditempuh dalam  waktu  yang  lebih  cepat.  Adanya  faktor  kemacetan  dapat memperlambat  waktu  tempuh  suatu  jalan.  Hal  ini  disesuaikan  pada pemodelan  jaringan  lintasan  searah  dimana  bobot arc -nya  diganti  dengan waktu tempuh dari satu titik ke titik berikutnya.  Oleh karena itu, penelitian ini  bertujuan  untuk  menemukan  rute  tercepat  pengiriman  susu  dengan menggunakan min plus algebra .

## 2 METODE
Penelitian  ini  merupakan  penelitian  yang  bertujuan  untuk  menerapkan algoritma min plus algebra pada permasalahan rute terpendek/tercepat jalur distribusi  susu.  Oleh  karena  itu  metode  yang  digunakan  adalah  metode penelitian kualitatif dengan jenis deskriptif.
Objek  pada  penelitian  ini  adalah  salah  satu  penghasil  susu  segar  di Malang  yang  melakukan pengiriman ke pabrik di area Tanggulangin. Data pada  penelitian  ini  berupa  1)  jenis  kendaraan  yang  digunakan,  2)  rute-rute yang bisa dilalui, 3) waktu tempuh tiap titik persimpangan.
Teknik pengumpulan data yang dilakukan pada penelitian ini meliputi (1) wawancara, (2) observasi lapangan, dan (3) dokumentasi. Langkah-langkah penelitian  yang  dilakukan  adalah  1)  studi  literatur,  2)  pengembangan prototipe program min plus algebra menggunakan Matlab, 3) pengambilan data  lapangan  pada  salah  satu  produsen  susu  area  Malang,  dan  4) menerapkan  prototipe  program  serta  menganalisis  hasil  dengan  kondisi praktik.

## 3 HASIL DAN PEMBAHASAN
Berdasarkan  hasil  pengambilan  data  lapangan  mengenai  jalur pengiriman  susu  dari  Kepanjen  ke  pabrik  pengolah  di  Tanggulangin, didapatkan data sebagai berikut.
a. Pengiriman  dilakukan  dengan  menggunakan  mobil  tangki  sehingga mobil tidak melalui jalur tengah kota.
b. Waktu perjalanan telah ditambah dengan perkiraan tingkat kemacetan.
c. Untuk  menuju  Tanggulangin,  satu-satunya  jalur  keluar  truk  dari Malang adalah melalui jalan raya Arjosari.
d. Berdasarkan wawancara yang dilakukan pada sopir truk tangki, waktu tempuh  dalam  praktik  pengiriman  susu  dari  Kepanjen  ke  pabrik adalah  berkisar  antara  2,5-3  jam  dengan  asumsi  adanya  kemacetan rutin pada jalur Malang Surabaya.
Rute  yang  dapat  dilalui  oleh  mobil  pengiriman  susu  dapat divisualisasikan dalam digraf berikut ini.
Gambar 1. Visualisasi digraf jalur truk
Keterangan:
1  : titik awal Produsen susu
2  : jalur jalan Raya Curung Rejo
3  : jalur jalan Raya Kebon Agung
4  : jalur jalan Raya Bululawang
5 dan 6  : area terminal Gadang
7  : jalur Arjosari
8   : jalur jalan Raya Malang-Pandaan dilanjutkan jalur non tol
9  :  jalur  jalan  Raya  Malang-Pandaan  dilanjutkan  jalur  tol  Pandaan Surabaya
10  : titik akhir pabrik pengolah di Tanggulangin
Jarak pada digraf adalah waktu tempuh dari satu titik ke titik lain. Waktu tempuh  dinyatakan  dalam  satuan  menit.  Untuk  titik  yang  tidak  terhubung maka  entri  matriks  adalah  dimana    .  Bentuk  matriks  jarak  telah disesuaikan  dengan  bentuk  matriks  pada  [2]  dan  [1].  Representasi  matriks jarak untuk graf pada gambar 1 adalah sebagai berikut ini.
                                                                                                                        22 35 45 45 36 32 0 7 7 7 35 28 29 A Perhitungan min plus algebra dapat dilakukan dengan alur seperti pada algoritma berikut ini.
Algoritma pencarian rute tercepat min plus algebra
Input : matriks bobot A
Output : saat mulai paling awal x e , saat mulai paling lambat x 1
Mulai
Hitung 1 *      n A A E A  Hitung e e b A x   *
Hitung   T e n x b      1 Hitung 1 * ) ( ) (      n T T T A A E A  Hitung     1 * 1 b A x T   
Waktu tempuh=0;
p=1
For i=2 to n if 1 i e i x x  then
Hitung waktu tempuh = waktu tempuh + waktu tempuh (p,i); Masukkan titik (p,i) dalam rangkaian rute p=i end; end;
Selesai
Berdasarkan  alur  perhitungan  pada  algoritma,  prototipe  program  min  plus algebra  dapat  dibuat. Command  program Matlab  untuk min  plus  algebra adalah sebagai berikut.
Program utama %minplus vivi jaringan lintasan searah clc; clear; A=input( 'masukkan matriks bobot A = ' ) be=[]; e=inf; [m,n]=size(A); E=[]; for i=1:m for j=1:n if i==j E(i,j)=0; else E(i,j)=e; end end ; end ; %mencari xe for i=1:n if i==1 be(i)=0; else be(i)=e; end end ; bet=transpose(be); Ab=E; for i=1:n-1
Ab=plusmin(Ab,pangkatmin(A,i)); end ; xe=kalimin(Ab,bet); %mencari x1 At=transpose(A); Atb=E; for i=1:n-1 Atb=plusmin(Atb,pangkatmin(At,i)); end ; b1=[]; for i=1:n if i==n b1(i)=-(xe(n)); else b1(i)=e; end end ; b1t=transpose(b1); x1=-(kalimin(Atb,b1t)); %membandingkan xe dan x1 jarak=0; disp( 'rangkaian rute tercepat adalah sebagai berikut' ); p=1; for i=2:n if xe(i)==x1(i) fprintf( '(%d , %d) , ' ,p,i); if i<=p jarak=jarak+A(p,i); else jarak=jarak+A(i,p); end p=i; end end ; fprintf( 'dengan total rute tercepat = %d' , jarak);
Function transpose matriks function B=transpose(C) [n,m]=size(C); B=[]; for i=1:n for j=1:m b(i,j)=C(j,i); end ; end ; end
Function penjumlahan matriks min plus algebra function Am=plusmin(A,B) if size(A)==size(B) [m,n]=size(A);
for i=1:m for j=1:n Am(i,j)=min(A(i,j),B(i,j)); end ; end ; else disp( 'ukuran matriks berbeda' ); end
Function perkalian matriks min plus algebra function h=kalimin(A,B) [m,n]=size(A); [k,r]=size(B); %if n==k for i=1:m for j=1:r h(i,j)=inf; for l=1:n h(i,j)=min(h(i,j),A(i,l)+B(l,j)); end ; end ; end ; %disp(h); %else %disp('matriks tidak bisa dikalikan'); end
Function perpangkatan matriks min plus algebra function Ap=pangkatmin(A,n) Ap=A; if n==1 Ap=A; else for i=1:n-1 Ap=kalimin(Ap,A); end ; end end
Hasil perhitungan rute tercepat dengan min plus  algebra menggunakan program Matlab dapat dilihat pada gambar berikut.
Gambar 2. Hasil perhitungan min plus algebra dengan program Matlab Berdasarkan  hasil  perhitungan  pada  gambar  2  diketahui  rute  tercepat yang  bisa  dilalui  adalah  :  (1  ,  3)  ,  (3  ,  5)  ,  (5  ,  7)  ,  (7  ,  9)  ,  (9  ,  10)  produsen  –  jalan  Raya  Kebon  Agung  –  terminal  gadang  –  jalur  arjosari  – jalur jalan Raya Malang Pandaan lanjut tol – pabrik di Tanggulangin. Total waktu yang diperlukan adalah 134 menit atau 2 jam 14 menit. Waktu yang tempuh  hasil  perhitungan  ini  merupakan  hasil  minimal  sesuai  dengan Suprayitno [3] yang menyatakan bahwa min plus algebra mampu menjamin bahwa  prosedurnya  selalu  memberikan  jawaban  yang  benar.  Hal  ini  juga dibuktikan  oleh  Watanabe  &  Watanabe  [4]  yang  menyatakan  bahwa ketunggalan nilai eigen pada matriks dengan input min plus algebra datang dari  bobot  rata-rata  minimal  dari  sirkuit  yang  bersesuaian  dengan  matriks tersebut.

## 4 Kesimpulan
Penetapan jalur terpendek pada pengiriman dapat diperhitungkan dengan menggunakan min  plus  algebra .  Panjang  lintasan  pada min  plus  algebra
masukkan matriks bobot A =
[inf inf inf inf inf inf inf inf inf inf;29 inf inf inf inf inf inf inf inf inf; 28 inf inf inf inf inf inf inf inf inf; 35 inf inf inf inf inf inf inf inf inf; inf 7 7 inf inf inf inf inf inf inf; inf inf inf 7 0 inf inf inf inf inf; inf inf inf inf 32 36 inf inf inf inf; inf inf inf inf inf inf 45 inf inf inf; inf inf inf inf inf inf 45 inf inf inf; inf inf inf inf inf inf inf 35 22 inf];
A =
Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf
29   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf 28   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf 35   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf Inf     7     7   Inf   Inf   Inf   Inf   Inf   Inf   Inf Inf   Inf   Inf     7     0   Inf   Inf   Inf   Inf   Inf Inf   Inf   Inf   Inf    32    36   Inf   Inf   Inf   Inf Inf   Inf   Inf   Inf   Inf   Inf    45   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf   Inf    45   Inf   Inf   Inf Inf   Inf   Inf   Inf   Inf   Inf   Inf    35    22   Inf rangkaian rute tercepat adalah sebagai berikut
(1 , 3) , (3 , 5) , (5 , 7) , (7 , 9) , (9 , 10) , dengan total rute tercepat = 134>>
merupakan  waktu  tempuh  dari  satu  titik  ke  titik  berikutnya.  Dengan menggunakan  prototipe  program  Matlab  didapat  jalur  yang  tercepat  yang dapat dilalui adalah produsen – jalan Raya Kebon Agung – terminal gadang –  jalur  arjosari  –  jalur  jalan  Raya  Malang  Pandaan  lanjut  tol  –  pabrik pengolah.  Lama  waktu  yamg  diperlukan  adalah  134  menit  atau  2  jam  14 menit.  Untuk selanjutnya disarankan untuk  melakukan penerapan min plus algebra pada  masalah  distribusi  yang  lebih  kompleks  dengan  node  yang lebih banyak. Selain itu, program yang dikembangkan dapat lebih diperbaiki lagi baik dalam segi codding maupun tampilan sehingga diperoleh program yang lebih mudah digunakan oleh umum.

## 5 Pustaka
[1] Rudhito,  M.  A., Aljabar  Max  Plus  dan  Penerapannya, Universitas Sanata Dharma, Yogyakarta, 2016.
[2] Subiono, Aljabar  Min-Max  Plus  dan  Terapannya, Jurusan Matematika-ITS, Surabaya, 2015
[3] Suprayitno, H., “Correctness Proof of Min-plus Algebra for Network Shortest-Paths Simultaneous Calculation” Journal of Technology and Social Science (JTSS), 1, 1, 61-69, 2017.
[4] Watanabe,  S.  &  Watanabe,  Y.,  “Min  Plus  Algebra  and  Network” RIMS  Kokyuroku  Bessatsu, B47,  41-54,  Research  Institute  for Mathematical Sciences, Kyoto University, 2014.
[5] Heidergott, B., Olsder, G.J., Woude, Jacob van der, Max Plus at Work: Modelling and Analisys of  Synchronized Systems: A Course on Max- Plus  Algebra  and  Its  Application, Princeton  University  Press,  New Jersey, 2006
[6] Schutter,  B.  D., Max-Algebraic  System  Theory  for  Discrete  Event Systems ,  Thesis  Ph.D.,  Katholieke  Universiteit  Leuven,  Heverlee, 1996.