Prosiding
ANNUAL RESEARCH SEMINAR 2016 6 Desember 2016, Vol 2 No. 1
ISBN : 979-587-626-0 | UNSRI
http://ars.ilkom.unsri.ac.id
Analisis Penugasan Sopir Pada Rute Optimal Pengangkutan Sampah Di Kota Palembang Dengan Menggunakan Metode Hungarian Indrawati 1), Irmeilyana2), Ning Eliyati, Agus Lukowi Jurusan Matematika, Fakultas MIPA, Universitas Sriwijaya 1 email:
[email protected] 2 email:
[email protected] (one-to-one). Tujuan dari masalah penugasan untuk menetapkan setiap tugas yang sesuai pada pekerja, sehingga total kompetensi atau hasil pekerjaan dapat dimaksimalkan (Anton & Rorres, 2005). Salah satu metode yang dapat digunakan untuk menyelesaikan masalah penugasan yaitu dengan menggunakan metode Hungarian. Sistem pengangkutan sampah di Kota Palembang dilakukan secara bertahap. Pengangkutan sampah oleh petugas Dinas Kebersihan dan Keindahan (DKK) dari TPS (Tempat Pembuangan Sementara) ke TPA (Tempat Pembuangan Akhir) dilakukan berdasarkan pembagian Wilayah Kerja (WK). Pengangkutan sampah pada semua TPS dalam satu WK dilakukan oleh 1 orang sopir dengan satu kendaraan tetap. Kendaraan ini hanya mengangkut sampah dari TPSTPS yang ada pada WK-nya saja. Proses pengangkutan dengan memperhatikan kapasitas masing-masing kendaraan dan kapasitas permintaan (sampah) pada setiap rute disebut Vehicle Routing Problem (VRP). Solusi dari VRP adalah rute optimal (terpendek), sehingga dapat menghemat jarak tempuh kendaraan, biaya transportasi (termasuk biaya bahan bakar), dan waktu. Pada masalah CVRP (Capacitated VRP) konvensional seperti yang dibahas dalam Irmeilyana, dkk. (2009) kendaraan pengangkut komoditas (sampah) diharuskan kembali ke depot setelah menyelesaikan pekerjaannya. Tetapi, untuk beberapa kendaraan pengangkut biasanya tidak kembali ke depot setelah melaksanakan tugasnya, tetapi kembali ke tempat lain, misalnya rumah sopir pengangkut sampah tersebut. Dalam hal ini masalah menjadi lintasan terbuka OCVRP (Open CVRP). Indrawati, dkk. (2016) membahas penentuan rute optimal pada pengangkutan sampah di Kecamatan Ilir Timur I Kota Palembang dengan menggunakan metode saving matrix. Tujuan yang dibahas pada makalah ini adalah menentukan penugasan (penempatan) optimal dari seorang sopir pada satu
Abstrak- Metode Hungarian adalah algoritma kombinasi untuk optimasi yang dapat digunakan dalam menemukan solusi optimal dari permasalahan personnel assignment problem. Penelitian ini bertujuan untuk menentukan penugasan optimal sopir dump truck pada rute optimal pengangkutan sampah di Kecamatan Ilir Timur I Palembang. Rute optimal yang dibahas merupakan masalah Open Capacitated Vehicle Routing Problem (OCVRP). Ditinjau dari jumlah objek dan jumlah tugas, maka masalah penugasan sopir yang sering membawa pulang dump truck (penugasan I) merupakan kondisi penugasan tidak seimbang, sedangkan pada masalah sopir yang jarang membawa pulang dump truck (penugasan II) merupakan kondisi penugasan seimbang. Dengan menggunakan metode Hungarian, ada 5 penugasan optimal yang mungkin pada masalah penugasan I dan ada 2 penugasan optimal untuk masalah penugasan II. Dalam hal ini, ada 10 kemungkinan solusi masalah penugasan sopir pada rute optimal pengangkutan sampah di Kecamatan Ilir Timur I Palembang. Kata kunci: Rute optimal, metode Hungarian, penugasan sopir dump truck, pengangkutan sampah. I. PENDAHULUAN Aljabar matriks merupakan salah satu teori matematika yang dapat diaplikasikan pada ilmu optimasi. Salah satu masalah ilmu optimasi yang dapat diselesaikan dengan matriks adalah masalah penugasan. Masalah penugasan mensyaratkan adanya fasilitas-fasilitas yang sama banyaknya dengan tugastugas, misalnya masing-masing sebanyak n. Dalam hal ini, terdapat n! cara yang berbeda untuk menetapkan tugas-tugas pada fasilitas-fasilitas dengan korespondensi satu-ke-satu
305
Prosiding
ANNUAL RESEARCH SEMINAR 2016 6 Desember 2016, Vol 2 No. 1
ISBN : 979-587-626-0 | UNSRI
http://ars.ilkom.unsri.ac.id
WK pada rute optimal yang didapat dari metode saving matrix (Indrawati,dkk., 2016) jika sebenarnya rute-rute tersebut merupakan lintasan terbuka yang dimulai dari rumah sopir dan kembali ke TPA, kemudian dilanjutkan kembali dari TPA ke rumah sopir setelah proses pengangkutan sampah selesai. Analisis penugasan optimal ini menggunakan metode Hungarian untuk memperoleh total jarak tempuh minimal dari penugasan sopir .
seimbang), yaitu dengan cara menambahkan dummy job atau worker job. 3. Tentukan nilai terkecil dari setiap baris, kemudian kurangkan setiap nilai dalam baris tersebut dengan nilai terkecilnya. 4. Periksa apakah setiap kolom telah mempunyai nilai nol, bila sudah dilanjutkan ke Langkah 5. Bila belum, dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kolom tersebut dikurangkan dengan nilai terkecilnya. 5. Tutupi semua nilai nol dengan menggunakan baris vertikal atau horizontal seminimal mungkin. Bila jumlah garis sudah sama dengan jumlah baris atau kolom maka tabel telah optimal. Jumlah garis belum sama dengan jumlah baris atau kolom, maka dilanjutkan ke Langkah 6. 6. Tentukan nilai terkecil dari nilai-nilai yang tidak tertutup garis. Selanjutnya semua nilai yang tidak tertutupi garis dikurangkan dengan nilai terkecil tersebut. 7. Kembali ke Langkah 5. Selanjutnya, pada entri-entri nol, dilakukan uji optimalitas untuk analisis penugasan optimal.
II. KAJIAN LITERATUR
2.1.Metode Hungarian Rumusan tentang penugasan optimal secara tepat dengan sejumlah kuantitas adalah: = biaya untuk menetapkan tugas ke-j pada fasilitas ke-i. dengan i, j = 1, 2, . . . n. Matriks biaya (cost matrix) merupakan matriks n x n yang mempunyai syarat tiap fasilitas dikenai oleh sebuah tugas yang unik atas dasar korespondensi satu ke satu adalah ekuivalen dengan syarat bahwa tidak ada dua yang berasal dari baris atau kolom yang sama. Matriks biaya dituliskan sebagai: C=[
]
(1)
2.2. Rute Optimal pada Indrawati, dkk. (2016) Data rute optimal pada Indrawati, dkk. (2016) sebagai berikut: 1. TPA - TPS Pasar Induk (J) – TPA. 2. TPA - TPS Jln. Letkl Iskandar (K2) - TPS Jln. Masjid Lama (E1) - Pasar 16 Ilir (E4) - Tengkuruk Permai (E3) – TPA. 3. TPA - TPS Jln. Kol Atmo (K1) - Kol. Atmo Depan JM (F7) - TPS Air Mancur s/d Sekip (I2) - Pasar 16 Ilir (K3) - TPA. 4. TPA - Jalur Tertib Jend. Suderman (I1) - Jln. Ali Gatsmir 14 Ilir (E2) - TPS Pasar Cinde (M7) - Rumah Susun (K4) - TPS Lapangan Hatta (M5) - TPA. 5. TPA - Sekip Bendung (H2) - RK Caritas s/d Jendral Sudirman (G3) - TPS Depo Bay Salim (H1) - Jln. Rajawali (H5) - Pasar Sekip Ujung (H4) - TPA. 6. TPA - TPS Simpang Sekip (M6) - Jend. Sudirman s/d Simpang Sekip (KI-KA) (F5) - TPS Departemen Agama (M3) - TPS Kantor Gubernur (M2) - TPS Rumah Sakit Caritas (M4) - Jln. Bay salim (H3) TPS Belakang Panglima (M1) – TPA.
Jumlah n entri dari sebuah penugasan disebut biaya penugasan tersebut. Penugasan dengan biaya terkecil yang mungkin disebut penugasan optimal (optimal assignment) (Anton & Rorres, 2005). Masalah penugasan sederhana adalah masalah penugasan yang hanya mempunyai satu tujuan optimasi, yaitu memaksimalkan atau meminimalkan suatu sumber daya (pendapatan, biaya, jasa, atau waktu) yang digunakan untuk menyelesaikan tugas. Winston (1991) menyatakan metode Hungarian adalah sebuah algoritma kombinasi untuk optimasi yang dapat digunakan untuk menemukan solusi optimal dari permasalahan personnel assignment problem. Anton & Rorres (2005) menyatakan langkah-langkah penyelesaian masalah penugasan menggunakan Algoritma Hungarian pada masalah minimasi dengan matriks adalah sebagai berikut. 1. Identifikasi dan penyederhanaan masalah dalam bentuk matriks biaya. 2. Modifikasi matriks biaya ke dalam matriks efektivitas; jika n ≠ m (masalah penugasan tidak
306
Prosiding
ANNUAL RESEARCH SEMINAR 2016 6 Desember 2016, Vol 2 No. 1
ISBN : 979-587-626-0 | UNSRI
7.
8.
9.
http://ars.ilkom.unsri.ac.id
TPA - TPS Jln. Jendral Sudirman (G1) - TPS kantor Kecamatan Ilir Timur I (L1) - Sekip Pangkal (G2) – TPA. TPA - Taman Fly Over (F3) - Depan SPBU Romi Herton (F2) - SMK N2 (F8) - TPS Jln. Demang Lebar Daun (F1) - PLN Demang (F4), Demang Lebar Daun (F6) – TPA. TPA - TPS Kemuning (L2) - Km.5 (K5) - TPA.
4. 5.
IV. HASIL DAN PEMBAHASAN Berdasarkan rute optimal pada kendaraan dump truck yang diperoleh dari Indrawati, dkk. (2016), maka dapat diketahui TPS yang pertama dikunjungi oleh sopir. Beberapa sopir sering membawa pulang kendaraan dump truck setiap hari (selanjutnya disebut Masalah Penugasan I). Sedangkan beberapa sopir jarang membawa pulang mobil ke rumah (selanjutnya disebut Masalah Penugasan II). Mereka biasanya akan membawa pulang mobil jika diperlukan. Seperti penuhnya lokasi parkir di TPA, menghindari kemacetan agar tidak telat dalam mengangkutan sampah, dan alasan lain. Tabel 1 dan Tabel 2 berikut ini merupakan data jarak antara rumah setiap sopir dengan TPS yang pertama kali dikunjungi pada rute optimal dan juga jarak antara rumah setiap sopir dengan TPA.
III. METODE PENELITIAN Penelitian ini merupakan studi kasus dengan menggunakan data rute optimal kendaraan dump truck pada Indrawati, dkk. (2016). Data diperoleh dari DKK Kota Palembang dan survei lapangan. Adapun langkah- langkah yang dilakukan adalah : 1. Mengumpulkan data sopir yang ‗sering‘ membawa mobil ke rumah. 2. Mengukur jarak antara rumah setiap sopir dengan TPS yang pertama kali dikunjungi pada setiap rute optimal dan juga jarak antara rumah setiap sopir dengan TPA. 3. Menyusun matriks biaya; yang entrinya adalah total jarak rumah sopir dengan TPA dan jarak rumah sopir dengan
Nama
setiap TPS pertama yang dikunjungi pada setiap rute optimal (hasil Langkah 2). Mengolah hasil Langkah 3 dengan menggunakan metode Hungarian untuk masalah minimasi. Menganalisis hasil perhitungan dari Langkah 4.
Tabel 1. Jarak TPS yang Pertama Dikunjungi dengan Rumah Setiap Sopir pada Masalah Penugasan I R1 R2 R3 R4 R5 R6 R7 R8 R9
TPA
Zulhadi
12,75
18,80
9,29
8,42
7,92
8,00
6,83
6,05
7,01
12,80
Amran
17,21
12,02
11,19
10,84
10,43
9,99
8,74
8,21
7,87
1,75
Harianto
17,41
12,22
11,39
11,04
10,63
10,19
8,94
8,41
8,07
1,55
Badarudin
17,43
12,24
11,41
11,06
10,65
10,11
8,96
8,43
8,09
1,53
Budiman
18,92
13,76
12,90
12,95
12,14
11,70
10,45
9,92
9,58
0,04
Keterangan: Satuan jarak dalam km. R1-R9 = Jarak terdekat dengan TPS yang pertama pada rute optimal ke 1 sampai 9, yaitu ; TPS Pasar Induk, Jln. Letnan Kol. Iskandar, Jln. Kol. Atmo, Jalur Tertib Jed. Sudirman, Sekip Bandung, Simpang Sekip, Jln. Jend. Sudirman, Taman Fly Over, dan TPS Kemuning.
Tabel 2. Jarak TPS yang Pertama Dikunjungi dengan Rumah Setiap Sopir pada Masalah Penugasan II Nama R1 R2 R3 R4 R5 R6 R7 R8 R9 Misbahudin 20,93 15,77 14,91 14,96 14,18 13,71 12,46 11,93 11,59 Alidin 9,10 11,82 11,51 12,39 14,02 13,00 14,15 14,88 14,76 Eman 2,66 4,88 4,60 5,45 7,09 6,10 7,21 7,93 7,84 Sopian
2,07
3,72
3,41
4,28
5,95
307
4,91
6,05
6,77
6,67
TPA 2,05 22,75 16,96 16,00
Prosiding
ANNUAL RESEARCH SEMINAR 2016 6 Desember 2016, Vol 2 No. 1
ISBN : 979-587-626-0 | UNSRI
http://ars.ilkom.unsri.ac.id
Selanjutnya masalah penugasan setiap sopir pada rute optimal diselesaikan dengan metode Hungarian. Untuk membuat matriks biaya, jarak yang dihitung adalah penjumlahan dari jarak rumah setiap sopir dengan TPS yang pertama dikunjungi pada rute optimal dan jarak TPA ke rumah setiap sopir. Satuan jarak dalam km diubah dalam satuan hm (dikali 10) dengan pembulatan (tanpa desimal). Matriks biaya
yang diperoleh untuk Masalah Penugasan Sopir yang sering/selalu membawa pulang dump truck merupakan masalah penugasan tidak seimbang, sehingga perlu ditambah 4 sopir dummy, seperti pada Tabel 3.
Zulhadi
R1 256
Tabel 3. Tabel Matriks Biaya pada Masalah Penugasan I R2 R3 R4 R5 R6 R7 316 221 212 207 208 196
R8 189
R9 198
Amran
190
138
130
126
122
118
105
100
97
Harianto
190
138
130
126
122
118
105
100
97
Badarudin
189
137
129
126
122
116
105
99
96
Budiman
189
138
129
130
121
117
105
99
96
Dummy 1
0
0
0
0
0
0
0
0
0
Dummy 2
0
0
0
0
0
0
0
0
0
Dummy 3
0
0
0
0
0
0
0
0
0
Dummy 4
0
0
0
0
0
0
0
0
0
Zulhadi
R1 67
R80 0
R9 9
Amran
93
41
33
29
25
21
8
3
0
Harianto
93
41
33
29
25
21
8
3
0
Badarudin
93
41
33
30
26
20
9
3
0
Budiman
93
42
33
34
25
21
9
3
0
Dummy 1
0
0
0
0
0
0
0
0
0
Dummy 2
0
0
0
0
0
0
0
0
0
Dummy 3
0
0
0
0
0
0
0
0
0
Dummy 4
0
0
0
0
0
0
0
0
0
Tabel 4. Penyelesaian I dari Tabel Matriks Biaya Masalah Penugasan I R2 R3 R4 R5 R6 R7 127 32 23 18 19 7
308
Prosiding
ANNUAL RESEARCH SEMINAR 2016 6 Desember 2016, Vol 2 No. 1
ISBN : 979-587-626-0 | UNSRI
http://ars.ilkom.unsri.ac.id
Zulhadi
R1 60
Tabel 5. Penyelesaian II dari Tabel Matriks Biay a Masalah Penugasan I R2 R3 R4 R5 R6 120 25 16 11 12
Amran
86
34
26
22
18
Harianto
86
34
26
22
Badarudin
86
34
26
Budiman
86
35
Dummy 1
0
Dummy 2
R7 0
R80 0
R9 9
14
1
3
0
18
14
1
3
0
23
19
13
2
3
0
33
27
18
14
2
3
0
0
0
0
0
0
0
7
7
0
0
0
0
0
0
0
7
7
Dummy 3
0
0
0
0
0
0
0
7
7
Dummy 4
0
0
0
0
0
0
0
7
7
Zulhadi
R1 60
R80 0
R9 10
Amran
85
33
25
21
17
13
0
2
0
Harianto
85
33
25
21
17
13
0
2
0
Badarudin
85
33
25
22
18
12
1
2
0
Budiman
85
34
32
26
17
13
1
2
0
Dummy 1
0
0
0
0
0
0
0
7
8
Dummy 2
0
0
0
0
0
0
0
7
8
Dummy 3
0
0
0
0
0
0
0
7
8
Dummy 4
0
0
0
0
0
0
0
7
8
Zulhadi
R1 60
R80 0
R9 12
Amran
83
31
23
19
15
11
0
0
0
Harianto
83
31
23
19
15
11
0
0
0
Badarudin
83
31
23
20
16
10
1
0
0
Tabel 6. Penyelesaian III dari Tabel Matriks Biaya Masalah Penugasan I R2 R3 R4 R5 R6 R7 120 25 16 11 12 0
Tabel 7. Penyelesaian IV dari Tabel Matriks Biaya Masalah Penugasan I R2 R3 R4 R5 R6 R7 120 25 16 12 2 11
309
Prosiding
ANNUAL RESEARCH SEMINAR 2016 6 Desember 2016, Vol 2 No. 1
ISBN : 979-587-626-0 | UNSRI
Budiman
83
http://ars.ilkom.unsri.ac.id
32
30
24
15
11
2
0
0
Dummy 1
0
0
0
0
0
0
2
7
10
Dummy 2
0
0
0
0
0
0
2
7
10
Dummy 3
0
0
0
0
0
0
2
7
10
Dummy 4
0
0
0
0
0
0
2
7
10
R6 1
R7 2
R80 0
R9 12
Tabel 8. Penyelesaian V dari Tabel Matriks Biaya Masalah Penugasan I R1 R2 R3 R4 R5 Zulhadi 49 109 14 5 0 Amran
72
20
12
8
4
0
0
0
0
12
8
4
0
0
0
0
Harianto
72
20
Badarudin
72
20
12
9
5
1
1
0
0
Budiman
72
21
19
13
4
0
1
0
0
Dummy 1
0
0
0
0
0
0
13
18
21
Dummy 2
0
0
0
0
0
0
13
18
21
Dummy 3
0
0
0
0
0
0
13
18
21
Dummy 4
0
0
0
0
0
0
13
18
22
Berdasarkan Tabel 8, ada 5 penugasan optimal yang mungkin, yang semuanya menghasilkan jarak minimal yang sama, yaitu 625. Penugasan yang mungkin tersebut dapat dilihat pada Tabel 9. Tabel 9. Solusi Masalah Penugasan I
Zulhadi
I R5
II R5
Kemungkinan Solusi III R5
IV R5
V R5
Amran
R6
R7
R6
R7
R8
Harianto
R7
R6
R7
R8
R7
Badarudin
R8
R8
R9
R9
R9
Budiman
R9
R9
R8
R6
R6
rute optimal ‗sisa‘, yaitu R1, R2, R3, dan R4. Tabel 10 sampai Tabel 13 merupakan penyelesaian masalah penugasan II.
Masalah penugasan II, yaitu untuk sopir yang jarang membawa pulang dump truck, penugasannya menggunakan
310
Prosiding
ANNUAL RESEARCH SEMINAR 2016 6 Desember 2016, Vol 2 No. 1
ISBN : 979-587-626-0 | UNSRI
http://ars.ilkom.unsri.ac.id
(i)
Tabel 10. Tabel Matriks Biaya Masalah Penugasan II R1 R2 R3 R4 Misbahudin
230
179
170
171
Alidin
237
346
343
352
Eman
173
175
175
176
Sopian
162
164
163
164
(ii)
Tabel 11. Penyelesaian I dan II Masalah Penugasan II R R2 R3 R4 R R2 R3 R4 1 Misbahudi n Alidin
Karena pada solusi masalah penugasan I ada 5 kemungkinan, dan pada solusi masalah penugasan II ada 2 kemungkinan, maka ada 10 kemungkinan penugasan sopir pada rute optimal.
1
68
17
8
9
68
15
7
7
75
18
18
19
75
18
18
18
4
1
0
2
0
8
Eman
11
13
13
14
11
11
12
12
Sopian
0
2
1
2
0
0
0
0
V. KESIMPULAN Berdasarkan hasil dan pembahasan maka diperoleh kesimpulan bahwa ada 5 penugasan optimal yang mungkin pada masalah penugasan sopir yang sering membawa pulang dump truck. Sedangkan pada masalah sopir yang jarang membawa pulang dump truck, ada 2 penugasan optimal, yang semuanya menghasilkan jarak minimal yang sama. Dalam hal ini, ada 10 kemungkinan solusi masalah penugasan sopir pada rute optimal pengangkutan sampah di Kecamatan Ilir Timur I Palembang.
Tabel 12. Penyelesaian III dan IV Masalah Penugasan II R R2 R3 R4 R R2 R3 R4 1 Misbahudi n Alidin
1
61
8
0
0
61
8
0
0
68
17
17
18
64
17
16
17
5
3
1
1
9
7
Eman
4
4
5
5
0
0
1
1
Sopian
0
0
0
0
0
0
0
0
REFERENSI [1]
[2]
Tabel 13. Penyelesaian V Masalah Penugasan II R1 R2 R3 R4 Misbahudin
61
8
0
0
Alidin
0
107
105
113
Eman
0
0
1
1
Sopian
0
0
0
0
Misbahudin bertugas di R4, Alidin bertugas di R1, Eman bertugas di R2, dan Sopian bertugas di R3. Jarak optimal (minimal) = 171 +237 +175 + 163 = 746. Misbahudin bertugas di R3, Alidin bertugas di R1, Eman bertugas di R2, dan Sopian bertugas di R4. Jarak optimal (minimal) = 170 +237 +175 + 164 = 746.
[3]
Berdasarkan Tabel 13, hanya ada 2 kemungkinan solusi, yaitu:
[4]
311
Anton, H dan Rorres, C. 2005. Aljabar Linier Elementer Versi Aplikasi, Jilid 2 Edisi Kedelapan. Jakarta: Erlangga. Indrawati, Irmeilyana, N. Eliyati, A. Lukowi. 2016. Determination of optimal routes on garbage transportation by using saving matrix method. Draft paper yang submit pada ICMS 2016, Malaysia. Irmeilyana, Puspita, F. M., & Indrawati. (2009). Pemodelan dan solusi optimal Open Capacitated Vehicle Routing Problem pada transportasi pengangkutan sampah di Kecamatan Ilir Timur I Kota Palembang. Paper dipresentasikan pada Konferensi Nasional Teknologi Informasi dan Aplikasinya, Fak. Ilmu Komputer UNSRI. Winston, W. L. 1991. Operations Research: Applications and Algorithms. 2nd Edition. California: Wadsworth Publishing.