IMPLEMENTASI ALGORITMA FLOYD WARSHALL DAN NEAREST .

IMPLEMENTASI ALGORITMA FLOYD WARSHALL DAN NEARESTNEIGHBOUR DALAM PENGOPTIMALAN RUTE CAPACITATED VEHICLEROUTING PROBLEM WITH TIME WINDOWSSKRIPSIDiajukan kepada Fakultas Matematika dan Ilmu Pengetahuan AlamUniversitas Negeri Yogyakartauntuk Memenuhi Sebagian Persyaratanguna Memperoleh Gelar Sarjana SainsOlehIntrada ReviladiNIM 11305144037PROGRAM STUDI MATEMATIKAFAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS NEGERI YOGYAKARTA2016

ii

iii

iv

MOTTO HIDUP“Orang yang sukses bukan orang yang tidak pernah mengalami kegagalan dalamhidupnya, namun orang yang sukses adalah orang yang tidak pernah menyerah meskiharus gagal berkali-kali”v

PERSEMBAHANSkripsi ini saya persembahkan untuk:Papa, Mama dan kedua adikku, Luke Ottaviandri dan Qantaza Rian Ardito,yang selalu memotivasi saya dan memberikan dorongan moral maupunmateri,Mbah Esti dan Eyang Nana, terimakasih atas dukungan dan doanya,Kharisma Nanda yang telah banyak membantu saya dan berbagi ilmu dalamhal pemrograman, serta teman-teman TIT yang juga memberikan dukungandan semangatnya,Sahabat-sahabatku, Yogya, Dika, Muhsin, Humam, Noval, Yoga, dan temanteman yang turut serta memberi motivasi dalam proses pembuatan skripsi ini,Teman-teman MATSWA 2011 atas kebersamaannya selama 4 tahun ini danpengalaman yang tak terlupakan,Keluarga besar Himatika 2012 dan BSO TIMM 2013 untuk pengalaman dalamberorganisasi,Teman-teman KKN ND35 atas kebersamaannya dan kerjasamanya selamadua bulan bersama,dan untuk semua pihak yang tidak dapat saya sebutkan satu per satu,vi

IMPLEMENTASI ALGORITMA FLOYD WARSHALL DAN NEARESTNEIGHBOUR DALAM PENGOPTIMALAN RUTE CAPACITATED VEHICLEROUTING PROBLEM WITH TIME WINDOWSOlehIntrada ReviladiNIM 11305144037ABSTRAKCapacitated Vehicle Routing Problem with Time Windows (CVRPTW)merupakan masalah penentuan rute tercepat kendaraan untuk memenuhi permintaankonsumen yang terdiri dari pelayanan antar dengan kendala kapasitas kendaraan,time windows, dan kecepatan pada tiap jalur berdasarkan waktu per jam.Permasalahan CVRPTW dapat diselesaikan dengan menggunakan algoritma yangbersifat eksak dan heuristik. Dalam menyelesaikan masalah CVRPTW akandigunakan dua algoritma, yakni algoritma floyd warshall dan nearest neighbour.Pada penelitian ini, akan dijelaskan mengenai penggunaan algoritma floydwarshall dan nearest neighbour dalam penyelesaian masalah CVRPTW yangkemudian akan diimplementasikan pada data simulasi secara manual danmenggunakan perangkat lunak MatLab. Selanjutnya akan dibandingkan efektifitaskedua algoritma tersebut yang diukur berdasarkan proses dan hasil pembentukanrute.Berdasarkan hasil penelitian, diperoleh bahwa algoritma floyd warshall dapatmembentuk rute dengan total waktu tempuh yang lebih efektif dibandingkan denganalgoritma nearest neighbour. Namun dalam proses penerapannya, algoritma nearestneighbour jauh lebih cepat dan praktis dibandingkan dengan algoritma floydwarshall.Kata Kunci : capacitated vehicle routing problem with time windows (CVRPTW),floyd warshall, nearest neighbourvii

