Menentukan rute pengangkutan sampah untuk memperkecil total jarak

tempuh dengan menggunakan Metode Savings Heuristic

I. MASALAH NYATA

Sampah adalah limbah yang bersifat padat, yang terdiri dari zat atau bahan

organik dan non organik. Setiap hari sampah dihasilkan oleh setiap rumah tangga

dalam masyarakat sebagai bagian dari kehidupan sehari-hari, namun hal tersebut

secara umum seringkali tidak menjadi bahan pemikiran yang mendalam bagi semua

warga masyarakat. Seringkali pembuangan sampah di rumah hanya cukup sekedar

menyimpannya dalam bak sampah / tong sampah untuk kemudian selanjutnya adalah

menjadi urusan pengumpul/pengangkut sampah tingkat RT/RW hingga ke Kelurahan

untuk kemudian tugas terakhir yang merupakan beban terberat ada di pihak petugas

kebersihan kota yang membuangnya ke Tempat Pembuangan Sampah Akhir.

Dinas Kebersihan sebagai pihak yang bertanggung jawab tentunya

menginginkan agar sampah di tiap-tiap TPS dapat terangkut dan biaya pengangkutan

sampah ke TPS-TPS dapat diminimumkan dengan mengharapkan hasil yang

maksimum. Dalam hal ini yang akan dibahas adalah menemukan jalur yang tepat

(minimum) dari depot ke seluruh TPS tepat sekali dan kembali lagi ke depot dengan

jarak terpendek. Dengan menemukan rute terpendek, secara tidak langsung dapat

meminimumkan biaya transportasi sehingga mengakibatkan bahan bakar yang

digunakan juga dapat diminimumkan.

Dengan menggunakan Savings Heuristic, maka akan ditentukan rute yang

optimal untuk memperoleh jarak total minimum.

II. RUMUSAN MASALAH

Bagaimana menentukan rute pengangkutan sampah untuk memperkecil total

jarak tempuh dengan menggunakan Metode Savings Heuristic?

III. ASUMSI

Sebuah kota mempunyai truk pemungut sampah yang harus mengangkut

sampah di Sembilan jalur yang memiliki beberapa titik tempat pembuangan sampah.

Setiap harinya, setiap truk harus mulai dan berakhir pada depot dan pada akhirnya

akan dikumpulkan pada satu tempat pembuangan akhir sampah. Misalkan setiap node

pada rute awal dipenuhi secara individual oleh suatu kendaraan secara terpisah.

Dimana setiap node membentuk rute tersendiri yang dilayani oleh kendaraan yang

berbeda. Seperti pada Gambar 3.1 yaitu rute o-i-o dilayani oleh satu kendaraan, dan

rute o-j-o dilayani oleh kendaraan lain yang berbeda.

i j

coi coj

coi coj

o

Gambar 3.1 Bentuk Awal Rute

0 ( Depot )

1

2

3

4

5

6

7

8

9

IV. DATA

Total jarak yang ditempuh sebelum menggunakan Saving Heuristic adalah

408 km (ditunjukkan pada gambar 4.1)

Gambar 4.1 Depot dan 9 node yang harus dikunjungi

V. MODEL MATEMATIKA

Menghitung nilai penghematan (Si,j) berupa jarak tempuh dari satu kendaraan

yang menggantikan dua kendaraan untuk melayani node i dan j dengan menggunakan

persamaan :

Si,j = coi + coj - cij......................................................................................................(1)

dimana,

Sij = nilai penghematan jarak dari node i ke node j

coi = jarak dari depot ke node i

coj = jarak dari depot ke node j

cij = jarak dari node i ke node j

Nilai penghematan (Si,j) adalah jarak yang dapat dihemat jika rute o-i-o

digabungkan dengan rute o-j-o menjadi rute tunggal o-i-j-o yang dilayani oleh satu

kendaraan yang sama (ditunjukkan dalam Gambar 3.2)

i cij j

coi coj

o

Gambar 3.2 Bentuk Penghematan Rute

Adapun langkah-langkah penyelesaian pemecahan persoalan dengan

menggunakan Metode Savings Heuristik adalah sbb :

1. Membuat matriks jarak yaitu matriks jarak antara depot dengan node dan jarak

antar node. Pengukuran jarak dari node i ke j sama dengan jarak dari node j ke i

sehingga matriks jarak ini termasuk matriks simetris.

2. Menghitung nilai penghematan (savings) dengan menggunakan persamaan (1).

3. Membuat matriks hasil penghematan (savings) yaitu matriks penghematan antara

depot dengan node dan jarak antar node yaitu berupa pengukuran jarak dari node i

ke j.

4. Buat ranking dari perhitungan savings dan buat list dari hasil savings yang terbesar

hingga terendah.

5. Untuk hasil savings s( i,j ) yang sedang dipertimbangkan sudah termasuk hubungan

