OPTIMASI MULTI TRAVELLING SALESMAN PROBLEM (M-TSP) PADA MOBIL PATROLI POLISI DENGAN ALGORITMA HEURISTIC ASSIGNMENT FISHER-JAIKUMAR DAN ALGORITMA A*

Abstract

Perjalanan n mobil patroli (n>1) ke sejumlah m titik rawan (m>n) termasuk dalam m-TSP (Multi Travelling Salesman Problem). Makalah ini memaparkan penyelesaikan permasalahan m-TSP dengan mengelompokkan terlebih dahulu m-1 (m titik tanpa titik start) titik rawan ke dalam n sub tur, dan satu titik rawan hanya boleh menjadi anggota sebuah sub tur. Pengelompokkan ini menggunakan metode heuristic assignment FisherJaikumar. Selanjutnya masing-masing sub tur direpresentasikan dalam bentuk graf dan 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. Evaluasi hasil dilakukan dengan cara membandingkan dengan solusi semua kemungkinan. Perbandingan dilakukan pada lima kali uji coba menggunakan tujuh, delapan, sembilan, sepuluh dan sebelas titik rawan. Pada perhitungan total 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.