KATA PENGANTARSyukur alhamdullillah penulis panjatkan kepada Allah atas nikmat sertakarunia yang diberikan kepada penulis untuk menyelesaikan tugas akhir skripsi.Skripsi yang berjudul “Implementasi Metode Floyd Warshall dan Nearest Neighbourdalam Pengoptimalan Rute Capacitated Vehicle Routing Problem With TimeWindows” disusun untuk memenuhi salah satu syarat kelulusan guna meraih gelarSarjana Sains pada Program Studi Matematika, Fakultas Matematika dan IlmuPengetahuan Alam, Universitas Negeri Yogyakarta.Skripsi ini tidak dapat diselesaikan tanpa bantuan, dukungan, serta bimbinganbeberapa pihak. Penulis mengucapkan terimakasih kepada:1. Bapak Dr. Hartono, selaku Dekan Fakultas Matematika dan Ilmu PengetahuanAlam, Universitas Negeri Yogyakarta,2. Bapak Dr. Ali Mahmudi, selaku Ketua Jurusan Pendidikan Matematika, FMIPA,Universitas Negeri Yogyakarta,3. Bapak Dr. Agus Maman Abadi, selaku Ketua Program Studi Matematika,FMIPA, Universitas Negeri Yogyakarta yang telah memberikan motivasi dalamkelancaran skripsi serta membantu kelancaran administrasi skripsi,4. Bapak Bambang Sumarno H.M., M.Kom, selaku dosen pembimbing yang telahberkenan memberikan waktu luang, arahan, bimbingan serta dengan penuhkesabaran meneliti setiap kata demi kata dalam skripsi,5. Dewan Penguji yang telah memberikan saran dalam penulisan skripsi,6. Bapak Sugiyono, M.Pd, selaku Penasehat Akademik yang telah memberikanbimbingan serta motivasi selama studi,viii

7. Seluruh dosen dan staf Jurusan Pendidikan Matematika Universitas NegeriYogyakarta yang telah memberikan ilmu serta pelayanannya kepada penulis,8. Teman-teman Program Studi Matematika 2011 yang telah saling mendukunguntuk saling belajar,9. Semua pihak yang telah memberikan dukungan, bantuan, dan motivasi kepadapenulis.Penulis menyadari adanya kekurangan dalam penulisan tugas akhir skripsi ini.Oleh karena itu, penulis menerima kritik dan saran yang bersifat membangun.Semoga penulisan tugas akhir ini dapat bermanfaat bagi pembaca dan pihak yangterkait.Yogyakarta, 23 Mei 2016PenulisIntrada Reviladiix

DAFTAR ISIPERSETUJUAN . IIPENGESAHAN . IIIPERNYATAAN . IVPERSEMBAHAN . VIABSTRAK . VIIKATA PENGANTAR . VIIDAFTAR ISI . XDAFTAR GAMBAR . XIIDAFTAR TABEL . XIVBAB I PENDAHULUANA. Latar Belakang . 1B. Batasan Masalah . 4C. Rumusan Masalah . 4D. Tujuan Penelitian . 5E. Manfaat Penelitian . 5BAB II KAJIAN TEORIA. Distribusi . 6B. Optimasi . 8C. Efektivitas . 11D. Graf . 111.Definisi Graf. 112.Jenis-jenis Graf. 123.Keterhubungan . 144.Representasi Graf dalam Matriks . 15E. Vehicle Routing Problem . 161.Pengertian Vehicle Routing Problem . 162.Klasifikasi Jenis-jenis VRP . 18F. Capatitated Vehicle Routing Problem with Time Windows . 191.Pengertian . 192.Formulasi CVRPTW . 20x

3.Representasi Solusi . 23G. Algoritma . 24H. Algoritma Floyd Warshall dan Nearest Neighbour . 271.Floyd Warshall . 272.Nearest Neighbour . 29BAB III METODE PENELITIANA. Metode Penelitian . 32B. Jenis dan Sumber Data Penelitian . 32C. Teknik Pengumpulan Data . 32D. Teknik Analisis Data . 33E. Desain Penelitian . 33BAB IV PEMBAHASANA. Algoritma Floyd Warshall dan Nearest Neighbour pada Model CVRPTW . 351. Algoritma Floyd Warshall . 352. Algoritma Nearest Neighbour . 36B. Formulasi Floyd Warshall dan Nearest Neighbour pada PenyelesaianCVRPTW . 37C. Penyelesaian Model CVRPTW dengan Algoritma Floyd Warshall danNearest Neighbour . 391. Deskripsi Masalah . 392. Pengumpulan Data . 413. Pengolahan Data . 47BAB V KESIMPULAN DAN SARANA. Kesimpulan . 75B. Saran . 77DAFTAR PUSTAKA . 78LAMPIRAN . 81xi