node ( i,j ) pada satu rute. Bila tidak ada rute pembatas maka akan mengganggu

pencantuman dari rute ( i,j ) dan bila :

a. Baik i atau j sudah ditentukan pada satu rute dimana pada beberapa kasus, rute

baru diajukan termasuk ke dalam i dan j.

b. Atau, hanya satu dari dua titik (i atau j) sudah termasuk dalam rute yang ada

dan node tersebut tidak termasuk pada rute itu (satu node termasuk pada rute

0 ( Depot )

1

2

3

4

5

6

7

8

9

bila tidak berbatasan dengan depot D sehingga tidak melebihi node), dimana

hubungan ( i,j ) ditambahkan pada rute yang sama.

c. Atau, baik i dan j sudah termasuk ke dalam dua rute yang berbeda dan node

yang lain termasuk ke dalam rute, dimana dua rute dapat digabungkan.

VI. SOLUSI

Gambar 6.1 Depot dan 9 node yang harus dikunjungi

Tabel 1 Kapasitas dari setiap node

Node 1 2 3 4 5 6 7 8 9

Unit 4 6 5 4 7 3 5 4 4

Dengan total kapasitas = 23 unit sekali angkut. Setelah diketahui masing – masing

jarak dari setiap titik, maka dapat dilakukan perhitungan savings.

kedari

0 0 25 43 57 43 61 29 41 48 711 25 0 29 34 43 68 49 66 72 912 43 29 0 52 72 96 72 81 89 1143 57 34 52 0 45 71 71 95 99 1084 43 43 72 45 0 27 36 65 65 655 61 68 96 71 27 0 40 66 62 466 29 49 72 71 36 40 0 31 31 437 41 66 81 95 65 66 31 0 11 468 48 72 89 99 65 62 31 11 0 369 71 91 114 108 65 46 43 46 36 0

430 1 2 5 9876

Tabel 2 Matriks Jarak

Langkah – langkah penghitungan Saving sebagai berikut :

Menghitung Si,j yaitu nilai penghematan jarak dari node i ke node j dengan

menggunakan persamaan (1) maka diperoleh :

s(0,1) = d( 0,0 ) + d ( 0,1 ) – d ( 0,1 )

= 0 + 25 - 25

= 0

s(0,2) = d ( 0,0) + d ( 0,2) – d ( 0,2 )

= 0 + 43 -43

= 0

s(0,3) = d ( 0,0 ) + d ( 0,3) – d ( 0,3 )

= 0 + 57 – 57

= 0

s(0,4) = d (0,0) + d (0,4) – d (0,4)

= 0 + 43 – 43

= 0

s(0,5) = d (0,0) + d ( 0,5 ) – d ( 0,5 )

= 0 + 61 – 61

= 0

s(0,6) = d (0,0) + d (0,6) – d(0,6)

= 0 + 29 – 29

= 0

s(0,7) = d (0,0) + d (0,7) – d (0,7)

= 0 + 41 – 41

= 0

s(0,8) = d (0,0) + d(0,8) – d(0,8)

= 0 + 48 – 48

= 0

s(0,9) = d (0,0) + d (0,9) – d (0,9)

= 0 + 71 – 71

= 0

s(1,2) = d (0,1) + d (0,2) – d (1,2)

= 25 + 43 – 29

= 39

s(1,3) = d(0,1) + d (0,3) – d(1,3)

= 25 + 57 – 34

= 48

s(1,4) = d (0,1) + d (0,4) – d(1,4)

= 25 + 43 – 43

= 25

S(1,5) = d (0,1) + d(0,5) – d(1,5)

= 25 + 61 – 68

= 18

S(1,6) = d(0,1) + d(0,6) – d(1,6)

= 25 + 29 – 49

= 5

S(1,7) = d (0,1) + d (0,7) – d (1,7)

= 25 + 41 – 66

= 0

S(1,8) = d (0,1 ) + d (0,8) – d (1,8)

= 25 + 48 – 72

= 1

S(1,9) = d (0,1) + d(0,9) – d (1,9)

= 25 + 71 – 91

= 5

S(2,3) = d (0,2) + d(0,3) – d(2,3)

= 43 + 57 – 52

= 48

S(2,4) = d (0,2) + d (0,4) – d (2,4)

= 43 + 43 – 72

= 14

S (2,5) = d (0,2) + d (0,5) – d (2,5)

= 43 + 61 – 96

= 8

S(2,6) = d (0,2) + d (0,6) – d (2,6)

= 43 + 29 – 72

= 0

S(2,7) = d (0,2) + d (0,7) – d (2,7)

= 43 + 41 – 81

= 3

S(2,8) = d (0,2) + d (0,8) – d (2,8)

= 43 + 48 – 89

= 2

S(2,9) = d (0,2) + d (0,9) – d (2,9)

