Analisis dan Usulan Rute Optimum dengan Menggunakan Algoritma Generate and Test di PT Agronesia Divisi AMDK (Agroplas) Proposal and Analysis of Optimum Route by Using Generate and Test Algorithm at PT Agronesia AMDK Division (Agroplas) Astrid Astari Pattawala, Victor Suhandi Jurusan Teknik Industri – Fakultas Teknik Universitas Kristen Maranatha E-mail:
[email protected],
[email protected]
Abstrak PT Agronesia Divisi AMDK sebagai salah satu perusahaan yang bergerak di bidang industri pengolahan air minum dalam kemasan, memiliki rute pendistribusian produk dimana target konsumen yang akan dikunjungi dalam satu hari berada di beberapa wilayah berbeda. Oleh karena itu, dilakukan penelitian di perusahaan ini dengan tujuan untuk mengoptimalkan rute pendistribusian produk menggunakan tiga metode pencarian rute optimum, yaitu metode Nearest Neighbor Heuristic, Branch and Bound Method dan algoritma Generate and Test. Hasil yang diperoleh adalah metode NNH menghemat waktu sebesar 0,823 jam atau 9,78%, metode B&B menghemat waktu sebesar 1,116 jam atau 13,55% dan algoritma G&T menghemat waktu sebesar 1,14 jam atau 13,83%. Sehingga algoritma G&T lebih baik dibandingkan metode NNH dan B&B. Usulan yang diberikan berupa rute pendistribusian baru dimana pembagian target konsumen berdasarkan wilayah (menurut peta) sehingga dihasilkan enam wilayah konsumen. Konsumen dalam satu wilayah yang sama akan dikunjungi dalam waktu satu hari. Selanjutnya metode Linear Programming digunakan untuk menentukan sumber pemenuhan permintaan tiap wilayah dan algoritma G&T digunakan untuk mencari rute optimum di setiap wilayah. Hasil yang diperoleh adalah penghematan waktu sebesar 13,5 jam atau 27,88% dari rute perusahaan saat ini, sehingga rute usulan lebih baik dibandingkan dengan rute perusahaan. Kata kunci: Rute optimum, Nearest Neighbor Heuristic, Branch and Bound Method, Algoritma Generate and Test, Linear Programming Abstract PT Agronesia AMDK Division as a company that engaged in manufacturing of bottled drinking water has product distribution route where the customers target in a day are on different regions. Therefore, a research is done in this company with the goal to optimize product distribution routes using three optimum route search methods, those are Nearest Neighbor Heuristic method, Branch and Bound Method and Generate and Test algorithm. The results are NNH method reduces time for 0,823 hours or 9,78%, B&B method reduces time for 1,116 hours or 13,55% and G&T algorithm reduces time for 1,14 hours or 13,83%. So the G&T algorithm is better than NNH and B&B methods. The given proposal is a new product distribution route where customers target allocation based on regions (according to the map) so the result is six regions of customers. Customers in the same region will be visited in one day time. Furthermore Linear Programming method is used to determine the source of the demand fulfillment in each region and the G&T algorithm is used to find the optimum route in each region. The result is the new route reduces time for 13,5 hours or 27,88% of the company's current route, so the proposal route is better compared to the company’s route. Keywords: Optimum Route, Nearest Neighbor Heuristic, Branch and Bound Method, Generate and Test Algorithm, Linear Programming
1
JURNAL INTEGRA VOL. 3, NO. 1, JUNI 2013: 1-14
1. Pendahuluan Industri Air Minum Dalam Kemasan (AMDK) merupakan salah satu sektor industri yang memiliki prospek sangat baik. Hal ini disebabkan perubahan pola konsumsi masyarakat yang menyukai barang serba praktis dan siap saji, sehingga permintaan akan air minum dalam kemasan cenderung meningkat. Itu berarti jumlah konsumen semakin bertambah banyak dan industri AMDK diharapkan dapat memenuhi permintaan konsumen tersebut. Dengan meningkatnya jumlah konsumen maka pihak perusahaan harus memikirkan cara untuk mendistribusikan produk tepat waktu dan tidak ada konsumen yang terlewatkan. Oleh karena itu, masalah distribusi merupakan salah satu bagian penting dalam industri. Faktor-faktor yang merupakan kendala bagi distribusi antara lain faktor jarak, waktu, alat transportasi, biaya dan sebagainya. Salah satu masalah distribusi yang sering dibahas adalah Traveling Salesman Problem (TSP). Banyak peneliti berusaha mengkaji masalah distribusi ini terutama dari segi jarak dan waktu dengan metode-metode tertentu. Metode yang akan digunakan untuk menyelesaikan masalah ini dapat menghasilkan rute terpendek yang mendekati optimal ataupun optimal dengan mengunjungi setiap daerah tepat satu kali. PT Agronesia Divisi AMDK sebagai salah satu perusahaan yang bergerak di bidang industri pengolahan Air Minum Dalam Kemasan (AMDK) dengan merek dagang BMC, dapat mengalami kendala dalam hal transportasi atau distribusi produk ke konsumen yang berada di area kota Bandung. Permasalahan/kendala yang terjadi adalah rute pendistribusian produk yang belum optimum. Hal ini disebabkan oleh target konsumen yang akan dikunjungi dalam waktu sehari berada pada beberapa wilayah yang berbeda, sehingga berpengaruh terhadap total jarak perjalanan yang harus ditempuh. Target konsumen yang akan dikunjungi setiap hari ditetapkan oleh perusahaan berdasarkan permintaan konsumen. Oleh karena itu, penulis bermaksud menganalisis rute yang diterapkan perusahaan saat ini, agar dapat menghemat waktu perjalanan dan dapat memberikan rute usulan yang lebih baik.
2. Pembahasan Berikut adalah langkah-langkah penelitian yang dilakukan agar proses pengerjaan dapat berjalan dengan baik: 1. Penelitian pendahuluan. 2. Identifikasi masalah. 3. Pembatasan masalah dan asumsi. 4. Perumusan masalah. 5. Tujuan penelitian. 6. Tinjauan pustaka. 7. Penentuan metode pemecahan masalah. 8. Pengumpulan data. 9. Pengolahan data. 10. Usulan. 11. Kesimpulan dan saran. Ada 3 metode yang digunakan untuk memecahkan masalah (mencari rute optimum) yaitu metode Nearest Neighbor Heuristic (NNH), Branch and Bound (B&B) dan Algoritma Generate and Test (G&T). Metode NNH dan B&B merupakan metode yang dapat digunakan untuk memperoleh solusi yang baik. Sedangkan Algoritma G&T merupakan metode dengan teknik pencarian cerdas menggunakan bantuan komputer yang menjamin hasil yang optimal. Algoritma ini membangkitkan seluruh kombinasi yang ada dan diuji satu persatu, kemudian dipilih alternatif solusi yang terbaik. Dari ketiga metode ini, nantinya akan dipilih satu metode yang terbaik berdasarkan total jarak dan waktu perjalanan terkecil. Penggunaan metode-metode di atas mengacu pada data per hari yang ada di perusahaan. Hal ini memiliki kelemahan berkenaan dengan tempat-tempat yang akan dikunjungi dapat berjauhan. 2
RUTE OPTIMUM MENGGUNAKAN ALGORITMA GENERATE & TEST (Astrid A. P., et al.)
Untuk mengatasi hal ini, diperlukan jadwal pengiriman per wilayah. Setiap wilayah memiliki beberapa tempat yang berdekatan yang hendak dikunjungi. Metode Linear Programming digunakan untuk menentukan sumber pemenuhan untuk setiap wilayah, dimana pemenuhan permintaan suatu wilayah akan dinotasikan kedalam bentuk matematis, sehingga diperoleh bentuk fungsi tujuan serta kendalanya. Metode ini memiliki variabel keputusan berupa proporsi pengiriman yang rentang nilainya dari nol sampai satu. Metode ini digunakan untuk mencari sumber pemenuhan permintaan (pabrik atau gudang) ke tiap wilayah. Setelah sumber pemenuhan ditentukan untuk setiap wilayah, kemudian dilanjutkan menggunakan NNH, B&B, dan G&T untuk penentuan rute dalam setiap wilayah. Apabila cara ini dapat diterapkan secara jangka panjang maka diperkirakan akan memberikan penghematan yang sangat besar. Lama perjalanan dihitung dari jarak tempuh dibagi dengan kecepatan rata-rata kendaraan yang disampaikan oleh Direktur Jenderal Perhubungan Darat pada 28 Juni 2012, yakni rata-rata 14,3 km/jam untuk wilayah Bandung. Sedangkan untuk lamanya armada berada di suatu tempat diestimasi menggunakan regresi linear. 2.1 Nearest Neighbor Heuristic Metode Nearest Neighbor Heuristic merupakan salah satu algoritma awal yang digunakan untuk menentukan solusi pada Travelling Salesman Problem. Metode ini dapat digambarkan sebagai berikut seorang salesman memulai perjalanannya dari kota mana saja yang dipilih secara acak dan kemudian melanjutkan perjalanannya dengan mengunjungi kota terdekat berikutnya sampai semua kota telah dikunjungi. Metode ini dapat dengan cepat menghasilkan jalur tur yang pendek, tetapi biasanya bukan jalur yang optimal. Langkah-langkah penyelesaian dengan metode Nearest Neighbor Heuristic: 1. Pilih salah satu kota secara bebas yang mana saja. 2. Kemudian pilih kota selanjutnya yang belum dikunjungi dan memiliki jarak yang paling minimum dari kota sekarang. 3. Ulangi langkah 2 hingga semua kota terkunjungi dan rute telah terbentuk. 4. Hitung hasilnya dengan cara menjumlahkan jarak dari awal sampai akhir rute perjalanan. Solusi yang lebih baik mungkin dapat diperoleh dengan cara mengulang pencarian rute dan dimulai dari kota awal yang berbeda. (Taha, 2011) 2.2 Branch and Bound Method Branch and Bound (B&B) merupakan metode algoritma yang umum dalam mencari solusi optimal atas masalah optimasi yang beragam, khususnya dalam optimasi diskrit dan kombinatorial. Metode Branch and Bound terdiri dari penghitungan sistematis semua kandidat solusi. Metode Branch and Bound adalah salah satu metode untuk menghasilkan penyelesaian optimal program linier yang menghasilkan variable-variable keputusan bilangan bulat. Sesuai dengan namanya, metode ini membatasi penyelesaian optimum yang akan menghasilkan bilangan pecahan dengan cara membuat cabang atas dan bawah bagi masing-masing variable keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru. Dalam branch and bound terdapat tiga tahap dasar yaitu percabangan (branching), pembatasan (bounding), dan pengukuran (fathoming). Penjelasan ketiga tahap tersebut adalah sebagai berikut: 1. Percabangan (branching) Percabangan berhubungan dengan pemilihan sub masalah yang belum dicabangkan dan memecahnya menjadi sub masalah yang lebih kecil. 2. Pembatasan (bounding)
3
JURNAL INTEGRA VOL. 3, NO. 1, JUNI 2013: 1-14
Pembatasan dilakukan untuk menentukan suatu batas yang digunakan untuk melihat seberapa baik solusi untuk suatu sub masalah. 3. Pengukuran (fathoming) Pengukuran dilakukan untuk menentukan apakah suatu sub masalah perlu untuk ditelusuri lebih lanjut. 2.3 Algoritma Generate and Test Algoritma generate and test adalah algoritma yang dalam sistem kerjanya membangun semua lintasan yang mungkin merupakan solusi dari permasalahan pencarian lintasan terpendek dan melakukan pengujian terhadap lintasan-lintasan tersebut, sehingga diperoleh solusi berupa lintasan terpendek. Kelebihan dari algoritma generate and test ini adalah pencariannya yang lengkap dan selalu menghasilkan solusi yang optimal. Sedangkan kelemahannya adalah perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar dalam pencariannya. Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Pada prinsipnya, algoritma ini meng-generate sebuah kandidat solusi, lalu dites apakah kandidat tersebut solusi yang dicari. Iterasi berhenti setelah semua kandidat solusi telah dites untuk menghasilkan solusi yang optimal. Algoritmanya sebagai berikut: 1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal). 2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. 3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama. (Kusumadewi, 2005)
Sumber : http://nurmanto.com/metode-generate-and-test/ Gambar 1. Alur Pencarian dengan Generate and Test
2.4 Linear Programming Linear Programming adalah teknik yang kuat untuk membantu pengambilan keputusan manajerial bagi beberapa jenis masalah. Pendekatan dasarnya adalah untuk merumuskan model matematika yang disebut model Linear Programming untuk menunjukan masalah dan kemudian untuk menganalisis model ini. Kata linear mengacu pada bentuk ekspresi matematika dalam model ini. Programming tidak mengacu pada pemrograman komputer, melainkan pada dasarnya adalah sebuah sinonim untuk perencanaan. Dengan demikian, Linear Programming berarti perencanaan kegiatan diwakili oleh model matematika linear.
4
RUTE OPTIMUM MENGGUNAKAN ALGORITMA GENERATE & TEST (Astrid A. P., et al.)
Setiap model Linear Programming meliputi variabel keputusan untuk mewakili keputusan yang harus dibuat, kendala untuk mewakili pembatasan pada nilai-nilai yang layak dari variabel keputusan, dan fungsi tujuan yang mengekspresikan ukuran keseluruhan kinerja masalah. (Hillier, 2003) 2.5 Pengumpulan dan Pengolahan Data 2.5.1 Rute Perjalanan Perusahaan Rute perjalanan perusahaan dapat dilihat pada Tabel 1 yang merupakan target lokasi-lokasi yang akan dikunjungi dalam satu hari. Tabel 1. Target Kunjungan Perusahaan Target Konsumen (lokasi)
Hari ke1
1
4
16
17
21
22
49
50
2
2
3
6
9
11
12
45
48
3
8
10
13
14
15
19
35
38
40
4
5
7
18
20
23
24
25
46
47
5
30
31
39
41
42
43
44
6
26
27
28
29
32
33
34
36
37
2.5.2 Penentuan Pembagian Wilayah Berdasarkan data konsumen yang ada, wilayah pengiriman produk galon dapat dibagi menjadi enam wilayah (berdasarkan peta) sebagai berikut: 1. Wilayah Cimahi sebanyak 15 konsumen. Tabel 2. Titik Koordinat (derajat) dan Demand (galon) Wilayah Cimahi Lintang
Bujur
Demand
A Harmaen
Nama Konsumen
Cigugur Tengah, Cimahi Tengah, Jawa Barat
Alamat
-6.893
107.565
5
B Santi
Cipageran, Cimahi Utara, Jawa Barat
-6.845
107.554
5
C Kartika Sari Holis
Jalan Paralon, Bandung, Jawa Barat
-6.928
107.567
12
D Taufik
Jalan Batujajar - Warung Pulus, Batujajar, Jawa Barat
-6.918
107.509
12
E
Ade Ezzer
Jalan Cigugur Tengah, Cimahi Tengah, Jawa Barat
-6.889
107.552
5
F
Doni Iskandar
Jalan Cijerah 2, Cimahi Selatan, Jawa Barat
-6.924
107.559
16
G Yudi
Jalan Gegerkalong Tengah 2, Parompong, Jawa Barat
-6.866
107.581
20
H Kusuma
Jalan Leuwigajah, Cimahi Selatan, Jawa Barat
-6.903
107.535
10
I
Mitra Suplier
Jalan RH Abdul Halim, Cimahi Tengah, Jawa Barat
-6.891
107.552
37
J
Unjani
Jalan Terusan Jendral Sudirman Cimahi, Jawa Barat
-6.886
107.532
7
K Ade
Jalan Terusan, Cimahi Tengah, Jawa Barat
-6.872
107.546
30
L
Jalan Trowulan 2, Margaasih, Jawa Barat
-6.918
107.555
59
M Mulia
Cibeber, Cimahi Selatan, Jawa Barat
-6.896
107.53
7
N Cece
Kompleks Bukit Permata Cimahi Blok F
-6.868
107.522
15
O Amarulah
Jalan Raya Cimindi, Cimahi Tengah, Jawa Barat
-6.892
107.558
77
Tuti
5
JURNAL INTEGRA VOL. 3, NO. 1, JUNI 2013: 1-14
2. Wilayah Karees sebanyak 10 konsumen. Tabel 3. Titik Koordinat (derajat) dan Demand (gallon) Wilayah Karees Nama Konsumen
Alamat
Lintang
Bujur
Demand
A Rudi
Jalan Galunggung, Bandung
-6.925
107.627
30
B Trisnadi
Jalan Buah Batu, Bandung
-6.940
107.626
36
C Riri
Jalan Burangrang, Bandung
-6.925
107.620
30
D Yeni
Jalan Jenderal Gatot Subroto, Bandung
-6.925
107.631
28
E
Anita
Jalan Guntursari, Bandung
-6.937
107.627
35
F
Agung
Jalan Lele, Bandung
-6.932
107.617
32
G Cecep Wawan
Jalan Lengkong Tengah, Bandung
-6.928
107.612
40
H Bahtiar
Jalan Lodaya, Bandung
-6.931
107.622
35
I
Nurkustia Pualam
Jalan Pualam, Bandung
-6.941
107.624
30
J
Kadin
Jalan Talaga Bodas, Bandung
-6.928
107.623
35
3. Wilayah Gedebage sebanyak 6 konsumen. Tabel 4. Titik Koordinat (derajat) dan Demand (galon) Wilayah Gedebage Nama Konsumen
Alamat
Lintang
Bujur
Demand
A Duta Abadi Perkasa Jalan Batununggal Indah 2, Bandung
-6.956
107.624
40
B Sarahfie
Jalan Cipagalo Girang, Bandung
-6.951
107.648
45
C Dedi
Jalan Cipamokolan, Bandung
-6.951
107.677
38
D Herman
Jalan Kali Cipamokolan, Bandung
-6.941
107.675
50
E
Encep
Jalan Soekarno Hatta, Bandung
-6.943
107.649
45
F
Upit
Jalan Waas, Bandung
-6.952
107.627
50
4. Wilayah Kabupaten Bandung sebanyak 9 konsumen. Tabel 5. Titik Koordinat (derajat) dan Demand (galon) Wilayah Kabupaten Bandung Nama Konsumen
Alamat
Lintang
Bujur
Demand
A Tisti
Jalan Cicalengka, Bandung
-6.920
107.657
36
B Moriuchi
Jalan Cisirung, Padalarang 1, Bandung
-6.974
107.606
40
C Awang
Jalan Pajagalan, Bandung
-6.925
107.601
30
D BSTM FT
Jalan Raya Dayeuhkolot, Bale Endah, Bandung
-6.985
107.623
30
E
Fajar
Jalan Batu Indah 3, Bandung
-6.953
107.634
28
F
Namura
Jalan Buana Sari Raya Timur, Bandung
-6.963
107.645
30
G Adam
Jalan Logam, Bandung
-6.959
107.644
28
H Neneng
Jalan Jakarta, Bandung
-6.914
107.639
25
I
Jalan Natuna, Bandung
-6.917
107.616
40
Endang
5. Wilayah Ujungberung sebanyak 4 konsumen. Tabel 6. Titik Koordinat (derajat) dan Demand (galon) Wilayah Ujungberung Nama Konsumen
6
Lintang
Bujur
Demand
A Dani
Cibiru, Bandung
Alamat
-6.919
107.717
60
B Efa
Jalan Cipadung, Bandung
-6.927
107.711
70
C Upen
Jalan Golf, Bandung
-6.918
107.689
60
D Iwan
Jalan Jatikusumah, Cilengkrang, Bandung
-6.904
107.698
65
RUTE OPTIMUM MENGGUNAKAN ALGORITMA GENERATE & TEST (Astrid A. P., et al.)
6. Wilayah Lembang sebanyak 6 konsumen. Tabel 7. Titik Koordinat (derajat) dan Demand (galon) Wilayah Lembang Nama Konsumen
Alamat
Lintang
Bujur
Demand
A Joko
Jalan Grand Hotel, Lembang, Bandung
-6.816
107.618
50
B Usep
Jalan Kebon Hui, Lembang, Bandung
-6.828
107.590
65
C Evelin
Jalan Raya Lembang, Lembang, Bandung
-6.819
107.612
50
D Rudy
Jalan Tangkuban Perahu, Lembang, Bandung
-6.779
107.644
35
E Tini
Jalan Wira, Lembang, Bandung
-6.818
107.627
46
F
Jalan Nyampay, Lembang, Bandung
-6.815
107.646
50
Indah
Titik koordinat lintang dan bujur diperoleh dari Google Maps. 2.5.3 Penentuan Rasio Jarak Tempuh Sebenarnya dengan Jarak Dua Titik Koordinat Lintang dan Bujur Uji normal dilakukan untuk mengetahui apakah rasio antara jarak tempuh sebenarnya (dari GoogleMaps) dengan jarak dua tempat secara garis lurus yang didapatkan dari hasil perhitungan rumus phytagoras dari titik koordinat yang diperoleh (karena peta Indonesia berada di sekitar ekuator sehingga derajat pada lintang dan bujur relatif sama jaraknya) dapat diaplikasikan kedalam program. Jika data berdistribusi normal maka rasio ini akan dijadikan patokan untuk mendapatkan jarak tempuh dari titik koordinat masing-masing lokasi konsumen. Data yang akan diuji normal adalah data dari wilayah Cimahi. Tabel 8 menampilkan hasil rasio jarak. Dari hasil pengolahan diperoleh nilai Z hitung (0,092 dan -1,567) berada diantara Z tabel ( 1,96) maka data mengikuti distribusi normal pada taraf nyata 0,05. Setelah mengetahui data berdistribusi normal maka dicari nilai rasio yang akan digunakan sebagai patokan penentuan jarak tempuh. Nilai rasio ini didapatkan dengan cara merata-ratakan data rasio jarak yang ada sehingga didapatkan nilai rasio sebesar 1,408. Tabel 8. Data Rasio Jarak
2.5.4 Uji Regresi Linear untuk Menghitung Lamanya Kunjungan Uji regresi linear digunakan untuk mencari nilai konstanta a dan b dalam persamaan y = a + bx. Persamaan regresi ini akan digunakan untuk menghitung waktu kunjungan tiap lokasi konsumen. Nilai a menunjukan waktu yang diperlukan untuk parkir dan nilai b menunjukan waktu bongkar 7
JURNAL INTEGRA VOL. 3, NO. 1, JUNI 2013: 1-14
muat 1 galon serta x menunjukan demand. Berikut data demand dan waktu kunjungan yang akan diolah: Tabel 9. Data Demand dan Waktu Kunjungan
Dari hasil uji regresi linear diperoleh nilai konstanta a dan b. Nilai a = 0,097 jam atau 6 menit dan b = 0,008 jam atau 30 detik, maka persamaan regresi linear untuk mencari waktu kunjungan di tiap lokasi konsumen menjadi y = 1/10 + (1/120)x, dimana x adalah demand. 2.5.5 Pengolahan Data Rute Perjalanan Perusahaan Contoh input dan output dari metode NNH, B&B dan G&T yang digunakan untuk mengolah data rute perjalanan perusahaan sebagai berikut: 1. Metode NNH Input untuk metode NNH menggunakan software WinQSB dapat dilihat pada Gambar 2, sedangkan untuk hasil pengolahannya dapat dilihat pada Gambar 3.
Gambar 2. Input NNH Hari Ke-1
Gambar 3. Output NNH Hari Ke-1
Rute perjalanannya adalah G-22-21-17-16-1-4-49-50-G dengan total jarak 71,97 km. 2. Metode B&B Input untuk metode B&B menggunakan software WinQSB dapat dilihat pada Gambar 4, sedangkan untuk hasil pengolahannya dapat dilihat pada Gambar 5. 8
RUTE OPTIMUM MENGGUNAKAN ALGORITMA GENERATE & TEST (Astrid A. P., et al.)
Gambar 4. Input B&B Hari Ke-1
Gambar 5. Output B&B Hari Ke-1
Rute perjalanannya adalah G-49-50-1-4-22-21-17-16-G dengan total jarak 70,42 km. 3. Algoritma G&T Input untuk metode G&T menggunakan software G&T dapat dilihat pada Gambar 6, sedangkan untuk hasil pengolahannya dapat dilihat pada Gambar 7.
Gambar 6. Input G&T Hari Ke-1
Gambar 6 menunjukan input hari ke-1. Angka 8 pada bagian kiri atas menunjukan jumlah lokasi konsumen, baris pertama menunjukan titik koordinat garis lintang dan bujur sumber pemenuhan permintaan (gudang). Sedangkan pada baris selanjutnya, kolom pertama menunjukan titik koordinat garis lintang masing-masing lokasi konsumen, kolom kedua menunjukan titik koordinat garis bujur masing-masing lokasi konsumen dan kolom ketiga menunjukan jumlah demand masing-masing konsumen. Tabel. 10 Output G&T Hari Ke-1 Hari ke-1 No
0
1
2
3
4
5
6
7
8
Konsumen
G
1
4
16
17
21
22
49
50
Output G&T Rute terpilih
0
2
1
7
8
3
4
5
6
0
Artinya
G
4
1
49
50
16
17
21
22
G
9
JURNAL INTEGRA VOL. 3, NO. 1, JUNI 2013: 1-14
Gambar 7. Output G&T Hari Ke-1
Berdasarkan tabel 10, nomor 0 berarti gudang, nomor 1 berarti konsumen ke-1 dan seterusnya sampai nomor 8 berarti konsumen ke-50. Gambar 7 menunjukan urutan rute terpilih adalah 02-1-7-8-3-4-5-6-0, jadi urutan rute dengan nomor konsumen yang sebenarnya adalah G-4-1-4950-16-17-21-22-G dengan total jarak 68,49 km. Waktu yang digunakan untuk transportasi sebesar 68,49 km / 14,3 km/jam yakni 4,79 jam. Sedangkan lamanya armada di setiap lokasi sesuai demand masing-masing (menggunakan rumus y = 1/10 + (1/120)x secara total adalah 2,89 jam. Jadi waktu total yang dibutuhkan sebesar 7,68 jam. 2.5.6 Perbandingan Hasil Ketiga Metode dan Rute Perusahaan Rute perusahaan yang telah diolah menggunakan tiga metode pencarian rute optimum akan dibandingkan dengan rute perusahaan saat ini untuk mengetahui total jarak terkecil diantara semua metode yang digunakan. Tabel 11 merupakan contoh rangkuman rute perjalanan dengan ketiga metode dan rute perusahaan. Tabel 11. Rute Perjalanan dengan Metode NNH, B&B, G&T dan Rute Perusahaan Untuk Hari Ke-1 Hari ke-
1
Rute
Metode
Jarak (Km)
Waktu Perjalanan (Jam)
NNH
G
22
21
17
16
1
4
49
50
G
71.97
5.033
B&B
G
49
50
1
4
22
21
17
16
G
70.42
4.924
G&T
G
4
1
49
50
16
17
21
22
G
68.49
4.790
Perusahaan
G
1
4
16
17
21
22
49
50
G
76.90
5.378
Rute yang dihasilkan dari metode NNH adalah G-22-21-17-16-1-4-49-50-G, dengan total jarak 71,97 km dan waktu perjalanan 5,033 jam. Rute yang dihasilkan dari metode B&B adalah G-4950-1-4-22-21-17-16-G, dengan total jarak 70,42 km dan waktu perjalanan 4,924 jam. Rute yang dihasilkan dari metode G&T adalah G-4-1-49-50-16-17-21-22-G, dengan total jarak 68,49 km dan waktu perjalanan 4,79 jam. Sedangkan rute dari perusahaan yaitu G-1-4-16-17-21-22-49-50-G menghasilkan total jarak 76,90 km dan waktu perjalanan 5,378 jam. Setelah didapatkan waktu kerja yang tersedia, waktu perjalanan dan waktu kunjungan maka dilakukan perhitungan total waktu keseluruhan untuk setiap hari kunjungan. Kemudian dilakukan perbandingan total waktu antara ketiga metode dan rute perusahaan dengan waktu yang tersedia untuk mengetahui apakah rute tersebut layak untuk digunakan. Rute dapat dikatakan layak jika total waktu keseluruhan lebih kecil atau sama dengan waktu yang tersedia. Selain itu penulis juga melakukan perbandingan total waktu antara ketiga metode dengan rute perusahaan untuk mengetahui apakah rute perusahaan sudah baik. Berikut hasil perbandingannya: Tabel 12. Perbandingan Total Waktu Untuk Hari Ke-1 Hari ke-
1
Metode
Waktu Perjalanan (Jam)
Waktu Kunjungan (Jam)
Total Waktu (Jam)
NNH
5.033
2.892
7.925
B&B
4.924
2.892
7.816
G&T
4.790
2.892
7.681
Perusahaan
5.378
2.892
8.269
Total waktu yang didapatkan dari metode NNH sebesar 7,925 jam dan jika dibandingkan dengan waktu yang tersedia sebesar 8 jam maka rute ini dikatakan layak. Total waktu yang didapatkan dari metode B&B sebesar 7,816 jam dan jika dibandingkan dengan waktu yang tersedia sebesar 8 jam 10
RUTE OPTIMUM MENGGUNAKAN ALGORITMA GENERATE & TEST (Astrid A. P., et al.)
maka rute ini dikatakan layak. Total waktu yang didapatkan dari metode G&T sebesar 7,681 jam dan jika dibandingkan dengan waktu yang tersedia sebesar 8 jam maka rute ini dikatakan layak. Untuk rute perusahaan, total waktu yang didapatkan sebesar 8,269 jam dan jika dibandingkan dengan waktu yang tersedia sebesar 8 jam maka rute ini dikatakan tidak layak.
2.6 Usulan Usulan yang diberikan berupa rute pendistribusian baru dimana pembagian target konsumen berdasarkan wilayah (menurut peta) sehingga dihasilkan enam wilayah konsumen. Konsumen dalam satu wilayah yang sama akan dikunjungi dalam waktu satu hari. Selanjutnya metode Linear Programming digunakan untuk menentukan sumber pemenuhan permintaan tiap wilayah dan algoritma G&T digunakan untuk mencari rute optimum di setiap wilayah. 2.6.1 Penentuan Sumber Pemenuhan Permintaan Setelah konsumen dibagi menjadi beberapa wilayah berdasarkan peta, kemudian menentukan sumber pemenuhan permintaan untuk masing-masing wilayah. Ada 2 sumber untuk memenuhi permintaan konsumen yaitu dari pabrik dan gudang. Sumber pemenuhan permintaan ditentukan berdasarkan jarak terdekat dari pabrik atau gudang ke wilayah tertentu. Setelah itu, perhatikan kapasitas yang ada di pabrik atau gudang apakah cukup untuk memenuhi permintaan wilayah tersebut. Untuk menyelesaikan masalah ini digunakan metode Linear Programming (LP). Berikut penjelasan mengenai penentuan sumber pemenuhan permintaan menggunakan metode LP: Formulasi masalah : Variabel keputusan : X11 = Keputusan pengiriman dari pabrik ke wilayah 1 X21 = Keputusan pengiriman dari gudang ke wilayah 1 X12 = Keputusan pengiriman dari pabrik ke wilayah 2 X22 = Keputusan pengiriman dari gudang ke wilayah 2 ... Xij = Keputusan pengiriman dari i ke wilayah j, dimana i = 1 atau 2, dan j = 1 sampai 6 Fungsi tujuan : Min Jarak (Z) Min Jarak (Z)
=
atau
= roundup
* J11 + roundup
* J21 +
roundup
* J12 + roundup
* J22 + ... +
roundup
* J1j + roundup
Kendala : Kapasitas pabrik
* J2j
(1)
=
KP
(2)
=
KG
(3)
Kapasitas produksi =
KPr
(4)
Kapasitas gudang D1
=
(5)
D2
=
(6)
Dn
=
(7)
Keterangan : i = Sumber pemenuhan (1 = pabrik ; 2 = gudang)
11
JURNAL INTEGRA VOL. 3, NO. 1, JUNI 2013: 1-14
j Dj K Jij KP KG KPr
= = = = = = =
Wilayah yang dituju (wilayah 1 sampai 6) Demand wilayah ke-j (unit galon/minggu) Kapasitas kendaraan (unit galon) Jarak dari i ke wilayah j (km) Kapasitas pabrik (unit galon/minggu) Kapasitas gudang (unit galon/minggu) Kapasitas produksi (unit galon/minggu)
Berdasarkan hasil pengolahan dengan metode LP dapat diketahui nilai X11 = 0, X21 = 1, X12 = 0, X22 = 1, X13 = 0, X23 = 1, X14 = 0, X24 = 1, X15 = 0, X25 = 1, X16 = 1 dan X26 = 0. Artinya sumber pemenuhan permintaan untuk wilayah satu sampai lima adalah gudang dan sumber pemenuhan permintaan untuk wilayah enam adalah pabrik. 2.6.2 Penentuan Rute Usulan dengan Algoritma Generate and Test Contoh pengolahan rute usulan dengan algoritma G&T (untuk wilayah Lembang dengan jumlah konsumen adalah 6 konsumen) sebagai berikut:
Gambar 8. Input Wilayah Lembang
Gambar 9. Output Wilayah Lembang Tabel 13. Output Wilayah Lembang
No Konsumen
0 G
Rute terpilih Artinya
0 G
Wilayah Lembang 1 2 3 4 45 46 47 48 Output G&T 2 3 1 5 46 47 45 49
5 49
6 50
6 50
4 48
0 G
Berdasarkan tabel 13, nomor 0 berarti gudang, nomor 1 berarti konsumen ke-45 dan seterusnya sampai nomor 6 berarti konsumen ke-50. Gambar 9 menunjukan urutan rute terpilih adalah 0-2-31-5-6-4-0, jadi urutan rute dengan nomor konsumen yang sebenarnya adalah G-46-47-45-49-50-48G dengan total jarak 26,28 km dan total waktu pendistribusian produk ke konsumen sebesar 4,9 jam. 2.6.3 Perbandingan Rute Perusahaan dengan Rute Usulan Rute usulan dibuat berdasarkan pengelompokan konsumen dalam wilayah yang sama. Hal ini dimaksudkan agar jarak perjalanan untuk mengelilingi target kunjungan harian menjadi lebih pendek dibandingkan dengan rute perusahaan yang target kunjungannya berpencar di beberapa wilayah. Berikut contoh perbandingan total jarak dan waktu perjalanan rute perusahaan dengan rute usulan:
12
RUTE OPTIMUM MENGGUNAKAN ALGORITMA GENERATE & TEST (Astrid A. P., et al.) Tabel 14. Perbandingan Total Jarak dan Waktu Rute Perusahaan dengan Rute Usulan Hari Ke-1 Hari ke1
Metode
Total Jarak (Km)
Waktu Perjalanan (Jam)
Waktu Kunjungan (Jam)
Total Waktu (Jam)
Perusahaan
76.90
5.378
2.892
8.269
Usulan
58.83
4.114
3.876
7.990
Berdasarkan tabel 14, total jarak perjalanan yang ditempuh dengan menggunakan rute perusahaan adalah 76.9 km dengan total waktu sebesar 8.269 jam. Sedangkan total jarak perjalanan yang ditempuh dengan menggunakan rute usulan adalah 58.83 km dengan total waktu sebesar 7.99 jam. Selisih total waktu rute usulan dengan rute perusahaan untuk hari ke-1 adalah 0.279 jam. Itu artinya dengan menggunakan rute usulan, perusahaan dapat menghemat waktu sebesar 3.38% dari rute yang diterapkan sekarang. Berikut hasil perbandingan total jarak dan waktu selama periode 1 minggu dari kedua rute: Tabel 15. Perbandingan Total Jarak dan Waktu Kedua Rute Rute
Total (Periode 1 Minggu) Jarak (Km)
Waktu (Jam)
Perusahaan
412.03
48.43
Usulan
219.19
34.93
Selisih
%
13.50
27.88
Total jarak rute perjalanan tanpa pembagian wilayah (rute perusahaan) lebih besar dibandingkan rute perjalanan berdasarkan pembagian wilayah (rute usulan). Hal ini disebabkan oleh lokasi antar konsumen pada rute perusahaan tidak berada dalam satu wilayah yang sama, rute ini melayani konsumen pada beberapa wilayah dalam 1 hari kunjungan. Sedangkan rute usulan dibuat agar konsumen yang akan dikunjungi dalam 1 hari berada dalam wilayah yang sama, sehingga total jarak yang didapatkan lebih kecil. Total waktu diperoleh dengan cara menjumlahkan waktu perjalanan dan waktu kunjungan. Waktu perjalanan mengikuti jarak perjalanan, semakin besar jarak yang ditempuh maka waktu perjalanan pun semakin lama. Waktu perjalanan didapatkan dengan cara jarak dibagi dengan kecepatan kendaraan (14,3 km/jam). Dari hasil perbandingan yang telah dilakukan, dapat dilihat penghematan total waktu pendistribusian produk rute usulan terhadap rute perusahaan sebesar 13.5 jam atau 27.88%.
3. Simpulan Berdasarkan hasil pengumpulan dan pengolahan data serta analisis yang telah dibuat maka penulis dapat menarik beberapa kesimpulan sebagai berikut: 1. Rute perjalanan yang ditetapkan perusahaan saat ini masih belum optimal sehingga masih dapat ditingkatkan untuk periode-periode selanjutnya. 2. Rute yang dihasilkan dari pengolahan data menggunakan metode Nearest Neighbor Heuristic, Branch and Bound dan algoritma Generate and Test lebih baik dibandingkan dengan rute perusahaan. Penghematan waktu dengan metode NNH sebesar 0.823 jam atau 9.78%, penghematan waktu dengan metode B&B sebesar 1.116 jam atau 13.55% dan penghematan waktu dengan metode G&T sebesar 1.14 jam atau 13.83% dari rute perusahaan saat ini. 3. Dari ketiga metode untuk mencari rute optimum, metode yang terbaik adalah Generate and Test karena memiliki total jarak dan waktu perjalanan paling kecil. 4. Usulan yang diberikan berupa rute pendistribusian baru dimana pembagian target konsumen berdasarkan wilayah (menurut peta) sehingga dihasilkan enam wilayah konsumen. Konsumen dalam satu wilayah yang sama akan dikunjungi dalam waktu satu hari. Selanjutnya metode Linear Programming digunakan untuk menentukan sumber pemenuhan permintaan tiap wilayah dan algoritma G&T digunakan untuk mencari rute optimum di setiap wilayah.
13
JURNAL INTEGRA VOL. 3, NO. 1, JUNI 2013: 1-14
5. Rute usulan lebih menghemat total waktu pendistribusian produk dibandingkan dengan rute perusahaan karena jarak antar lokasi konsumen dalam target kunjungan harian menjadi lebih kecil. Rute usulan menghasilkan penghematan waktu sebesar 13.5 jam atau 27.88% dari rute perusahaan saat ini.
4. Daftar Pustaka Akib, S. (2012), “Ini Dia Laju Kecepatan Kendaraan di Berbagai Kota di Tanah Air”, http://oto.detik.com/read/2012/06/28/121652/1953032/1207/ini-dia-laju-kecepatan-kendaraan-diberbagai-kota-di-tanah-air, tanggal akses: 11 Januari 2013 pukul 23.05 WIB. Bose, N. K. and Ping Liang (1996), “Neural Network Fundamentals with Graphs, Algorithms and Applications”, McGraw-Hill Book Co, New York. Chase, R. B., Aquilano, N. J, Jacobs, F. R. (1998), “Production and Operations Management: Manufacturing and Services”, Eighth Edition, McGraw-Hill Book Co. Hidayat, A. (2011), “Menggunakan Selisih Derajat Garis Lintang dan Bujur untuk Menghitung Jarak dan Mencari Skala Peta”, http://andimanwno.wordpress.com/2011/08/15/membaca-peta-3/, tanggal akses: 2 Desember 2012 pukul 22.20 WIB. Hillier, F. S. and Mark S. Hillier (2003) “Introduction To Management Science”, McGraw-Hill Book Co. Kusumadewi, S. dan Hari Purnomo (2005) “Penyelesaian Masalah Optimasi dengan TeknikTeknik Heuristik”, Graha Ilmu, Yogyakarta. Nurmanto (2011), “Metode Generate and Test”, http://nurmanto.com/metode-generate-and-test/, tanggal akses: 17 Januari 2013 pukul 22.30 WIB. Taha, H. A. (2011), “Operations Research: An Introduction”, Ninth Edition, Prentice Hall, New Jersey.
14