DAFTAR GAMBARGambar 2.1. Flowchart Proses Pengambilan Keputusan . 10Gambar 2.2. Graf G. 12Gambar 2.3. Graf G1 . 13Gambar 2.4. Graf G2 . 13Gambar 2.5. Graf G3 . 13Gambar 2.6. Graf G4 . 14Gambar 2.7. Matriks Ketetanggaan . 16Gambar 2.8. Ilustrasi Solusi Layak CVRPTW . 23Gambar 2.9. Contoh Algoritma Mengambil Uang Tabungan di Bank . 24Gambar 2.10. Flowchart Algoritma Floyd Warshall . 29Gambar 2.11. Flowchart Algoritma Nearest Neighbour . 31Gambar 3. Desain Penelitian Pengoptimalan Rute dalam CVRPTW . 34Gambar 4.1. Permasalahan CVRPTW pada Data Simulasi . 40Gambar 4.2. Hasil Rute 1 pada Data Simulasi dengan NN . 51Gambar 4.3. Hasil Rute 2 pada Data Simulasi dengan NN . 54Gambar 4.4. Hasil Rute 3 pada Data Simulasi dengan NN . 57Gambar 4.5. Hasil Rute 4 pada Data Simulasi dengan NN . 59Gambar 4.6. Hasil Rute 5 pada Data Simulasi dengan NN . 61Gambar 4.7. Hasil Output pada Matlab dengan nearest neighbour . 62Gambar 4.8. Hasil Rute 1 pada Data Simulasi dengan FW . 68Gambar 4.9. Hasil Rute 2 pada Data Simulasi dengan FW . 68Gambar 4.10. Hasil Rute 3 pada Data Simulasi dengan FW . 71Gambar 4.11. Hasil Rute 4 pada Data Simulasi dengan FW . 73Gambar 4.12. Hasil Rute 5 pada Data Simulasi dengan FW . 73xii

DAFTAR TABELTabel 4.1. Lokasi Depot dan Konsumen . 42Tabel 4.2. Jumlah Permintaan Konsumen. 43Tabel 4.3. Data Jarak antar lokasi . 43Tabel 4.4. Time Windows Konsumen. 44Tabel 4.5. Data Keterhubungan antar lokasi. . 45Tabel 4.6. Data Kecepatan Rata-rata pada pukul 07.00-08.00. 45Tabel 4.7. Data Kecepatan Rata-rata pada pukul 08.00-09.00. 46Tabel 4.8. Data Kecepatan Rata-rata pada pukul 09.00-10.00. 46Tabel 4.9. Data Kecepatan Rata-rata pada pukul 10.00-11.00. 46Tabel 4.10. Data Kecepatan Rata-rata pada pukul 11.00-12.00. 47Tabel 4.11. Data Keseluruhan . 48Tabel 4.12.a. Matriks waktu tempuh kendaraan ke-1 saat t 0 . 49Tabel 4.12.b. Matriks waktu tempuh kendaraan ke-1 saat t 55 . 50Tabel 4.13. Rekapitulasi Hasil penyelesaian CVRPTW dengan NN. 61Tabel 4.14.a. Total Waktu Tempuh Pembentukan Rute Pertama denganFloyd Warshall pada iterasi 1 . 64Tabel 4.14.b. Total Waktu Tempuh Pembentukan Rute Pertama denganFloyd Warshall pada iterasi 2 . 65Tabel 4.15. Total Waktu Tempuh Pembentukan Rute Pertama denganFloyd Warshall saat Kembali ke Depot . 67Tabel 4.16.a. Total Waktu Tempuh Pembentukan Rute Ketiga denganFloyd Warshall pada iterasi 1 . 69Tabel 4.16.b. Total Waktu Tempuh Pembentukan Rute Ketiga denganFloyd Warshall pada iterasi 2 . 69Tabel 4.17. Total Waktu Tempuh Pembentukan Rute Ketiga denganFloyd Warshall saat Kembali ke Depot . 70Tabel 4.18. Total Waktu Tempuh Pembentukan Rute Keempat denganFloyd Warshall pada iterasi 1 . 71Tabel 4.19. Total Waktu Tempuh Pembentukan Rute Keempat denganFloyd Warshall saat Kembali ke Depot . 72xiii

Tabel 4.20. Rekapitulasi Hasil penyelesaian CVRPTW dengan FW . 74xiv

vii IMPLEMENTASI ALGORITMA FLOYD WARSHALL DAN NEAREST NEIGHBOUR DALAM PENGOPTIMALAN RUTE CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS Oleh Intrada Reviladi NIM 11305144037 ABSTRAK Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) merupakan masalah penentuan rute tercepat kendaraan untuk memenuhi permintaan