Penentuan Rute Perjalanan Multi Travelling Salesman Problem (m-TSP) pada Mobil Patroli Keamanan Polisi dengan Metode Heuristic Assignment Fisher-Jaikumar dan Algoritma A*
| Main Author: | SantiDwiNurhumam |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | eng |
| Terbitan: |
, 2007
|
| Subjects: | |
| Online Access: |
http://repository.ub.ac.id/151632/1/050702102.pdf http://repository.ub.ac.id/151632/ |
Daftar Isi:
- Perjalanan n mobil patroli (di mana n lebih dari satu) ke sejumlah m titik rawan (di mana m lebih dari n) dengan asumsi titik (1) sebagai kantor polisi (tempat keberangkatan semua mobil patroli) termasuk dalam m-TSP (Multi Travelling Salesman Problem). Dalam tugas akhir ini akan dibangun sebuah perangkat lunak yang mampu menyelesaikan permasalahan tersebut dengan mengelompokkan terlebih dahulu m-1 (kecuali titik rawan (1)) titik rawan ke dalam n sub tur, di mana satu titk rawan hanya boleh menjadi anggota sebuah sub tur. Pengelompokkan ini menggunakan metode heuristic assignment Fisher-Jaikumar. Selanjutnya masing-masing sub tur direpresentasikan dalam bentuk graf, lalu dilakukan optimasi pencarian rute berdasarkan jarak pada masing-masing sub tur menggunakan algoritma A*, hasilnya berupa rute yang harus ditempuh oleh masing-masing mobil patroli. Untuk mengevaluasi hasil dari metode yang digunakan, dilakukan perbandingan dengan hasil perhitungan pada semua kemungkinan. Perbandingan dilakukan pada lima kali uji coba menggunakan tujuh, delapan, sembilan, sepuluh dan sebelas titik rawan. Pada perhitungan jarak menggunakan metode heuristic assignment Fisher-Jaikumar dan algoritma A* menghasilkan galat rata-rata sebesar 20,43% dari jarak minimum sebenarnya. Sedangkan waktu pemrosesannya jauh lebih cepat untuk jumlah titik rawan lebih dari tujuh daripada dengan menghitung semua kemungkinan. .