PENENTUAN RUTE PENGAMBILAN SAMPAH DI KOTA MERAUKE DENGAN METODE SAVING HEURISTIC Endah Wulan Perwitasari 1, Subanar2 Dosen Universitas Musamus Merauke Jalan Kamizaun, Mopah Lama, Merauke Pos-el:
[email protected] 1,
[email protected] Abstract: Waste distribution problem has the common characteristics of the poor of scheduling and poor establishing route of waste. The waste distribution problems cover several issues such as the selection the route for the vehicle and the minimizing the distribution cost. The waste collection route is modeled into Vehicle Routing Problem (VRP). VRP is the selection of which route used by the dump trucks. The purpose of VRP is to minimize the time, distance, and distribution cost. There are two methods to deal with the VRP problems, which are the exact and heuristic methods. The exact method aimed to the optimum result, whereas heuristic method put emphasis on near-to-optimum but with quicker computing time. The result obtained by this research is the combination between exact and heuristic method. This combination is successfully implemented and it is able to determine which route to fulfill the problems of waste distribution. Keywords: Waste Collection Route, Algorithm, VRP, and Saving Heustic Abstrak : Permasalahan distribusi sampah mempunyai karakteristik diantaranya tidak ada penjadwalan ataupun pemilihan rute yang tepat untuk pengambilan sampah pada TPS. Permasalahan distribusi sampah melibatkan beberapa pertimbangan utama meliputi rute kendaraan, kendaraan sampai dengan minimasi ongkos distribusi. Permasalahan tersebut di modelkan dengan Vehicle Routing Problem (VRP). VRP adalah masalah penentuan rute yang digunakan oleh armada untuk memberikan pelayanan kepada konsumen. Dimana VRP mempunyai tujuan untuk minimasi waktu tempuh, jarak tempuh kendaraan dan minimasi ongkos distribusi.Terdapat dua macam metode untuk penyelesaian permasalahan VRP, yaitu metode eksak dan metode heuristic, dimana metode eksak lebih ditekankan pada hasil yang optimal, sedangkan pada metode heuristic hasil yang dicapai mendekati optimal namun mempunyai waktu komputasi yang cepat. Hasil yang diperoleh dalam penelitian ini adalah kombinasi antara metode eksak dan metode heuristic berhasil diimplementasikan dengan baik dan dapat membentuk rute yang memenuhi karakteristik permasalahan distribusi sampah. Kata kunci: Rute Pengambilan Sampah, Algoritma, VRP, dan Saving Heuristic
1.
sampah untuk menghindari adanya dampak
PENDAHULUAN
negatif Sampah adalah sisa kegiatan sehari-hari manusia dan proses alam yang berbentuk padat. Setiap individu pasti menghasilkan sampah
yang
mungkin
ditimbulkan
dari
keberadaan sampah (Kristian dan Chaerul, 2010). Pendistribusian sampah yang terkoodinasi
dalam jumlah yang variatif setiap harinya.
dengan
Jumlah timbunan sampah semakin meningkat
peningkatan
seiring
pertumbuhan
Pendistribusian sampah merupakan salah satu
penduduk kota. Peningkatan timbunan sampah
bagian penting dari kegiatan distribusi barang
merupakan
atau jasa yang dilakukan instansi pemerintah
dengan
peningkatan
konsekuensi
dari
peningkatan
kualitas dan perubahan pola hidup masyarakat. Oleh karena itu, laju timbunan sampah harus
baik
termasuk kualitas
salah
satu
pengelolaan
usaha sampah.
ataupun perusahaan tertentu. Permasalahan beberapa
sampah
pertimbangan
utama
Penentuan Rute Pengambilan Sampah di Kota Merauke dengan…… (Endah WP & Subanar)
85
diikuti oleh peningkatan kualitas pengelolaan
melibatkan
distribusi
meliputi rute kendaraan, kendaraan sampai
Tipe
masalah
vehicle
routing
dapat
dengan minimasi ongkos distribusi, sehingga
digambarkan sebagai suatu kasus dengan tujuan
dapat memperluas wilayah pelayanan dari
mencari rute terpendek dari suatu depot menuju
pengambilan sampah dengan armada yang
sekumpulan titik-titik tertentu. Pada umumnya
terbatas (Ballou dan Ronald, 1999). Masalah
solusi masalah vehicle routing diperoleh dengan
yang berkaitan dengan pendistribusian sampah
metode heuristik, diantaranya menggunakan
diantaranya
keputusan-keputusan
Metode Saving, Algoritma Sweep dan Algoritma
mengenai rute pengambilan sampah. Pemilihan
Genetika yang berdasarkan pada mekanisme
rute kendaraan akan menentukan total jarak
seleksi alam dan proses evolusi alam (Sarwadi
perjalanan armada.
dan Anjar, 2004). Berdasarkan uraian di atas
membuat
Karakteristik permasalahan penentuan rute
permasalahan pada penelitian ini mempunyai
pengambilan sampah yaitu terdapat depo dimana
karakteristik yang sama dengan Vehicle Routing
kendaraan berangkat dan pulang, tiap konsumen
Problem.
tepat dilayani satu kali dalam sebuah rute,
Penentuan
rute
pengambilan
sampah
kapasitas yang diangkut dalam setiap rute tidak
merupakan salah satu permasalahan optimasi
lebih
dimana
dari
kapasitas
maksimal
kendaraan
terdapat
beberapa
metode
untuk
pengangkut (Fitria dkk, 2009). Sehingga rute
penyelesaiannya. Menggabungkan metode eksak
yang optimal adalah rute yang memenuhi
dan metode heuristik diduga akan mampu
karakteristik
membentuk rute dengan perubahan tingkat
perrmasalahan
penentuan
rute
pengambilan sampah.
optimal dan waktu pembentukan rute.
Berdasarkan penelitian Asteria (2008)
Pengambilan sampah di kota Merauke saat
menyatakan, pada dasarnya, terdapat tiga macam
ini
penyelesaian optimasi. Yaitu metode eksak,
pengambilan
heuristik dan metaheuristik. Pada solusi eksak
pengambilan dengan arm roll truck. Dimana
(metode optimasi) dilakukan pendekatan dengan
pelanggan atau konsumen yang dilayani dengan
menghitung setiap solusi yang mungkin hingga
dump truck lebih banyak jumlahnya. Belum
menghasilkan jawaban terbaik (optimal). Branch
dipisah nya antara sampah basah dan sampah
and bound dan branch and cut merupakan
kering sehingga konsumen meminta periode
contoh dari penyelesaian eksak. Metode heuristik
pengambilan sampah dilakukan setiap hari. Hal
memberikan suatu cara untuk menyelesaikan
ini
permasalahan optimasi yang lebih sulit dan
sehingga menimbulkan bau dan pemandangan
dengan kualitas dan waktu penyelesaian yang
yang
lebih cepat daripada solusi eksak. Contoh
pengambilan sampah akan berpengaruh pada
metode heuristik antara lain: Saving Based,
kesehatan dan segi keindahan kota.
Matching
based,
Multiroute
heuristic, dan lain sebagainya.
86
impirovement
dilakukan
dengan dengan
dikarenakan
pengambilan
dump
sampah
mengganggu.
Penelitian
dua
ini
sampah
Pada
cepat
cara,
yaitu
truck
dan
membusuk
akhirnya
dilakukan dengan
pada dump
sistem
cara truck.
Jurnal Imiah MATRIK Vol.15 No.2, Agustus 2013: 85 - 94
Karena pada cara tersebut terdapat jumlah
semula dapat dilewati menjadi tidak dapat
konsumen terbanyak. Pada cara ini pengambilan
dilewati, kendaraan yang tiba-tiba tidak dapat
sampah dapat dilakukan tiap hari mengingat
dioperasikan ataupun permintaan musiman tidak
kondisi sampah di kota Merauke belum dipisah
diperhitungkan dalam penelitian ini
antara sampah basah dan sampah kering.
Tujuan
Penelitian
adalah
1)
Pengambilan sampah dengan cara dump truck ini
Mengimplementasikan algoritma Dijkstra yang
mempunyai tantangan penyesuaian kapasitas
dikombinasikan dengan metode saving heuristic
truk dengan kapasitas sampah yang diambil.
yang
Penentuan rute dilakukan dengan metode saving
permasalahan
penentuan
heuristic dimana metode ini yang paling banyak
sampah;
Membuktikan
digunakan untuk mengkonstruksi rute (Salaki,
kombinasi metode eksak dan metode heuristik
2009) dan dapat menghasilkan total jarak lebih
dapat
kecil (Kartikasari, 2010).
karakteristik
Permasalahan penelitian
ini
yang adalah:
dibahas 1)
dalam
dapat
2)
memenuhi
membentuk
rute
permasalahan
karakteristik
rute
pengambilan
dugaan
yang
bahwa
memenuhi
penentuan
rute
pengambilan sampah.
Bagaimana
mengimplementasikan kombinasi antara metode eksak dan metode heuristic untuk mendapatkan
2.
METODOLOGI PENELITIAN
rute; 2) Bagaimana mendapatkan rute yang optimal pada pengambilan sampah dimana permasalahan
tersebut
dimodelkan
dengan
vehicle routing problem. Dalam
penelitian
Metode yang digunakan dalam penelitian ini adalah sebagai berikut: penelitian dilakukan pada area pelayanan pengambilan sampah yang
ini
permasalahan
dibatasi pada: 1) Pembentukan rute dilakukan
dilakukan oleh dinas cipta karya dikota kota Merauke.
pada area pelayanan dinas Cipta Karya kota
Pada penelitian ini yang menjadi sampel
Merauke; 2) Pencarian rute optimal yaitu setiap
data adalah: 1) Jumlah kendaraan atau armada
konsumen tepat dilayani satu kali, dan total
pengangkut sampah; 2) Kapasitas kendaraan atau
volume yang diangkut tidak melebihi kapasitas
armada
maksimal truk pengangkut sampah serta tidak
konsumen atau tempat pembuangan sementara
melebihi jarak maksimal yang diperbolehkan
sampah; 4) Jumlah permintaan konsumen atau
truk pengangkut sampah; 3) Truk pengangkut
volume tempat pembuangan sementara sampah.;
sampah mempunyai kapasitas yang sama.; 4)
5) Lokasi konsumen atau tempat pembuangan
Semua konsumen/TPS harus dilayani setiap hari
sementara
sehingga tidak ada pembobotan prioritas pada
pembuangan akhir sampah; 7) Biaya transportasi
tiap-tiap konsumen/TPS; 5) Nilai pinalti akan
yaitu berupa ongkos bahan bakar.
dihitung
berdasarkan
jumlah
pelanggaran
terhadap batasan-batasan yang sudah ditentukan;
pengangkut
sampah;
sampah;
6)
3)
Lokasi
Jumlah
tempat
Tahapan penelitian sebagai berikut: 1) Prosedur Penelitian
6) Kejadian tak terduga seperti jalan yang Penentuan Rute Pengambilan Sampah di Kota Merauke dengan…… (Endah WP & Subanar)
87
a) Pengkajian untuk
metode
saving
menyelesaikan
heuristic
mencapai
permasalahan
tujuan
menggunakan
penentuan rute pengambilan sampah.
penelitian
data
dari
ini
akan
instansi
yang
digunakan sebagai model guna perbandingan
b) Pengumpulan data. Data-data penelitian
dengan
didapat dari dinas cipta karya kabupaten
sistem
yang
dihasilkan
oleh
penelitian.
Merauke. c) Pemodelan
saving
heuristic:
i)
2.1
Teori Graf
Menentukan jarak antar konsumen yang berhubungan
ii)
Graf adalah kumpulan dari titik (node)
algoritma
dan garis dimana pasangan-pasangan titik (node)
Dijkstra mencari jarak terpendek antara
tersebut dihubungkan oleh segmen garis. Node
tiap-tiap titik dan terhadap depo; iii)
ini biasa disebut simpul (verteks) dan segmen
Mencari nilai saving dari masing-masing
garis disebut ruas (edge). Simpul dan ruas dalam
koordinat; iv) Mengurutkan nilai saving
graf
mulai dari nilai saving terbesar sampai
informasi. Sebagai contoh, simpul bisa diberi
terkecil secara urut; v) Pembentukan rute
nomor atau label dan ruas dapat diberi nilai juga.
berdasarkan urutan nilai saving; vi)
Perluasan dengan pemberian informasi ini sangat
Menghitung total volume terangkut,
berguna dalam penggunaan graph untuk banyak
menghitung
waktu
yang
aplikasi komputer (Chartrand, 1985). Contoh,
dilakukan
oleh
hingga
graf dengan simpul yang merepresentasikan kota
membentuk rute, menghitung total jarak
dan ruas merepresentasikan jarak yang ditempuh
tempuh
diantara kota-kota tersebut (atau harga tiket
Dengan
secara
langsung;
menggunakan
eksekusi sistem
masing-masing
rute
yang
dapat
diperluas
dengan
penambahan
terbentuk, menghitung nilai pinalti, dan
pesawat
menghitung nilai penghematan biaya
digunakan sebagai “transportation network”
operasional kendaraan.
untuk mempelajari total jarak (atau harga) dari
2) Implementasi
suatu
antara
kota-kota
perjalanan
dengan
tersebut),
banyak
dapat
kota
Tahapan menterjemahkan hasil desain ke
pemberhentian. Satu kemungkinan pertanyaan
dalam bahasa pemrograman php dengan
yang bisa muncul adalah “Jalur mana yang
data-base MySQL.
terpendek dengan satu atau lebih tempat
3) Pengujian
pemberhentian,
yang
menghubungkan
kota
Pengujian digunakan untuk mencapai tujuan
tertentu menuju kota tertentu lainnya dalam
penelitian,
transportation network tersebut ?”.
yaitu
membuktikan
dugaan
bahwa kombinasi metode eksak dan metode heuristik memenuhi
dapat
membentuk
karakteristik
rute
yang
permasalahan
penentuan rute pengambilan sampah. Untuk
88
Jurnal Imiah MATRIK Vol.15 No.2, Agustus 2013: 85 - 94
2.2
dengan berawal dan berakhir dari tempat
Lintasan dan Sirkuit Hamilton
asalnya. Masalah ini pertama kali dirumuskan Lintasan Hamilton adalah lintasan yang
sebagai masalah matematika pada tahun 1930
melalui tiap simpul di dalam graf tepat satu kali.
dan merupakan salah satu masalah yang paling
Sirkuit Hamilton adalah sirkuit yang melalui tiap
intensif dalam mempelajari masalah optimasi,
simpul di dalam graf tepat satu kali, kecuali
dan digunakan sebagai patokan bagi banyak
simpul asal (sekaligus simpul akhir) yang dilalui
metode optimasi dalam jumlah besar dengan
dua kali. Graf yang memiliki sirkuit Hamilton
cara yang tepat, dan metode yang mudah untuk
dinamakan graf Hamilton, sedangkan graf yang
diketahui, sehingga beberapa kasus dengan
hanya memiliki lintasan Hamilton disebut graf
puluhan ribu kota dapat diselesaikan dengan baik
semi-Hamilton (Weisstein, 2010).
(Sutapa dan Widyadana, 2008).
Syarat lintasan dan sirkuit Hamilton
2.4
(Weisstein, 2010):
Vehicle Routing Problem
1) Syarat cukup (jadi bukan syarat perlu) VRP
supaya graf sederhana G dengan n ( 3)
adalah
salah
yang
bentuk
buah simpul adalah graf Hamilton ialah bila
permasalahan
derajat tiap simpul paling sedikit n/2 (yaitu,
pendistribusian barang maupun orang kepada
d(v) n/2 untuk setiap simpul v di G).
pelanggan dengan menggunakan kendaraan dan
2) Setiap graf lengkap adalah graf Hamilton.
bertujuan untuk meminimasi beberapa tujuan
3) Di dalam graf lengkap G dengan n buah
distribusi
simpul (n 3), terdapat (n - 1)!/2 buah
transportasi
satu
melibatkan
VRP merupakan perumuman dari TSP atau disebut juga m-TSP dengan m menunjukkan
sirkuit Hamilton. 4) Di dalam graf lengkap G dengan n buah
banyaknya
salesman
yang
mengunjungi
simpul (n 3 dan n ganjil), terdapat (n - 1)/2
sejumlah kota. Jadi VRP berkaitan dengan
buah sirkuit Hamilton yang saling lepas
penentuan rute optimal untuk permasalahan lebih
(tidak ada sisi yang beririsan). Jika n genap
dari satu kendaraan (vehicle) dengan kapasitas
dan n 4, maka di dalam G terdapat (n -
tertentu untuk mengunjungi sejumlah pelanggan
2)/2 buah sirkuit Hamilton yang saling lepas.
dengan permintaannya masing-masing. Rute yang dibentuk harus dimulai dan diakhiri di suatu
2.3
tempat
yang
disebut
depot.
Setiap
pelanggan dikunjungi hanya satu kali dan total
Travelling Salesman Problem
permintaan semua pelanggan dalam satu rute Travelling
Salesman
problem
(TSP)
merupakan salah satu terapan dari teori graf yang
diilhami
oleh
permasalahan
seorang
pedagang yang mengunjungi sejumlah kota
tidak
melebihi
kapasitas
kendaraan
yang
melayani rute tersebut. VRP menjadi TSP pada saat hanya terdapat satu alat angkut yang kapasitasnya
tak
hingga
(Kallehauge
dan
Marsen, 2001). Penentuan Rute Pengambilan Sampah di Kota Merauke dengan…… (Endah WP & Subanar)
89
2.5
Dalam menyelesaikan masalahnya metode
Algoritma Dijkstra
ini dipecah menjadi dua komponen yaitu untuk
mengelompokkan (clustering) permasalahan
mencari lintasan terpendek pada graf berarah.
ke dalam rute yang layak dan baru dilakukan
Namun, algoritma ini juga benar untuk graf tak
pembuatan rute (routing), sehingga cara
berarah. Algoritma Dijkstra mencari lintasan
tersebut dapat dinyatakan dengan: cluster-
terpendek dalam sejumlah langkah. Algoritma
first route-second dan route first _cluster
ini menggunakan prinsip greedy. Prinsip greedy
second.
Algoritma
Dijkstra
diterapkan
pada algoritma Dijkstra menyatakan bahwa pada
3) Metode perbaikan (Improvement methods)
setiap langkah kita memilih sisi yang berbobot
Metode ini mencoba mencari setiap solusi
minimum dan memasukannya dalam himpunan
yang layak dengan melakukan pertukaran
solusi.
urutan node, baik didalam rute itu sendiri (intra route exchange) maupun di luar rute
2.6
yang sudah terbentuk.
Heuristic
Berdasarkan penelitian Asteria (2008) Metode heuristik merupakan salah satu metode
penentuan
solusi
optimal
dari
permasalahan optimasi kombinatorial. Berbeda
menyatakan, pada dasarnya, terdapat tiga macam penyelesaian VRP: 1) Solusi Eksak.
dengan solusi eksak yang menentukan nilai
Pada
solusi
eksak
solusi secara tepat, metode ini menghampiri
dilakukan pendekatan dengan menghitung
solusi permasalahan utama dengan cara mencari
setiap
nilai optimal suatu bagian tertentu atau irisan
menghasilkan jawaban terbaik (optimal) dari
dari masalah utamanya. Dalam hal ini, perolehan
persoalan Branch and bound dan branch and
solusi fisibel secara cepat dari segi komputasi
cut merupakan contoh dari penyelesaian
lebih ditekankan meskipun tidak menjamin
eksak.
solusi
(metode
yang
optimasi)
mungkin
hingga
2) Heuristik.
solusi tersebut optimal. Menurut Laporte (2010), metode heuristik
Metode Heuristik memberikan suatu cara
untuk menyelesaikan VRP dapat dikategorikan
untuk menyelesaikan permasalahan optimasi
dalam tiga kelompok,
yang lebih sulit dan dengan kualitas dan
1) Heuristik
konstruktif
(constructive
waktu
penyelesaian
yang
lebih
cepat
heuristic).Secara berurutan atau gradual
daripada solusi eksak. Contoh metode
membentuk
heuristik
solusi
yang
layak
dengan
antara
lain:
Saving
Based,
memperhatikan biaya solusi, akan tetapi
Matching based, Multiroute improvement
tidak
heuristic, dan lain sebagainya.
terdapat
fase
perbaikan
peningkatan.
atau
3) Metaheuristik.
2) Heuristik dua fase (two phase heuristic)
90
Jurnal Imiah MATRIK Vol.15 No.2, Agustus 2013: 85 - 94
Metaheuristik, adalah suatu metode untuk melakukan
2
Depo-Jl.Mandala-Sumatra-AngkasaParako-Missi-Pendidikan-MartadinataBiak-G.Nusantara-Natuna-Jl.JawaNoari-Kalimantan-Nusabarong-Depo Depo-Spadem-Depo
eksplorasi yang lebih dalam
pada daerah yang menjanjikan dari ruang
3
solusi yang ada. Kualitas solusi yang dihasilkan dari metode ini jauh lebih baik
Setelah
terbentuk
kita
dapat
daripada yang didapat heuristik klasik.
menghitung total volume yang terangkut dengan
Contoh
mengakumulasi volume sampah pada tiap titik-
metaheuristik
adalah
genetic
algorithm, simulated annealing, tabu search,
titik TPS pada tiap rute.
ant colony system dan sebagainya.
2.7
rute
Tabel 2. Total volume terangkut
Saving Heuristic Metode saving
disebut juga
metode
Rute 1 2 3 Total volume
volume terangkut 5,26 m3 5,97 m3 0,09 m3 11,32 m3
Clarke-Wright karena diperkenalkan oleh Clarke
Lama proses pembentukan rute ini terdiri
dan Wright pada tahun 1964. Metode ini
dari lama penentuan jarak terpendek dengan
merupakan metode heuristik yang paling banyak
menggunakan Dijkstra, waktu mencari nilai
digunakan untuk mengkonstruksi rute. Metode
saving
ini diawali dengan suatu solusi yang setiap
rangking, dan lama proses pembentukan rute.
dan
pelanggannya dilayani secara individu oleh satu
mengurutkannya
berdasarkan
Tabel 3. Waktu proses
rute secara terpisah menghasilkan penghematan
Banyak Jalan 40 50 60 70 80
(saving) berupa jarak tempuh sebesar sij=ci0+c0jcij dengan cij = jarak dari pelanggan i ke pelanggan j.
Saving Heuristik 4.126 9.118 17.76 32.357 51.567
Kombinasi antara metode eksak dan
3.
HASIL
metode heuristik yang pada penelitian ini menggunakan Dijkstra dan saving heuristic
Penelitian penentuan rute pembuangan
berpengaruh terhadap waktu proses.
sampah di kota Merauke dengan metode saving heuristik menghasilkan 3 rute. Tabel 1. Rute yang terbentuk Nomor 1
Rute Depo- Sesate-Gak-Onggatmit-jl.Kelinci II-jl Kelinci I-Asmat – Ermasu-PrajuritTMP-Bakti-Brawijaya-Ampera IAmpera III-Ali Arkam-Ampera IVAmpera II-Paulus Napi-Kimamjl.Trikora-Yobar-Seringgu-G.KangguruKamp.Timor-Jl.Tomor-G.Aru-Depo
Setelah rute terbentuk, kita dapat mencari total
jarak
yang
dilalui
oleh
kendaraan
pengangkut
pada
setiap
rutenya.
Dalam
penelitian ini, jarak terpendek belum tentu jarak yang optimal, karena adanya batasan lain dalam penentuan optimasi, yaitu kapasitas kendaraan.
Penentuan Rute Pengambilan Sampah di Kota Merauke dengan…… (Endah WP & Subanar)
91
terbentuk. Yaitu mengangkut volume dibawah
Tabel 4. Jarak Tempuh Rute 1 2 3 Total jarak
3.1
50% kapasitas kendaraan atau kurang dari 3m3
Jarak tempuh 26.81 km 19.25 km 1.24 km 47,3 km
pada setiap rute ke dua. Sedang pada penelitian pembentukan rute menggunakan metode saving heuristik pada tabel 6 menunjukkan total volume terangkut tiap rute
Pembahasan
menunjukkan Pembahasan
dilakukan
dengan
kapasitas
Tabel 6. Rute Hasil Sistem
Cipta Karya kota Merauke dengan hasil dari Rute
sistem. Yang akan dibandingkan adalah volume
diperlukan sistem untuk membentuk rute.
100%
kendaraan kecuali pada rute ke tiga.
membandingkan data yang diperoleh dari dinas
terangkut, jarak tempuh dan waktu yang
mendekati
1 2 3
Dijkstra + saving heuristic Volume Jarak Waktu Terangkut Tempuh Sistem (m3) (km) (detik) 5.26 26.81 5.97 19.25 0.09 1.24 11.32*6 = 47.3*6 = 4,3617 67,92 283,8
Pinalti 177 195 1
3.1.1 Total Volume Terangkut Tabel 7. Rute Pembanding Sistem
Berdasarkan data yang diperoleh dari kantor Cipta Karya Merauke pada tabel 5, rute yang berjalan saat ini jika dihitung total volume terangkut per rute adalah berkisar 1 m3 hingga 4,21 m3. Perhari mejalani 2 rute yang dilakukan oleh 2 kendaraan. Sehingga 1 rute dilakukan oleh
Rute 1 2 3 4
1 kendaraan dengan volume terangkut 50%
Brute force + saving heuristic Volume Jarak Waktu Terangkut Tempuh Sistem Pinalti (m3) (km) (detik) 3.78 38.16 97 3.49 19.27 79 3.96 3.86 6 0.09 1.24 1 11.32*6 = 62.53*6 2,71 = 67,92 375.18
sampai dengan 70% dari kapasitas maksimal kendaraan 6m3.
Dari tabel 6 dan tabel 7 dapat dilihat
Tabel 5. Rute yang ada
bahwa total volume terangkut antara Dijkstra
Cipta Karya Volume Jarak Terangkut (m3) Tempuh (km) 4.10 19.12 1.21 11.35 3.96 14.04 2.25 26.16 4.21 29.92 2.32 22.84 2.63 11.87 1 20.34 3.22 22.84 37.17 240.56
yang dikombinasikan dengan saving heuristic
Dari data yang didapat, dapat dilihat
menekankan pada nilai saving atau penghematan
sangat tidak efisien nya salah satu rute yang
total ongkos maka kombinasi Dijkstra dengan
Rute
1 2 3 4 5 6 7 8 9 Total
92
dengan brute force yang dikombinasikan dengan saving heuristic tidak ada perbedaan, namun pada total jarak tempuh pada Dijkstra yang dikombinasikan
dengan
saving
heuristic
mempunyai nilai yang lebih kecil. Sedangkan pada
nilai
pinalti,
algoritma
pembanding
menghasilkan nilai pinalti yang lebih kecil. Karena
pada
penelitian
ini
lebih
Jurnal Imiah MATRIK Vol.15 No.2, Agustus 2013: 85 - 94
saving heuristic yang dipilih. Karena semakin
didapatkan grafik waktu proses seperti pada
kecil total jarak tempuh akan semakin kecil total
gambar 1.
ongkos.
grafik waktu 60.000 40.000 20.000 0.000
waktu
3.1.2 Pinalti Pada tabel 6 dan 7 menunjukkan pinalti
40
50
60
70
80
pada algoritma pembanding mempunyai total
dijkstra
3.65 7.56 14.6 26.6 41.8
nilai yang lebih kecil dari pada nilai pinalti rute
saving
0.55 1.45 2.97 5.63 9.42
rute
0.00 0.09 0.15 0.10 0.24
yang
dihasilkan
oleh
sistem.
Hal
ini
menunjukkan bahwa algoritma pembanding
Gambar 1. Grafik waktu
memberikan jumlah pelanggaran yang lebih sedikit
pada
batasan-batasan
yang
Metode
sudah
ditentukan. Namun karena pada penelitian ini menekankan pada penghematan (saving) total ongkos, maka metode yang menghasilkan jarak
waktu
perhitungan lebih lama dibandingkan metode heuristik. Meskipun proses saving dan penetuan rute sangat cepat, namun pada akhirnya akan
pembuangan
sampah
ini.
Untuk
setiap
penambahan sebanyak 10 jalan (dengan banyak
3.1.3 Total Jarak Berdasar tabel 6 dan tabel 7, pada perhitungan penghematan, akan dipengaruhi oleh total jarak tempuh harian dari tiap-tiap rute sampah.
menghasilkan
menambah total proses dalam pembentukan rute
terpendeklah yang dapat memenuhi kriteria.
pengambilan
eksak
Total
jarak
konsumen) akan memerlukan lama proses 2 kali lebih lama dari proses sebelum penambahan jalan.
yang
dihasilkan dengan sistem pada penelitian akan dibandingkan dengan data pada tabel 5.
4.
SIMPULAN
Berdasar hasil penelitian biaya operasional membutuhkan ongkos sebesar Rp. 606.000,-.
Berdasarkankan pembahasan yang telah
Sehingga biaya yang telah dianggarkan dapat
diuraikan pada bab-bab sebelumnya, maka
dilakukan penghematan sebesar Rp.1.794.000,-
diambil beberapa kesimpulan sebagai berikut: 1)
didasarkan hasil penelitian.
Algoritma dengan
3.1.4 Pengaruh Pertambahan Jumlah Jalan
Dijkstra metode
dapat saving
dikombinasikan heuristic
dan
menghasilkan rute pengambilan pengambilan
Terhadap Waktu
sampah di kota Merauke; 2) Metode saving
Kombinasi antara metode eksak dan
heuristic yang dikombinasikan dengan metode
metode heuristik yang pada penelitian ini
eksak
yaitu
algoritma
Dijkstra
ataupun
menggunakan Dijkstra dan saving heuristik
algoritma brute force akan menghasilkan waktu
berpengaruh pada waktu proses. Dari table 3
perhitungan yang lebih cepat daripada metode eksak; 3) Kombinasi antara metode eksak yaitu
Penentuan Rute Pengambilan Sampah di Kota Merauke dengan…… (Endah WP & Subanar)
93
algoritma Dijkstra dengan metode heuristic yaitu Saving Heuristic dapat menghasilkan rute yang
Laporte, G. 2010. Fitfty Years of Vehicle Routing. Canada Research Chair in Distribution Management. HEC Montreal.
memenuhi kriteria permasalahan penentuan rute pengambilan sampah, yaitu
terdapat depot
dimana kendaraan berangkat dan pulang, tiap konsumen tepat dilayani satu kali dalam sebuah rute, kapasitas yang diangkut dalam setiap rute tidak lebih dari kapasitas maksimal kendaraan pengangkut.
DAFTAR RUJUKAN Asteria, C. 2008. Penentuan Distribusi Dengan Algoritma Tabu Search Untuk VRP Dengan Time Windows. Universitas Indonesia. Jakarta.
Sarwadi dan Anjar K.S.W. 2004. Algoritma Genetika Untuk Penyelesaian Masalah Vehicle Routing. Universitas Diponegoro. Semarang. Sutapa, I.N. dan Widyadana, I.G.A. 2003. Studi Tentang Travelling Salesman dan Vehicle Routing Problem dengan Time Windows, Universitas Kristen Petra. Surabaya. Salaki, T.D. 2009. Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif. Institut Pertanian Bogor. Bogor. Weisstein, E.W. 2010. Hamiltonian Graph. From MathWorld --A Wolfram Web Resource, (Online), (http://mathworld.wolfram.com/Hamiltoni anGraph.html, diakses tanggal 13 Februari 2012).
Ballou dan Ronald, H. 1999. Business Logistics Management. Prentice Hall. Upper Saddle River N.J. Chartrand, G, 1985. Introductory Graph Theory. Dover Publ. Inc. New York. Fitria, L., Susanty, S. dan Suprayogi. 2009. Penentuan Rute Pengambilan dan Pengangkutan Sampah di Bandung. Fakultas Teknologi Industri, Institut Teknologi Bandung. Bandung. Kallehauge, B., J. Larsen, dan O.B.G. Marsen. 2001. Lagrangean Duality Applied on Vehicle Routing with Time Windows. Technical Report, IMM, Technical University of Denmark. Kartikasari, Y. 2010. Implementasi ClarkeWright Saving Method pada Layanan Taksi Berbasis VOIP. Institut Teknologi Sepuluh November. Surabaya. Kristian, Y. dan Chaerul, M. 2010. Analisis Awal Implementasi Tempat Pengolahan Sampah Terpadu.Skripsi, Fakultas Teknik Sipil dan Lingkungan, ITB. Bandung.
94
Jurnal Imiah MATRIK Vol.15 No.2, Agustus 2013: 85 - 94
