Reka Integra ISSN: 2338-5081
Jurnal Online Institut Teknologi Nasional
©Jurusan Teknik Industri Itenas | No.02 | Vol.4 April 2016
USULAN RUTE DISTRIBUSI KOPI ARABIKA PREMIUM MENGGUNAKAN METODE NEAREST NEIGHBOUR DAN TABU SEARCH DI PT. X Suci Oktarina, Fifi Herni Mustofa, Lisye Fitria Jurusan Teknik Industri Institut Teknologi Nasional (Itenas) Bandung Email:
[email protected] ABSTRAK
PT. X merupakan perusahaan berlokasi di Bandung yang mendistribusikan kopi arabika premium kepada konsumen tetap. Permasalahan yang diteliti adalah rute yang dilewati kendaraan dalam mendistribusikan kopi arabika premium. Rute yang dilakukan perusahaan masih berdasarkan intuisi dari supir sehingga rute dan waktu yang dilalui belum optimal. Untuk memecahkan masalah tersebut dapat menggunakan Vehicle Routing Problem (VRP). Salah satu metode VRP yang digunakan adalah metode Nearest Neighbour. Setelah mendapatkan solusi awal dilakukan perbaikan menggunakan Tabu Search yang bertujuan mendapatkan jarak dan waktu yang minimum dari metode sebelumnya. Hasil tur untuk pendistribusian pertiga hari adalah 3 tur, pendistribusian perminggu 2 tur, dan pendistribusian gabungan 2 tur. Jumlah kendaraan yang digunakan tetap 2 unit kendaraan dimana masing-masing kendaraan mengalami overtime 3,5 jam. Kata kunci: Vehicle Routing Problem (VRP), Nearest Neighbour, Tabu Search ABSTRACT
PT. X is a company located in Bandung which charge of distributing premium arabica coffee to all of the regular costumer. The problems in this study is the vehicles that passed in distributing premium arabica coffee.The route that this company used is still based on the driver’s intuition so that the route and the elapsed time are still not optimal. In order to solve these problems, Vehicle Routing Problem (VRP) can be used. One of the VRP method that is used is Nearest Neighbour. After getting the initial solution, repairs can be done by using Tabu Search which aims to get the distance and minimum time of previous methods. Result for distributing third day tour is 3 tours, 2 tours weekly distribution, and the distribution of the combined two tours. Number of vehicles used remain two vehicles in which each vehicle is run into overtime 3,5 hours. Keywords: Vehicle Routing Problem (VRP), Nearest Neighbour, Tabu Search
Reka Integra - 149
Oktarina,dkk
1. PENDAHULUAN 1.1 Pengantar PT. X merupakan perusahaan yang memproduksi kopi di kota Medan dan mempunyai cabang dibeberapa kota besar lainnya. Salah satu cabangnya adalah PT. X Bandung yang mendistribusikan kopi arabika premium ke beberapa hotel dan café di kota Bandung. Rute yang biasa digunakan perusahaan masih tidak efektif dan efisien karena dilakukan berdasarkan intuisi sopir. Perusahaan mendistribusikan produknya menggunakan mobil dengan kapasitas daya angkut 24 dus. Kendaraan harus mengantarkan kopi ke beberapa pelanggan dan setiap pelanggan memiliki permintaan kopi yang berbeda-beda. Lokasi pelanggan juga tersebar di berbagai wilayah. Hal ini menyebabkan adanya keterlambatan barang sampai ke tangan konsumen. Kopi menjadi salah satu minuman yang dikonsumsi setiap hari oleh masyarakat. Keterlambatan pendistribusian kopi ke hotel dan café akan mempengaruhi kualitas layanan dari hotel dan café tersebut. Oleh karena itu, berdasarkan kendala yang ada perusahaan harus menentukan proses pendistribusian dengan baik yang bertujuan untuk menghasilkan tingkat kepercayaan kepada pelanggan. Waktu pengiriman untuk café pertiga hari yaitu Senin dan Kamis sedangkan untuk beberapa hotel perminggu dengan waktu pengriman Senin. Pendekatan dalam menentukan rute diperlukan untuk mendapatkan rute yang baik. Masalah dalam penentuan rute kendaraan disebut Vehicle Routing Problem (VRP). 1.2 Identifikasi Masalah Permasalahan yang akan diteliti adalah penentuan rute distribusi kopi di PT. X yang berlokasi di Bandung. Identifikasi masalah digunakan untuk mengetahui bagaimana cara memecahkan suatu masalah yang ada dalam proses pendistribusian kopi. Perusahaan diminta untuk menentukan proses pendistribusian yang baik sehingga dapat memberikan kepuasan dan meningkatkan kepercayaan pelanggan. Permasalahan yang saat ini terjadi di PT. X Bandung adalah perusahaan masih belum mempunyai rute distribusi yang baik seperti pelanggan mana yang harus didatangi terlebih dahulu. Selain itu harus diperhatikan juga jarak tempuh yang berbeda-beda, kapasitas daya angkut mobil, dan waktu jam kerja. Metode yang digunakan dalam penelitian ini adalah nearest neighbour dan tabu search. Nearest neighbour adalah metode heuristik, metode ini memilih titik pelanggan terdekat dari titik sebelumnya dalam menghasilkan rute. Tabu Search merupakan salah satu algoritma yang berada dalam ruang lingkup metode heuristik. Konsep dasar Tabu Search adalah suatu algoritma yang menuntun setiap tahapannya agar dapat menghasilkan fungsi tujuan yang paling optimum tanpa terjebak ke dalam solusi awal yang ditemukan selama tahapan berlangsung. 2. STUDI LITERATUR 2.1 Distribusi dan Transportasi Menurut Pujawan dan Mahendrawati (2010), manajemen distribusi dan transportasi pada umumnya melakukan sejumlah fungsi dasar yaitu melakukan segmentasi dan menentukan target service level, menentukan mode transportasi yang akan digunakan, melakukan konsolidasi informasi dan pengiriman, melakukan penjadwalan dan penentuan rute pengiriman, memberikan pelayanan nilai tambah, menyimpan persediaan, dan menangani pengembalian. Reka Integra - 150
Usulan Rute Distribusi Kopi Arabika Premium Menggunakan Metode Nearest Neighbour dan Tabu Search di PT. X
2.2 Vehicle Routing Problem (VRP) Vehicle Routing Problem (VRP) adalah masalah penentuan rute-rute yang optimal dari satu depot menuju sejumlah pelanggan yang tersebar secara geografis dengan memperhatikan sejumlah batasan (Laporte, 1992). Tujuan dari VRP adalah mengantarkan barang pada konsumen dengan biaya minimum melalui rute-rute kendaraan yang keluar-masuk depot. Untuk masalah-masalah seperti ini, biasanya yang dicari adalah aproksimasi solusi yang terdekat, karena solusi tersebut dapat dicari dengan cepat dan cukup akurat. Biasanya masalah ini terselesaikan dengan menggunakan berbagai variasi dari metode heuristik yang memerlukan sedikit pengamatan pada ruang lingkup masalah. 2.3 Metode Nearest Neighbour Nearest neighbour adalah pemilihan lokasi berdasarkan jarak terdekat dari lokasi terakhir yang dikunjungi (Johnson, dkk, 1997). Nearest neighbour merupakan algoritma yang mudah untuk diimplementasikan dan mudah untuk dieksekusi, tetapi tidak menjamin solusi yang dihasilkan optimal. 2.4 Metode Tabu Search Tabu Search pertama kali diperkenalkan oleh Glover (1986). Kata tabu atau “taboo” berasal dari bahasa Tongan, suatu bahasa Polinesia yang digunakan oleh suku Aborigin pulau Tonga untuk mengindikasikan suatu hal yang tidak boleh “disentuh” karena kesakralannya (Glover dan Laguna 1997). Tabu Search merupakan salah satu algoritma yang berada dalam ruang lingkup metode heuristik. Konsep dasar dari Tabu Search adalah suatu algoritma yang menuntun setiap tahapannya agar dapat menghasilkan fungsi tujuan yang paling optimum tanpa terjebak ke dalam solusi awal yang ditemukan selama tahapan ini berlangsung. Tujuan algoritma ini mencegah terjadinya perulangan dan ditemukannya solusi yang sama pada suatu iterasi yang akan digunakan lagi pada iterasi selanjutnya. 2.5 TRAVELING SALESMAN PROBLEM (TSP) Travelling Salesman Problem dikenal sebagai suatu permasalahan optimasi yang bersifat klasik dan Non-Deterministic Polynominal-time Complete (NPC), dimana tidak ada penyelesaian yang paling optimal selain mencoba seluruh kemungkinan penyelesaian yang ada. Permasalahan ini melibatkan seorang traveling salesman yang harus melakukan kunjungan sekali pada semua kota dalam sebuah lintasan sebelum kembali ke titik awal, sehingga perjalanannya dikatakan sempurna. Selanjutnya dengan permasalahan ini, TSP dibuat menjadi permasalahan yang terkenal dan popular untuk dipakai sebagai model produksi, transportasi dan komunikasi (Lestari, 2010). 2.6 METODE BRANCH AND BOUND Metode Branch and Bound diusulkan pertama kali oleh A.H.Land dan A.G.Doig pada tahun 1960. Metode ini merupakan prosedur enumerasi yang efisien untuk memeriksa semua solusi layak yang mungkin. Metode ini menggunakan pohon pencarian, setiap simpul di pohon merupakan representasi dari sejumlah kemungkinan solusi dari Travelling Salesman Problem. Masalah yang muncul berhubungan dengan rute perjalanan untuk mengantarkan atau menjual barang pada beberapa kota dengan seminimal mungkin waktu dan jarak perjalanan. Algoritma Branch and Bound digunakan untuk meminimalkan masalah. Oleh karena itu algoritma ini terdiri dari tiga komponen, yaitu fungsi pembatas, strategi seleksi dan aturan pencabangan (Riyanti, 2004).
Reka Integra - 151
Oktarina,dkk
2.7 SOFTWARE WinQSB WinQSB adalah sistem interaktif untuk membantu pengambilan keputusan yang berisi alat yang berguna untuk memecahkan berbagai jenis masalah dalam bidang riset operasi. Sistem ini terdiri dari modul-modul yang berbeda, satu untuk setiap model jenis atau masalah. WinQSB menggunakan mekanisme tampilan jandela seperti Windows, yaitu jendela, menu, toolbar, dan lain-lain. Oleh karena itu pengelolaan program serupa dengan yang lain menggunakan lingkungan Windows. WinQSB sendiri terdapat beberapa modul yang dapat digunakan untuk menyelesaikan masalah - masalah operasional riset dan ilmu manajemen seperti analisis Sampling, Agregat dalam sistem Produksi, Analisis Keputusan, Pemrograman dinamis, goal programming, Tata letak fasilitas, peramalan permintaan, Sistem inventory, Penjadwalan kerja, Pemrograman Linier dan Integer, Pernencanaan kebutuhan material (MRP), Proses Markov, dan Network Modeling (Winarno, 2008). 3. METODOLOGI PENELITIAN Metodologi penelitian merupakan langkah-langkah yang akan dilakukan dalam penelitian untuk mencapai tujuan yang diinginkan. Langkah-langkah pemecahan masalah sebagai berikut: 1. Identifikasi Masalah Permasalahan yang saat ini terjadi di PT. Coffindo Bandung adalah perusahaan masih belum mempunyai rute distribusi yang baik seperti pelanggan mana yang harus didatangi terlebih dahulu. Selain itu harus diperhatikan juga jarak tempuh yang berbeda-beda, kapasitas daya angkut mobil, dan waktu jam kerja. 2. Studi Literatur Dalam studi literatur tedapat teori yang behubungan dengan metode yang digunakan untuk penyelesaian masalah. Teori tersebut meliputi distribusi, transportasi, vehicle routing problem (VRP), dan metode yang digunakan yaitu nearest neighbor, tabu search, dan branch and bound. 3. Penentuan Metode yang Digunakan Penentuan metode yang digunakan secara analitik adalah branch and bound. Penentuan metode secara heuristik adalah metode nearest neighbour dan tabu search. 4. Pengumpulan Data Data yang dibutuhkan untuk menyelesaikan masalah adalah sebagai berikut: data permintaan, jarak tempuh, waktu tempuh,jumlah kendaraan, kapasitas kendaraan, waktu loading dan unloading, kecepatan kendaraan, waktu administrasi, dan jam kerja supir. 5. Penentuan Rute Kendaraan Penentuan rute kendaraan dengan menggunakan metode nearest neghbour, tabu search dan branch and bound. Metode ini diharapkan dapat memecahkan masalah di PT. X yang berlokasi di Bandung. 6. Analisis Analisis yang dilakukan adalah analisis terhadap permasalahan di perusahaan dan metode yang digunakan dalam memecahkan permasalahan tersebut. Analisis diperoleh berdasarkan hasil perhitungan metode yang digunakan. 7. Kesimpulan Dan Saran Berdasarkan penelitian yang dilakukan di PT. Coffindo yang berlokasi di Bandung dapat disimpulkan segala hal yang berhubungan dengan penelitian baik permasalahan yang terjadi maupun metode yang digunakan. Selain itu ada saran untuk perusahaan melakukan perbaikan mengenai pendistribusian sesuai dengan metode yang diusulkan.
Reka Integra - 152
Usulan Rute Distribusi Kopi Arabika Premium Menggunakan Metode Nearest Neighbour dan Tabu Search di PT. X
4.PENGUMPULAN DAN PENGOLAHAN DATA 4.1 Pengumpulan Data Data yang dibutuhkan untuk menyelesaikan masalah adalah sebagai berikut: 1. Data Permintaan Data permintaan pelanggan PT. X yang berlokasi di Bandung yaitu kopi arabika premium yang didistribusikan perusahaan ke beberapa hotel dan café yang ada di Bandung. Data permintaan ada yang perminggu dapat dilihat pada Tabel 1 dan ada yang pertiga hari dapat dilihat pada Tabel 2. Tabel 1. Data Permintaan Pertiga Hari PERMINTAAN PER 3 HARI No 2 3 4 6 7 8 9 10 12 13 15 16 17 18 19 20 21 22 25 27 28 29 30 32 33 34 35 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 61 62 63
Outlet California Hotel Grand Pacific hotel Grand Pasundan Hotel Hotel @hom Hotel Serena Hotel Citarum Hotel Dafam Hotel Grand Sovia Hotel Ibis Pasteur Hotel Kembang Hotel Santika hotel amarossa Karang setra Hotel Max One Hotel Nom-nom eatery - café RM Cibiuk - resto (Soeta) Rully Bistro Cafe & Resto Sangria Resort & SPA foodtruck Cafe Theory Batara Hotel Hotel Bumi Sawunggaling Kawasan 27 Garden Cafe Hotel Sheo & resort Apricot fruit Market 101 Hotel Barbarossa Cafe Café Halaman Choco-latte Coffee Khatulistiwa Cafe Koffie Tidj - café Kopi kamu Cafe Liana Swalayan Oasis Siliwangi Rockstar Cafe Tomodachi Resto Upper East - café Waroeng Mas Boy Wiki Coffee - café Roti Selai Cafe Giant SPM ISTANA PLAZA De Java Hotel Hotel Malaka Verona Palace East Boss Cafe Soda cafe Park Hotel Ardjuna Cafe Resort Dago Heuveul Dien's Cafe Cafe Braga Coffee Cafe Redlong Gayo Coffee
Alamat / No Hp Jalan Wastukencana No 48, Jawa Barat 40116, Indonesia Jalan Pasirkaliki No. 100, Jawa Barat 40115, Indonesia Jalan Peta No.147-149, Lingkar Selatan, Jawa Barat 40233, Indonesia Jl. Perintis Kemerdekaan Jl. Manjuk No 4 Kebon Kawung Jl. Citarum No 16, West Java 40294, Indonesia Jl. WR Wahidin No 5 Jl. Kebon Kawung No 16 Jl Dr Junjunan 22 Bandung, Indonesia Jl. Cihampelas no 100 Bandung Jl. Sumatera No 52-54 Jl. Aceh No. 71A, Bandung, Jawa Barat 40115, Indonesia Jl. Bungur No. 2, Sukajadi, Jawa Barat 40162, Indonesia Jl.Halimun No 36 Jl. Merak No 2 Bandung / 085720300053 Jl. Soekarno Hatta No. 595 Margasari Margacinta Bandung Jawa Barat, Indonesia Jl. Cibiru Raya No 63 Jl. Holtikultura Komp. Bukit Padjadjaran No 205 Jl. Cihampelas No 112 Bandung 40131 Jl. Sawunggaling No 13 Jl. Sultan Agung Tirtayasa No 27 Bandung Jl. Dr Setiabudi No 198 Bandung Jln Ciumbuleuit No 152 Jl. Sawunggaling No 5 Bandung 40116 Jl. Ir. H. Djuanda No.3, Bandung, Jawa Barat 40132, Indonesia Jl. Wastukencana No 55 Jalan Tamansari No.92, Bandung, Jawa Barat 40132, Indonesia BTC Food Court LT 1 Jl. Sumatera Jl Flores no. 8, Bandung 40117, Indonesia Jl. Tamansari No 66 Jl. Gegerkalong Hilir No 175 Jl. Lombok no 10 Jl. Soekarno Hatta (Meto Indah Mall) G 25 Komp. Taman Sakura Indah No 22A Bandung Jl. Raya Golf No. 92, Dago Pakar (Dago Atas) Jl. Tubagus ismail Dalam No 16 Jalan Braga No.90, Bandung, Jawa Barat 40111, Indonesia / 082219014122 Jl. Ranca Kendal Dago Atas Pasir Kaliki Bandung Jl. Sukajadi No 148-150 Jl. Halimun NO 36 Jl. Surya Sumantri NO 36 Jl. Aceh No 66 Jl. Ir H Djuanda No 1 Dago Bandung Jl. PHH Mustofa No 47/57 Bandung 40124 Jl. Kiputih Ciumbuleuit Jl. Ciburial No 45 Dago Pakar Bandug Jl. Cigadung Raya Bandung Jln Braga Jl. Teuku Umar No. 1/60 Bandung Jumlah Kapasitas Kendaraan
Reka Integra - 153
Permintaan Kopi (Dus) 3 2 6 5 5 4 3 7 2 2 3 3 3 3 2 3 4 6 2 4 5 1 2 4 2 4 2 2 1 1 1 3 4 3 1 1 2 2 3 1 4 5 5 3 1 1 4 1 2 3 2 2 150 24
Oktarina,dkk
Tabel 2. Data Permintaan Perminggu PERMINTAAN PERMINGGU No 1 5 11 14 23 24 26 31 36 44 60
2.
3.
4.
5.
6.
7. 8. 9.
Outlet Hotel Ibis TSM Hotel & Resort Kampung Legok Hotel Ibis Asia Afrika Hotel Noor Terminal Wisata Grafika The Salis Hotel Hotel Imperium Hotel Arwiga Cafe Coffee Time Pasundan coffee - café Hotel Ruby
Alamat / No Hp Jl. Gatot Subroto No 289 Jl. Kolonel Masturi No 99 Jl. Asia Afrika No 128 Jl. Madura No 6 Bandung Jln. Tangkuban Perahu KM. 8 Lembang Jl. Dr Setiabudhi No 272 Jl. Dr Rum No 30 Bandung Jl. Sederhana No 53 Bandung TKI II Ruko III No 7 Jl. Gatot Subroto No. 19, Cimahi, West Java, Indonesia Jl. Dr Rabani No. 4 Bandung Total Permintaan Kapasitas Kendaraan
Permintaan Kopi (Dus) 10 8 10 6 10 10 4 6 6 3 4 77 24
Jarak Tempuh Jarak yang dibutuhkan perusahaan dalam proses pendistribusian. Jarak tempuh digunakan untuk mendapatkan waktu tempuh. Jarak tempuh yang dihitung antar konsumen dan jarak dari depot ke konsumen. Jarak tempuh diperoleh menggunakan bantuan google maps dengan satuan kilometer. Waktu Tempuh Waktu tempuh adalah waktu yang dibutuhkan kendaraan selama proses pendistribusian berlangsung. Waktu tempuh diperoleh dari jarak tempuh dibagi kecepatan rata-rata dikalikan 60 menit. Waktu tempuh = ( x 60 menit) (1)
Dij= Jarak Tempuh (Km) v= Kecepatan rata-rata mobil (km/jam)
Jumlah Kendaraan PT. X yang berlokasi di Bandung mempunyai kendaraan mobil avanza dalam pendistribusian kopi. Jenis kendaraan tersebut mempunyai kapasitas angkut yang terbatas. Kapasitas Kendaraan Kapasitas kopi yang dapat diangkut oleh mobil avanza menentukan berapa banyak permintaan pelanggan yang dapat dipenuhi perusahaan. Kapasitas kendaraan 24 dus/kendaraan. Waktu Loading dan Unloading Waktu loading adalah waktu yang dibutuhkan untuk menaikan kopi dari tempat ke kendaraan. Waktu unloading adalah waktu yang dibutuhkan untuk menurunkan kopi dari kendaraan ke tempat pelanggan. Kecepatan Kendaraan Kecepatan kendaraan adalah kecepatan yang digunakan supir saat melakukan proses pendistribusian. Kecepatan kendaraan diasumsikan sama. Waktu administrasi Waktu administrasi adalah waktu yang dibutuhkan oleh pelanggan untuk pembayaran. Jam Kerja Supir Jam kerja supir adalah batas waktu yang digunakan dalam proses pendistribusian. Jam kerja menentukan proses pendistribusian dapat tersalurkan tepat waktu atau tidak dengan melihat keterbatas jam kerja yang ada.
Reka Integra - 154
Usulan Rute Distribusi Kopi Arabika Premium Menggunakan Metode Nearest Neighbour dan Tabu Search di PT. X
4.2 Pengolahan Data Pengolahan data berdasarkan metode yang digunakan. Pengolahan data pembentukan rute menggunakan nearest neighbor, perbaikan menggunakan branch and bound, dan tabu search. 4.2.1 Pembentukan Rute Menggunakan Nearest Neighbour Penentuan rute dengan metode Nearest Neighbour dilakukan berdasarkan langkah-langkah, rute yang dihasilkan dapat dilihat pada pada Tabel 3 sampai Tabel 5. Tabel 3. Rekapitulasi Metode Nearest Neighbour Per 3 Hari Tur 1 2 3
Rute
Konsumen
Total Jarak (km)
1 2 3 1 2 1 2
0-37-30-63-48-19-41-28-33-34-0 0-56-47-50-59-16-40-43-55-8-15-29-2-35-0 0-27-13-51-3-12-7-6-0 0-32-58-17-52-46-10-2-0 0-49-62-53-9-57-25-38-18-45-0 0-61-39-42-54-4-20-21-0 0-22-0
12,02 20,96 16,75 16,6 46,5 59,8 22
Total Waktu (menit)
Jangka Waktu Kirim
375,502 Per 3 hari (Senin dan Kamis)
311,679 255,026
Tabel 4. Rekapitulasi Metode Nearest Neighbour Perminggu Tur 1 2
Rute
Konsumen
Total Jarak (km) Total Waktu (menit)
1 2 1 2
0-31-26-60-11-0 0-14-1-24-5-0 0-24-44-36-0 0-23-0
14,23 42,6 43 32
Jangka Waktu Kirim
296,45 Per minggu (Senin) 275,06
Tabel 5. Rekapitulasi Metode Nearest Neighbour Hari Senin Tur
1
2
Rute 1 2 3 4 5 6 1 2 3 4
Kons ume n 0-37-30-63-48-19-41-28-33-34-0 0-56-47-50-59-16-40-14-55-43-15-29-0 0-31-52-46-17-27-13-35-0 0-32-58-60-26-51-3-12-54-0 0-2-62-11-6-49-0 0-8-9-53-1-39-0 0-61-57-25-38-18-45-7-0 0-24-42-5-0 0-4-20-21-36-44-0 0-22-23-0
Total Jarak 12,02 16,67 13,85 19,13 12,6 23,3 33 33,2 83,3 35,8
Total Waktu
681,4
666,834
4.2.2 Perbaikan Menggunakan Branch and Bound Perbaikan rute dengan metode Branch and Bound dilakukan berdasarkan langkah-langkah, rute yang dihasilkan dapat dilihat pada pada Tabel 6 sampai Tabel 8. Tabel 6. Rekapitulasi Metode Branch and Bound Per 3 Hari
Tur 1 2 3
Rute 1 2 3 1 2 1 2
Konsumen 0-37-30-48-63-19-34-33-28-41-0 0-56-50-47-59-16-40-43-55-8-15-29-2-35-0 0-27-13-51-3-12-7-6-0 0-32-58-17-52-46-10-2-0 0-9-62-49-53-45-18-57-25-38-0 0-42-39-54-4-20-21-61-0 0-22-0
Total Jarak (km) 10,92 16,01 16,75 16,6 42,5 52,4 22
Reka Integra - 155
Total Waktu (menit)
Jangka Waktu Kirim
369,109 301,963 255,026
Per 3 hari (Senin dan Kamis)
Oktarina,dkk
Tabel 7. Rekapitulasi Metode Branch and Bound Perminggu Tur
Rute 1 2 3 4
1 2
Tur
1
2
Konsumen 0-11-26-60-31-0 0-24-5-14-1-0 0-24-44-36-0 0-23-0
Total Jarak (km) 14,03 39,6 43 32
Total Waktu (menit) 227,667 275,062
Waktu Kirim Perminggu (Senin)
Tabel 8. Rekapitulasi Metode Branch and Bound Hari Senin Total Jarak Total Waktu Rute Konsumen Waktu Kirim (km) (menit) 1 0-37-30-48-63-19-34-33-28-41-0 10,92 2 0-56-47-50-59-16-40-55-14-43-15-29-0 16,67 3 0-17-46-52-31-13-35 13,25 674,347 4 0-32-58-60-26-51-3-54-12-0 19,13 Senin 5 0-49-11-6-62-2-0 12,6 (Penggabungan) 6 0-8-9-1-53-39-0 23,3 1 0-8-45-18-38-25-57-61-0 33 2 0-42-5-2-0 26,9 663,67 3 0-21-20-4-36-44 65,2 4 0-22-23-0 35,8
4.2.3 Perbaikan Menggunakan Tabu Search Perbaikan rute dengan metode Tabu Search dilakukan berdasarkan langkah-langkah, rute yang dihasilkan dapat dilihat pada pada Tabel 9 sampai Tabel 11. Tabel 9. Rekapitulasi Metode Tabu Search Per 3 Hari Tur
Rute
2 3
Tur 1 2
Total Waktu (menit)
0-37-30-48-19-63-41-28-33-34-0 18,92 374,780 0-56-47-50-59-16-40-43-55-8-15-2-29-35-0 18,26 0-27-13-51-3-12-7-6-0 16,75 0-58-32-17-52-46-10-2-0 16,6 311,679 0-49-62-53-9-57-25-38-18-45-0 46,5 0-61-42-39-54-4-20-21-0 59,8 255,026 0-22-0 22 Tabel 10. Rekapitulasi Metode Tabu Search Perminggu
1 2 3 1 2 1 2
1
Total Jarak (km)
Konsumen
Rute 1 2 3 4
Konsumen 0-31-60-26-11-0 0-1-14-24-5-0 0-24-44-36-0 0-23-0
Total Jarak (km) 14,03 40,2 43 32
Reka Integra - 156
Total Waktu (menit) 243,700 275,062
Waktu Kirim
Per 3 Hari (Senin dan Kamis)
Waktu Kirim Perminggu (Senin)
Usulan Rute Distribusi Kopi Arabika Premium Menggunakan Metode Nearest Neighbour dan Tabu Search di PT. X
Tur
1
2
Rute 1 2 3 4 5 6 1 2 3 4
Tabel 11. Rekapitulasi Metode Tabu Search Hari Senin Total Jarak Total Waktu Waktu Kirim Konsumen (km) (menit) 0-37-30-48-19-63-41-28-33-34-0 11,92 0-56-47-50-59-16-40-55-14-43-15-29-0 16,67 0-31-52-46-17-35-13-27-0 14,96 679,45 0-32-58-60-26-51-3-54-12-0 19,13 Senin 0-2-62-6-11-49-0 12,6 (Penggabungan) 0-8-9-1-53-39-0 23,3 0-61-57-25-18-38-45-7-0 33 0-24-5-42-0 32,6 665,78 0-4-20-21-44-36-0 83,3 0-22-23-0 35,8
5. ANALISIS 5.1 Analisis Metode yang Digunakan Berdasarkan Alamat Pelanggan Pencarian rute menggunakan nearest neighbour sebatas pendekatan untuk mencari rute terbaik. Semua tur berawal dan berakhir di depot. Waktu yang digunakan tidak melebihi kapasitas horizon perencanaan yang tersedia. Penentuan rute kendaraan dengan nearest neighbour membuat efektif penerapannya dengan melayani semua konsumen berdasarkan jarak terakhir dari lokasi kendaraan yang selanjutnya akan didistribusikan. Pendistribusian pertiga hari menghasilkan 3 tur dengan waktu 375,502 menit, 311,679 menit dan 353,55 menit, sedangkan pendistribusian perminggu menghasilkan 2 tur dengan waktu 296,45 menit dan 275,06 menit. Setelah mendapatkan output dari metode Nearest Neighbour maka dilakukan perbaikan dengan menggunakan metode analitik yaitu Branch and Bound menggunakan software WinQsB. Tujuan dari metode ini adalah untuk memeriksa semua solusi layak yang mungkin sehingga mendapatkan hasil yang optimal. Perbaikan menggunakan Tabu Search menuntun setiap tahapannya agar dapat menghasilkan fungsi tujuan yang paling optimum tanpa terjebak ke dalam solusi awal yang ditemukan selama tahapan ini berlangsung. Perbaikan ini dilakukan untuk mencegah terjadinya perulangan dan ditemukannya solusi yang sama pada suatu iterasi yang akan digunakan lagi pada iterasi selanjutnya. Berdasarkan hasil perbaikan didapatkan solusi yang lebih efektif. Terjadi pertukaran posisi pada masing-masing rute sehingga menghasilkan penghematan waktu tempuh. Pertukaran posisi ini berpengaruh terhadap jarak tempuh yang dilalui oleh kendaraan.
Output dari kedua metode perbaikan mengalami hasil yang berbeda. Penggunaan metode Branch and Bound menghasilkan solusi yang lebih baik dibandingkan metode Tabu Search. Pendistribusian pertiga hari membutuhkan 3 unit kendaraan dan perminggu 2 unit kendaraan.
5.2 Analisis Metode yang Digunakan Berdasarkan Waktu Pengiriman Perusahaan melakukan pendistribusian kopi arabika premium ke pelanggan yaitu pertiga hari untuk setiap Senin dan Kamis, dan perminggu untuk setiap hari Senin. Jumlah kendaraan yang terbatas mengakibatkan perlunya penggabungan rute kendaraan berdasarkan waktu pengirimannya yaitu hari Senin. Reka Integra - 157
Oktarina,dkk
Setelah mendapatkan output dari metode Nearest Neighbour maka dilakukan perbaikan dengan menggunakan metode analitik yaitu Branch and Bound. Tujuan dari metode ini adalah untuk memeriksa semua solusi layak yang mungkin sehingga mendapatkan hasil yang optimal. Untuk mendapatkan hasil dari metode ini menggunakan software WinQsB.
Output dari Nearest Neighbour
juga dapat dipakai sebagai solusi awal untuk perbaikan menggunakan metode heuristik yaitu Tabu Search. Perbaikan menggunakan Tabu Search menuntun setiap tahapannya agar dapat menghasilkan fungsi tujuan yang paling optimum tanpa terjebak ke dalam solusi awal yang ditemukan selama tahapan ini berlangsung. Terjadi pertukaran posisi pada masing-masing rute sehingga menghasilkan penghematan waktu tempuh. Pertukaran posisi ini berpengaruh terhadap jarak tempuh yang dilalui oleh kendaraan.
Output dari kedua metode perbaikan mengalami hasil yang berbeda. Untuk metode Branch and Bound menghasilkan solusi yang lebih baik dibandingkan metode Tabu Search. Dari rute yang terbentuk dapat dilihat bahwa semua tur/rute berawal dan berakhir di depot. Waktu yang digunakan melebihi kapasitas jam kerja supir sebesar 3,5 jam. Perusahaan tetap menggunakan 2 unit kendaraan. Overtime yang dialami setiap kendaraan dapat dilakukan dengan penambahan jam kerja pada hari tersebut atau dengan melanjutkan ke hari selanjutnya.
5.3 Analisis Hasil Implementasi Pada saat ini PT. Coffindo Cabang Bandung memiliki jumlah kendaraan sebanyak 2 mobil avanza untuk mendistribusikan kopi arabika premium ke 63 pelanggan dengan jarak yang berbeda-beda. Penentuan rute dengan menggunakan metode Nearest Neighbour maka diperoleh 2 jenis pendistribusian yaitu pertiga hari (setiap Senin dan Kamis) dan perminggu (setiap Senin). Kekurangan kendaraan menyebabkan kedua jenis pendistribusian ini digabung dikirim untuk satu hari yang sama yaitu hari Senin. Untuk pengiriman hari Senin masing-masing kendaraan mengalami overtime sebanyak 3,5 jam. Selanjutnya diperbaiki dengan menggunakan metode analitik yaitu Branch and Bound dan meetode heuristik yaitu Tabu Search. Kedua metode perbaikan ini mengalami hasil yang berbeda. Pengiriman dengan menggunakan metode Branch and Bound menghasilkan solusi yang lebih baik dibandingkan menggunakan metode Tabu Search. Pengiriman pertiga hari (setiap Senin dan Kamis) membutuhkan 3 unit kendaraan dan pengiriman perminggu (setiap Senin) membutuhkan 2 unit kendaraan. Hal ini menyebabkan kekurangan jumlah kendaraan. Untuk mengatasinya dilakukan penggabungan pengiriman setiap Senin. Penggabungan ini tetap menggunakan 2 unit kendaraan tetapi masing-masing kendaraan mengalami overtime 3,5 jam. Overtime ddapat dilakukan pada hari yang sama dengan menambah jam kerja supir atau dengan melanjutkan ke hari selanjutnya. Tujuan dari penggabungan pengiriman ini untuk menekan biaya operasional perusahaan.
Reka Integra - 158
Usulan Rute Distribusi Kopi Arabika Premium Menggunakan Metode Nearest Neighbour dan Tabu Search di PT. X
6. KESIMPULAN Kesimpulan yang diperoleh dari hasil penelitian adalah: 1. Pendistribusian yang dilakukan perusahaan yaitu pendistribusian pertiga hari (setiap Senin dan Kamis) dan pendistribusian perminggu (setiap Senin). 2. Pendistribusian pertiga hari menghasilkan 3 tur sedangkan pendistribusian perminggu menghasilkan 2 tur. 3. Pendistribusian gabungan yang dilakukan hari Senin menghasilkan 2 tur dan masingmasing kendaraan mengalami overtime 3,5 jam. 4. Overtime dapat dilakukan pada hari yang sama dengan menambah jumlah jam kerja supir atau dilanjutkan hari berikutnya. 5. Penelitian lanjutan dapat menggunakan metode lain seperti: metode eksak (metode Dinamis), metode heuristik (Sequential Insertion dan Clarke and Wright Savings), metode metaheuristik (Algoritma Genetika dan Simulated Annealing). REFERENSI Pujawan, I.N., Mahendrawathi, (2010), Supply Chain Management, Edisi Kedua, Guna Widya, Surabaya. Laporte, G. (1992). The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms, European Journal of Operating Research, 59. Johnson, D. L., Bentley J.L., Mc Geoch L. A., and Rothberg E. E. (1997). Near - optimal
solutions to very large travelling salesman problem , Monograph, in preparation.
Glover, F and Laguna, M. (1997). Tabu Search. Massachusetts: Kluwer Academic Publisher. Lestari, A., Metode Travelling Salesman untuk Menentukan Lintasan Terpendek pada Daerah-daerah yang Teridentifikasi Bahaya. Tugas Akhir S-1, Surabaya: Institut Teknologi Sepuluh November, 2010. Riyanti, Eka., Penerapan Algoritma Branch and Bound Untuk Penentuan Rute Objek Wisata. Tugas Akhir S-1, Bandung: Universitas Komputer Indonesia, 2004. Toth P., & Vigo D., 2002, The Vehicle Routing Problem, Philadelphia: SIAM,2002. Winarno, Wing Wahyu. 2008. Analisis Manajemen Kuantitatif Dengan WinQSB 2.0. Yogyakarta: UPP STIM YKPN. Miller, David M., Matson, Jessica O., Vaidyanathan, Bharat S., (1999), A Capacitated Vehicle Routing Problem For Just in Time delivery, ITE Trancactions. Suprayogi. (2003). Algoritma Sequential Insertion Untuk Memecahkan Vehicle Routing Problem. Jurnal Teknik dan Manajemen Industri, 23(3).
Reka Integra - 159