= 43 + 71 – 114

= 0

S(3,4) = d (0,3) + d (0,4) – d (3,4)

= 57 + 43 – 45

= 55

S(3,5) = d (0,3) + d (0,5) – d (3,5)

= 57 + 61 – 71

= 47

S(3,6) = d (0,3) + d (0,6) – d (3,6)

= 57 + 29 – 71

= 15

S(3,7) = d (0,3) + d (0,7) – d (3,7)

= 57 + 41 – 95

= 3

S(3,8) = d (0,3) + d (0,8) – d (3,8)

= 57 + 48 – 99

= 6

S (3,9) = d (0,3) + d (0,9) – d (3,9)

= 57 + 71 – 108

= 20

S (4,5) = d (0,4) + d (0,5) – d (4,5)

= 43 + 61 – 27

= 77

S (4,6) = d (0,4) + d(0,6) – d(4,6)

= 43 + 29 – 36

= 36

S (4,7) = d (0,4) + d (0,7) – d (4,7)

= 43 + 41 – 65

= 19

S (4,8) = d (0,4) + d (0,8) – d (4,8)

= 43 + 48 – 65

= 26

S (4,9) = d (0,4) + d (0,9) – d(4,9)

= 43 + 71 – 65

= 49

S (5,6) = d (0,5) + d (0,6) – d (5,6)

= 61 + 29 – 40

= 50

S (5,7) = d (0,5) + d (0,7) – d (5,7)

= 61 + 41 – 66

= 36

S (5,8) = d (0,5) + d (0,8) – d (5,8)

= 61 + 48 – 62

= 47

S (5,9) = d (0,5) + d (0,9) – d (5,9)

= 61 + 71 – 46

= 86

S (6,7) = d (0,6) + d (0,7) – d (6,7)

= 29 + 41 – 31

= 39

S (6,8) = d (0,6) + d (0,8) – d (6,8)

= 29 + 48 – 31

= 46

S (6,9) = d (0,6) + d (0.9) – d (6,9)

= 29 + 71 – 43

= 57

S (7,8) = d (0,7) + d (0,8) – d (7,8)

= 41 + 48 – 11

= 78

S (7,9) = d (0,7) + d (0,9) – d (7,9)

= 41 + 71 – 46

= 66

S (8,9) = d (0,8) + d (0,9) – d (8,9)

= 48 + 71 – 36

= 83

Tabel 3 Savings ( diatas diagonal ) dan jarak ( dibawah diagonal )

j0 1 2 3 4 5 6 7 8 9

i0 - - - - - - - - - -1 25 - 39 48 25 18 5 0 1 52 43 29 - 48 14 8 0 3 2 03 57 34 52 - 55 47 15 3 6 204 43 43 72 45 - 77 36 19 26 495 61 68 96 71 27 - 50 36 47 866 29 49 72 71 36 40 - 39 46 577 41 66 81 95 65 66 31 - 78 668 48 72 89 99 65 62 31 11 - 839 71 91 114 108 65 46 43 46 36 -

Setelah dilakukan perhitungan keseluruhan, didapatkan daftar ranking dari hasil

savings yang terbesar yaitu 86 dengan koordinat node ( 5, 9 ) sampai savings yang

terkecil yaitu 0 dengan koordinat node ( 2, 6 ).

Tabel 2.4 Daftar ranking dari savings

No. Koordinat Node Savings

1 5,9 86

2 8,9 83

3 7,8 78

4 4,5 77

5 7,9 66

6 6,9 57

7 3,4 55

8 5,6 50

9 4,9 49

10 2,3 48

11 1,3 48

12 3,5 47

13 5,8 47

14 6,7 46

15 1,2 39

16 6,7 39

17 4,6 36

18 5,7 36

19 4,8 26

20 1,4 25

21 3,9 20

22 4,7 19

23 1,5 18

24 3,6 15

25 2,4 14

26 2,5 8

27 3,8 5

28 1,6 5

29 1,9 5

30 2,7 3

31 3,7 3

32 2,8 2

33 1,8 1

34 1,7 0

35 2,6 0

36 2,9 0

Setelah diperoleh daftar ranking, langkah selanjutnya adalah menentukan rute

mana yang harus dipilih sesuai dengan urutan dan jumlah masing – masing kapasitas

angkut tidak boleh melebihi 23 unit.

Langkah penentuan rute adalah sebagai berikut :

1. Savings terbesar menjadi awal rute, berarti rute yang dilalui dari 0 menuju 5

kemudian 9 dan kembali ke 0 ( 0,5,9,0 ), dengan kapasitas di node 5 adalah 7 dan

kapasitas node 9 adalah 4, sehingga kapasitas angkut pada rute 1 adalah 7 + 4 =

11. Mengingat kapasitas per sekali angkut adalah 23 unit. maka rute selanjutnya

