Jurnal Media Teknik & Sistem Industri Vol.2 (no.2) (2018) hal.37-42 http://jurnal.unsur.ac.id/index.php/JMTSI e-issn: 2581-0561 p-issn: 2581-0529

## Penentuan Jarak Pendistribusian Gas LPG 3 Kg Dengan Metode Algoritma Heuristik
Akhmad Sutoni 1 , Nur Asilah 2
1,2 Teknik Industri Universitas Suryakancana Jln. Pasir Gede Raya, Cianjur, Indonesia
tbungsu13@gmail.com
Dikirimkan: 09, 2018.  Diterima: 09,2018.  Dipublikasikan: 10,2018.
Abstract — PT. Anugrah Ditamas Lestari is an agent of 3 kg LPG Gas, to distribute to bases. PT. Anugrah Ditamas Lestari has a problem in distributing 3 kg of gas to the base, so it must have good planning so that the items to be distributed can reach the base in a timely manner. Traveling Salesman Problem (TSP) is a distribution problem in the form of transportation equipment (vehicle) from the agent to the base then back to PT. Anugrah Ditamas Lestari (agent). The research conducted aims to determine the minimum mileage for each route. The preparation of this Gas distribution route was completed using the Heuristic Algorithm. The initial stage is the formation of a sub route which is the process of grouping the base into the route. The next stage of the sub route development phase that has been formed is based on the existing travel time, the last stage minimizes the distance where the agent must first deliver the product until the last base and return to the  agent.  Sub  route  formation  is  still  done  manually  while  to  compare  the  final  results  is  done  using WinQSB Software. Based on this distance determination study, the distance traveled was closer, and did not come to the base twice.
Keywords — Distribution; TSP (Traveling Salesman Problem); Heuristic Algorithm.
Abstrak— PT. Anugrah Ditamas Lestari merupakan suatu agen Gas LPG 3 kg, untuk mendistribusikan ke pangkalan-pangkalan. PT. Anugrah Ditamas Lestari memiliki permasalahan dalam pendistribusian Gas 3 kg kepada  pangkalan,  maka  harus  mempunyai  perencanaan  yang  baik  agar  barang  yang  akan  di  distribusikan dapat  sampai  ke  pangkalan  secara  tepat  waktu. Traveling  Salesman  Problem (TSP)  merupakan    medel permasalahan  distribusi  berupa  alat  angkut  (kendaraan)  dari  agen  ke  pangkalan  kemudian  kembali  ke  PT. Anugrah  Ditamas  Lestari  (agen).  Penelitian  yang  dilakukan  bertujuan  untuk  menentukan  jarak  tempuh minimum  untuk  setiap  rute.  Penyusunan  rute  distribusi  Gas  ini  diselesaikan  menggunakan Algoritma Heuristik .  Tahap  awal  yaitu  pembentukan  sub  rute  yang  merupakan  proses  pengelompokan  pangkalan kedalam  rute  tersebut.  Tahap  selanjutnya  tahap  pengembangan  sub  rute  yang  telah  dibentuk  berdsarkan waktu  tempuh  yang  ada,  tahap  terakhir  meminimalisasi  jarak  tempuh  kemana  pertama  kali  agen  harus mengantar produk sampai terakhir pangkalan dan kembali ke agen. Pembentukan sub rute masih dilakukan secara manual sedangkan untuk membandingkan hasil akhirnya dilakukan menggunakan Software WinQSB. Berdasarkain  penelitian  penentuan  jarak  ini,  maka  jarak  tempuh  yang  diperoleh  menjadi  lebih  dekat,  dan tidak mendatangi pangkalan dua kali.
Kata kunci — Distribusi; TSP (Traveling Salesman Problem); Algoritma Heuristik.

