OPTIMALISASI PENGANGKUTAN SAMPAH DI KOTA SEMARANG DENGAN MENERAPKAN ALGORITMA FLOYD-WARSHALL
Skripsi diajukan sebagai salah satu persyaratan untuk memperoleh gelar Sarjana Pendidikan Program Studi Pendidikan Teknik Informatika dan Komputer
HALAMAN JUDUL Oleh Firstyan Ariful Rizal NIM.5302411112
JURUSAN TEKNIK ELEKTRO FAKULTAS TEKNIK UNIVERSITAS NEGERI SEMARANG 2015
i
ii
iii
iv
MOTTO DAN PERSEMBAHAN
Motto :
Sesungguhnya dibalik kesulitan pasti ada kemudahan. (Q.S. Al-Insyiroh : 5). Maka ni’mat Tuhanmu yang manakah yang kamu dustakan. (Q.S. Ar-Rohman : 55). Allah tidak akan membebani seseorang, melainkan sesuai dengan kesanggupannya. (Q.S. Al-Baqoroh : 286).
Persembahan :
Dengan mengucap syukur Alhamdulillah, saya persembahkan karya kecil ini untuk orang-orang yang saya sayangi: Ayah ( Mashuri) dan Ibu (Sri Mulyani) tercinta, motivator terbesar dalam hidup saya, terima kasih untuk setiap dukungan, nasihat dan doa yang selalu diberikan. Setiap perjuangan dan pengorbanan yang kalian berikan selalu menjadi penguat dalam setiap langkah untuk menempuh pendidikan ini. Dosen pembimbing, Bapak Aryo Baskoro Utomo, S.T., M.T., Terima kasih sudah berkenan meluangkan waktunya untuk membimbing saya, terima kasih untuk semua bimbingan dan nasihatnya. Saudara saya Brilliansyah Fata Priestama. Keluarga besar Rombel 3 PTIK UNNES 2011, terima kasih untuk kerja samanya selama ini. Kalian memang hebat. Keluarga Hanif kost, Sompret, Pak Seto, Pak Drajat, Bang Ikhsan, Hanif, Rafi, Ibu dan Bapak kost. Teman berkelana selama kuliah, kak Ika, kak Im, kak Beb, kak April, kak Rulan, kak Son. Kalian membuat masa kuliah ini menjadi lebih berwarna.
v
ABSTRAK
Rizal, Firstyan Ariful. 2015. “Optimalisasi Pengangkutan Sampah di Kota Semarang dengan Menerapkan Algoritma Floyd-Warshall”. Skripsi. Pendidikan Teknik Informatika dan Komputer. Jurusan Teknik Elektro. Fakultas Teknik. Universitas Negeri Semarang. Pembimbing : Aryo Baskoro Utomo, S.T., M.T. Kata Kunci : Floyd-Warshall, node, path, SOP, TPS, TPA, simpang, optimalisasi, pengangkutan sampah. Pertumbuhan penduduk kota yang sangat tinggi serta meningkatnya kegiatan pembangunan di berbagai sektor menimbulkan berbagai masalah di wilayah-wilayah perkotaan yang antara lain urbanisasi, permukiman kumuh, persampahan dan sebagainya. Berdasarkan data Dinas Kebersihan dan Pertamanan Kota Semarang, pada tahun 2014 hanya sekitar 86,4% dari total jumlah sampah di Kota Semarang yang dapat terangkut ke TPA. Tujuan penelitian ini adalah melakukan optimalisasi pengangkutan sampah dengan cara mencari jalur terpendek pengangkutan sampah dari TPS menuju ke TPA Jatibarang, Kota Semarang. Algoritma Floyd-Warshall digunakan untuk mencari jalur terpendek pengangkutan sampah di Kota Semarang, dengan mengambil wilayah Semarang Tengah sebagai sampel penelitian. Perhitungan dimulai dengan membuat graf jaringan pengangkutan sampah terlebih dahulu. TPS, TPA dan persimpangan jalan sebagai node, sedangkan jalan yang menghubungkan antar node sebagai sisinya. Setelah jaringan terbentuk, selanjutnya dibuat matriks jarak node ketetanggaan pada jaringan tersebut dan melakukan proses perhitungan menggunakan algoritma Floyd-Warshall hingga mendapatkan nilai matriks jalur terpendek antar tiap titip yang optimum. Pengujian dilakukan dengan cara membandingkan rute perjalanan yang dihasilkan oleh perhitungan sistem dengan rute yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang. Hasil perhitungan sistem menunjukkan bahwa ada perbedaan pilihan rute perjalanan pengangkutan sampah, dibandingkan dengan yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang. Pilihan rute perjalanan yang dihasilkan oleh sistem dapat memberikan panjang rute perjalanan yang lebih pendek dari pada yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang sesuai SOP. Berdasarkan hasil perhitungan sistem, dari 20 TPS yang ada di Kecamatan Semarang Tengah, terdapat 15 TPS yang mendapat pilihan jalur berbeda dari SOP DKP Kota Semarang, sedangkan 5 lainnya sama. Pilihan jalur yang diberikan oleh sistem menghasilkan selisih panjang lintasan positif dibandingkan dengan yang selama ini diterapkan oleh DKP yaitu antara 200 hingga 1240 meter. Oleh karena itu algoritma FloydWarshall bisa menjadi solusi dalam pemecahan masalah pencarian jalur terpendek.
vi
KATA PENGANTAR
Puji syukur saya sampaikan kehadirat Allah SWT karena atas limpahan rahmat dan karunia-Nya, sehingga penulis dapat menyelesaikan Skripsi yang berjudul “Optimalisasi Pengangkutan Sampah di Kota Semarang dengan Menerapkan Algoritma Floyd-Warshall”. Skripsi ini merupakan tugas akhir yang diajukan untuk memenuhi syarat dalam memperoleh gelar Sarjana Pendidikan pada Program Studi Pendidikan Teknik Informatika dan Komputer Jurusan Teknik Elektro Fakultas Teknik Universitas Negeri Semarang. Penulis menyadari bahwa penulisan ini tidak akan terwujud tanpa adanya bantuan dan dorongan dari berbagai pihak. Oleh karena itu penulis menyampaikan ucapan terima kasih kepada : 1. Prof. Dr. Fathur Rokhman, M.Hum , Rektor Universitas Negeri Semarang atas kesempatan yang diberikan kepada penulis untuk menempuh studi di Universitas Negeri Semarang. 2. Bapak Dr. H. Muhammad Harlanu M.Pd., Dekan Fakultas Teknik. 3. Bapak Drs. Suryono, M.T., Ketua Jurusan Teknik Elektro UNNES. 4. Bapak Feddy Setio Pribadi, S.Pd., M.T., Ketua Prodi PTIK UNNES. 5. Bapak Aryo Baskoro Utomo, S.T., M.T., selaku dosen pembimbing yang telah memberikan bimbingan, arahan, nasehat serta motivasi dalam penyusunan skripsi ini. 6. Kepala Dinas Kebersihan dan Pertamanan Kota Semarang beserta staff yang telah memberikan kesempatan kepada penulis untuk melakukan penelitian. 7. Rekan-rekan PTIK 2011, khususnya rekan-rekan Rombel 3 yang telah membantu menyusun laporan skripsi ini. Semoga laporan skripsi ini bermanfaat dan memberikan sumbangan yang berarti bagi pihak yang membutuhkan. vii
Semarang, 2 September 2015 Penulis
DAFTAR ISI
HALAMAN JUDUL................................................................................................ i PERNYATAAN KEASLIAN ................................ Error! Bookmark not defined. PERSETUJUAN PEMBIMBING .......................... Error! Bookmark not defined. HALAMAN PENGESAHAN ................................ Error! Bookmark not defined. MOTTO DAN PERSEMBAHAN .......................................................................... v ABSTRAK ............................................................................................................. vi KATA PENGANTAR .......................................................................................... vii DAFTAR ISI ........................................................................................................ viii DAFTAR TABEL ................................................................................................... x DAFTAR GAMBAR ............................................................................................. xi DAFTAR LAMPIRAN ......................................................................................... xii BAB I PENDAHULUAN ....................................................................................... 1 1.1 Latar Belakang ............................................................................................ 1 1.2 Permasalahan ............................................................................................... 5 1.3 Pembatasan Masalah ................................................................................... 5 1.4 Tujuan.......................................................................................................... 6 1.5 Manfaat ........................................................................................................ 7 1.6 Sistematika Penulisan .................................................................................. 7 BAB II LANDASAN TEORI ................................................................................. 9 2.1 Riset Operasi ............................................................................................... 9 2.2 Graf............................................................................................................ 14 2.3 Representasi Graf dalam Matriks .............................................................. 18 2.4 Jaringan (Network) .................................................................................... 23 2.4.1 Model Distribusi Terkendali.......................................................... 25 2.4.2 Model Minimum Spanning Tree .................................................... 26 2.4.3 Model Rute Terpendek .................................................................. 27 2.5 Algoritma Floyd-Warshall untuk Graf Berarah ........................................ 28 2.6 Kajian Penelitian yang Relevan ................................................................ 35
viii
2.7 Kerangka Pikir........................................................................................... 36 BAB III METODE PENELITIAN........................................................................ 38 3.1 Membuat Peta Jaringan Awal Pengangkutan Sampah Kota Semarang .... 38 3.2 Pengambilan Data ..................................................................................... 39 3.3 Pemodelan Jaringan dan Penyelesaian Model Matematis ......................... 40 3.4 Pengembangan Sistem............................................................................... 41 3.4.1 Arsitektur Sistem ........................................................................... 41 3.4.2 Desain Sistem ................................................................................ 43 3.4.3 Pengkodean Sistem ........................................................................ 46 3.5 Perancangan Pengujian ............................................................................. 48 3.5.1 Bahan Pengujian ............................................................................ 48 3.5.2 Tujuan Pengujian ........................................................................... 49 3.5.3 Skenario dan Kriteria Pengujian .................................................... 49 BAB IV HASIL DAN PEMBAHASAN .............................................................. 51 4.1 Hasil Penelitian ......................................................................................... 51 4.1.1 Pemetaan Awal Jaringan ............................................................... 51 4.1.2 Proses Perhitungan Algoritma Floyd-Warshall ............................. 60 4.2 Pembahasan ............................................................................................... 74 BAB V PENUTUP ................................................................................................ 78 5.1 Kesimpulan................................................................................................ 78 5.2 Saran .......................................................................................................... 79 DAFTAR PUSTAKA ........................................................................................... 78 LAMPIRAN .......................................................................................................... 80
ix
DAFTAR TABEL
Tabel 2.1 Rancangan biaya pemasangan jaringan listrik ...................................... 20 Tabel 2.2 Contoh sistem jaringan ........................................................................ 24 Tabel 4.1 Data titik/node jaringan pengangkutan sampah Semarang Tengah ...... 51 Tabel 4.2 Data Path jaringan pengangkutan sampah Semarang Tengah .............. 53 Tabel 4.3 Rute perjalanan pengangkutan sampah hasil perhitungan algoritma Floyd-Warshall ..................................................................................... 62 Tabel 4.4 Rute perjalanan pengangkutan sampah berdasarkan SOP Dinas Kebersihan dan Pertamanan Kota Semarang........................................ 65 Tabel 4.5 Perbedaan pilihan jalur dari TPS Matahari Johar menuju TPA ............ 69 Tabel 4.6 Perbandingan panjang rute perjalanan .................................................. 71
x
DAFTAR GAMBAR
Gambar 2.1 Penyederhanaan masalah................................................................... 11 Gambar 2.2 Contoh graf ........................................................................................ 14 Gambar 2.3 Graf dari contoh 1 ............................................................................. 17 Gambar 2.4 Contoh Graf G ................................................................................... 17 Gambar 2.5 Graf H yang memiliki sisi paralel dan loop ...................................... 19 Gambar 2.6 Graf G untuk contoh 4 ....................................................................... 21 Gambar 2.7 Graf sederhana F untuk contoh 5 ...................................................... 22 Gambar 2.8 Terminologi Jaringan ........................................................................ 23 Gambar 2.9 Contoh Jaringan................................................................................. 24 Gambar 2.10 Model Jaringan Transportasi dan Distribusi Terkendali ................. 26 Gambar 2.11 Graf berarah dan berbobot............................................................... 31 Gambar 2.12 Path terpendek dari v1 ke v6........................................................... 34 Gambar 2.13 Kerangka Berpikir ........................................................................... 37 Gambar 3.1 Bagan alur metode penelitian ............................................................ 39 Gambar 3.2 Arsiterktur sistem penghitung jalur terpendek .................................. 42 Gambar 3.3 Alur proses pengembangan sistem .................................................... 43 Gambar 3.4 Tampilan halaman utama .................................................................. 44 Gambar 3.5 Antarmuka menampilkan pilihan rute berdasar kecamatan .............. 44 Gambar 3.6 Antarmuka menampilkan jalur pengangkutan sampah ..................... 45 Gambar 4.1 Jaringan pengangkutan sampah kecamatan Semarang Tengah ......... 57 Gambar 4.2 Contoh perbandingan pilihan jalur sesuai SOP dan hasil sistem ...... 69
xi
DAFTAR LAMPIRAN
Lampiran 1. Peta awal jaringan pengangkutan sampah ....................................... 81 Lampiran 2. Matriks Wij awal jaringan pengangkutan sampah kecamatan Semarang Tengah ................................................................................ 84 Lampiran 3. Matriks Zij awal jaringan pengangkutan sampah kecamatan Semarang Tengah ................................................................................ 89 Lampiran 4. Matriks W* akhir jaringan pengangkutan sampah kecamatan Semarang Tengah ................................................................................. 94 Lampiran 5. Matriks Z* akhir jaringan pengangkutan sampah kecamatan Semarang Tengah ................................................................................. 99 Lampiran 6. Source Code Program ..................................................................... 104 Lampiran 7. Data TPS dan Operasional Armada Pengangkut Sampah di Kecamatan Semarang Tengah ............................................................ 108 Lampiran 8. Standar Operasional dan Prosedur Rute Pengangkutan Sampah Kota Semarang ................................................................................... 109 Lampiran 9. Validasi Hasil Rute Pengangkutan Sampah oleh Kepala Seksi Penyapuan dan Pengangkutan Sampah ............................................. 111 Lampiran 10. Validasi Hasil Rute Pengangkutan Sampah oleh Sopir Armada Pengangkut Sampah ........................................................................... 116 Lampiran 11. Surat Usulan Topik Skripsi .......................................................... 121 Lampiran 12. Surat Usulan Dosen Pembimbing Skripsi .................................... 122 Lampiran 13. Surat Penetapan Dosen Pembimbing Skripsi ............................... 123 Lampiran 14. Surat Permohonan Observasi di DKP Kota Semarang ................. 124 Lampiran 15. Surat Rekomendasi Penelitian dari Badan Kesbangpol ............... 125 Lampiran 16. Surat Keterangan Telah Melaksanakan Penelitian ....................... 127 Lampiran 17. Dokumentasi ................................................................................. 128
xii
BAB I PENDAHULUAN
1.1
Latar Belakang Prof. H.R. Sudrajat (dalam Mengelola Sampah Kota, 2003) menggambarkan
potensi timbunan sampah per hari di beberapa kota besar di Indonesia. Seiring dengan semakin meningkatnya jumlah penduduk di suatu kota, memungkinkan timbunan sampah akan semakin meningkat per harinya.
Volume
sampah
yang meningkat dan tidak segera dikelola akan berdampak buruk terhadap lingkungan dan kehidupan masyarakat. Sampah merupakan salah satu dari sekian banyak masalah sosial yang dihadapi masyarakat. Masyarakat kota ataupun daerah yang padat penduduknya pasti menghasilkan sampah yang begitu banyak. Sampah kota merupakan kewajiban pemerintah kota untuk menanganinya, untuk itu sistem pengelolaannya telah dikembangkan secara nasional. Sistem persampahan yang lazim digunakan di Indonesia adalah sistem yang didasarkan atas premis kesehatan, ialah bahwa sampah merupakan bahaya kesehatan, sehingga harus secepatnya dikumpulkan, diangkut, dan dibuang serta dijaga agar dampak lingkungan yang diakibatkannya dapat diminimalkan. Yang menjadi masalah adalah kota-kota besar pada umumnya tidak dapat mengangkut seluruh timbulan sampahnya, yakni sekitar 70% hingga 80% saja. Sampah yang tak terangkut umumnya dibakar, dipendam, atau dibuang di selokan dan sungai sehingga
1
2
menyebabkan aliran air tidak lancar yang pada akhirnya akan menyebabkan banjir (Cipta Karya, 1999). Khususnya Kota Semarang sebagai kota pemerintahan, perdagangan, pelayanan jasa dan kota pendidikan sangat sulit untuk menanggulangi masalah sampah. Masalah yang dihadapi pemerintah dan masyarakat Kota Semarang dalam upaya menjadi kota yang nyaman sebagai tempat tinggal adalah persampahan. Terbatasnya unit truk sampah yang ada sering kali membuat proses pengangkutan sampah menjadi terhambat, sehingga membuat sampah-sampah menumpuk sampai menunggu proses pengangkutan oleh truk-truk sampah. Volume timbunan sampah di Kota Semarang setiap harinya yang bisa terangkut ke TPA adalah hanya sebesar 86,4% dari total jumlah sampah yang ada di Kota Semarang yaitu sebesar ±800 ton (Data Dinas Kebersihan dan Pertamanan Kota Semarang, 2014). Hal ini menunjukkan terjadi ketidakefisienan dalam pengangkutan sampah. Secara teknis operasional faktor penyebabnya antara lain diduga oleh kurangnya jumlah armada pengangkut, timbulnya hambatan di samping perjalanan dan belum adanya rute-rute yang secara pasti terjadwal dalam truk - truk sampah mengangkut dari TPS ke TPA (Sutiyono, 2006). Pengangkutan sampah dipengaruhi oleh aksesibilitas (waktu tempuh), pola pengangkutan, moda pengangkutan, frekuensi pengangkutan dan tingkat pelayanan pengangkutan. Suatu
metode
yang dapat
digunakan untuk mempercepat
proses
pengangkutan sampah di Kota Semarang dan sampah-sampah bisa secara merata dapat diangkut oleh truk-truk sampah adalah dengan mencari rute terpendek untuk mengangkut sampah-sampah tersebut ke Tempat Pembuangan Akhir (TPA)
3
Jatibarang yang terletak di Kelurahan Kedungpane, Kecamatan Mijen, Kota Semarang. Menentukan rute terpendek pada jaringan pengangkutan sampah di Kota Semarang menuju ke TPA Jatibarang merupakan hal yang menarik untuk dikaji karena dapat diketahui ruas jalan mana saja yang sebaiknya ditempuh oleh truk pengangkut sampah agar dapat ditentukan jarak paling pendek dan dapat menjangkau seluruh kawasan penampungan sampah sementara di Kota Semarang. Penggunaan rute terpendek dalam pengangkutan sampah diharapkan dapat menghemat waktu tempuh dan dapat meminimalisir biaya bahan bakar yang dikeluarkan. Seiring dengan semakin berkembangnya ilmu pengetahuan dan teknologi, terutama dalam bidang riset operasi pada akhir-akhir ini baik dalam metodologi maupun dalam penerapan model-model optimasi jaringan kerja, sejumlah terobosan algoritma pada tahun 70-an hingga 80-an telah menimbulkan pengaruh yang besar. Berbagai metode dan perkembangan perangkat lunak (software) kini dapat dimanfaatkan untuk menyelesaikan banyak masalah komputasi yang tidak dapat dipecahkan pada beberapa dekade yang lalu. Sebagai contoh adalah berkembangnya perangkat lunak yang bermanfaat dalam penyelesaian masalah matematis seperti Matlab, Microsoft Excel, dan lain sebagainya. Beberapa algoritma yang dapat digunakan untuk memecahkan permasalahan rute terpendek, antara lain algoritma Dijkstra, algoritma Bellman-Ford, algoritma Greedy, algoritma Floyd-Warshall dan lain-lain. Algoritma Floyd-Warshall adalah salah satu algoritma yang paling mudah penerapannya, karena algoritma ini merupakan bagian dari program dinamik yang dapat mencari semua lintasan
4
terpendek masing-masing antara tiap kemungkinan pasang tempat yang berbeda (All-pairs Shortest Path Problems) dan sangat efektif digunakan dalam menangani masalah rute optimum (Saputra, 2011). Algoritma Floyd-Warshall ditemukan oleh Warshall untuk mencari rute/lintasan terpendek. Algoritma ini merupakan algoritma yang sederhana dan mudah implementasinya (Siang, 2002:272). Algoritma ini sangat efisien dari sudut pandang penyimpanan data karena dapat diimplementasikan dengan hanya melakukan pengubahan sebuah matrik jarak dan dapat menghitung bobot terkecil dari semua titik yang menghubungkan sebuah pasangan titik dan melakukannya sekaligus untuk semua pasangan titik. Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisi-sisi pada sebuah jalur adalah bobot jalur tersebut. Saputra (2011) dalam penelitiannya membahas tentang pembangunan sistem informasi geografis pencarian rute optimum objek wisata kota Yogyakarta dengan algoritma Floyd-Warshall, yang digunakan sebagai media wisatawan untuk mencari suatu lokasi atau penuntun arah ke suatu lokasi dengan mencari rute optimum lokasi objek wisata tertentu. Hasil dari penelitian ini didapatkan bahwa algoritma Floyd-Warshall dapat digunakan dalam mencari rute optimum dengan pemrograman visual. Sedangkan dalam penelitian Hougardy (2010) seorang peneliti di Research Institute for Discrete Mathematics, University of Bonn, pada jurnal Internasional yang berjudul “The Floyd-Warshall algorithm on graphs with
5
negative cycles” menjelaskan bahwa Algoritma Floyd-Warshall adalah algoritma sederhana dan banyak digunakan untuk menghitung jalur terpendek. Dari permasalahan sampah di Kota Semarang dan penelitian tentang pencarian jalur terpendek, maka menentukan rute minimum pada jaringan pengangkutan sampah di wilayah Kota Semarang menuju ke TPA Jatibarang merupakan hal yang menarik untuk dikaji. Oleh karena itu, penulis tertarik untuk melakukan penelitian dengan judul “Optimalisasi Pengangkutan Sampah di Kota Semarang dengan Menerapkan Algoritma Floyd-Warshall”.
1.2
Permasalahan Dari latar belakang di atas, permasalahan yang akan dikaji adalah sebagai
berikut: 1. Bagaimana penyelesaian optimum dalam menentukan rute terpendek pada pemodelan jaringan pengangkutan sampah di wilayah Kota Semarang dari TPS menuju ke TPA Jatibarang dengan menggunakan algoritma FloydWarshall? 2. Bagaimana perbandingan rute pengangkutan sampah di Kota Semarang yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang dengan rute pengangkutan sampah menggunakan perhitungan algoritma Floyd-Warshall?
1.3
Pembatasan Masalah Dalam penyusunan skripsi ini, permasalahan yang akan dibahas dibatasi
pada:
6
1. Graf jaringan pengangkutan sampah terdiri dari titik dan sisi. Titik/node merepresentasikan lokasi TPS, TPA, serta persimpangan jalan. Sisi adalah setiap jalan yang menghubungkan antar titik dalam jaringan. Penentuan titik dan sisi dalam jaringan didasarkan pada Standar Operasional dan Prosedur Pengangkutan Sampah Dinas Kebersihan dan Pertamanan Kota Semarang. 2. Armada / truk pengangkut sampah adalah tipe Arm Roll Truck, yaitu jenis truk yang dapat melepas dan mengangkut bak, sehingga pengangkutan sampah dilakukan sekali jalan untuk 1 kontainer. 3. Optimalisasi yang dihitung dalam penelitian ini adalah optimalisasi/ meminimumkan jarak tempuh yang dilalui oleh truk sampah dari TPS menuju ke TPA. 4. Penghitungan untuk pencarian rute terpendek hanya dilakukan untuk wilayah Semarang Tengah sebagai sampel.
1.4
Tujuan Tujuan dari penelitian ini adalah sebagai berikut:
1. Menentukan rute terpendek pada jaringan pengangkutan sampah di wilayah Kota Semarang menuju ke TPA Jatibarang dengan menggunakan algoritma Floyd-Warshall. 2. Mengetahui hasil perbandingan rute pengangkutan sampah antara rute yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang dengan rute yang dihasilkan dari perhitungan algoritma Floyd-Warshall.
7
1.5
Manfaat Manfaat dari penelitian ini adalah sebagai berikut:
1. Diharapkan dapat menambah wawasan dan pengetahuan tentang masalah menentukan rute terpendek pada model jaringan. 2. Dapat mengaplikasikan algoritma Floyd-Warshall pada penyelesaian optimum dalam masalah pencarian rute terpendek pada model jaringan. 3. Dapat mengetahui cara penyelesaian pada model jaringan pengangkutan sampah di Kota Semarang dengan algoritma Floyd-Warshall dengan bantuan aplikasi berbasis web. 4. Diharapkan hasil penelitian ini dapat digunakan sebagai bahan pertimbangan dalam mengambil keputusan tentang penentuan rute terpendek yang akan ditempuh oleh truk pengangkut sampah untuk mengangkut sampah-sampah di Kota Semarang menuju ke TPA Jatibarang.
1.6
Sistematika Penulisan Secara garis besar skripsi ini dibagi menjadi tiga bagian, yaitu bagian awal
skripsi, bagian pokok skripsi dan bagian akhir skripsi. Bagian awal skripsi meliputi Halaman Sampul, Halaman Judul, Halaman Pengesahan, Motto dan Persembahan, Kata Pengantar, Abstrak, Daftar Isi, Daftar Gambar, Daftar Tabel dan Daftar Lampiran. Bagian pokok skripsi secara garis besar terdiri dari lima bab, yaitu: BAB I
PENDAHULUAN Di dalam bab ini dikemukakan latar belakang, permasalahan, pembatasan masalah, tujuan, manfaat, dan sistematika penulisan.
8
BAB II
LANDASAN TEORI Di dalam bab ini dikemukakan konsep-konsep yang dijadikan landasan teori dalam penelitian yang akan dilakukan oleh peneliti, yaitu teori-teori yang berhubungan pencarian rute terpendek. Selain itu, dalam bab ini juga dikemukakan tentang penelitian terdahulu serta kerangka pikir penulis.
BAB III
METODE PENELITIAN Di dalam bab ini dikemukakan metode penelitian yang berisi langkahlangkah yang harus ditempuh untuk menyelesaikan permasalahan, pengambilan data, pemodelan jaringan dan penyelesaian model matematis, pengembangan sistem serta perancangan pengujian.
BAB IV
HASIL PENELITIAN DAN PEMBAHASAN Di dalam bab ini dikemukakan hasil penelitian dan pembahasan yang berisi
mengenai
penerapan
algoritma
Floyd-Warshall
dalam
menentukan rute terpendek pada pemodelan jaringan pengangkutan sampah di Kota Semarang. BAB V
PENUTUP Di dalam bab ini dikemukakan simpulan dari pembahasan hasil penelitian dan saran.
Bagian akhir skripsi meliputi Daftar Pustaka dan Lampiran-lampiran yang mendukung penulisan skripsi.
BAB II LANDASAN TEORI
Pada bab ini, akan dibahas tentang konsep-konsep yang dijadikan sebagai landasan teori dalam penelitian yang akan dilakukan oleh peneliti, yaitu teori-teori yang berhubungan pencarian rute terpendek. Teori-teori yang akan dibahas antara lain tentang riset operasi, graf, jaringan (network), model distribusi terkendali, model rentang jaringan minimum, model rute terpendek, serta penerapan algoritma Floyd-Warshall untuk graf berarah. Selain itu, dalam bab ini juga memuat tentang penelitian terdahulu yang relevan dan kerangka pikir penelitian.
2.1
Riset Operasi Riset operasi adalah penerapan metode-metode ilmiah terhadap masalah-
masalah rumit yang muncul dalam pengarahan dan pengelolaan dari suatu sistem besar manusia, mesin, bahan dan uang dalam industri, bisnis, pemerintahan dan pertahanan. Pendekatan khusus ini bertujuan membentuk suatu model ilmiah dari sistem, menggabungkan ukuran-ukuran faktor-faktor seperti kesempatan dan risiko, untuk meramalkan dan membandingkan hasil-hasil dari beberapa keputusan, strategi atau pengawasan. Tujuannya adalah membantu pengambil keputusan menentukan kebijaksanaan dan tindakannya secara ilmiah (Agustini, 2004:2-3). Operation Research Society of America mendefinisikan riset operasi sebagai berikut
:“
Riset
operasi
berhubungan 9
dengan
keputusan
ilmiah
10
tentang bagaimana mengoptimalkan rancangan dan operasi mesin maupun SDM, yang biasanya terjadi pada keadaan di mana sumber daya dan alokasinya terbatas”. Riset operasi diartikan sebagai peralatan manajemen yang menyatukan ilmu pengetahuan, matematika dan logika dalam kerangka pemecahan masalahmasalah yang dihadapi sehari-hari, sehingga akhirnya permasalahan tersebut dapat dipecahkan secara optimal (Subagyo, 2000:4). Riset operasi berhubungan dengan prinsip optimisasi, yaitu bagaimana cara menggunakan sumber daya (waktu, tenaga, biaya, dan lain-lain) untuk mengoptimalkan hasil. Mengoptimalkan hasil dapat berarti meminimumkan sesuatu yang merugikan/dikeluarkan atau memaksimumkan sesuatu yang menguntungkan/
didapatkan.
Beberapa
contoh
kasus
sehari-hari
yang
berhubungan dengan riset operasi antara lain: 1. Ada banyak jalur darat yang bisa dilalui dari Jakarta ke Yogyakarta. Jalur mana yang paling optimal dari segi jarak? Dari segi biaya? Dari segi waktu? 2. Pembuatan kaleng untuk menyimpan makanan. Berapa ukuran kaleng (diameter dan tinggi) agar dengan volume tertentu membutuhkan bahan seminimum mungkin? 3. Pengaturan lampu traffic light. Berapa lama lampu hijau/merah di tiaptiap sisi harus menyala agar panjang antrean kendaraan seminimum mungkin? (Siang, 2011:2).
11
Riset operasi mencari keputusan/hasil terbaik pada penyelesaian suatu masalah yang memenuhi beberapa kondisi yang ditentukan. Dalam prosesnya, riset operasi berhubungan dengan model. Model adalah interaksi/hubungan antara variabel-variabel yang mempengaruhi sistemnya. Kompleksnya sistem yang dipelajari akan membuat penyelesaian masalah menjadi sulit. Untuk itu perlu untuk mereduksi “dimensi” sistem sehingga model (tiruan sistem) dapat dibuat, seperti pada gambar 2.1 (Siang, 2011:4).
Sistem yang sebenarnya
Penyederhanaan sistem
Model
Gambar 2.1 Penyederhanaan masalah Dalam riset operasi, pembuatan model melibatkan 3 komponen dasar yang penting, yaitu: 1. Variabel keputusan, yaitu faktor-faktor yang mempengaruhi nilai tujuan. 2. Tujuan, yaitu suatu fungsi atau persamaan yang menghubungkan variabel dan membentuk kesatuan tentang apa yang ingin dicapai. Dalam riset operasi akan mencari harga fungsi tujuan yang optimal, artinya kita akan mencari nilai-nilai variabel yang akan meminimumkan/memaksimumkan fungsi tujuan. 3. Kendala, yaitu sekumpulan persamaan atau pertidaksamaan yang membatasi harga suatu variabel. Harga variabel yang mengoptimumkan
12
fungsi tujuan harus memenuhi semua kendala yang ditetapkan (Siang, 2011:6). Di dalam riset operasi, pembentukan model yang cocok hanyalah salah satu tahap dari aplikasi riset operasi. Pola dasar penerapan riset operasi terhadap suatu masalah memiliki beberapa proses yang dapat dipisahkan menjadi 5 tahapan, yaitu merumuskan masalah, pembentukan model, mencari penyelesaian masalah, validasi model dan penerapan hasil akhir. 1. Merumuskan Masalah Sebelum solusi terhadap suatu persoalan dipikirkan, pertama kali suatu definisi persoalan yang tepat harus dirumuskan. Dalam perumusan masalah ini ada tiga pertanyaan penting yang harus dijawab. a. Variabel keputusan yaitu unsur-unsur dalam persoalan yang dapat dikendalikan oleh pengambilan keputusan. Ia sering disebut sebagai instrumen. b. Tujuan (objective). Penetapan tujuan membantu pengambil keputusan memusatkan perhatian pada persoalan dan pengaruhnya terhadap organisasi. Tujuan ini diekspresikan dalam variabel keputusan. c. Kendala (constrain) adalah pembatas-pembatas terhadap alternatif tindakan yang tersedia. 2. Pembentukan Model Sesuai
dengan
definisi
persoalannya,
pengambil
keputusan
menentukan model yang paling cocok untuk mewakili sistem. Model merupakan ekspresi kuantitatif dari tujuan dan kendala-kendala persoalan
13
dalam variabel keputusan. Jika model yang dihasilkan cocok dengan salah satu model matematis yang biasa (misalnya linear), maka solusinya dapat dengan mudah diperoleh dengan program linear. 3. Mencari Penyelesaian Masalah Pada tahap ini bermacam-macam teknik dan metode solusi kuantitatif yang merupakan bagian utama dari riset operasi memasuki proses. Penyelesaian masalah sesungguhnya merupakan pengaplikasian satu atau lebih teknik-teknik terhadap model. Sering kali, solusi terhadap model berarti nilai-nilai variabel keputusan yang mengoptimumkan salah satu fungsi tujuan dengan nilai fungsi tujuan lain yang diterima. 4. Validasi Model Asumsi-asumsi yang digunakan dalam pembentukan model harus valid. Dengan kata lain, model harus diperiksa apakah ia mencerminkan berjalannya sistem yang diwakili. Suatu metode yang biasa digunakan untuk menguji validitas model adalah membandingkan performance-nya dengan data masa lalu yang tersedia. Model dikatakan valid jika dengan kondisi masukan yang serupa, ia dapat menghasilkan kembali performance seperti masa lampau. Masalahnya adalah bahwa tak ada yang menjamin performance masa depan akan berlanjut meniru cerita lama. 5. Penerapan Hasil Akhir Tahap terakhir adalah menerapkan hasil model yang telah diuji. Hal ini membutuhkan suatu penjelasan yang hati-hati tentang solusi yang
14
digunakan dan hubungannya dengan realitas. Suatu tahap kritis pada tahap ini adalah mempertemukan ahli riset operasi (pembentuk model) dengan mereka yang bertanggung jawab terhadap pelaksanaan sistem (Mulyono, 2002:7-8).
2.2
Graf Secara sederhana, graf adalah suatu diagram yang memuat informasi
tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari, graf digunakan untuk menggambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti. Beberapa contoh graf yang sering dijumpai dalam kehidupan sehari-hari antara lain: struktur organisasi, bagan alir pengambilan mata kuliah, peta, rangkaian listrik, dan lainlain (Siang, 2002:185). Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa
diselesaikan
dengan
bantuan
graf.
Graf
juga
digunakan
untuk
merepresentasikan suatu jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (titik/node) dan jalan yang menghubungkan setiap kota sebagai sisi (garis). Contoh graf ditunjukkan pada gambar 2.2.
15
B 200
A
50
100
180 75
D
60
E
C Gambar 2.2 Contoh graf Tiap-tiap diagram memuat sekumpulan objek (kotak, titik, dan lain-lain) beserta garis-garis yang menghubungkan objek-objek tersebut. Garis bisa berarah ataupun tidak berarah. Garis yang berarah biasanya digunakan untuk menyatakan hubungan yang mementingkan urutan antar objek-objek. Urutan-urutan objek akan mempunyai arti yang lain jika arah garis diubah. Sebagai contoh adalah garis komando yang menghubungkan titik-titik struktur sebuah organisasi. Sebaliknya, garis yang tidak berarah digunakan untuk menyatakan hubungan antar objekobjek yang tidak mementingkan urutan. Sebagai contoh adalah garis yang menyatakan jarak hubungan 2 kota pada gambar 2.2. Jarak dari kota A ke kota B sejauh 200 km, akan sama dengan jarak kota B ke kota A. Apabila jarak 2 tempat tidak sama jika dibalik (misalnya karena harus melalui jalan memutar), maka garis yang digunakan haruslah garis yang berarah. Sebuah graf linier (atau secara sederhana disebut graf) G = (V,E) adalah suatu sistem yang terdiri atas suatu himpunan objek V = {v1, v2, ...} yang disebut himpunan titik, dan sebuah himpunan E = {e1, e2, ...} yang merupakan himpunan sisi sedemikian hingga tiap sisi ek dikaitkan dengan suatu pasangan tak terurut (vi,vj). Titik vivj yang berkaitan dengan ek disebut titik-titik ujung sisi ek (Sutarno, dkk, 2003:59).
16
Titik pada graf dapat dinomori dengan huruf, misalkan v, w, ..., atau dengan menggunakan bilangan asli 1, 2, 3, ..., atau gabungan keduanya. Sedangkan sisi yang menghubungkan titik vi dengan titik vj dinyatakan dengan pasangan (vi,vj), atau dengan lambang e1, e2, ... Dengan kata lain, jika e adalah sisi yang menghubungkan titik vi dengan titik vj, maka e dapat dituliskan sebagai e = (vi,vj), di mana i,j adalah indeks angka bilangan asli 1, 2, 3, ... . Setiap garis berhubungan dengan satu atau dua titik. Titik-titik tersebut dinamakan Titik ujung. Garis yang hanya berhubungan dengan satu titik ujung disebut Loop. Dua garis berbeda yang menghubungkan titik yang sama disebut Garis paralel. Dua titik dikatakan berhubungan (adjacent) jika ada garis yang menghubungkan keduanya. Titik yang tidak mempunyai garis yang berhubungan dengannya disebut Titik terasing (Isolating Point). Untuk mempermudah dalam pemahaman graf, dijelaskan pada contoh 1 dan contoh 2. Contoh 1. Menggambar graf. Ada 7 kota (A, ..., G) yang beberapa di antaranya dapat dihubungkan secara langsung dengan jalan darat. Hubungan-hubungan langsung yang dapat dilakukan adalah sebagai berikut : A dengan B dan D ; B dengan D ; C dengan B ; E dengan F. Buatlah graf yang menunjukkan keadaan transportasi di 7 kota tersebut! Penyelesaian: Misalkan
kota-kota
dianggap
sebagai
titik-titik.
Dua
titik
(kota)
dihubungkan dengan garis bila dan hanya bila ada jalan yang
17
menghubungkan langsung kedua kota tersebut. Dengan demikian, keadaan transportasi di 7 kota dapat dinyatakan dalam gambar 2.3. B E e1
A
G
e4 e3
e2
e5 C F
D
Gambar 2.3 Graf dari contoh 1 Dalam graf tersebut e1 berhubungan dengan titik A dan B (keduanya disebut titik ujung e1). Titik A dan B dikatakan berhubungan, sedangkan titik A dan G tidak berhubungan karena tidak ada garis yang menghubungkannya secara langsung. Titik G adalah titik terasing karena tidak ada garis yang berhubungan dengan G. Dalam interpretasinya, kota G merupakan kota terasing karena tidak dapat dikunjungi dari kota-kota lain dengan jalan darat. Contoh 2. Graf G yang memiliki titik ujung, garis paralel dan loop. V1 V4 e1
e5
e3
V5
e6
e2 e4
V3
e7
V6
V2
Gambar 2.4 Contoh Graf G Dalam graf G pada gambar 2.4, V(G) = {v1, v2, v3, v4, v5, v6} dan E(G) = {e1, e2, e3, e4, e5, e6, e7}. Titik-titik ujung dari masing-masing garis,
18
misalkan garis e1 memiliki titik ujung {v1, v2}. Garis paralel adalah e1 dan e2 yang keduanya menghubungkan titik v1 dan v2. Loop adalah e6 dan e7, sedangkan titik terasing adalah v6. Graf yang tidak mempunyai titik ujung (sehingga tidak mempunyai garis) disebut Graf kosong (Siang, 2002:187). Graf sederhana adalah graf yang tidak memiliki loop dan sisi paralel. Graf yang semua garisnya berarah disebut Graf berarah. Sedangkan graf yang semua garisnya tidak berarah disebut Graf tak berarah. Bobot pada sisi graf adalah sebuah bilangan asli yang dapat bernilai positif, misalkan bobot yang menyatakan suatu jarak, waktu tempuh, atau ongkos transportasi dari satu titik ke titik yang lainnya. Akan tetapi, dalam beberapa model persoalan dimungkinkan bahwa bobot dari suatu sisi bernilai negatif, misalkan titik merepresentasikan bandara, sisi merepresentasikan penerbangan yang memungkinkan, dan bobot dari setiap sisi adalah biaya yang dikeluarkan dalam penerbangan tersebut. Untuk suatu kasus di mana seseorang akan dibayar untuk menempuh rute tertentu oleh suatu biro penerbangan, maka bobotnya akan bernilai negatif (Kamayudi, 2006:1). Graf yang setiap sisinya diberikan suatu bobot dinamakan dengan Graf berbobot. 2.3
Representasi Graf dalam Matriks Matriks dapat digunakan untuk menyatakan suatu graf. Hal ini sangat
membantu untuk membuat program komputer yang berhubungan dengan graf. Jika dapat menyatakan graf sebagai suatu matriks, maka perhitungan-perhitungan yang diperlukan dapat dilakukan dengan melakukan operasi pada matriks tersebut seperti penjumlahan, pengurangan, dan lain lain. Beberapa matriks yang terkait
19
dengan graf yaitu meliputi matriks ketetanggaan, matriks ketetanggaan untuk graf berbobot dan matriks boolean.
1. Matriks Ketetanggaan Matriks ketetanggaan atau matriks keterhubungan digunakan untuk menyatakan graf dengan cara menyatakannya dalam jumlah garis yang menghubungkan titik-titiknya. Jumlah baris (dan kolom) matriks ketetanggaan sama dengan jumlah titik dalam graf. Misalkan G adalah sebuah graf dengan n titik. Matriks ketetanggaan dari graf G adalah matriks bujur sangkar (persegi) berordo n, X(G) = xij, dengan elemen xij menyatakan banyaknya sisi yang menghubungkan titik ke-i ke titik ke-j. Dengan definisi ini memungkinkan untuk menyatakan sebuah graf yang memiliki sisi paralel atau loop dengan matriks ketetanggaan (Sutarno, dkk. 2003:79). Contoh graf yang memiliki sisi paralel dengan matriks ketetanggaan dicontohkan pada gambar 2.5. Contoh 3. Sebuah graf yang memiliki sisi paralel dan loop.
b
a
e c
d
Gambar 2.5 Graf H yang memiliki sisi paralel dan loop Matriks ketetanggaannya: a
b c d e
20
( ) [
]
Matriks ketetanggaan juga digunakan untuk menyatakan graf berbobot, yaitu elemen-elemennya menyatakan bobot garis. 2. Matriks Ketetanggaan untuk Graf Berbobot Diketahui G graf berbobot dengan setiap sisi dengan suatu bilangan riil tak negatif. Matriks yang bersesuaian dengan graf berbobot G adalah matriks ketetanggaan atau matriks keterhubungan X(G) = xij dengan xij = bobot garis yang menghubungkan titik vi dengan vj. Jika titik vi tidak berhubungan langsung dengan titik vj maka xij = ∞, dan xij = 0, jika i = j. (Siang, 2002:262). Contoh 4. Representasi graf ketetanggaan berbobot. Dalam suatu provinsi, ada 8 kota (v1, v2, ..., v8) yang akan dihubungkan dengan jaring-jaring listrik. Biaya pemasangan jaringan listrik yang akan dibuat antar 2 kota ditunjukkan pada tabel 2.1. Bagaimanakah graf dan matriks ketetanggaannya? Tabel 2.1 Rancangan biaya pemasangan jaringan listrik Garis
Kota yang dihubungkan
Biaya persatuan
e4 e7
v2 – v3
3
v4 – v6
4
e2
v1 – v7
5
e8
v3 – v4
5
e9
v3 – v5
5
e1
v1 – v2
15
21
e3
v1 – v4
15
e10
v6 – v8
15
e5
v7 – v8
15
e11
v5 – v6
15
e6
v6 – v7
18
Penyelesaian: Graf berbobot untuk menyatakan jaringan listrik di 8 kota digambarkan pada gambar 2.6. Angka dalam kurung menyatakan bobot garis yang bersangkutan. Bobot tersebut menyatakan biaya pemasangan jaringan listrik. V1
e2 (5)
e1 (15)
e3 (15)
V7
e4 (3) e8 (5)
V4 e6 (18)
e10 (15)
V3
e7 (4)
e5 (15) V8
V2
e9 (5)
V6
V5
e11 (15)
Gambar 2.6 Graf G untuk contoh 4 Matriks keterhubungan untuk menyatakan graf berbobot pada gambar 2.6 adalah matriks X(G) = xij dengan: xij = bobot garis yang menghubungkan titik vi dengan vj. xij = ∞, jika titik vi tidak berhubungan langsung dengan titik vj, dan xij = 0, jika i = j. v1 v2
v3
v4
v5
v6
v7
v8
22
( )
[
]
Dalam program komputer, sel dengan harga ∞ diisi dengan suatu bilangan yang harganya jauh lebih besar dibandingkan dengan harga elemen-elemen yang bukan ∞. 3. Matriks Boolean Matriks Boolean adalah matriks yang elemen-elemennya hanya bernilai 0 (nol) dan 1 (satu). Elemen-elemennya bisa hanya bernilai 0 (nol) semua, bernilai 1 (satu) semua atau gabungan dari keduanya. Salah satu contoh dari kegunaan matriks boolean ini adalah biasanya digunakan dalam perhitungan untuk membantu menentukan rute bagi suatu jaringan. Bentuk dan sifat-sifat perhitungan dari suatu matriks boolean sama dengan
matriks
biasa,
bedanya
pada
Matriks
Boolean
proses
perhitungannya menggunakan operator logika (Nurhayati, 2003:1). Contoh graf sederhana untuk matriks boolean ditunjukkan pada gambar 2.7. Contoh 5. Graf sederhana matriks boolean.
a d
b
c
23
Gambar 2.7 Graf sederhana F untuk contoh 5 Matriks ketetanggaannya : a b c
( )
2.4
d
[
]
Jaringan (Network) Jaringan (Network) adalah istilah model untuk memvisualisasikan sebuah
sistem jaringan agar sistem jaringan yang sesungguhnya bisa diketahui dan dipahami dengan mudah, cepat dan tepat. Jaringan (Network) secara visual pada dasarnya terdiri dari rangkaian titik (node) dan garis/sisi. Garis berfungsi untuk menghubungkan antar titik mewakili kegiatan, saluran, dan jalan. Garis bisa berupa anak panah yang akan menunjukkan arah arus dari titik awal atau sumber ke titik akhir atau tujuan. Anak panah menandai arah arus, maka ada dua arah arus yang dapat terjadi yaitu arus yang searah dan arah arus yang dua arah. (Siswanto, 2006:381). Untuk mempermudah dalam memahami jaringan, terminologi jaringan dapat digambarkan seperti dalam gambar 2.8.
Node awal
Anak panah penghubung node awal dan node akhir
Node awal 1
2
1
Gambar 2.8 Terminologi Jaringan
2
24
Contoh 6. Sistem Jaringan. Tabel 2.2 Contoh sistem jaringan Sistem Jaringan Transportasi darat Transportasi udara Transportasi laut Listrik Bahan bakar kendaraan
Pabrik / perakitan telepon
Node Kota, persimpangan Pelabuhan udara (Bandara) Pelabuhan Pusat tenaga listrik, gardu induk kota Pelabuhan, penyulingan, depot induk, pompa bensin Pusat kerja / perakitan sentral telepon otomatis, gardu induk, terminal box
Anak panah / garis
Jenis Arus
Jalan
Kendaraan
Jalur penerbangan
Pesawat terbang
Jalur pelayaran
Kapal
Jalur kabel
Listrik
Pipa, kendaraan pengangkut bahan bakar
Bahan bakar
Material handling kabel telepon
Bahan, barang, informasi
Contoh 7. Sistem jaringan transportasi darat. Sebuah perusahaan kendaraan umum mengoperasikan armada dari kota O ke kota T. Untuk menempuh perjalanan ini, ada beberapa alternatif rute yang bisa dilaluinya, yang jaringannya digambarkan pada gambar 2.9.
25
A
7
4 O
D
6
6 B
5 C
5
4
1 E
T
8
Gambar 2.9 Contoh Jaringan Sistem jalan tersebut ditunjukkan garis (tanpa lengkungan), di mana O, A, B, C, D, E, T sebagai abjad yang menunjukkan kota yang dilalui armada dari perusahaan kendaraan umum, sedangkan angka-angka pada garis menunjukkan jarak dari satu kota ke kota yang lainnya, dalam satuan km. Armada ini akan beroperasi dari kota O ke kota T. Dari berbagai permasalahan jaringan, ada empat macam model jaringan yang bisa digunakan untuk membantu pemecahan masalah-masalah jaringan, yaitu model distribusi terkendali, model rentang jaringan minimum, model rute terpendek, dan model aliran maksimum (Siswanto, 2006:381). 2.4.1
Model Distribusi Terkendali Model distribusi terkendali pada dasarnya adalah sebuah model distribusi
seperti model transportasi namun model ini lebih rumit karena sifat distribusinya yang dinamis di mana sebuah sumber bisa juga berfungsi sebagai tujuan, demikian pula sebaliknya dengan sebuah tujuan. Keadaan demikian akan memungkinkan terbentuknya rangkaian hubungan antar node di dalam sebuah jaringan. Inilah letak perbedaan dasar antara model distribusi terkendali dengan model transportasi yang memiliki sifat distribusi statis di mana distribusi sumber
26
ke tujuan bukan merupakan sebuah rangkaian distribusi yang saling bersambung seperti pada gambar 2.10.
1
3
2
4
1
2
4
3
a
b
Gambar 2.10 Model Jaringan a. Transportasi b. Distribusi Terkendali Di dalam model transportasi yang ditunjukkan oleh gambar 2.10a, node 1 dan node 2 adalah node-node sumber, dan node 3 dan 4 adalah node-node tujuan. Di sini hanya terjadi arus searah dari sumber ke tujuan, yaitu 1-3, 1-4, dan 2-4. Sebaliknya, di dalam model distribusi terkendali yang ditunjukkan oleh gambar 2.10b, node 1 adalah node sumber sekaligus node awal. Dari node 1 mengalir arus ke node 2 dan 3 sebagai tujuan. Kedua node ini kemudian juga berfungsi sebagai node-node sumber bagi node 4 yaitu node tujuan. Dalam hal ini, dapat diketahui bahwa model distribusi terkendali termasuk di dalam kelompok model jaringan yang tidak terarah. 2.4.2
Model Minimum Spanning Tree Model Minimum Spanning Tree adalah salah satu model jaringan yang
menjelaskan pemilihan hubungan antar node sedemikian rupa sehingga jaringan hubungan itu akan membuat seluruh node terhubung dengan panjang hubungan total terpendek. Dengan kata lain, model ini akan meminimumkan rentang jaringan hubungan seluruh node (Siswanto, 2006:391).
27
Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titik dalam jaringan tersebut pada total jarak (panjang) minimum. Langkah-langkah dari pohon rentang minimum adalah : 1. Pilih secara acak sebuah node dalam jaringan. 2. Hubungkan
node
tersebut
dengan
node
terdekat
yang
dapat
meminimalkan total jarak. 3. Perhatikan semua node apakah terdapat node yang belum terhubung, temukan dan hubungkan node terdekat yang belum terhubung. 4. Ulangi langkah ketiga sampai seluruh node dapat terhubung 2.4.3
Model Rute Terpendek Model rute terpendek adalah salah satu model jaringan yang dapat
digunakan untuk menentukan jarak terpendek dari berbagai rute yang tersedia atau mencoba untuk memecahkan masalah pemilihan jaringan paling efisien yang akan menghubungkan satu titik ke titik yang lain. Suatu lintasan antara dua buah titik adalah serangkaian garis yang berbeda yang menghubungkan titik-titik tersebut. Untuk setiap dua titik dapat terjadi beberapa lintasan, maupun lintasan dengan jarak terpendek atau bobok minimum. Bobot minimum dapat berupa jarak, waktu tempuh atau biaya transportasi dari satu titik ke titik yang lainnya yang berbentuk rute tertentu (Dimyati, dkk. 1992:164). Rute terpendek yang dicari adalah rute dari sumber ke tujuan yang memecahkan persoalan jarak total minimum. Faktor-
28
faktor yang mempengaruhi pemilihan rute di antaranya adalah waktu tempuh, jarak, biaya, kemacetan, dan antrean. Terdapat beberapa macam persoalan rute terpendek, antara lain: 1. Rute terpendek antara dua buah titik tertentu. 2. Rute terpendek antara semua pasangan titik. Dapat diselesaikan dengan menggunakan algoritma Floyd-Warshall. 3. Rute terpendek dari titik tertentu ke semua titik yang lain. Dapat diselesaikan dengan menggunakan algoritma Dijkstra dan algoritma Bellman-Ford. (Defindall, dkk. 2003).
2.5
Algoritma Floyd-Warshall untuk Graf Berarah Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V,E),
yang berupa daftar titik (node/titik V) dan daftar sisi (sisi E). Bobot garis e dapat diberi simbol w(e). Jumlah bobot sisi-sisi pada sebuah jalur adalah total bobot jalur tersebut. Sisi pada E dipebolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi graf wii untuk memiliki siklus dengan bobot negatif. Algoritma ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik. Dalam menentukan lintasan terpendek dengan algoritma Floyd-Warshall memulai iterasi dari titik awalnya kemudian memperpanjang lintasan dengan mengevaluasi titik demi titik hingga mencapai titik tujuan dengan jumlah bobot yang paling minimum.
29
Misalkan W0 adalah matriks keterhubungan graf berarah berbobot mula-mula. W* adalah matriks keterhubungan minimal dengan Wi,j = lintasan terpendek dari titik vi ke vj. Algoritma Floyd-Warshall untuk mencari lintasan terpendek adalah sebagai berikut: 1) W = W0 2) Untuk k = 1 hingga n, lakukan : Untuk i = 1 hingga n, lakukan : Untuk j = 1 hingga n, lakukan : Jika W[i,j] > W[i,k] + W[k,j] maka tukar W[i,j] dengan W[i,k] + W[k,j]. 3) W* = W. Dalam iterasinya untuk mencari lintasan terpendek, algoritma FloydWarshall membentuk n matriks, sesuai dengan iterasi-k. Ini akan menyebabkan prosesnya lambat, terutama untuk nilai n yang besar. Meskipun waktu prosesnya bukanlah yang tercepat, algoritma Floyd-Warshall sering dipergunakan untuk menghitung lintasan terpendek karena kesederhanaannya. Di samping itu, implementasi algoritma Floyd-Warshall sangat mudah dibuat. Matriks keterhubungan W yang digunakan untuk menyatakan graf berarah berbobot sama dengan matriks yang digunakan untuk menyatakan graf berbobot, yaitu elemen-elemennya menyatakan bobot garis. Secara umum matriks keterhubungan untuk menyatakan graf berarah berbobot tidaklah simetris karena bobot garis dari titik vi ke vj (= Wi,j) tidak sama dengan bobot garis dari titik vj ke vi (= Wj,i) dan Wi,i = ∞ untuk semua i.
30
Algoritma Floyd-Warshall di atas hanya menghitung jarak terpendek dari semua titik ke semua titik, tetapi tidak menjelaskan bagaimana path terpendeknya. Untuk menentukan path yang menghasilkan jarak terpendek, maka harus ditambahkan matriks bujur sangkar Z (ukuran n x n) yang disusun sebagai berikut: ( )
Inisialisasi Z(0) i,j = { ( )
Dalam iterasi ke-k, apabila titik vk disisipkan antara titik-i dan titik-j (berarti menukar Wi,j dengan Wi,k + Wk,j), maka ganti Zi,j dengan Zi,k. Agar lebih efisien, penggantian matriks Z dilakukan bersama-sama dengan iterasi pencarian jarak terpendeknya. Revisi algoritma Floyd-Warshall dengan melibatkan path terpendeknya adalah sebagai berikut: 1) W = W0 ; Z = Z0 2) Untuk k = 1 hingga n, lakukan : Untuk i = 1 hingga n, lakukan : Untuk j = 1 hingga n, lakukan : Jika W[i,j] > W[i,k] + W[k,j] maka a.
tukar W[i,j] dengan W[i,k] + W[k,j].
b.
Ganti Zi,j dengan Zi,k
3) W* = W. Contoh penyelesaian pencarian jalur terpendek untuk graf berarah menggunakan algoritma Floyd-Warshall dijelaskan pada contoh 8.
31
Contoh 8. Graf berarah berbobot Tentukan lintasan terpendek dari titik vi ke vj ( i,j = 1, 2, ..., 6) menggunakan algoritma Floyd-Warshall untuk graf berarah berbobot pada gambar 2.11!
v1
v2
7
2
v3
4
3
1 4
2
1
2 v4
v5
v6
Gambar 2.11 Graf berarah dan berbobot Penyelesaian: Matriks keterhubungan graf gambar 2.11 adalah v1 v2 v3 v4 v5 v6
v1 v2 v3 v4 v5 v 6
6
Z = Z(0) =
W = W0 = [
]
[
Iterasi untuk k = 1 Untuk setiap sel matriks W dicek apakah W[i,j] > W[i,k] + W[k,j]. Jika ya, maka W[i,j] diganti dengan W[i,k] + W[k,j]. Sebagai contoh:
W[1,2] = 7, sedangkan W[1,1] + W[1,2] = ∞ + 7 = ∞. Karena W[1,2] tidak > W[1,1] + W[1,2], maka W[1,2] tidak diubah.
W[5,4] = ∞, sedangkan W[5,1] + W[1,4] = 2 + 2 = 4.
]
32
Karena W[5,4] > W[5,1] + W[l,4], maka W[5,4] diubah menjadi 4. Ini berarti bahwa ada lintasan dari v5 ke v4 melalui v1 yang mempunyai bobot lebih kecil (yaitu lintasan v5v1v4 dengan jumlah bobot 4) dibandingkan dengan lintasan dari v5 ke v4 secara langsung (bobot = ∞ karena tidak ada lintasan dari v5 ke v4 secara langsung). Dengan cara yang sama, harga W[i,j] dihitung untuk setiap i dan j. Didapatkan matriks : v 1 v2 v3 v4 v5 v6
v1 v2 v3 v4 v5 v 6
6
Z(1) =
W1 = [
𝟏
[
]
𝟏
]
Iterasi untuk k = 2 Iterasi untuk k=2 dilakukan dengan cara yang sama seperti iterasi untuk k = 1, hanya titik perantaranya adalah titik v2. Sebagai contoh:
W[6,5] = ∞, sedangkan W[6,2] + W[2,5] = 1+1 = 2. Karena W[6,5] > W[6,2] + W[2,5] maka harga W[6,5] diganti dengan 2. Ini berarti bahwa lintasan dari v6 ke v5 melalui v2 (v6v2v5) lebih pendek dibandingkan lintasan v6 ke v5 secara langsung.
Proses yang sama dilakukan untuk semua harga i dan j. Didapatkan : v 1 v2 v3
v4
v1 v2 v3 v4 v5 v6
v5 v6
𝟐
𝟐
𝟐
𝟐 𝟏 𝟐
6
Z(2) = [
𝟐
]
33
W2 = [
]
Dengan cara yang sama, untuk k = 3, 4, 5, 6 diperoleh matriks : v 1 v2 v3
v4
v5 v6
Z(3) =
W3 = [
]
v 1 v2 v3
v4
v1 v2 v3 v4 v5 v6 𝟐 𝟑 6 𝟐 𝟑 [ 𝟐] v1 v2 v3 v4 v5 v6
v5 v6
𝟒 𝟒
𝟒 𝟒
6
Z(4) =
W4 =
𝟏
[
[
𝟏
]
]
v 1 v2 v3
v4
v1 v2 v3 v4 v5 v6
v5 v6
𝟒 𝟒 𝟓 𝟓 𝟓 𝟓
6 Z(5) =
W5 = [
𝟐
6 6
(6)
Z =
W* = W6 =
𝟓 𝟔 𝟔 𝟔 𝟔 𝟔 6 [
6
𝟐 𝟐 𝟐 𝟐]
v1 v2 v3 v4 v5 v6
v1 v2 v3 v4 v5 v 6
[
𝟐 𝟐
[𝟐
]
𝟒 𝟓 6 𝟐
]
𝟑
𝟑
]
34
Jika pada W* ada Wij dengan harga ∞ berarti tidak ada lintasan dari vi ke vj baik langsung maupun tidak langsung. W* merupakan matriks jarak terpendek dari semua titik dan Z6 merupakan path yang harus dilalui. Sebagai contoh, jarak dari v1 ke v6 adalah 12, path yang harus dilalui adalah:
Z(6)1,6 = 4 Z(6)4,6 = 2 Z(6)2,6 = 5 Z(6)5,6 = 3 Z(6)3,6 = 6 Jadi path terpendek dari v1 ke v6 adalah v1 → v4 → v2 → v5 → v3 → v6 dengan jarak terpendek = 12, ditunjukkan pada gambar 2.12. (Siang, 2002:272-276).
v1
v2
7
2
v3
4
3
1 4
2 2
v4
v5
1 v6
Gambar 2.12 Path terpendek dari v1 ke v6
35
2.6
Kajian Penelitian yang Relevan Penelitian mengenai optimalisasi pencarian jalur terpendek menggunakan
algoritma Floyd-Warshall pernah dilakukan oleh peneliti-peneliti sebelumnya dengan berbagai permasalahan yang berbeda. Jajali, S.E. dan M. Noroozi (2009:1077) dengan penelitiannya yang berjudul “Determination of the Optimal Escape Routes of Underground Mine Networks in Emergency Cases”, melakukan penelitian yang bertujuan untuk mencari jalur terpendek untuk jalur evakuasi pada jaringan tambang bawah tanah jika terjadi suatu kecelakaan kerja. Sedangkan Saputra (2011:19) dengan penelitiannya yang berjudul “Sistem Informasi Geografis Pencarian Rute Optimum Obyek Wisata Kota Yogyakarta dengan Algoritma Floyd-Warshall”, yaitu membuat suatu sistem informasi berbasis web yang dirancang untuk mencari jalur terpendek dengan menggunakan algoritma Floyd-Warshall yang menghubungkan antar obyek wisata di Kota Yogyakarta. Sani, A., Ni Ketut Tari T., I Made Eka D. (2013:1) juga melakukan penelitian yang mengimplementasikan algortima Floyd-Warshall dengan judul “Algoritma Floyd Warshall untuk Menentukan Jalur Terpendek Evakuasi Tsunami di Kelurahan Sanur”, yaitu pencarian jalur terpendek untuk jalur evakuasi tsunami di Kelurahan Sanur. Kriswanto, Y. R., R. Kristoforus J.B., Arif Aliyanto (2014:1) dengan judul “Penentuan Jarak Terpendek Rute Transmusi dengan Algoritma Floyd-Warshall”, melakukan penelitian yang bertujuan untuk mencari jalur terpendek jalur Transmusi yang merupakan sarana transportasi publik di Kota Palembang.
36
2.7
Kerangka Pikir Kota Semarang sebagai kota pemerintahan, pendidikan, dan perdagangan
memiliki permasalahan klasik yang sama halnya dimiliki oleh kota-kota lain di Indonesia, yaitu persampahan. Sampah menjadi permasalahan yang sampai saat ini menjadi masalah yang masih sulit untuk ditanggulangi, terus bertambahnya jumlah penduduk menjadi salah satu penyebabnya. Setiap hari sampah terus menumpuk dengan penanggulangan pengangkutan yang kurang maksimal. Menurut definisi World Health Organization (WHO) sampah adalah sesuatu yang tidak digunakan, tidak dipakai, tidak disenangi atau sesuatu yang dibuang yang berasal dari kegiatan manusia dan tidak terjadi dengan sendirinya (Chandra, 2006). Untuk menanggulangi permasalahan penumpukan sampah, diperlukan suatu solusi pengangkutan sampah yang cepat dan efisien, salah satunya dengan cara mencari lintasan terpendek (shortest path) dari tempat-tempat penampungan sampah sementara (TPS) menuju ke tempat pembuangan akhir (TPA). Hal ini dapat menghemat jarak tempuh yang dilalui oleh armada pengangkut sehingga dapat juga menghemat waktu tempuh perjalanannya. Salah satu algoritma yang dapat digunakan untuk mencari lintasan terpendek adalah algoritma FloydWarshall, yang ditemukan oleh Stephen Warshall Floyd. Dengan membuat suatu graf yang menghubungkan antara lokasi TPS-TPS serta lokasi TPA dengan tepat dan memperhatikan Standar Operasional Prosedur (SOP) pengangkutan sampah yang digunakan oleh Dinas Kebersihan dan Pertamanan kota Semarang, diharapkan dapat memberikan perhitungan yang tepat
37
dalam mencari lintasan terpendek pengangkutan sampah dari TPS di kota Semarang menuju ke TPA, sehingga permasalahan pengangkutan sampah di kota Semarang mendapatkan solusi yang tepat. Secara umum, kerangka pikir penulis digambarkan pada gambar 2.13. PENUNJANG (OPPORTUNITY) Dinas Kebersihan dan Pertamanan Kota Semarang membutuhkan solusi yang tepat untuk pengoptimalan pengangkutan sampah
PERMASALAHAN (PROBLEMS)
SOLUSI (APPROACH)
1. Penumpukan Sampah di TPS 2. Kurangnya jumlah armada pengangkut sampah
Implementasi Algoritma Floyd-Warshall untuk mencari jalur terpendek pengangkutan sampah dari TPS menuju TPA
PENGEMBANGAN SOFTWARE (DEVELOPMENT)
Analisis kebutuhan dan desain software Pembangunan software : PHP and MySQL Uji software dengan membandingkan hasil hitung aplikasi dan SOP DKP
IMPLEMENTASI SOFTWARE (IMPLEMENTATION)
Jalur-jalur yang menghubungkan dari TPS ke TPA sesuai dengan SOP DKP
KEBERHASILAN SOFTWARE (MEASUREMENT)
Perbedaan jalur yang selama ini digunakan oleh DKP dan jalur yang dihasilkan oleh sistem
HASIL (RESULT) Penerapan Algoritma Floyd-Warshall dalam mencari lintasan terpendek untuk pengangkutan sampah dari TPS menuju TPA memberikan hasil jalur yang lebih pendek dari pada jalur yang selama ini digunakan oleh Dinas Kebersihan dan Pertamanan Kota Semarang sesuai dengan SOP.
Gambar 2.13 Kerangka Pikir
BAB III METODE PENELITIAN
Langkah-langkah yang dilakukan pada penelitian ini adalah membuat peta awal jaringan pengangkutan sampah, pengambilan data, pemodelan jaringan dan penyelesaian model matematis, pengembangan sistem, serta perancangan pengujian. Bagan alur metode penelitian digambarkan pada gambar 3.1.
3.1
Membuat Peta Jaringan Awal Pengangkutan Sampah Kota Semarang Tahap pertama yang dilakukan pada penelitian ini adalah membuat jaringan
pengangkutan sampah di Kota Semarang terlebih dahulu, yaitu berupa jalan-jalan yang mungkin dilewati oleh truk pengangkutan sampah. Jaringan jalan awal masih berupa jaringan jalan yang lengkap/kompleks, di mana jaringan belum diberikan batasan jalan mana saja yang boleh dilalui maupun yang tidak, dan belum terdapat titik TPS dari hasil pengambilan data ke Dinas Kebersihan dan Pertamanan Kota Semarang. Supaya lebih mudah dalam membuat jaringan, Google Maps digunakan untuk membantu membuat jaringan awal. Jaringan jalan awal yang mungkin dilewati oleh truk sampah memiliki node sebanyak 67 titik yang terdiri atas 66 titik persimpangan jalan dan 1 titik TPS, digambarkan pada lampiran 1.
38
39
Mulai
Peta jaringan awal pengangkutan sampah
Pengambilan Data
Lokasi TPS Lokasi TPA SOP rute perjalanan truk sampah Peta Kota Semarang
Pemodelan jaringan dan penyelesaian matematis
Pengembangan sistem
Pengujian sistem Tidak
Apakah berhasil?
Ya
Selesai
Gambar 3.1 Bagan alur metode penelitian
3.2
Pengambilan Data Metode pengumpulan data yang diterapkan dalam memperoleh data yang
dibutuhkan yaitu metode pengumpulan data dengan cara mengambil data sekunder yang diperoleh dari Dinas Kebersihan dan Pertamanan Kota Semarang.
40
Pengambilan data di Dinas Kebersihan dan Pertamanan Kota Semarang dilaksanakan mulai tanggal 12 Februari hingga 12 Mei 2015. Data yang diambil yaitu berupa Standar Operasional Prosedur (SOP) rute truk pengangkut sampah di Kota Semarang dari TPS menuju TPA, lokasi TPS di setiap kecamatan dan lokasi TPA yang menjadi titik akhir dari pengangkutan sampah di Kota Semarang. Lokasi TPS, TPA, serta persimpangan jalan nantinya akan dijadikan sebagai node-node dalam jaringan jalur pengangkutan sampah. Dalam SOP Dinas Kebersihan dan Pertamanan Kota Semarang juga memuat tentang ruas jalan yang bisa dilewati oleh truk-truk sampah, karena tidak semua jalan diperkenankan dilewati oleh truk sampah. Berdasarkan wawancara langsung dengan Kepala Seksi Bidang Pengelolaan dan Pengangkutan Sampah, Bapak Siswanto, jalan-jalan yang terdapat banyak gedung pemerintahan dan pendidikan lebih baik untuk dihindari karena akan sangat mengganggu pengguna jalan terutama oleh bau menyengat yang dihasilkan oleh sampah, mengingat jalan-jalan itu akan sangat ramai setiap harinya. Ruas jalan yang dihindari adalah jalan Pandanaran, jalan Pemuda, dan jalan Pahlawan. Untuk menentukan jarak setiap titik jaringan, digunakan bantuan Google Maps sehingga mempermudah dalam penentuan jarak antar titik manapun.
3.3
Pemodelan Jaringan dan Penyelesaian Model Matematis Setelah didapatkan data berupa lokasi TPS, TPA, serta persimpangan jalan
yang mungkin bisa dilalui oleh truk sampah, langkah selanjutnya adalah memodelkan data yang didapat menjadi suatu jaringan. Jaringan yang dibuat
41
sesuai dengan kondisi yang sebenarnya di lapangan, yaitu memperhatikan ruas jalan yang mungkin dilalui oleh truk sampah serta ruas jalan dua arah atau satu arah. Jaringan yang telah terbentuk kemudian di translasikan ke suatu model matematis sehingga akan mudah dalam proses perhitungannya. Titik-titik (node) TPS, TPA, dan persimpangan jalan disimbolkan dengan v1, v2, v3, ..., vn , dan jalan-jalan (path) yang menghubungkan node-node disimbolkan dengan e1, e2, e3, ..., en dengan bobotnya berupa panjang jalan yang menghubungkan 2 titik. Dari model jaringan yang telah terbentuk, dibuat suatu matriks awal W0 yang nantinya akan dioperasikan dalam perhitungan pencarian jalur terpendek menggunakan algoritma Floyd-Warshall. W* adalah matriks keterhubungan minimal dengan Wij = lintasan terpendek dari titik vi ke vj, sedangkan k merupakan jumlah iterasi proses sejumlah n-matriks. Algoritma Floyd-Warshall untuk mencari lintasan terpendek telah dijelaskan pada bab 2.
3.4
Pengembangan Sistem Pengembangan sistem untuk menghitung rute terpendek yang digunakan
dalam penelitian ini melalui beberapa tahapan, yaitu arsitektur sistem, desain sistem, serta proses pengkodean sistem. 3.4.1 Arsitektur Sistem Sistem yang digunakan untuk menghitung rute terpendek pengangkutan sampah dari TPS menuju ke TPA yang dikembangkan dalam penelitian ini memiliki arsitektur seperti yang ditunjukkan pada gambar 3.2. Tahap
42
penghitungan dimulai dari pembentukan matriks W0 jaringan pengangkutan sampah hasil inputan graf oleh admin, yang merupakan matriks awal jaringan. Setelah terbentuk matriks W0, akan dibentuk matriks Z(0) yang digunakan sebagai matriks pembantu untuk menentukan path terpendek dari graf yang dicari jarak terpendeknya. Tahap selanjutnya setelah terbentuk matriks W0 dan Z(0) adalah melakukan perhitungan dengan algoritma Floyd-Warshall untuk mencari bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik. Penghitungan dilakukan sampai dengan iterasi ke-k, dengan k merupakan banyaknya titik yang membentuk graf.
Server Database
Input data graf
Optimum Routes Application
Qu
er y
Admin
Request
Save
Matriks Processing W0 and Z0
Floyd-Warshall processing
Optimum matriks
Gambar 3.2 Arsiterktur sistem penghitung jalur terpendek pengangkutan sampah
43
3.4.2
Desain Sistem 1. Alur Proses Pengembangan Sistem Penjabaran lebih jelas untuk rancangan alur pencarian jalur terpendek pengangkutan sampah dari TPS menuju ke TPA di Kota Semarang ditunjukkan pada gambar 3.3.
44
Mulai
Input path
Matriks Processing (Wi,j)
Melakukan perhitungan pada iterasi K ke-n
Lakukan Perhitungan pada tiap W[i,j] hingga sel ke-n
Hitung Apakah W[i,j]>W[i,k]+W[k,j] ? Y
Tidak
Ya
Pilih W[i,k]+W[k,j]
Simpan jarak yang terpilih
Tidak
Apakah i = n, j = n, dan k = n?
Ya Selesai
Gambar 3.3 Alur proses pengembangan sistem (Kriswanto,dkk. 2014:213)
Pilih W[i,j]
45
2. Perancangan Antarmuka Desain antarmuka pencarian rute terpendek pengangkutan sampah di kota Semarang dapat dilihat pada gambar 3.4, 3.5, dan 3.6. Gambar 3.4 merupakan
tampilan
halaman
utama,
gambar
3.5
antarmuka
menampilkan pilihan rute berdasar kecamatan, sedangkan gambar 3.6 merupakan antarmuka menampilkan jalur pengangkutan sampah
header menu sistem
isi konten
footer
Gambar 3.4 Tampilan halaman utama
header menu sistem - pilih kecamatan tampil
isi konten
footer
Gambar 3.5 Antarmuka menampilkan pilihan rute berdasar kecamatan
46
header menu sistem
animasi peta jalur pengangkutan sampah
- titik awal -
- titik tujuan -
tampil
footer
Gambar 3.6 Antarmuka menampilkan jalur pengangkutan sampah
3.4.3 Pengkodean Sistem Dalam pengkodean untuk membuat sistem, digunakan bahasa pemrograman PHP dan MySQL. Berikut gambaran fungsi-fungsi utama dalam proses perhitungan pencarian jalur terpendek pengangkutan sampah, yaitu: 1. Matriks Processing Matriks Processing adalah proses pemecahan data path hasil inputan menjadi matriks. Matriks itu yang nantinya akan diproses untuk mencari jalur terpendek pengangkutan sampah di kota Semarang. Pseudocode untuk matriks processing adalah sebagai berikut: Matriks Processing for i = 0 to iterasi-N explode isi titik with | count isi titik for j = 0 to iterasi-N save isi titik[i][j] isi titik[i][j] = matriks[i][j]
47
for i=0 to iterasi-N for j=0 to iterasi-N matriks[i][j] if (i=j) matriks[i][j] = 0 else matriks[i][j] = INF
2. Operasi matriks dengan algoritma Floyd-Warshall Pada tahap ini, matriks yang telah terbentuk akan dihitung menggunakan algoritma Floyd-Warshall untuk mendapatkan nilai jarak terpendek antara semua titik yang membentuk graf. Pseudocode untuk operasi algoritma Floyd-Warshall adalah sebagai berikut: Floyd-Warshall Operation for i = 1 to N for j = 1 to N if there is an edge from i to j W[0][i][j] = the lenght of the edge from i to j Z[0][i][j] = j else W[0][i][j] = INFINITY Z[0][i][j] = 0 for k 1 to N for i = 1 to N for j = 1 to N if(W[i][j] > W[i][k] + W[k][j]) W[i][j] = W[i][k] + W[k][j] Z[i][j] = Z[i][k] + Z[k][j] else W[i][j] = W[0][i][j] Z[i][j] = Z[0][i][j] end if
48
3. Operasi pencarian rute terpendek antar titik Merupakan fungsi yang digunakan untuk menentukan path yang menghasilkan jarak terpendek antara setiap titik. Berikut ini pseudo code untuk operasi pencarian rute terpendek antar titik. Shortest Path Floyd-Warshall Algorithm path i,j { input i input j if(walk[i,j] = j) { output(i,j); } else { path(i, walk[i,j]); path(walk[i,j],j); } }
3.5
Perancangan Pengujian Pada subbab ini akan dilakukan perancangan uji coba dari sistem pencarian
jalur terpendek pengangkutan sampah, baik pengujian terhadap sistem maupun evaluasi hasil operasi penghitungan matriks dengan algoritma Floyd-Warshall. Hasil perhitungan akan dievaluasi dengan membandingkan hasil perhitungan secara manual untuk beberapa titik graf. 3.5.1
Bahan Pengujian Bahan yang akan digunakan pada proses pengujian ini adalah matriks graf
hubungan antar TPS-TPS dan TPA di kecamatan Semarang Tengah yang telah
49
dirancang sesuai dengan SOP pengangkutan sampah yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang. Selanjutnya, hasil rute terpendek yang hasilkan oleh sistem juga akan menjadi bahan pengujian pada penelitian ini. 3.5.2 Tujuan Pengujian Beberapa hal yang menjadi tujuan dari pelaksanaan pengujian terhadap sistem pencarian jalur terpendek pengangkutan sampah, yaitu : 1. Memeriksa apakah hasil matriks yang dihasilkan oleh perhitungan sistem mengalami kesalahan atau tidak. 2. Mengevaluasi hasil pencarian jalur terpendek yang dihasilkan, apakah sesuai dengan SOP atau tidak. 3.5.3 Skenario dan Kriteria Pengujian Pengujian yang dilaksanakan pada penelitian ini dibagi atas 2 bagian, yaitu pengujian hasil perhitungan sistem dan evaluasi hasil jalur terpendek yang dihasilkan oleh sistem. 1. Pengujian hasil perhitungan sistem Sesuai dengan tujuan pengujian pertama, maka pengujian bagian pertama ini berfungsi untuk memeriksa hasil perhitungan matriks oleh perangkat lunak. Melakukan pengujian untuk mengetahui apakah hasil yang dihasilkan sesuai dengan perhitungan secara manual. Pengujian dilakukan dengan cara memasukkan data jaringan yang lebih sederhana, yang telah dilakukan penghitungan secara manual sebelumnya. Setelah
50
itu dibandingkan hasil akhir antara keduanya, yaitu matriks hasil perhitungan sistem dan matriks yang dihasilkan dari perhitungan manual. 2. Evaluasi hasil jalur terpendek yang dihasilkan Evaluasi hasil pencarian jalur terpendek pada sistem dapat dilakukan dengan melakukan evaluasi terhadap matriks hasil perhitungan terlebih dahulu. Jika telah dilakukan evaluasi hasil matriks perhitungannya dan hasilnya sesuai, maka pengujian yang dilakukan selanjutnya adalah mencari path terpendek antara titik awal dan titik tujuan. Hasil pencarian jalur terpendek yang dihasilkan oleh sistem akan dibandingkan dengan jalur yang selama ini digunakan oleh Dinas Kebersihan dan Pertamanan sesuai dengan Standar Operasional Prosedur (SOP) pengangkutan sampah. Dari jalur yang dihasilkan oleh perhitungan sistem, diharapkan jalur yang dihasilkan merupakan jalur yang lebih optimum dari sisi jarak dibandingkan dengan jalur yang selama ini digunakan oleh Dinas Kebersihan dan Pertamanan Kota Semarang. Sebagai sampel, graf yang akan dibuat adalah graf TPS-TPS di kecamatan Semarang Tengah sejumlah 20 TPS dan 1 TPA yang terletak di Kelurahan Kedungpane, Kecamatan Mijen, Kota Semarang. Selain TPS dan TPA, yang akan menjadi titik graf adalah persimpangan jalan yang mungkin dilewati oleh armada sesuai dengan SOP Dinas Kebersihan dan Pertamanan Kota Semarang.
51
BAB IV HASIL DAN PEMBAHASAN
Pada bab ini berisi tentang hasil dan pembahasan penelitian yang telah dilakukan, yaitu pemetaan awal jaringan, hasil perhitungan matriks, analisis jalur yang diperoleh dan pembahasan.
4.1
Hasil Penelitian
4.1.1 Pemetaan Awal Jaringan Penelitian ini bertujuan mencari lintasan terpendek jaringan pengangkutan sampah dari Tempat Pembuangan Sementara (TPS) Kecamatan Semarang Tengah menuju ke Tempat Pembuangan Akhir (TPA) Jatibarang yang terletak di Kelurahan Kedungpane, Kecamatan Mijen, Kota Semarang. Untuk mencari jalur terpendek, algoritma Floyd-Warshall dimanfaatkan sebagai metode pencarian jalur karena mudah dalam hal penerapannya. Data lokasi penyebaran TPS di Kecamatan Semarang Tengah diperoleh dari Dinas Kebersihan dan Pertamanan (DKP) Kota Semarang dan data jaringan jalan google maps. Kemudian data tersebut disusun dalam bentuk gambar jaringan graf yang menggambarkan titiktitik TPS, TPA dan persimpangan jalan yang kemungkinan dapat dilewati truk pengangkut sampah. Berdasarkan data gambar jaringan graf dan SOP pengangkutan sampah yang telah ditetapkan DKP maka dapat dipilih jalur yang kemungkinan dapat dilalui oleh truk pengangkut sampah. Hal itu dikarenakan pada SOP terdapat beberapa
52
jalur yang tidak boleh dilalui oleh truk pengangkut sampah
seperti
Pemuda, jalan Pandanaran dan jalan Pahlawan. Sistem yang dibuat
jalan dalam
penelitian ini diharapkan dapat mempermudah dalam pencarian lintasan terpendek pengangkutan sampah. Sistem ini akan melibatkan titik dan garis atau sisi dalam jumlah yang sangat banyak. Hasil data graf pengangkutan sampah Kecamatan Semarang Tengah yang telah dibuat dapat dilihat pada tabel 4.1 dan 4.2, sedangkan gambar jaringan pengangkutan sampah hasil olahan data terdapat pada gambar 4.1. Tabel 4.1 Data titik/node jaringan pengangkutan sampah Semarang Tengah No
Simbol
Jenis
Lokasi Titik / Node
1
v1
TPA
2
v2
Simpang
Abdurrahman Saleh - Untung Suropati
3
v3
Simpang
Bundaran Kalibanteng
4
v4
Simpang
Pamularsih - W.R Supratman
5
v5
Simpang
W.R Supratman - Simongan
6
v6
Simpang
Pertigaan Sampokong
7
v7
Simpang
Lampu merah Kaligarang
8
v8
Simpang
Lampu merah RSUP Kariadi
9
v9
Simpang
Dr. Sutomo - Bendungan
10
v10
Simpang
Bendungan - Kyai Saleh
11
v11
Simpang
Bundaran Indraprasta
12
v12
Simpang
Indraprasta - Bima Raya
13
v13
TPS
Jl. Bima, Pindrikan Kidul
14
v14
Simpang
Nakulo Raya - Imam Bonjol
15
v15
Simpang
Bundaran Tugu Muda
16
v16
TPS
17
v17
Simpang
18
v18
TPS
19
v19
Simpang
20
v20
TPS
Abimanyu, Pindrikan Lor
21
v21
TPS
Abimanyu 2, Pindrikan Lor
22
v22
Simpang
TPA Jatibarang
Belakang Lawang Sewu, Sekayu Satria Utara - Batan Selatan R.M Nusantara, Pekunden Indraprasta - Abimanyu
Abimanyu - Imam Bonjol
53
No
Simbol
Jenis
Lokasi Titik / Node
23
v23
Simpang
Imam Bonjol - Tanjung
24
v24
Simpang
Kapt. Pierre Tendean - Depok
25
v25
TPS
Jl. Depok, Kembangsari
26
v26
Simpang
M.H Tamrin - Inspeksi
27
v27
TPS
Jl. M.H Tamrin, Miroto
28
v28
Simpang
Batan Selatan - D.I Panjaitan
29
v29
Simpang
Imam Bonjol - Gendingan
30
v30
Simpang
Gendingan - Depok
31
v31
Simpang
Inspeksi - Wotgandul Barat
32
v32
Simpang
Gajah Mada - Karanganyar
33
v33
TPS
Jl. Gajah Mada, Miroto
34
v34
TPS
Daerah kecamatan Semarang Tengah
35
v35
Simpang
Mayjen Sutoyo - Anggrek
36
v36
Simpang
Kyai Agus Salim -Kauman
37
v37
TPS
Sumeneban, Kauman
38
v38
Simpang
Depok - Gg. Warung
39
v39
Simpang
Plampitan - Wotgandul Barat
40
v40
TPS
41
v41
Simpang
42
v42
TPS
43
v43
Simpang
Mangunsarkoro - Wotgandul Barat
44
v44
Simpang
Kyai Agus Salim - M.T. Haryono
45
v45
Simpang
M.T. Haryono - Petudungan
46
v46
Simpang
Mangunsarkoro - Jagalan
47
v47
Simpang
Mangunsarkoro - Karangsaru
48
v48
Simpang
Mangunsarkoro - Pringgading
49
v49
Simpang
Mangunsarkoro - Mayjen Sutoyo
50
v50
TPS
51
v51
Simpang
52
v52
TPS
Citraland, Pekunden
53
v53
TPS
Matahari Simpang 5, Pekunden
54
v54
Simpang
Seroja - Jenderal Ahmad yani
55
v55
Simpang
Mangunsarkoro - Stadion Selatan
56
v56
Simpang
M.T. Haryono - Jenderal Ahmad Yani
57
v57
Simpang
M.T. Haryono - Stadion Selatan
58
v58
Simpang
M.T. Haryono - Mayjen Sutoyo
59
v59
Simpang
M.T. Haryono - Pringgading
60
v60
Simpang
M.T. Haryono - Karangsaru
Matahati Johar, Kauman Kyai Agus Salim - Gg. Lombok Petudungan, Jagalan
RS. Tlogorejo, Pekunden K.H Ahmad Dahlan - Anggrek
54
No
Simbol
Jenis
Lokasi Titik / Node
61
v61
Simpang
M.T. Haryono - Jagalan
62
v62
TPS
Jl. Karangsaru, Gabahan
63
v63
TPS
Jl. Karangsaru, Brumbungan
64
v64
TPS
Jl. Karangsaru, Jagalan
65
v65
TPS
Kalikuping, Jagalan
66
v66
TPS
Stadion Diponegoro, Karangkidul
67
v67
Simpang
M.T. Haryono - Singosari
68
v68
Simpang
Atmodirono – Singosari
69
v69
Simpang
Singosari – Sriwijaya
70
v70
Simpang
Kyai Saleh – Veteran
Tabel 4.2 Data Path jaringan pengangkutan sampah Semarang Tengah No
Path
Nama Jalan
Panjang Jalan (m)
1
v1 - v2
Jl. Untung Suropati
6.300
2
v2 - v3
Jl. Abdul Rahman Saleh
3.600
3
v2 - v5
Jl. Untung Suropati
1.900
4
v3 - v4
Jl. Pamularsih
5
v4 - v5
Jl. W.R. Supratman
2.200
6
v4 - v6
Jl. Pamularsih
1.700
7
v5 - v6
Jl. Simongan
1.500
8
v6 - v7
Jl. Kaligarang
350
9
v7 - v8
Jl. Kaligarang
550
10
v7 - v11
Jl. Basudewa
11
v8 - v9
Jl. Dr. Sutomo
300
12
v8 - v10
Jl. Dr. Kariadi
990
13
v9 - v10
Jl. Bendungan
1.000
14
v3- v11
Jl. Jenderal Sudirman
2.100
15
v9 - v15
Jl. Dr. Sutomo
900
16
v11 - v15
Jl. Siliwangi
850
17
v15 - v16
Jl. Satria Utara
100
18
v16 - v17
Jl. Satria Utara
350
19
v17 - v18
Jl. Pandanaran - Jl. Kyai Saleh
250
20
v18 - v10
Jl. Kyai Saleh
700
21
v11 - v12
Jl. Indraprasta
700
22
v12 - v13
Jl. Bima Taya
230
23
v13 - v14
Jl. Nakulo Raya
450
24
v15 - v14
Jl. Imam Bonjol
100
300
1.600
55
No
Path
Nama Jalan
Panjang Jalan (m)
25
v14 - v20
Jl. Imam Bonjol
450
26
v12 - v19
Jl. Indraprasta
450
27
v19 - v20
Jl. Indraprasta
100
28
v21 - v19
Jl. Abimanyu 1
300
29
v21 - v22
Jl. Abimanyu 1
160
30
v20 - v22
Jl. Imam Bonjol
350
31
v22 - v23
Jl. Imam Bonjol
350
32
v20 - v24
Jl. Kapt. Pierre Tendean
600
33
v17 - v26
Jl. Inspeksi
500
34
v17 - v28
Jl. Batan Selatan
400
35
v23 - v24
Jl. Tanjung
450
36
v24 - v26
Jl. M.H. Thamrin
500
37
v26 - v27
Jl. Inspeksi
100
38
v26 - v28
Jl. M.H. Thamrin
400
39
v23 - v29
Jl. Imam Bonjol
300
40
v27 - v31
Jl. Inspeksi
400
41
v28 - v33
Jl. D.I. Panjaitan
500
42
v29 - v30
Jl. Gendingan
500
43
v30 - v31
Jl. Gajah Mada
450
44
v31- v32
Jl. Gajah Mada
280
45
v32 - v34
Jl. Karanganyar
100
46
v32 - v33
Jl. Gajah Mada
350
47
v33 - v35
Jl. Mayjen Sutoyo
48
v29 - v36
Jl. Imam Bonjol
450
49
v30 - v38
Jl. Depok
250
50
v31 - v39
Jl. Wotgandul Barat
350
51
v36 - v40
Jl. K.H. Agus Salim
350
52
v40 - v41
Jl. K.H. Agus Salim
75
53
v36 - v37
Jl. Kauman
150
54
v37 - v38
Jl. Kauman
550
55
v38 - v39
Jl. Plampitan
350
56
v38 - v42
Jl. Gg. Warung
900
57
v39 - v43
Jl. Wotgandul Barat
700
58
v41 - v44
Jl. K.H. Agus Salim
600
59
v42 - v45
Jl. Petudungan
300
60
v41 - v42
Jl. Gg. Lombok
550
61
v42 - v43
Jl. Mangunsarkoro
230
62
v45 - v44
Jl. M.T. Haryono
500
50
56
No
Path
Nama Jalan
Panjang Jalan (m)
63
v34 - v47
Jl. Karanganyar
800
64
v35 - v49
Jl. Mayjen Sutoyo
700
65
v35 - v52
Jl. Anggrek
280
66
v52 - v51
Jl. Anggrek
500
67
v51 - v53
Jl. K.H. Ahmad Dahlan
200
68
v51 - v50
Jl. K.H. Ahmad Dahlan
300
69
v50 - v49
Jl. K.H. Ahmad Dahlan
150
70
v53 - v54
Jl. Seroja Selatan
750
71
v54 - v55
Jl. Mangunsarkoro
300
72
v55 - v49
Jl. Mangunsarkoro
500
73
v49 - v48
Jl. Mangunsarkoro
250
74
v48 - v47
Jl. Mangunsarkoro
300
75
v47 - v46
Jl. Mangunsarkoro
200
76
v46 - v43
Jl. Mangunsarkoro
270
77
v56 - v57
Jl. M.T. Haryono
650
78
v57 - v58
Jl. M.T. Haryono
650
79
v58 - v59
Jl. M.T. Haryono
250
80
v59 - v60
Jl. M.T. Haryono
300
81
v60 - v61
Jl. M.T. Haryono
300
82
v61 - v45
Jl. M.T. Haryono
500
83
v46 - v62
Jl. Jagalan
125
84
v62 - v61
Jl. Jagalan
125
85
v47 - v63
Jl. Karangsaru
100
86
v63 - v64
Jl. Karangsaru
100
87
v64 - v60
Jl. Karangsaru
100
88
v48 - v65
Jl. Pringgading
150
89
v65 - v59
Jl. Pringgading
150
90
v55 - v66
Jl. Stadion Timur
200
91
v57 - v66
Jl. Stadion Timur
150
92
v25 - v24
Jl. Depok
200
93
v30 - v25
Jl. Depok
300
94
v57 - v56
Jl. M.T. Haryono
650
95
v2 – v5
96
v56 – v67
Jl. M.T. Haryono
97
v56 – v68
Jl. Atmodirono
98
v67- v68
Jl. Singosari Raya
99
v67 – v69
Jl. Sriwijaya
100
v68 – v69
Jl. Singosari Raya
Jl. Simongan
1.900 750 1.000 600 1.500 500
57
No
Path
Nama Jalan
Panjang Jalan (m)
101
v69 – v70
Jl. Veteran
1.300
102
v70 – v8
Jl. Veteran
990
103
v70 – v10
Jl. Kyai Saleh
220
Data pada tabel 4.1 merupakan data titik/node yang membentuk jaringan pengangkutan sampah di Kecamatan Semarang Tengah. Node-node itu terdiri dari lokasi TPA, TPS, serta persimpangan jalan yang dimungkinkan dilewati oleh armada truk pengangkut sampah. Berdasarkan tabel 4.1 dapat diketahui bahwa node yang membentuk jaringan pengangkutan sampah di Kecamatan Semarang Tengah berjumlah 70 titik/node, yang terdiri atas 1 TPA, 20 TPS dan 49 persimpangan jalan. Berbeda dengan jaringan jalan yang dibuat sebelum disesuaikan dengan SOP yang terdiri atas 66 persimpangan jalan, karena pada SOP pengangkutan sampah ada beberapa jalan yang tidak boleh dilalui oleh truk pengangkut sampah. Titik-titik yang ada kemudian saling dihubungkan sesuai dengan jalan yang memungkinkan untuk dilalui oleh armada pengangkut sampah. Pada tabel 4.2 diketahui bahwa ada 103 path yang terbentuk, yang akan menjadi suatu jaringan pengangkutan sampah di Kecamatan Semarang Tengah. Untuk jaringan pengangkutan sampah Kecamatan Semarang Tengah secara lengkap digambarkan pada gambar 4.1. Pada gambar tersebut, terdapat titik yang disimbolkan lingkaran dengan 3 warna yang berbeda. Lingkaran yang berwarna merah adalah TPA Jatibarang, lingkaran biru adalah persimpangan jalan, sedangkan lingkaran hijau adalah TPS-TPS di kecamatan Semarang Tengah.
58
Dari data yang didapat dari tabel 4.1 dan tabel 4.2, dan ditunjang visualisasi jaringan pada gambar 4.1 maka didapat matriks Wi,j dan matriks Zi,j awal yang dapat dilihat secara lengkap pada lampiran 2 dan 3. Matriks Wi,j merupakan matriks yang berguna untuk mencari jarak terpendek setiap pasangan titik, sedangkan matriks Zi,j berguna untuk mencari path terpendek antar titik.
Gambar 4.1 Jaringan pengangkutan sampah Kecamatan Semarang Tengah
59
60
4.1.2 Proses Perhitungan Algoritma Floyd-Warshall Berdasarkan tabel lampiran 2 dan lampiran 3 matriks Wi,j dan Zi,j awal, kemudian dilakukan proses perhitungan dengan algoritma Floyd-Warshall untuk mencari jalur terpendek antar semua titik dalam jaringan tersebut. Berikut proses optimalisasi matriks jaringan pengangkutan sampah Kecamatan Semarang Tengah dengan melakukan perhitungan untuk matriks 5x5 potongan dari tabel lampiran 2 dan 3 hingga iterasi ke-5 : Iterasi untuk k = 1 Untuk setiap sel matriks W dicek apakah W[i,j] > W[i,k] + W[k,j]. Jika ya, maka W[i,j] diganti dengan W[i,k] + W[k,j] dan Z[i,j] diganti dengan Z[i,k] + Z[k,j]. i = 1, j = 1 W1,1 = 0, sedangkan W1,1 + W1,1 = 0+0 = 0 , maka W*i,j = 0, Z*i,j = 0 i = 1, j = 2 W1,2 = 6300, sedangkan W1,1 + W1,2 = 0 + 6300 = 6300 , maka W*i,j = 6300, Z*i,=2 i = 1, j = 3 W1,3 = ∞, sedangkan W1,1 + W1,3 = 0 + ∞ = ∞ , maka W*i,j = ∞, Z*i,j = 0 i = 1, j = 4 W1,4 = ∞, sedangkan W1,1 + W1,4 = 0 + ∞ = ∞ , maka W*i,j = ∞, Z*i,j = 0 i = 1, j = 5 W1,5 = ∞, sedangkan W1,1 + W1,5 = 0 + ∞ = ∞ , maka W*i,j = ∞, Z*i,j = 0 i=2,j=1 W2,1 = 6300, sedangkan W2,1 + W1,1 = 6300 + 0 = 6300 , maka W*i,j = 6300, Z*i,j=1 i=2,j=2 W2,2 = 0, sedangkan W2,1 + W1,2 = 6300 + 6300 = 12600 , maka W*i,j = 0, Z*i,j = 0 i=2,j=3 W2,3 = 3600, sedangkan W2,1 + W1,3 = 6300 + ∞ = ∞ , maka W*i,j = 3600, Z*i,j = 3
61
i=2,j=4 W2,4 = ∞, sedangkan W2,1 + W1,4 = 6300 + ∞ = ∞ , maka W*i,j = ∞ dan Z*i,j = 0 i=2,j=5 W2,5 = 1900, sedangkan W2,1 + W1,5 = 6300 + ∞ = ∞ , maka W*i,j = 1900, Z*i,j = 5 i=3,j=1 W3,1 = ∞, sedangkan W3,1 + W1,1 = ∞ + 0 = ∞ , maka W*i,j = ∞, Z*i,j = 0 i=3,j=2 W3,2 =3600, sedangkan W3,1 + W1,2 = ∞ + 3600 = ∞ , maka W*i,j = 3600, Z*i,j = 2 i=3,j=3 W3,3 = 0, sedangkan W3,1 + W1,3 = ∞ + ∞ = ∞ , maka W*i,j = 0, Z*i,j = 0 i=3,j=4 W3,3 = 300, sedangkan W3,1 + W1,4 = ∞ + ∞ = ∞ , maka W*i,j = 300, Z*i,j = 4 i=3,j=5 W3,5 = ∞, sedangkan W3,1 + W1,5 = ∞ + ∞ = ∞ , maka W*i,j = ∞, Z*i,j = 0 i=4,j=1 W4,1 = ∞, sedangkan W4,1 + W1,1 = ∞ + 0 = ∞ , maka W*i,j = ∞, Z*i,j = 0 i=4,j=2 W4,2 = ∞, sedangkan W4,1 + W1,2 = ∞ + 6300 = ∞ , maka W*i,j = ∞, Z*i,j = 0 i=4,j=3 W4,3 = 300, sedangkan W4,1 + W1,3 = ∞ + ∞ = ∞ , maka W*i,j = 300, Z*i,j = 3 i=4,j=4 W4,4 = 0, sedangkan W4,1 + W1,4 = ∞ + ∞ = ∞ , maka W*i,j = 0, Z*i,j = 0 i=4,j=5 W4,5 = 2200, sedangkan W4,1 + W1,5 = ∞ + ∞ = ∞ , maka W*i,j = 2200, Z*i,j = 5 i=5,j=1 W5,1 = ∞, sedangkan W5,1 + W1,1 = ∞ + 0 = ∞ , maka W*i,j = ∞, Z*i,j = 0 i=5,j=2 W5,2 = 1900, sedangkan W5,1 + W1,2 = ∞ + 6300 = ∞ , maka W*i,j = 1900, Z*i,j = 2 i=5,j=3 W5,3 = ∞, sedangkan W5,1 + W1,3 = ∞ + ∞ = ∞ , maka W*i,j = ∞, Z*i,j = 0 i=5,j=4
62
W5,4 = 2200, sedangkan W5,1 + W1,4 = ∞ + ∞ = ∞ , maka W*i,j = 2200, Z*i,j = 4 i=5,j=5 W5,5 = 0, sedangkan W5,1 + W1,5 = ∞ + ∞ = ∞ , maka W*i,j = 0, Z*i,j = 0 Dari iterasi 1, maka didapatkan matriks sebagai berikut : v1
v2
v3
v4
v1 v2 v3 v4 v5
v5
6 6
6
W1 =
Z(1) =
6 [
]
[
]
Iterasi untuk k = 2 Iterasi untuk k=2 dilakukan dengan cara yang sama seperti iterasi untuk k = 1, hanya titik perantaranya adalah titik v2. Proses yang sama dilakukan untuk semua harga i dan j, maka didapatkan matriks : v1
v2
v3
6
6
W2 =
v4
v1 v2 v3 v4 v5
v5
6
Z(2) =
6 [
]
[
]
Dari matriks di atas ditunjukkan adanya perubahan nilai, yaitu pada titik W 1,3, W1,5, W3,5, W3,1, W5,1, dan W5,3. Hal ini berarti bahwa adanya titik yang menghubungkan antara titik-titik tersebut, yaitu titik v2. Misalkan untuk melakukan perjalanan dari v1 menuju v5, melewati titik v2 terlebih dahulu, dan sebaliknya. Iterasi untuk k = 3 v1 6
W3 =
v2 6
v3
v4
v1 v2 v3 v4 v5
v5
6
Z(3) =
6 [
]
[
]
Iterasi untuk k = 4 v1
v2
v3
v4
v1 v2 v3 v4 v5
v5
Z(4) = [
]
63
6
6
W4 =
6 6
[
]
Iterasi untuk k = 5 v1 6
W5 =
v2 6
v3
v4
v1 v2 v3 v4 v5
v5
6
Z(5) =
6 [
]
[
]
Pada matriks iterasi ke-3 semua nilai matriks telah terisi, hal ini menunjukkan bahwa semua titik telah terhubung. Sehingga telah diketahui jarak yang menghubungkan setiap titik pada jaringan, beserta pathnya yang ditunjukkan oleh matriks Zij. Namun jarak yang diketahui pada perhitungan awal, atau sebelum dilakukan perhitungan hingga iterasi terakhir belum tentu merupakan jarak terpendeknya. Sebagai contohnya adalah jarak dari titik v3 menuju ke titik v5, sebelumnya pada iterasi ke-3 telah diketahui jarak antara kedua titik tersebut, yaitu 5.500 m dengan path lintasan v3 → v2 → v5. Namun pada iterasi ke-4, terdapat perubahan data jarak dari titik v3 menuju ke titik v5, yaitu menjadi 2.500 m. Hal ini terjadi karena ditemukan path yang lebih pendek dari titik v3 menuju v5, yaitu melalui lintasan v3 → v4 → v5. Sehingga untuk dapat mengetahui hubungan antar titik secara menyeluruh, harus dilakukan langkah perhitungan yang sama hingga
k = 70, i = 70, dan j = 70.
Setelah perhitungan dilakukan hingga iterasi terakhir, yaitu saat k = 70, i = 70, dan j = 70, maka didapatkan matriks W* atau matriks akhir hasil proses perhitungan algoritma Floyd-Warshall yang menunjukkan jalur terpendek antar
64
setiap titik dan matriks Z*. Secara lengkap, untuk tabel matriks W* dapat dilihat pada lampiran 4 dan tabel matriks Z* pada lampiran 5. Berdasarkan hasil perhitungan matriks jaringan pada lampiran 4 dan 5, maka kita dapat mengetahui jalur terpendek yang dapat ditempuh dari tiap TPS di Kecamatan Semarang Tengah menuju ke TPA Jatibarang. Rute perjalanan pengangkutan sampah dari TPS menuju TPA Jatibarang berdasarkan hasil perhitungan algoritma Floyd-Warshall ditunjukkan pada tabel 4.3, sedangkan rute perjalanan yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang sesuai dengan SOP pengangkutan sampah ditunjukkan pada tabel 4.4. Tabel 4.3 Rute perjalanan pengangkutan sampah TPS Kecamatan Semarang Tengah menuju TPA berdasarkan perhitungan algoritma Floyd-Warshall
No.
Titik Awal
Rute Perjalanan
Panjang Lintasan (m)
13.600
1
TPS Wilayah Kecamatan
Jl. Karanganyar → Jl. Gajah Mada → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
2
TPS Belakang Lawang Sewu
TPS → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
11.900
3
TPS Pringgading
TPS → Jl. Pringgading → Jl. Mangunsarkoro → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.300
4
TPS Bima Pindrikan Kidul
TPS → Jl. Nakulo Raya → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.350
65
No.
Titik Awal
Rute Perjalanan
Panjang Lintasan (m)
TPS RM Nusantara
TPS → Jl. Kyai Saleh → Jl. Dr. Kariadi → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.290
TPS Abimanyu 1
TPS → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.350
TPS Abimanyu 2
TPS → Jl. Abimanyu 1 → Jl. Indraprasta → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.750
8
TPS Jl. Depok Kembangsari
TPS → Jl. Depok → Jl. Kapt. Pierre Tendean → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
13.150
9
TPS M.H Thamrin - Miroto
TPS → Jl. Inspeksi → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.850
10
TPS Gajah Mada - Miroto
TPS → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
13.150
11
TPS → Jl. Kauman → Jl. Depok → Jl. Kapt. TPS Sumeneban - Pierre Tendean → Jl. Imam Bonjol → Jl. Dr. Kauman Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.250
5
6
7
12
13
TPS Matahari Johar - Kauman
TPS → Jl. K.H. Agus Salim → Jl. Kauman → Jl. Depok → Jl. Kapt. Pierre Tendean → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.750
TPS Petudungan - Jagalan
TPS → Jl. Mangunsarkoro → Jl. Wotgandul Barat → Jl. Inspeksi → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.530
66
No.
Titik Awal
14
TPS RS. Tlogorejo Pekunden
15
TPS Citraland Pekunden
16
TPS Matahari Simpang 5
17
18
19
20
Rute Perjalanan TPS → Jl. K.H. Ahmad Dahlan → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang TPS → Jl. Anggrek → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang TPS → Jl. K.H. Ahmad Dahlan → Jl. Anggrek → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
Panjang Lintasan (m)
14.050
13.480
14.180
TPS Karangsaru Gabahan
TPS → Jl. Jagalan → Jl. Mangunsarkoro → Jl. Wotgandul Barat → Jl. Inspeksi → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.695
TPS Karangsaru Brumbungan
TPS → Jl. Karangsaru → Jl. Karanganyar → Jl. Gajah Mada → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.500
TPS Karangsaru Jagalan
TPS → Jl. Karangsaru → Jl. Karanganyar → Jl. Gajah Mada → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.600
TPS Stadion Diponegoro
TPS → Jl. Stadion Timur → Jl. Mangunsarkoro → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. Batan Selatan → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.600
67
Tabel 4.4 Rute perjalanan pengangkutan sampah Kecamatan Semarang Tengah berdasarkan SOP Dinas Kebersihan dan Pertamanan Kota Semarang
No
Titik Awal
Rute Perjalanan
Panjang Lintasan (m)
14.100
1
TPS Wilayah Kecamatan
Jl. Karanganyar → Jl. Gajah Mada → Jl. Moch. Suyudi → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
2
TPS Belakang Lawang Sewu
TPS → Jl. Satria Utara → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
11.900
TPS Pringgading
TPS → Jl. Pringgading → Jl. Mangunsarkoro → Jl. Mayjen Sutoyo → Jl. M.H. Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.500
TPS Bima Pindrikan Kidul
TPS → Jl. Nakulo Raya → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Kaligarang → Jl. Simongan → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.350
TPS RM. Nusantara
TPS → Jl. Kyai Saleh → Jl. Dr. Kariadi → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.290
TPS Abimanyu 1
TPS → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.350
3
4
5
6
68
No
7
8
9
10
11
12
13
Titik Awal
Rute Perjalanan
Panjang Lintasan (m)
TPS Abimanyu 2
TPS → Jl. Abimanyu 1 → Jl. Indraprasta → Jl. Imam → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
12.750
TPS Jl. Depok Kembangsari
TPS → Jl. Depok → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.060
TPS M.H Thamrin Miroto
TPS → Jl. Inspeksi → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
13.460
TPS Gajah Mada Miroto
TPS → Jl. Gajah Mada → Jl. Mayjen Sutoyo → Jl. M.H. Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
13.750
TPS Sumeneban Kauman
TPS → Jl. Kauman → Jl. Depok → Jl. Gajah Mada → Jl. Mayjen Sutoyo → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
15.390
TPS Matahari Johar Kauman
TPS → Jl. K.H. Agus Salim → Jl. Kauman → Jl. Depok → Jl. Gajah Mada → Jl. Mayjen Sutoyo → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
15.990
TPS Petudungan Jagalan
TPS → Jl. Mangunsarkoro → Jl. Mayjen Sutoyo → Jl. D.I. Panjaitan → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
15.610
69
No
14
15
16
17
18
19
Titik Awal
Rute Perjalanan
Panjang Lintasan (m)
TPS RS. Tlogorejo Pekunden
TPS → Jl. K.H. Ahmad Dahlan → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
14.310
TPS Citraland Pekunden
TPS → Jl. Anggrek → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
13.990
TPS Matahari Simpang 5
TPS → Jl. K.H. Ahmad Dahlan → Jl. Anggrek → Jl. Anggrek → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
14.690
TPS Karangsaru Gabahan
TPS → Jl. Jagalan → Jl. Mangunsarkoro → Jl. Mayjen Sutoyo → Jl. D.I. Panjaitan → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
15.235
TPS Karangsaru Brumbungan
TPS → Jl. Karangsaru → Jl. Karanganyar → Jl. Gajah Mada → Jl. D.I Panjaitan →Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
15.010
TPS Karangsaru Jagalan
TPS → Jl. Karangsaru → Jl. Karanganyar → Jl. Gajah Mada → Jl. D.I Panjaitan → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
15.110
70
No
20
Titik Awal
TPS Stadion Diponegoro
Rute Perjalanan
Panjang Lintasan (m)
TPS → Jl. Stadion Timur → Jl. Mangunsarkoro → Jl. Mayjen Sutoyo → Jl. D.I Panjaitan → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA
15.110
Terlihat pada tabel 4.3 dan 4.4 bahwa jalur yang dihasilkan oleh penghitungan sistem dengan menggunakan algoritma Floyd-Warshall lebih optimal dari sisi jarak dibandingkan jalur yang selama ini digunakan oleh DKP. Hal ini dikarenakan algoritma Floyd-Warshall menghitung semua pasangan titik dalam jaringan hingga menemukan path terpendeknya. Berdasarkan hasil perhitungan sistem, dari 20 TPS yang ada di Kecamatan Semarang Tengah, terdapat 15 TPS yang mendapat pilihan jalur berbeda dari SOP DKP Kota Semarang, sedangkan 5 lainnya sama. Sehingga sistem telah mampu memberikan solusi dalam hal penentuan jalur yang optimal untuk pengangkutan sampah dilihat dari segi jarak. Sebagai contoh pada jalur pengangkutan sampah
dari TPS
Matahari Johar, Kauman menuju TPA Jatibarang. Terdapat perbedaan pilihan jalur yang diberikan antara jalur yang dihasilkan oleh sistem dan jalur yang selama ini diterapkan oleh DKP. Berikut perbedaan pemilihan jalur antara keduanya dijelaskan pada tabel 4.5 dan divisualisasikan pada gambar 4.2.
71
Tabel 4.5 Perbedaan pilihan jalur dari TPS Matahari Johar, Kauman menuju TPA Jatibarang Jalur Hasil Sistem
Rute
Panjang Lintasan (m)
TPS Matahari Johar → Jl. K.H. Agus Salim → Jl. Kauman → Jl. Depok → Jl. Kapt. Pierre Tendean → Jl. Imam Bonjol → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang
14.750 m
Jalur Sesuai SOP TPS Matahari Johar → Jl. K.H. Agus Salim → Jl. Kauman → Jl. Depok → Jl. Gajah Mada → Jl. Mayjen Sutoyo → Jl. M.H Thamrin → Jl. Pandanaran → Jl. Kyai Saleh → Jl. Kariadi → Jl. Dr. Sutomo → Jl. Kaligarang → Jl. Simongan → Jl. Untung Suropati → TPA Jatibarang 15.990 m
Gambar 4.2 Contoh perbandingan pilihan jalur sesuai SOP dan hasil sistem
72
Terlihat pada gambar 4.2 merupakan contoh pemilihan jalur yang selama ini digunakan oleh DKP dan yang dihasilkan oleh sistem. Warna merah pada jalur adalah hasil penghitungan dari sistem sedangkan warna kuning pada gambar adalah jalur sesuai dengan SOP. Dari perbandingan tabel 4.3 dan tabel 4.4, dapat diketahui bahwa jalur pengangkutan sampah dari beberapa TPS menuju TPA Jatibarang
yang
dihasilkan
oleh
perhitungan
algoritma
Floyd-Warshall
memberikan jalur yang lebih optimal dari sisi jarak daripada jalur yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang. Perbedaan jalan yang diambil secara umum terdapat pada pemilihan jalur menuju ke jalan Kaligarang. Jika pada sistem perhitungan menggunakan algoritma Floyd-Warshall, jalan yang dipilih untuk menuju ke jalan Kaligarang adalah melalui jalan Dr. Sutomo, sedangkan yang selama ini diterapkan oleh Dinas Kebersihan dan Pertamanan Kota Semarang, jalan yang dipilih adalah melalui jalan Kyai Saleh. Tetapi, pemilihan jalan untuk sekitar Tugu Muda, jalan Imam Bonjol dan jalan Indraprasta, rute jalan yang dihasilkan oleh sistem sama dengan rute jalan yang selama ini diterapkan oleh DKP. Perbandingan panjang jalan yang dihasilkan oleh sistem dan yang selama ini diterapkan oleh DKP selengkapnya ditunjukkan pada tabel 4.6.
73
Tabel 4.6 Perbandingan panjang rute perjalanan menuju ke TPA Jatibarang Panjang Rute Perjalanan (m) No
Titik Awal
Selisih (m) Sistem
SOP DKP
1
TPS Wilayah Kecamatan
13.600
14.100
500
2
TPS Belakang Lawang Sewu
11.900
11.900
0
3
TPS Pringgading
14.300
14.500
200
4
TPS Bima Pindrikan Kidul
12.350
12.350
0
5
TPS RM Nusantara
12.290
12.290
0
6
TPS Abimanyu 1
12.350
12.350
0
7
TPS Abimanyu 2
12.750
12.750
0
8
TPS Jl. Depok - Kembangsari
13.150
14.060
910
9
TPS M.H Thamrin - Miroto
12.850
13.460
610
10
TPS Gajah Mada - Miroto
13.150
13.750
600
11
TPS Sumeneban - Kauman
14.250
15.390
1140
12
TPS Matahari Johar -
14.750
15.990
1240
Kauman 13
TPS Petudungan - Jagalan
14.530
15.610
1080
14
TPS RS. Tlogorejo -
14.050
14.310
260
Pekunden 15
TPS Citraland - Pekunden
13.480
13.990
510
16
TPS Matahari Simpang 5
14.180
14.690
510
17
TPS Karangsaru - Gabahan
14.695
15.235
540
18
TPS Karangsaru -
14.500
15.010
510
Brumbungan 19
TPS Karangsaru - Jagalan
14.600
15.110
510
20
TPS Stadion Diponegoro
14.600
15.110
510
Hasil yang didapatkan dari hasil perhitungan menggunakan algoritma Floyd-Warshall memberikan pilihan rute perjalanan yang lebih optimum dari sisi jarak. Pilihan jalur yang diberikan oleh sistem menghasilkan selisih panjang lintasan positif dibandingkan dengan yang selama ini diterapkan oleh DKP yaitu
74
antara 200 hingga 1240 meter. Berdasarkan hasil validasi perhitungan jalur pengangkutan menggunakan algoritma Floyd-Warshall kepada Kepala Seksi Penyapuan dan Pengangkutan Sampah DKP Kota Semarang serta sopir armada pengangkut sampah yang terdapat pada lampiran 9 dan 10, menunjukkan bahwa hasil yang didapatkan valid 100% dapat diterima dan tidak ada pilihan jalur yang menyimpang. Hasil yang didapatkan juga dapat diterapkan oleh armada pengangkut sampah dalam pengangkutan sampah di Kecamatan Semarang Tengah. Jika diteliti lagi secara manual menggunakan bantuan Google Maps, pilihan rute jalan yang dihasilkan tidak ada penyimpangan seperti melawan arus jalan satu arah atau melewati jalan yang tidak diperkenankan dilewati oleh truk sampah. Sehingga hasil yang didapatkan dari sistem sudah sesuai dengan yang diharapkan.
4.2
Pembahasan Berdasarkan hasil penelitian yang telah dilakukan menunjukkan bahwa
algortima Floyd-Warshall dapat digunakan sebagai metode untuk menyelesaikan masalah pencarian jalur terpendek. Hal ini sejalan dengan hasil penelitian yang telah dilakukan sebelumnya oleh oleh Ragil Saputra dengan judul penelitian “Sistem Informasi Geografis pencarian Rute Optimum Obyek Wisata Kota Yogyakarta dengan Algoritma Floyd-Warshall”, penelitian ini membahas tentang penggunaan Sistem Informasi Geografis (GIS) dengan algortima Floyd-Warshall pada pencarian rute optimum pencarian lokasi objek wisata tertentu. Lokasi yang menjadi objek penelitian adalah lokasi wisata di Kota Yogyakarta. Tujuan dari
75
penelitian ini adalah dapat menemukan rute terpendek yang menghubungkan antar lokasi wisata yang ada di Kota Yogyakarta, di mana moda transportasi yang digunakan adalah kendaraan roda 4. Sehingga pemilihan jalan yang dapat dilalui adalah semua jalan yang dapat dilalui oleh kendaraan roda 4. Pada penelitian ini dibuat aplikasi berbasis web dengan menggunakan bahasa pemrograman PHP dan MySQL,
serta
menggunakan
bantuan
Google
Maps
karena
mudah
pengimplementasiannya. Ajeng Fitrah Sani, Ni Ketut Tari T, dan I Made Eka D. (2013:1) juga melakukan penelitian yang mengimplementasikan algortima Floyd-Warshall dengan judul “Algoritma Floyd Warshall untuk Menentukan Jalur Terpendek Evakuasi Tsunami di Kelurahan Sanur”. Tujuan dari penelitian ini adalah untuk mengetahui jalur terpendek evakuasi Tsunami yang dapat dilalui oleh masyarakat di Kelurahan Sanur untuk menuju zona aman (titik berkumpul) dengan menggunakan algoritma Floyd-Warshall dan mengetahui jalur terpendek dari titik evakuasi ke masing-masing zona aman evakuasi. Perhitungan untuk mencari nilai jarak terpendek pada penelitian ini dilakukan secara manual, karena titik pada jaringan jalur evakuasi ini tidak terlalu banyak, yaitu sebanyak 35 titik. Kriswanto, Y, R. Kristoforus J.B, dan Arif Aliyanto (2014:1) dengan judul “Penentuan Jarak Terpendek Rute Transmusi dengan Algoritma Floyd-Warshall”, juga melakukan penelitian dengan menerapkan algortima Floyd-Warshall yang bertujuan untuk mencari jalur terpendek jalur Transmusi yang merupakan sarana transportasi publik di Kota Palembang. Model proses pengembangan perangkat lunak yang digunakan pada penelitian ini adalah model waterfall. Perangkat lunak
76
diaplikasikan dengan penelitian
PHP , CSS, Javascript dan SQL Server 2008. Hasil
menunjukkan
bahwa
perangkat
lunak
yang dibangun
dapat
menjalankan algoritma Floyd-warshall dengan baik dan aplikasi ini dapat digunakan untuk menentukan jarak terdekat yang dapat dilalui penumpang transmusi. Jurnal internasional yang juga mengimplementasikan algoritma FloydWarshall dalam pemecahan masalah pencarian lintasan terpendek dilakukan oleh S.E. Jajali dan M. Noroozi dengan judul “Determination of the optimal escape routes of underground mine networks in emergency cases”, penelitian ini membahas tentang pencarian rute optimum untuk mencari jalan keluar atau jalur evakuasi dari sebuah kecelakaan kerja yang terjadi di tambang bawah tanah. Algoritma Floyd-Warshall dimanfaatkan untuk mencari rute terpendek dari lokasi terjadinya kecelakaan kerja menuju ke pintu keluar atau menuju ke lokasi yang aman. Proses perhitungan pada penelitian ini dilakukan secara manual karena node pada jaringannya tidak terlalu banyak, yaitu sebanyak 27 node. Sedangkan dalam penelitian Hougardy (2010) seorang peneliti di Research Institute for Discrete Mathematics, University of Bonn, pada jurnal Internasional yang berjudul “The Floyd-Warshall algorithm on graphs with negative cycles” menjelaskan bahwa Algoritma Floyd-Warshall adalah algoritma sederhana dan banyak digunakan untuk menghitung jalur terpendek. Jurnal yang terakhir adalah jurnal internasional yang berjudul “Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem”, penelitian yang dilakukan oleh Asghar Aini dan Amir Salehipour (2012) memanfaatkan
77
algoritma Floyd-Warshall untuk memecahkan masalah pencarian nilai lintasan terpendek pada jaringan graf berarah. Dari 6 jurnal tersebut, terdapat kesamaan secara metode dalam pencarian rute terpendek dari satu titik menuju satu titik tujuan, namun berbeda objek dalam penerapannya. Persamaan juga terletak pada jenis graf jaringan, yaitu graf berarah di mana titik v1 tidak sama dengan titik v2. Pada penelitian ini, yang menjadi masalah adalah rute pengangkutan sampah dengan beberapa syarat yang harus dipenuhi supaya hasil penelitian ini bisa sesuai dengan yang diharapkan. Jika pada penelitian sebelumnya, pemilihan jalan/jalur tidak ada aturan khusus, namun pada penelitian ini ada syarat yang harus dipenuhi, yaitu ada beberapa jalan yang tidak diperkenankan untuk dilewati. Sehingga penelitian ini harus dilakukan dengan lebih teliti dan memperhatikan fakta yang ada di lapangan perihal pemilihan jalan.
78
BAB V PENUTUP
5.1
Kesimpulan Pencarian rute terpendek pengangkutan sampah di Kecamatan Semarang
Tengah dimulai dari memodelkan jaringan berdasarkan SOP pengangkutan sampah DKP Kota Semarang dengan membuat TPS, TPA dan persimpangan jalan sebagai node, sedangkan jalan penghubung antar node sebagai sisinya. Kemudian jaringan yang telah terbentuk dibuat matriks ketetanggaannya dan dihitung menggunakan algoritma Floyd-Warshall hingga didapatkan pilihan jalur yang optimum. Hasil perhitungan sistem menunjukkan bahwa terdapat perbedaan pilihan jalur perjalanan pengangkutan sampah dibandingkan dengan yang selama ini diterapkan oleh DKP Kota Semarang. Dari 20 TPS yang ada di Kecamatan Semarang Tengah, 15 TPS mendapat hasil rute perjalanan yang berbeda dibandingkan dengan yang selama ini diterapkan oleh DKP Kota Semarang, sedangkan 5 TPS lainnya sama. Pilihan jalur yang diberikan oleh sistem menghasilkan selisih panjang lintasan positif dibandingkan dengan yang selama ini diterapkan oleh DKP yaitu antara 200 hingga 1240 meter. Hasil validasi perhitungan jalur oleh sistem kepada Kasi Penyapuan dan Pengangkutan Sampah DKP Kota Semarang dan sopir armada pengangkut sampah menunjukkan bahwa hasil yang didapatkan valid 100% dapat diterima dan tidak ada pilihan jalur yang
79
menyimpang. Sehingga hasil yang didapatkan dari sistem sudah sesuai dengan yang diharapkan.
5.2
Saran Kekurangan dari pencarian jalur terpendek menggunakan Floyd-Warshall
ini adalah waktu perhitungan yang relatif lama, semakin banyak titik/node dalam jaringannya, maka akan semakin pula waktu perhitungannya. Selain itu, pada sistem ini dalam mengoptimalkan pengangkutan sampah hanya memperhatikan panjang jalan tanpa memperhatikan variabel lain seperti tingkat kepadatan, maupun topografi wilayahnya. Oleh karena itu, disarankan penelitian selanjutnya dikembangkan sistem pengoptimalan pengangkutan sampah selain menghitung dari segi jarak, juga memperhitungkan tingkat kepadatan jalan serta topografi wilayahnya.
DAFTAR PUSTAKA
Agustini, D.H dan Rahmadi, Y.E. 2004. Riset Operasional Konsep-Konsep Dasar. Jakarta : PT Rineka Cipta. Aini, Asghar., Amir Salehipour. 2012. Speeding up the Floyd-Warshall algorithm for the cycled shortest Plath problem. Applied Mathematics Letters Vol 25 : 1-5. Andriani, Anik.2014. Rancang Bangun Sistem Informasi Rute Wisata Terpendek Berbasis Algoritma Floyd-Warshall. Bianglala Informatika Vol II, No.1: 98-107 Chandra, B. 2006. Pengantar Kesehatan Lingkungan. Jakarta : EGC. Defindal, LP, dkk. 2003. Algoritma Greedy Untuk Menentukan Lintasan Terpendek. http://kur2003.if.itb.ac.id/strategialgritmi/rencana/Algoritmagreedy. (diakses pada 1 Juni 2015) Dimyati, Tjutju Tarliah, dan Akhmad Dimyati. 1992. Operations Research Model-Model Pengambilan Keputusan. Bandung : Sinar Baru. Jalali, S.E., M. Noroozi. H. 2009. Determination of the Optimal Escape Routes of Underground Mine Networks in Emergency Cases. Safety Science Vol 47 : 1077-1082 Kamayudi, Apri. 2006. Studi Implementasi Algoritma Dijkstra, Bellman-Ford dan Floyd-Warshall dalam Menangani Masalah Lintasan Terpendek dalam Graf. http://www.informatika.org/~rinaldi/Matdis/20062007/Makalah/Makalah0 607-26.pdf. (diakses pada 1 Juni 2015) Kriswanto, Y. R., R. Kristoforus J.B., Arif Aliyanto. 2014. Penentuan Jarak Terpendek Rute Transmusi dengan Algortima Floyd-Warshall. Seminar Nasional Teknologi Informasi dan Komunikasi Terapan 2014 (pp. 209216). Palembang : Sekolah Tinggi Teknik Musi Palembang. Liwang, R., Santoso, A. J., & Rahayu, F. S.. 2013. Rancang Bangun Aplikasi Menggunkan Floyd Warshaall. Seminar Nasional Teknologi Informasi dan Multimedia (pp. 18-21). Yogyakarta : STMIK AMIKOM Yogyakarta. Mulyono, Sri. 2002. Riset Operasi. Jakarta : Lembaga Penerbit Fakultas Ekonomi Universitas Indonesia.
78
79
Nurhayati, Remi. 2003. Keterkaitan Antara Ideal Utama dalam Suatu Koleksi Matriks Boolean. http://digilib.gunadarma.ac.id/print.php?id=jbptitbchem-gdl-s1-2003reminurhay-5 (diakses pada 2 Juni 2015). Sani, A., Ni Ketut Tari T., I Made Eka D. 2013. Algoritma Floyd Warshall untuk Menentukan Jalur Terpendek Evakuasi Tsunami di Kelurahan Sanur. E-Jurnal Matematika Vol 2, No 1, 1-5. Saputra, Ragil. 2011. Sistem Informasi Geografis pencarian Rute Optimum Obyek Wisata Kota Yogyakarta dengan Algoritma Floyd-Warshall. Jurnal Matematika Vol. 14, No. 1, 19-2 Siang, Jong Jek. 2002. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta : ANDI. _______.2011. Riset Operasi dalam Pendekatan Algoritmis. Yogyakarta : ANDI. Siswanto. 2006. Operations Research Jilid 1. Jakarta : Erlangga. Subagyo, P. 2000. Dasar-Dasar Operation Research. Yogyakarta : BPFFYogyakarta. Sutarno, Heri, Nanang Priatna, dan Nurjanah. 2003. Matematika Diskrit. Malang : Universitas Negeri Malang (UM PRESS) Suyitno, H. 1997. Pengantar Program Linier. Semarang : Jurusan Matematika. FMIPA IKIP Semarang. Triadi, Dendy. 2013. Bedah Tuntas Fitur Android. Yogyakarta : Jogja Great! Publisher.
LAMPIRAN
LAMPIRAN
80
Lampiran 1. Peta awal jaringan pengangkutan sampah
81
82
No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
Simbol v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20 v21 v22 v23 v24 v25 v26 v27 v28 v29 v30 v31 v32 v33 v34 v35 v36 v37 v38 v39 v40
Jenis TPA Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan
Keterangan TPA Jatibarang Abdurrahman Saleh - Untung Suropati W.R. Supratman - Untung Suropati Bundaran Kalibanteng W.R. Supratman Pamularsih Pertigaan Sampokong Lampu merah Kaligarang Lampu merah RS. Kariadi Dr. Sutomo - Bendungan Veteran - dr. Kariadi Veteran - Kyai Saleh Perempatan Kyai Saleh - dr. Kariadi Kyai Saleh - Bendungan Perempatan Kyai Saleh - Pandanaran Bundaran Tugu Muda Bundaran Indraprasta Imam Bonjol - Nakulo Raya Indraprasta - Bima Raya Indraprasta - Abimanyu Perempatan Imam Bonjol - Indraprasta Imam Bonjol - Abimanyu Imam Bonjol - Tanjung Bundaran Paragon M.H. Tamrin - Inspeksi Satria Baru - Batan Selatan M.H. Tamrin - Batan Selatan Pandanaran - Tri Lomba Juang Pahlawan - Tri Lomba Juang Lampu Merah Polda Jateng Sriwijaya - Singosari Raya Imam Barjo - Erlangga Erlangga - Singosari Singosari - Singosari 2A Mataram - Singosari Raya Imam Barjo - Singosari 2A Erlangga - Singosari 2A Erlangga - Atmodirono Ahmad Yani - M.T. Haryono Ahmad Yani - Atmdirono Ahmad Yani - Atmodirono 1
83
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
v41 v42 v43 v44 v45 v46 v47 v48 v49 v50 v51 v52 v53 v54 v55 v56 v57 v58 v59 v60 v61 v62 v63 v64 v65 v66 v67
Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan Persimpangan
Mangunsarkoro - Seroja Selatan M.T. Haryono - Stadion Mangunsarkoro - Stadion Bundaran Simpang 5 Gajah Mada - Anggrek Gajah Mada - Mayjen Sutoyo K.H. Ahmad Dahlan - Anggrek Mayjen Sutoyo - K.H. Ahmad Dahlan Gajah Mada - Karanganyar Gajah Mada - Wotgandul Barat Gajah Mada - Depok Perempatan Sri Ratu Imam Bonjol - Gendingan Persimpangan Pasar Johar Kauman - Depok Plampitan - Wotgandul Barat Kyai Agus Salim - Gg. Lombok Gg. Lombok - Petudungan M.T. Haryono - Petudungan Mangunsarkoro - Wotgandul Barat Mangunsarkoro - Jagalan M.T. Haryono - Jagalan Mangunsarkoro - Karangsaru M.T. Haryono - Karangsaru Mangunsarkoro - Pringgading M.T. Haryono - Pringgading M.T. Haryono - Mayjen Sutoyo
Lampiran 2. Matriks Wij awal jaringan pengangkutan sampah Kecamatan Semarang Tengah
84
Lampiran 2. Matriks Wij awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
85
Lampiran 2. Matriks Wij awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
86
Lampiran 2. Matriks Wij awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
87
Lampiran 2. Matriks Wij awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
88
Lampiran 3. Matriks Zi,j awal jaringan pengangkutan sampah Kecamatan Semarang Tengah
89
Lampiran 3. Matriks Zi,j awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
90
Lampiran 3. Matriks Zi,j awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
91
Lampiran 3. Matriks Zi,j awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
92
Lampiran 3. Matriks Zi,j awal jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
93
Lampiran 4. Matriks W* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah
94
Lampiran 4. Matriks W* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
95
Lampiran 4. Matriks W* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
96
Lampiran 4. Matriks W* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
97
Lampiran 4. Matriks W* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
98
Lampiran 5. Matriks Z* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah
99
Lampiran 5. Matriks Z* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
100
Lampiran 5. Matriks Z* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
101
Lampiran 5. Matriks Z* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
102
Lampiran 5. Matriks Z* akhir jaringan pengangkutan sampah Kecamatan Semarang Tengah (lanjutan...)
103
104
Lampiran 6. Source Code Program Matriks Processing CountData($lokasi_tps,"graf_tps") as $value){ extract($value); $simpan_tps=explode("|", $titik_graf) ; $count_simpan_tps=count($simpan_tps); for ($j=0; $j < $count_simpan_tps; $j++) { $isi_tps[$iterasi_tps]=$simpan_tps[$j]; $nilai_jarak[$iterasi_tps]=$panjang_garis; $l=0; foreach($obj->showData("tps") as $value){ extract($value); if ($isi_tps[$iterasi_tps]=="$simbol_tps") { $matrik_isi_tps[$iterasi_tps]=$l; } $l++; } //echo "| $isi_tps[$iterasi_tps] $nilai_jarak[$iterasi_tps] $matrik_isi_tps[$iterasi_tps]
"; $titik_abjad[$iterasi]=$isi_tps[$iterasi_tps]; $titik_kode[$iterasi]=$matrik_isi_tps[$iterasi_tps]; $iterasi++; $iterasi_tps++; } $iterasi1=$iterasi_tps-2; $iterasi2=$iterasi_tps-1; $satu=$matrik_isi_tps[$iterasi1]; $dua=$matrik_isi_tps[$iterasi2]; $iterasi_1=$iterasi_tps-1; $matriks_awal[$satu][$dua]=$nilai_jarak[$iterasi_tps-1]; $satu1[$jumlah_matrik]=$satu; $dua1[$jumlah_matrik]=$dua; $nilai[$jumlah_matrik]=$nilai_jarak[$iterasi_1]; $jumlah_matrik++; //echo "matriks_awal[$satu][$dua] $nilai_jarak[$iterasi_1] "; //echo "
"; } $jumlah_tps=0; for ($i=0; $i < $iterasi_tps; $i++) { $flag=0; for ($j=($i+1); $j < $iterasi_tps; $j++) { if ($isi_tps[$i] == $isi_tps[$j]) { $flag=1; } } if ($flag==0) {
105
$isi_tps[$jumlah_tps]=$isi_tps[$i]; $jumlah_tps++; } } //////////Menampilkan Jumlah Kota//////////// /*for ($i=0; $i < $jumlah_tps; $i++) { echo "$isi_tps[$i] "; } echo "jumlah_tps : $jumlah_tps ";*/ for($i=0;$i<$jumlah_tps;$i++){ for($j=0;$j<$jumlah_tps;$j++){ if ($i==$j) { $matriks_awal[$i][$j]=0; //$matriks_awal[$i][$j]=999; }else{ $matriks_awal[$i][$j]=99999; } } } $jumlah_matrik=count($satu1); //Mengisi nilai array for($i=0;$i<$jumlah_matrik;$i++){ $satu11=$satu1[$i]; $dua11=$dua1[$i]; $nilai1=$nilai[$i]; $matriks_awal[$satu11][$dua11]=$nilai1; $matriks_awal[$dua11][$satu11]=$nilai1; //echo "matriks_awal[$satu11][$dua11]"; //printf($matriks_awal[$satu11][$dua11]); //echo "
"; } $awal=NULL; //isian form for ($i=0; $i < $jumlah_tps; $i++) { for ($j=0; $j < $iterasi; $j++) { if ($i==$titik_kode[$j]) { $titik_[$i]=$titik_abjad[$j]; //echo "$titik_[$i] $titik_kode[$j]
"; $j=$iterasi; } } } ?>
106
Floyd-Warshall algorithm for($k=0;$k<$jumlah_tps;$k++){ ?>
"; echo"
| Wij | "; for($l=1;$l<=$jumlah_tps;$l++){ echo"$l | "; } echo"Zij | "; for($l=1;$l<=$jumlah_tps;$l++){ echo"$l | "; } echo"
"; for($i=0;$i<$jumlah_tps;$i++){ $m=$i+1; echo"
"; echo"| $m | ";echo" "; for($j=0;$j<$jumlah_tps;$j++){ if ($wij[$i][$j]>($wij[$i][$k]+$wij[$k][$j])) { $jumlah_w[$i][$j]=$wij[$i][$k]+$wij[$k][$j]; $wij[$i][$j]=$wij[$i][$k]+$wij[$k][$j]; $z[$i][$j]=$z[$i][$k]; } echo""; if($wij[$i][$j]=="99999"){ echo"INF"; } else{ print($wij[$i][$j]); } echo" | "; } //matriks Z echo"$m | ";echo" "; for($n=0;$n<$jumlah_tps;$n++){ echo""; if($z[$i][$n]=="99999"){ echo"INF"; } else{ printf($z[$i][$n]); } echo" | "; }
echo"
"; //echo"
"; } echo"";?>
107
Shortest Path Floyd-Warshall Algorithm for ($i=0; $i < ($jumlah_titik-1); $i++) { $titik_awal=$titik_[$i]; $titik_akhir=$titik_[$i+1]; $pasang_jalan[$i]="$titik_awal|$titik_akhir"; $pasang_jalan_[$i]="$titik_akhir|$titik_awal"; echo "
$pasang_jalan[$i] || $pasang_jalan_[$i]
"; if ($tanda!=0) { $obj->insertpeta("alur_peta",$pasang_jalan[$i],$pasang_jalan_[$i]); }
}
$lokasi_tps=$_SESSION['lokasi']; for ($i=0; $i < ($jumlah_titik-1); $i++) { foreach($obj->CountData($lokasi_tps,"graf_tps") as $value){ extract($value); if ($pasang_jalan[$i]==$titik_graf || $pasang_jalan_[$i]==$titik_graf) { $nama_jalan_[$i]="$nama_jalan"; echo " $nama_jalan_[$i]
"; } } }
108
Lampiran 7. Data TPS dan Operasional Armada Pengangkut Sampah di Kecamatan Semarang Tengah
109
Lampiran 8. Standar Operasional dan Prosedur Rute Pengangkutan Sampah Kota Semarang
110
Lampiran 9. Validasi Hasil Rute Pengangkutan Sampah oleh Kepala Seksi Penyapuan dan Pengangkutan DKP Kota Semarang
111
112
113
114
115
Lampiran 10. Validasi Hasil Rute Pengangkutan Sampah oleh Sopir Armada Pengangkut Sampah
116
117
118
119
120
121
Lampiran 11. Surat Usulan Topik Skripsi
122
Lampiran 12. Surat Usulan Dosen Pembimbing Skripsi
123
Lampiran 13. Surat Penetapan Dosen Pembimbing Skripsi
124
Lampiran 14. Surat Permohonan Observasi di DKP Kota Semarang
125
Lampiran 15. Surat Rekomendasi Penelitian dari Badan Kesbangpol
126
127
Lampiran 16. Surat Keterangan Telah Melaksanakan Penelitian
128
Lampiran 17. Dokumentasi
Truk Arm Roll
Kontainer Sampah
129
TPS Belakang Lawang Sewu
TPA Jatibarang Kota Semarang