dapat dibuat berdasarkan daftar ranking savings.

2. Selanjutnya adalah ( 0,5,9,8,0 ) dengan kapasitas angkut adalah 15, berikutnya

dapat dibuat untuk satu kali perjalanan yaitu ( 0,5,9,8,7,0 ) dengan kapasitas 20

unit. Kapasitas per sekali angkut adalah 23 unit, berarti tersisa 3 unit yang dapat

diangkut. Dari daftar savings yang ada kita dapat melakukan trial and error untuk

menentukan rute mana yang harus dibuat.

3. Daftar savings ke – 4 dicoba untuk penentuan rute, bila dibuat rute ( 0,4,5,9,8,7,0 )

akan diperoleh kapasitas 24. Kapasitas sekali angkut yang diperbolehkan adalah

23, maka rute ini tidak dapat digunakan sehingga untuk savings ( 4,5 ) menjadi

awal rute kedua yang terbesar.

4. Kemudian dibuat rute dari data savings ke–5 sehingga diperoleh rute (0,6,5,9,8,7,0)

dengan kapasitas adalah 23 unit. Rute ini memungkinkan karena kapasitas per

sekali angkut sebanyak 23 unit.

5. Penentuan rute kedua sama halnya dengan tahap awal dan dimulai dari daftar

savings terbesar kedua yaitu ( 4,5 ) berarti rute yang dilalui dari 0 menuju 4 dan

kembali ke 0 ( 0,4,0 ), dengan kapasitas di node 4 adalah 4.Namun di node 5 tidak

lagi di kunjungi karena sudah ada pada rute sebelumnya.

6. Selanjutnya adalah ( 0,3,4,0 ) dengan kapasitas angkut adalah 9, berikutnya dapat

dibuat untuk satu kali perjalanan yaitu ( 0,2,3,4,0 ) dengan kapasitas 15 unit.

7. Kemudian dibuat rute dari daftar savings ke –11 sehingga diperoleh rute

( 0,1,2,3,4,0 ) dengan kapasitas adalah 19 unit.

8. Sehingga dari perhitungan diperoleh rute pertama yaitu ( 0,6,5,9,8,7,0 ) dengan

kapasitas adalah 23 unit. Kemudian rute kedua ( 0,1,2,3,4,0 ) dengan kapasitas 19

unit. Dua rute inilah yang menjadi solusi yang optimal dengan jarak total adalah

397 km.

V. INTERPRETASI

Rute 1 :

Savings terbesar menjadi awal rute , berarti rute yang dilalui dari 0 menuju 5

kemudian 9, kemudian 8, kemudian 7, kemudian 6, dan kembali ke 0

(0,6,5,9,8,7,0 ), dengan kapasitas di node 6 adalah 3, kapasitas di node 5 adalah 7,

kapasitas node 9 adalah 4 , kapasitas node 8 adalah 4, kapasitas node 7 adalah 5.

Sehingga kapasitas angkut pada rute ini adalah 3 + 7 + 4 + 4 + 5 = 23

Pada rute ini kita gunakan daftar rangking dari rangking 1 sampai rangking 6,

Kecuali pada daftar rangking 4, 5 dan 6 kita menggunakan trial and eror karena

daftar rangking ini melebihi kapasitas angkut dan sudah masuk pada daftar

rangking sebelumnya. Mengingat kapasitas per sekali angkut adalah 23.

Rute 2 :

Selanjutnya, untuk rute kedua kita mulai pada daftar rangking ke 4 sampai daftar

rangking ke 11. Pada rute ini di ambil dari node (0,1,2,3,4,0) dengan kapasitas di

node 1 adalah 4, kapasitas di node 2 adalah 6, kapasitas di node 3 adalah 5,

0 ( Depot )

1

2

3

4

5

6

7

8

9

kapasitas di node 4 adalah 4. Sehingga kapsitas angkut pada rute ini adalah 4 + 6 +

5 + 4 = 19.

Gambar 5.1 Depot dan 9 node yang harus dikunjungi

Dari hasil di atas dapat disimpulkan bahwa dengan menggunakan metode savings

heuristic diperoleh total jarak tempuh sebesar 397 km. Hasil ini bila dibandingkan dengan

total jarak awal sebesar 408 km menghasilkan selisih jarak sebesar 11 km. Dengan demikian

Dinas Kebersihan dapat meminimumkan biaya transportasi yang mengakibatkan bahan

bakar juga dapat diminimumkan.

Rute 1Rute 2

Tugas Pemodelan

Menentukan rute pengangkutan sampah untuk memperkecil total

jarak tempuh dengan menggunakan Metode Savings Heuristic

Di Susun Oleh :

Erlinda Lapago G 201 08 020

Lenny V. Wengkang G 201 08 028

Yerobeam Santule G 201 08 067

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS TADULAKO

DESEMBER, 2010