## I. P ENDAHULUAN
Salah satu penyebab terjadinya keterlambatan pengiriman  produk  pada  PT.  Anugrah  Ditamas Lestari  adanya  kesalahan  dalam  pengaturan  rute pengiriman,  jika  tidak  ditentukan  rute  perjalanan yang  akan  dijalani  terlebih  dahulu,  maka  akan ditentukan  tidak  terlaksana  secara  optimal.  Maka dari  itu  perlu  dilakukan  penentuan  rute distribusian dengan mempertimbangkan kapasitas alat  angkut  yang  tersedia  untuk  pangkalan  yang ada  di  kota  Cianjur.  Penyusunan  rute  yang  baik dapat  mempersingkat  jarak  tempuh  dan  waktu
pengiriman  produk,  maka  hasil  akhir  akan  ada penghematan biaya distribusi bagi perusahaan.
Tujuan  dari  penelitian  ini  yaitu  untuk mengetahui  rute  yang  harus  dilalui  oleh  PT. Anugrah  Ditamas  Lestari  kepada  pangkalan    dan mengetahui rute terpendek pada rute pendistribusian dari agen ke pangkalan.
1.1 Logistik
Beberapa  definisi  mengenai  sistem  logistik diantaranya adalah sebagai berikut :
1. Menurut Logistix Partners  Oy,  Helsinki, FI,  1996 [1]  :  Logistik  adalah  sebagai
sebuah  kerangka  perencanaan  usaha untuk  mengatur  aliran  material,  jasa, informasi  dan  modal,  termasuk  di dalamnya pengelolaan peningkatan informasi  yang  kompleks  atau  rumit, komunikasi  dan  sistem  kontrol  yang dibutuhkan dalam lingkungan usaha.
2. Menurut JCS  Pub  1-02  excerpt [1]  : Logistik adalah ilmu tentang perencanaan, pengangkutan dan perawatan dari kekuatan pasukan. Aspek tersebut dari operasional militer meliputi : perancangan dan pengembangan,  akuisisi,  penyimpanan, pergerakan distribusi, perawatan,
evakuasi,  dan  disposisi  dari  material. Pergerakan,  evakuasi  dan  penginapan maupun  rumah  sakit  untuk  personal pasukan.  Akuisi  untuk  konstruksi, perawatan,  operasi  dan  disposisi  dari pasilitas,  serta  akuisisi  dari  penyediaan jasa layanan.
3. Menurut Websters  Dictionary [1]  : Logistik  adalah  penyediaan,  perawatan, distribusi,  material  dan  penggantian personal.
4. Menurut
Council of logistics
Management [1]  :  Logistik  adalah sebuah  proses  perencanaan,  penerapan dan pengawasan secara efisiensi, efektif, aliran dan penyimpanan barang, jasa dan informasi  terkait  dari  titik  asal  ke  titik konsumsi yang bertujuan untuk memenuhi kesesuaian kebutuhan konsumen.
5. Menurut  MDC,  lOGlINK/ Logistics World [1]  :  Logistik  adalah  ilmu mengenai  perencanaan,  mengorganisir dan  mengatur  aktivitas-aktivitas  yang menghasilkan barang dan jasa.
6. Menurut ECRC  University  of  Scranton [1]  :  Logistik  adalah  ilmu  perencanaan dan penerapan akuisisi dalam pemanfaatan  kesesuaian  sumber  daya guna menjaga kesinambungan operasional dalam sistem.

