PENERAPAN ALGORITMA ANT COLONY UNTUK TRAVELLING SALESMAN PROBLEM PADA PERANGKAT BERGERAK
PRIYANKA GEMET ARISMOYO NRP 5109100178 Dosen Pembimbing I Henning Titi Ciptanigntyas S.Kom., M.Kom. Dosen Pembimbing II Erina Letivina Anggraini S.Kom., M.Kom.
Latar Belakang(1)
Latar Belakang(2)
Daftar lokasi ditulis di kertas Jika sudah dikunjungi, maka diberi tanda
Latar Belakang(3) Kurang mengenal daerah yang dikunjungi
Latar Belakang(4) Lokasi tidak bisa dikunjungi atau tidak dikunjungi
Solusi Pengingat Lokasi
Petunjuk Arah
Rekomendasi Rute Kunjungan
Rumusan Masalah
Bagaimana mengimplementasikan algoritma ant colony pada permasalahan TSP? Bagaimana menerapkan pengingat ketika user sudah berada di lokasi tujuan dan memberi tanda bahwa lokasi sudah dikunjungi? Bagaimana memberikan user rute baru ketika salah satu lokasi tujuan tidak bisa dikunjungi?
Tujuan Aplikasi
Membuat suatu aplikasi mobile dengan platform Android yang dapat mengingatkan pengguna tentang lokasi yang dikunjungi. Membantu salesman mendapat rekomendasi dalam mengunjungi semua lokasi.
Batasan Masalah
Perangkat lunak dibangun pada platform Android. Menggunakan Global Positioning System (GPS) yang terdapat pada perangkat berbasis Android. Peta yang digunakan berasal dari Google Maps. Algoritma yang diterapkan Ant Colony. Titik pembagian sudah ditetapkan terlebih dahulu. Pengguna aplikasi statis sehingga tidak bisa menambah pengguna.
Arsitektur Aplikasi
2
1
Rute
Titik Keberangkatan Aplikasi
3 Koordinat GPS
4 5 Response
SATELIT GPS
Map Request
Ant Colony
Alur Meminta rute
Mengirim Lokasi Awal
Mencari Rute terpendek
Recomendasi Rute terpendek
Alur Menjalankan Pengingat Lokasi
Memulai reminder
Muncul notifikasi
Mencari posisi pengguna
Cek kesamaan posisi
Lingkungan Uji Coba
Prosesor
Dual-core 1,0 GHz
RAM
512 MB RAM
Display
3.7 inchi
Sistem Operasi
Android 4.0.4
Merek
Sony Xperia Sola
Melihat Semua Lokasi
Melihat Lokasi pada Peta
Menambah Lokasi
Uji Coba Meminta Rute
Uji Coba Meminta Rute Ulang
Melihat Detail Lokasi
Meminta Petunjuk Arah
Reminder Lokasi
Akurasi Penentuan Posisi User
Selisih jarak dengan lokasi sebenarnya (dalam meter)
800 700 600
Tanpa GPS
500 400 300
Dengan GPS
200 100 0 1
2
3
4
Lokasi ke-n
5
Rata-rata dengan GPS 24,5 meter tanpa GPS 388 meter
Performa Meminta Rekomendasi Rute
Waktu Respon 14
12
Waktu (detik)
10
8
Waktu (detik)
6
4
2
0 1
2
3
4
5
6
7
Uji coba ke-n
8
9
10
Uji coba performa dilihat dari waktu pengiriman dan respon balik ke user rata-rata waktu adalah 6 detik.
Perbandingan Hasil Penghitungan Jarak
180.00 160.00 Jarak yang dihasilkan (KM)
140.00 120.00 100.00
Ant Colony
80.00
Genetic Algoritm
60.00 40.00 20.00 0.00 10
20
30
Jumlah Node
40
Uji coba dilakukan dengan membandingkan hasil perhitungan jarak TSP antara Ant Colony dan Genetic Algoritm.
Kesimpulan Algoritma Ant Colony telah dapat diimplementasikan pada aplikasi tugas akhir ini dengan waktu pemrosesan data dengan rata-rata 6 detik. Aplikasi dapat memberikan rekomendasi rute baru kepada user dengan menghilangkan lokasi yang telah dilewati maupun yang sengaja tidak dilewati. Penentuan posisi user dengan GPS memberi akurasi lebih baik dibandingkan dengan tanpa GPS.
Saran Pengembangan di kemudian hari bisa dimungkinkan memakai modul GPS yang khusus untuk navigasi sebagai penerima data lokasi. Agar lebih mudah dilakukan pengawasan terhadap petugas dari jarak jauh, perlu dikembangkan sistem berbasis web sehingga pemrograman di sisi server tidak hanya untuk memberi rekomendasi rute, tetapi juga bisa mengetahui lokasi yang dikunjungi.
Inisialisai graph dan bobotnya, inisialisasi semut, rute awal, feromon dan waktu pencarian
Rute baru lebih baik
iya
Hitung jarak rute terbaik sementara
Update semut dan feromon
Set nilai rute terbaik tidak
Waktu habis
Buat rute baru
Ant Colony
Bandingkan panjang rute terbaik sementara dengan rute baru
Terima titik keberangkatan dari server
iya Kirim daftar rute ke klien
tidak
Reminder Lokasi
