UNIVERSITAS BINA NUSANTARA Program Ganda T. Informatika - Matematika Skripsi Sarjana Program Ganda Semester Ganjil 2006/2007 PERANCANGAN PROGRAM APLIKASI PENENTUAN RUTE TERPENDEK DISTRIBUSI BUKU DAERAH DKI JAKARTA DENGAN ALGORITMA METROPOLIS (STUDI KASUS: PT TIGA LANCAR SEMESTA)
Suriawati Chandra NIM: 0600659736
Abstrak Masalah yang dihadapi perusahaan saat ini ialah masalah pendistribusian buku yang sudah diterbitkan dan dicetak ke toko-toko pelanggan. Rute distribusi yang selama ini digunakan dirasakan kurang optimal karena penentuan rute tersebut dilakukan secara manual menggunakan intuisi. Dampak dari penentuan secara intuisi adalah munculnya keluhan dari pelanggan mengenai waktu penerimaan buku yang berbeda dengan pelanggan yang lain dan ongkos ditribusi yang tinggi. Untuk mengatasi masalah ini, penulis merasa perlu dilakukan optimasi terhadap penentuan rute distribusi menggunakan suatu algoritma tertentu untuk menggantikan sistem penentuan rute yang selama ini dipakai dan membuat suatu program aplikasi penentuan rute terpendek untuk memudahkan pihak perusahaan dalam membuat penentuan rute terpendek. Optimasi penentuan rute terpendek akan menggunakan algoritma Metropolis. Algoritma Metropolis merupakan pengembangan dari metode Simulated Annealing. Algoritma Metropolis berkemampuan untuk menghindar dari terperangkapnya solusi dalam local minima, sehingga memungkinkan penyelesaian Traveling Salesman Problem untuk mendapatkan absolut minimum. Melalui input berupa jarak antar toko dengan kantor pusat dan toko lainnya yang disimpan dalam database, didapat rute yang paling optimal. Program aplikasi tersebut diuji dan berhasil menentukan rute terpendek optimal dengan menggunakan data hasil input-an sampai 15 kota.
Kata Kunci: traveling salesman problem, rute, optimasi, algoritma, metropolis.
KATA PENGANTAR Puji Syukur penulis panjatkan terhadap kehadiran Tuhan Yang Maha Esa atas rahmat dan petunjuk yang telah diberikan oleh-Nya sehingga penulis dapat mengerjakan dan menyelesaikan penulisan skripsi ini dengan baik. Walaupun tugas membuat Skripsi ini terasa berat oleh penulis, namun berkat bimbingan dari para dosen dan dukungan dari orang-orang yang banyak membantu, akhirnya Skripsi ini dapat diselesaikan walaupun masih jauh dari kesempurnaan. Adapun maksud dan tujuan dari penulisan skripsi ini adalah untuk memenuhi salah satu syarat dalam mendapatkan gelar Sarjana Jenjang Strata Satu pada Program Ganda Fakultas MIPA Jurusan Matematika, Universitas Bina Nusantara. Dalam kesempatan ini penulis dengan tulus hati ingin mengucapkan terima kasih yang sebesar-besarnya kepada semua pihak yang telah memberikan bantuan baik dari segi moral maupun spiritual yang sangat bermanfaat bagi penulis dalam penyusunan skripsi ini. Ucapan terima kasih ini, penulis tujukan kepada:
1. Bapak Prof. Dr. Geraldus Polla, M.App.Sc., selaku rektor Universitas Bina Nusantara, yang telah berkenan memberikan kesempatan untuk menuntut ilmu kepada penulis di Universitas yang berada di bawah pimpinan beliau. 2. Bapak Wikaria Gazali, S.Si., MT., selaku Dekan Fakultas MIPA Universitas Bina Nusantara atas perhatian, pertolongan dan pengajaran yang telah diberikan selama ini. 3. Bapak Drs. Ngarap Imanuel Manik, M.Kom., selaku Ketua Jurusan Matematika Fakultas MIPA Universitas Bina Nusantara atas perhatian, pertolongan dan pengajaran yang telah diberikan selama ini. 4. Bapak Rojali, S. Si., selaku Sekretaris Jurusan Matematika Fakultas MIPA Universitas Bina Nusantara atas perhatian, pertolongan dan pengajaran yang telah diberikan selama ini. 5. Bapak Tri Murdyanto, Drs, MSi, selaku Dosen Pembimbing kesatu yang telah banyak memberikan bantuan dan bimbingan yang diberikan selama masa
penyusunan skripsi ini serta atas pengertian, pengajaran, pertolongan dan kesabarannya yang memudahkan skripsi ini terselesaikan tepat pada waktunya. 6. Bapak Saulus Silitonga Drs, MSi, selaku Dosen Pembimbing kedua yang telah banyak memberikan bantuan dan bimbingan yang diberikan selama masa penyusunan skripsi ini serta atas pengertian, pengajaran, pertolongan dan kesabarannya yang memudahkan skripsi ini terselesaikan tepat pada waktunya. 7. Seluruh Dosen Universitas Bina Nusantara yang selama ini telah memberikan ilmu dan bimbingan akademis kepada penulis dari awal hingga akhir perkuliahan. 8. Pimpinan dan seluruh staf karyawan PT Tiga Lancar Semesta yang telah memberikan bantuan dan informasi yang berguna. 9. Keluarga penulis, atas doa, kasih, kesabaran, dan dukungan yang diberikan kepada penulis selama penyusunan skripsi ini. 10. Felicia Lawadi atas dukungan dan bantuannya yang diberikan kepada penulis selama ini. 11. Teman-teman jurusan ganda Teknik Informatika – Matematika atas dukungan dan bantuannya yang diberikan kepada penulis selama ini. 12. Pihak-pihak lain yang tidak dapat disebutkan satu persatu yang telah mendukung dan membantu penulis dalam penyelesaian skripsi ini.
Penulis menyadari bahwa skripsi ini masih jauh dari sempurna, karena keterbatasan kemampuan dan pengetahuan penulis. Oleh karenanya, penulis mohon maaf dan harap maklum serta pengertian dari pembaca jika menemukan kesalahankesalahan dalam penulisan kata-kata pada skripsi ini. Penulis berharap agar skripsi ini berguna dapat memberikan masukan yang positif bagi setiap pihak.
Jakarta, 24 Januari 2007
Penulis
DAFTAR ISI Abstrak Kata Pengantar Daftar Tabel Daftar Gambar Daftar Lampiran
v vi xi xii xiii
BAB 1 PENDAHULUAN 1 1.1 Latar Belakang Masalah 1 1.2 Tujuan dan Manfaat 4 1.2.1 Tujuan 4 1.2.2 Manfaat 4 1.3 Metodologi 5 1.3.1 Metode Studi Kepustakaan 5 1.3.2 Metode Penelitian Laboratorium 5 1.3.3 Metode Perancangan 5 1.4 Ruang Lingkup 6 BAB 2 LANDASAN TEORI 8 2.1 Gambaran Umum Traveling Salesman Problem 8 2.2 Alternatif Pemecahan Masalah 11 2.3 Deskripsi Teori 11 2.3.1 Graph 11 2.3.2 Traveling Salesman Problem 15 2.3.2.1 Definisi Traveling Salesman Problem 15 2.3.2.2 Algoritma Untuk Memecahkan Traveling Salesman Problem 18 2.3.2.3 Aplikasi Traveling Salesman Problem 25 2.3.2.3.1 Bidang Transportasi Dan Logistik 25 2.3.2.3.2 Bidang Penjadwalan 26 2.3.2.3.3 Bidang Antariksa 27 2.3.2.3.4 Bidang Elektronik 27 2.3.2.3.5 Bidang Biologi 28 2.3.2.3.6 Bidang Jaringan 28 2.3.3 Algoritma Metropolis 29 2.4 Rekayasa Piranti Lunak 34 2.5 Alat Bantu Perancsngan 35 2.5.1 State Transition Diagram 35 2.5.2 Pseudocode 36 BAB 3 PERANCANGAN 38 3.1 Gambaran Umum Perusahaan 38 3.1.1 Sistem Distribusi PT TIGA LANCAR SEMESTA 41 3.1.1.1 Sistem Yang Berjalan 41 3.1.1.2 Sistem Yang Diusulkan 42 3.2 Perancangan Program Aplikasi 42 3.2.1 Gambaran Umum Perancangan 42
ix
3.2.2 Penerapan Algoritma Metropolis 3.2.3 Perancangan Database 3.2.4 Perancangan Modul 3.2.4.1 Input 3.2.4.2 Process (Algoritma Metropolis) 3.2.4.3 Output 3.2.5 Perancangan Tampilan Layar 3.2.5.1 Layar Menu Utama 3.2.5.2 Layar Menu Add 3.2.5.3 Layar Menu Edit/Delete 3.2.5.4 Layar Menu About BAB 4 PENGUJIAN PROGRAM DAN HASIL PENGUJIAN 4.1 Spesifikasi Hardware dan Software 4.2 Proses Implementasi 4.3 Analisis Program Aplikasi 4.4 Evaluasi Program Aplikasi BAB 5 KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran
42 44 47 47 48 48 49 51 52 53 55 56 56 57 63 63 64 64 64
DAFTAR PUSTAKA RIWAYAT HIDUP
xiv xvi
x
DAFTAR TABEL Tabel 2.1 Banyaknya Kombinasi Traveling Salesman Problem Dari n Kota Tabel 3.1 Daftar Buku Yang Sudah Diterbitkan Tabel 4.1 Data Toko Untuk Tabel Utara Pada Database Tabel 4.2 Tambahan Data Untuk Tabel Utara
xi
10 41 57 58
DAFTAR GAMBAR Gambar 2.1 Kombinasi Kemungkinan Solusi ATSP Untuk 4 Kota Gambar 2.2 Kombinasi Kemungkinan Solusi TSP Untuk 4 Kota Gambar 2.3 Undirected Graph Gambar 2.4 Directed Graph Gambar 2.5 Graph Teka-Teki Hamiltonian Cycle Gambar 2.6 Hamiltonian Cycle Dari Gambar 2.5 Gambar 2.7 Absolute Minimum Gambar 2.8 Flowchart Algoritma Metropolis Gambar 2.9 Waterfall Model Gambar 3.1 Struktur Organisasi Perusahaan Gambar 3.2 Bagan Utama Proses Gambar 3.3 State Transition Diagram Gambar 3.4 Rancangan Layar Utama Gambar 3.5 Rancangan Layar Add Gambar 3.6 Rancangan Layar Edit Gambar 3.7 Rancangan Layar Delete Gambar 3.9 Rancangan Layar About Gambar 4.1 Tampilan Menu Utama Gambar 4.2 Menu Add Gambar 4.3 Tampilan Menu Add Gambar 4.4 Menu Edit/Delete Gambar 4.5 Menu Edit Gambar 4.6 Menu Delete Gambar 4.7 Tampilan Menu About
xii
9 9 12 13 15 15 30 33 35 40 49 50 51 53 54 55 55 57 58 59 60 61 62 62
DAFTAR LAMPIRAN Lampiran 1 Tabel Data Percobaan Lampiran 2 Listing Program
L.2 L.6
xiii