## 1.2 Distribusi dan Transportasi
Untuk  itu  perlu  halnya  pemahaman  tentang saluran distribusi yang tepat dalam sebuah usaha. Saluran distribusi adalah saluran  yang digunakan oleh  produsen    untuk    menyalurkan    produk sampai    ke    konsumen    atau    berbagai  aktivitas perusahaan  yang  mengupayakan  agar  produk sampai ketangan konsumen.[2]
Dalam  kamus  bahasa  Indonesia,  pengertian distribusi  adalah  pembagian  pengiriman  barang-
barang  kepada  orang  banyak  atau  ke  beberapa tempat.[3]
Selain itu ilmuan ekonomi konvensional philip Kotler mendefinisikan distribusi adalah himpunan perusahaan  dan perorangan  yang  mengambil alih hak, atau membantu dalam mengalihkan hak atas barang atau jasa tersebut berpindah dari produsen ke konsumen.[4]
Dari  sudut  pandangan  perencanaan  logistik, transportasi  itu  menghubungkan  pabrik,  gudang, dan  pasar  yang  terpisah-pisah  letaknya.  Jadi, transportasi itu memberikan tutupan ruang (spatial closure) dan memungkinkan spesialisasi. Transportasi  hendaklah  dipandang  sebagai penurun  biaya  ( cost  reducing ),  dalam  arti pengeluaran  memungkinkan  penghematan  lebih besar dalam proses manufakturing dan pemasaran. [5]
1.3 Rantai Pasok (Supply Chain) Sedangkan menurut Pujawan [6], supply chain adalah  jaringan  perusahaan-perusahaan  yang secara  bersama-sama  bekerja  untuk  menciptakan dan  menghantarkan  suatu  barang  ke  tangan pemakai  akhir  atau  bisa  dikatakan supply  chain adalah  jaringan  fisiknya,  yakni  perusahaan- perusahaa  yang  terlibat  dalam  memasok  barang, memproduksi suatu barang, maupun mengirimkannya ke pemakai akhir.
Menurut Chopra [7], tujuan dari supply chain adalah untuk memaksimalkan hubungan potensial di  setiap  bagian  di  dalam  rantai  supply  chain dengan  maksud  untuk  memberikan  hasil  atau barang  yang  terbaik  bagi  pelanggan  dan mengurangi biaya-biaya pada produk akhir.

## 1.4 Traveling Salesman Problem (TSP)
TSP (Traveling  Salesman  Problem) dapat dideskripsikan  sebagai  pencarian  urutan  tur  kota terdekat yang harus dikunjungi yang meminimalkan  total  biaya,  dimana  setiap  kota hanya  boleh  dikunjungi  maksimum  satu  kali. Pencarian  tur  kota  dengan  jumlah  kota  yang sedikit bisa diselesaikan dengan metode pencarian klasik  yaitu  dengan  cara  menghitung  akumulasi tiap  tur  dan  dipilih  tur  yang  terpendek, permasalahan akan muncul bila pencarian tempat terjadi  pada  jumlah  tempat  yang  banyak,  maka waktu  yang  dibutuhkan  untuk  menyelesaikan permasalahan  ini  akan  meningkat  luar  biasa  dan batas waktu yang mencapai kota tujuan.
Traveling Salesman Problem juga merupakan permasalahan optimasi kombinatorial yang sangat terkenal  dalam  teori  graf,  maka  dapat  dikatakan Traveling  Salesman  Problem tidak  lain  adalah permasalahan untuk menemukan Sirkuit Hamilton yang  memiliki bobot  minimum pada sebuah graf
terhubung. Sirkuit  Hamilton adalah  sirkuit  yang memulai  tiap  simpul  di  dalam graf terdapat  satu kali,  kecuali  simpul  asal  (sekaligus  simpul terakhir)  yang  dilalui  dua  kali.  Jika  setip  simpul mempunyai  sisi  ke  simpul  lain,  disebut  dengan graf lengkap  berbobot,  nilai  bobot edge pada suatu graf ,  didapatkan  dari  jarak  antar  dua  buah kota.  Untuk  TSP  pada  sembarang graf lengkap sangat  mudah  menghitung  jumlah Sirkuit Hamilton yang ada. Dari simpul pertama ada n-1
pilihan,  dari  simpul  kedua  ada  n-2  pilihan,  dst. Sehingga  untuk  n  buah  kota,  ada  pilihan  (n-1)! Yang mungkin. Namun karena Sirkkuit Hamilton terhubung  2  kali  maka  pilihan  yang  ada  harus dibagi  dua  menjadi  (n-1)!/2  buah Sirkuit Hamilton . Aturan-aturan yang yang mengidentifikasikan  yang  termasuk travelling salesman problem (TSP) yaitu :
1.  Perjalanan  di  mulai  serta  di  akhiri  di  tempat yang sama sebagai tampat asal agen.
2.  Seluruh  pangkalan  harus  dikunjungi  tanpa satupun pangkalan yang terlewatkan.
3.  Salesman  tidak  boleh  kembali  ke  tempat  asal sebelum seluruh pangkalan terkunjungi.

