penerapan algoritma ant colony untuk … · perangkat lunak dibangun pada platform android. ......

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.

PENERAPAN ALGORITMA ANT COLONY UNTUK TRAVELLING SALESMAN

PROBLEM PADA PERANGKAT BERGERAK

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

Rekomendasi Rute Kunjungan

Petunjuk Arah

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

Titik Keberangkatan Rute

1 2

3 4

5

Aplikasi

Map Request

Response

Koordinat GPS

SATELIT GPS

Ant Colony

Alur Meminta rute

Mencari Rute

terpendek

Recomendasi Rute terpendek

Mengirim Lokasi Awal

Alur Menjalankan Pengingat Lokasi

Mencari posisi pengguna

Cek kesamaan posisi

Memulai reminder

Muncul notifikasi

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

Rata-rata dengan GPS 24,5 meter tanpa GPS 388 meter

0

100

200

300

400

500

600

700

800

1 2 3 4 5

Selis

ih ja

rak

deng

an lo

kasi

se

bena

rnya

(da

lam

met

er)

Lokasi ke-n

TanpaGPS

DenganGPS

Performa Meminta Rekomendasi Rute

Uji coba performa dilihat dari waktu pengiriman dan respon balik ke user rata-rata waktu adalah 6 detik.

0

2

4

6

8

10

12

14

1 2 3 4 5 6 7 8 9 10

Wak

tu (

deti

k)

Uji coba ke-n

Waktu Respon

Waktu(detik)

Perbandingan Hasil Penghitungan Jarak

Uji coba dilakukan dengan membandingkan hasil perhitungan jarak TSP antara Ant Colony dan Genetic Algoritm.

0.00

20.00

40.00

60.00

80.00

100.00

120.00

140.00

160.00

180.00

10 20 30 40

Jara

k ya

ng d

ihas

ilkan

(K

M)

Jumlah Node

AntColony

GeneticAlgoritm

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.

Ant Colony Terima titik keberangkatan

dari server

Update semut dan feromon

Hitung jarak rute terbaik

sementara

Rute baru lebih baik

Kirim daftar rute ke klien

Inisialisai graph dan bobotnya,

inisialisasi semut, rute awal, feromon

dan waktu pencarian

Buat rute baru

Bandingkan panjang rute

terbaik sementara dengan rute baru

Set nilai rute terbaik

iya

Waktu habis

iya

tidak

tidak

Reminder Lokasi