## II. M ETODOLOGI P ENELITIAN
1.  Pengumpulan  data  yang  dilakukan  dalam rangka  pemecahan  masalah,  diantaranya,  data yang  di  perloleh  dari  hasil  wawancara  kepada pihak agen Gas.
2.  Selanjutnya  dilakukan  pengolahan  data,  data yang  diperoleh  dari  pengumpulan  data,  yang berasal  dari  hasil  wawancara  tentang  menentuan rute  untuk  mencarian  jalur  terpendek  dengan analisis Travelling  Salesman  Problem yang  di optimasikan  oleh Algoritma  Heuristik pada  agen Gas.
3.  Analisis  dan  pembahasan  dilakuan  setelah strategi yang digunakan. Analisis dan pembahasan tersebut  untuk mengetahui  jauh atau dekat  suatu  rute  dengan  metode Algoritma Heuristik. 4.  Kesimpulan  untuk  menarik  suatu  kesimpulan dari hasil analisis dan pembahasan.

## III. HA SIL P ENELITIAN
Pendistribusian agen Gas PT. Anugrah Ditamas Lestari  yang  langsung  di  distribusikan  kepada  7 pangkalan yang adadi kota Cianjur.
Tabel  1. Pembulatan  Matrik  Jarak  (Km)  PT. Anugrah Ditamas Lestari
TEM PAT A B C D E F G H A 0 13 13 10 7 4 5 8
B 13 0 4 14 17 15 16 20 C 13 4 0 14 17 15 16 20 D 10 14 14 0 4 7 8 10 E 7 17 17 4 0 4 5 7 F 4 15 15 7 4 0 1 5 G 5 16 16 8 5 1 0 5 H 8 20 20 10 7 5 5 0 Tabel 2. Waktu (Menit) Pendistribusian Gas LPG 3 Kg TEM PAT A B C D E F G H A 0 15 17 13 10 6 7 13 B 15 0 7 23 25 21 22 23 C 16 8 0 24 26 22 23 29 D 14 24 26 0 8 10 11 16 E 10 26 28 8 0 6 7 12 F 6 21 23 10 7 0 1 13 G 7 23 25 11 9 2 0 15
H 13 29 31 16 12 11 12 0
Tabel  3 . Ongkos  (Ribu  rupiah)  Pendistribusian
Gas LPG Per Kilo Meter TEM PAT A B C D E F G H A 0 26 26 20 14 8 1 16 B 26 0 8 28 34 30 32 40
C 26 8 0 28 34 30 32 40 D 20 28 28 0 8 14 16 20
E 14 34 34 8 0 8 10 14
F 8 30 30 14 8 0 1 10
G 10 32 32 16 10 2 0 1 H 16 40 40 20 14 10 10 0
Untuk  jarak  pendistribusian  dari  PT.  Anugrah Ditamas Lestari (Km) bisa dilihat seberti   gambar 1.
Jarak  antar  pangkalan,  diberikan graf lengkap yang  berbobot  dengan  8  (delapan)  simpul  yang saling  terhubung  dari  PT.  Anugrah  Ditamas Lestari  (agen)  ke  pangkalan  ,  dapat  dilihat  pada gambar 2.
A B C D E F G H 5 8 1 5 7 10 11 13 4 7 1 7 2 1 13 13 20 PT. Anugrah Ditamas Lestari Pangkalan Hegarmanah (Asep Rahmat ) Pangkalan Samolo (Bpk. Muhidin) Pangkalan Sindangasih (Ibu Erna ) P an gk al an S uk as irn a (I bu E lis N ur ai sa h) Pangkalan Babakan Caringin (bpk. Maman Ghazali ) Pangkalan Gudang (Bpk. Didin Raphiyudin ) Pangkalan Sukagalih (Bpk. Dedin) Gambar 1 . Jarak Pendistribusian Gas LPG 3 Kg dari Agen Ke Pangkalan A D G B E H C F 13 13 10 7 4 5 8 4 14 17 15 16 20 14 17 15 16 20 4 7 8 10 4 5 7 1 5 5 Gambar 2 . Graf Lengkap Permasalahan Di PT. Anugrah Ditamas Lestari
Karena simpul A adalah  simpul  yang terdepan yang menjadi agen untuk mendistribusikan barang ke  simpul  B,  C,  D,  E,  F,  G,  H,  maka  simpul  A akan  dijadikan  patokan  dalam  jaringan  untuk menentukan jalur terpendek untuk pendistribusian tersebut.  Jumlah  kemungkinan  pada  penentuan TSP  ( Traveling  Salesman  Problem )  dengan  8 (delapan)  input  ini  ada  (8-1)!/2  =  2520 kemungkinan  sehingga  proses  enumerasi  lalu membandingkan seluruh total bobot akan menjadi
sangat  rumit.  Metode Algoritma  Heuristik akan menjadi  salah  satu  solusi  yang  dapat  diterapkan pada kasus ini.
Pohon  merentang  minimum  telah  memberikan jalur  yang  akan  mengunjungi  seluruh  pangkalan dengan jumlah jarak total palih minimal. Namun, hasil dari algoritma ini belum  membentuk sirkuit, seperti gambar 3.
Gambar 3. Pohon Merentang Minimum (Jaringan A)
Untuk proses terakhir dari pembentukan simpul berderajat  ganjil  yang  dihubungkan  sehingga menjadi berderajat genap maka akan dihubungkan simpul  A  menuju  simpul  G  dengan  jarak  5  Km dan simpul D dengan simpul H  dengan jarak  10 Km, bisa dilihat pada gambar 4.
Gambar  4.  Pohon  Rentang  Minimum  Dengan Garis A,G dan D,H.
Setelah  proses  membuat  simpul  berderajat ganjil selesai maka terbentuk sirkuit euler. Sirkuit ini  merupakan  aproksimasi  dari  solusi  TSP (Traveling Salesman Problem). Pada hasil proses
ini sisi dari A dan D menjadi jaringan A, dan sisi dari D dan H menjadi jaringan B. Untuk jaringan C  terbentuk  dengan  seluruh  simpul  berderajat genap  yang  merupakan sirkuit  euler .  Sirkuit  ini merupakan  aproksimasi  dari  solusi  TSP    yang diinginkan,  hasilnya  seperti  terlihat  pada  gambar 5.
Gambar  5.  Jaringan  C  Yang  Membentuk Sirkuit
Euler
Langkah  berikutnya  adalah  memeriksa  apakah ada  simpul  yang  dikunjungi  lebih  dari  satu  kali lalu  harus  lalukan  proses  perbaiakan  perjalanan Traveling  Salesman  Problem dengan  memeriksa ketidak samaan :
1(a,b)<1(a,c)+1(c,b)
Pemeriksaan  pada  graf  mengimplikasikan pemeriksaan pada perjalanan dari simpul awal ke simpul akhir.
Setelah  proses  terakhir,  maka  terbentuk  suatu sirkuit  Hamilton  minimum atau  solusi  dari permasalahan Traveling  salesman  Problem. Sehinggga diperoleh seperti gambar 6.

## IV. P EMBAHASAN
Dari proses yang sudah dijalankan, maka hasil akhir  dari  penentuan  rute  pendistribusian  Gas LPG  3  kg  dengan  cara  perhitungan  manual adalah  :  pendistribusiannya  dimulai  dari  PT. Anugrah  Ditamas  Lestari  (A)  menuju  Pangkalan G  sebagai  jalur  pendistribusian  pertama  dengan jarak  5  Km,  lalu  ke  Pangkalan  F  dengan  jarak  1 Km,  terus  ke  Pangkalan  H  dengan  jarak  5  Km, terus  menuju  ke  Pangkalan  D  dengan  jarak  10 Km, terus menuju ke Pangkalan E dengan jarak 4 Km,  terus  menuju  ke  Pangkalan  C  yang  panjang jaraknya 17 km, setelah itu menuju ke Pangkalan
B  dengan  jarak  sepanjang  13  Km,  karena pangkalan  sudah  terlalui  oleh  mobil  maka  dari Pangkalan  B  langsung  kembali  ke  PT.  Anugrah Ditamas  Lestari  (A)  dengan  jarak  13  Km.  Jarak Total adalah 73 Km.
A PT. Anugrah Ditamas Lestari B D E F G Pa ngk ala n He ga rma nah (Bp k. Ase p ra hm at) Pan gka lan Sa mo lo (Bp k. M uh idin ) Pa ng ka lan S in da ng as i h (Ib u Er n a ) Pangkalan Sukasirna (Ibu Elis Nuraisah ) P angkalan B abakan Caringin (B pk. Maman Ghazali ) Pangkalan Gudang (Bpk. Didin Raphiyudin ) C Pa ngk ala n Sa mo lo ( Bp k. M uh idin ) Jl. R aya Ba nd ung SDN Babakan caringin 3 Jl .R ay a S uk as irn a Jl . R ay a Ja ng ar i Jl. Ra ya Ja nga ri G Pangkalan Sukagalih (Bpk. Dedin)
Gambar 6. Sirkuit Hamilton Minimum
Untuk  hasil  komputerisasinya  dari  penentuan rute dari PT. Anugrah Ditamas Lestari bisa dilihat dalam gambar 7.
Gambar 7. Hasil TSP Melalui Komputerisasi
Sedangkan  hasil  TSP  dengan  komputerisasi ( Software  WinQSB )  pendistribusian  Gas  LPG  3 kg  dari  PT.  Anugrah  Ditamas  Lestari  A  menuju pangkalan B sebagai jalur pendistribusian pertama dengan  jarak  5  km,  ongkos  10000  dan  waktu  7 menit,  lalu  ke  pangkalan  C  dengan  jarak  1  km, ongkos  2000  dan  waktu  2  menit,  terus  ke
pangkalan  D  dengan  jarak  5  km,  ongkos  10000 dan waktu 13 menit, terus menuju ke pangkalan E dengan jarak 10 km, ongkos 20000 dan waktu 12 menit,  terus menuju ke pangkalan F dengan jarak 4  km,  ongkos  8000  dan  waktu  8  menit,    terus menuju  ke  pangkalan  gudang  G  yang  panjang jaraknya  17  km,  ongkos  34000  dan  waktu  28 menit,  setelah itu menuju ke pangkalan H dengan jarak sepanjang  4  km,  ongkos 8000  dan waktu  8 menit, karena pangkalan sudah terlalui oleh mobil maka dari pangkalan H langsung kembali ke PT. Anugrah  Ditamas  Lestari  (A).  Jadi  total  waktu tempuh  dari  keseluruhan  64  km,  ongkos  Rp. 109.000, dan mengelurkan waktu 93 menit.
Metode Traveling  Salesman  Problem dengan metode Algoritma  Heuristik cocok  untuk memecahkan permasalahan distribusi yang terjadi pada  perusahaan  ini.  Karena  motode  ini  cocok dalam  penentuan  jarak  pada  suatu  tempat  yang akan di kunjungi.

## V. K ESIMPULAN
1.  Dengan  dilakukannya  penentuan  jarak  dari agen  ke  pangkalan  menggunakan Traveling Salesman  Problem yang  di  optimalakan  oleh metode Algoritma  Heuristik ,  maka  PT.  Anugrah Ditamas  Lestari  dapat  mengetahui  dengan  jelas pangkalan  mana  yang  harus  dikunjungi  terlebih dahulu sampai yang terakhir.
2.  Total  jarak  tempuh  adalah  64  Km,  dengan waktu  tempuh  93  menit,  dan  total  ongkos  Rp. 109.000,00

## R EFERENSI
[1] Bowersox, Donald J., 2000, Manajemen Fisik dan Material Jilid 1 , Jakarta.
[2] Fuad  M.,  2006, Pengantar  Bisnis ,  Gramedia Pustaka Utama, Jakarta.
[3] Anwar  Desi,  2001, Kamus  Bahasa Indonesia , Karya Abditama, Surabaya.
[4] Aziz  Abdul,  2008, Ekonomi  Islam  Analisis Mikro dan Makro ,Graha Ilmu, Yogyakarta.
[5] Bowersox,  Donald  J.,  2002, Manajemen Logistik , Bumi Aksara, Jakarta.
[6] Pujawan I., 2005, Supply Chain Management , Guna Widya, Surabaya.
[7] Chopra,S.,  and  Meindle,  P.,  2001, Supply Chain  Management  Strategy,  Planning,  & Operation , USA.