Jurusan Matematika

Fakultas Matematika dan Ilmu Pengetahuan Alam

Institut Teknologi Sepuluh Nopember

Surabaya

2011

Perancangan dan Pembuatan Sistem Navigasi Perjalanan Untuk Pencarian

Rute Terpendek Dengan Algoritma A* Berbasis J2ME

Oleh :

M. ARIEF HIDAYATULLOH

1204 100 071

Dosen Pembimbing :

Prof. Dr. M. Isa Irawan, MT

PENDAHULUAN

TINJAUAN

PUSTAKA

METODOLOGI

PENELITIAN

MENU UTAMA

UJI COBA dan

PEMBAHASAN

PENUTUP

Running Program

Pendahuluan1. Permasalahan lalu lintas pada suatu kota besar merupakan

persoalan yang cukup rumit untuk ditangani. Luasnya kota

dan banyaknya rute lalu lintas yang tersedia seringkali

menyulitkan pengguna jalan untuk mencari jalan atau rute

paling optimum dari segi jarak untuk pergi dari suatu tempat

ke tempat lain dalam kota.

2. Teknologi komunikasi bergerak (mobile commnunication)

khususnya perangkat seluler atau lebih dikenal dengan

sebutan handphone telah berkembang begitu pesat dari segi

kemampuan perangkat pendukung teknologinya, sehingga

saat ini perangkat selular tidak hanya menjadi sebuah

perangkat komunikasi.

3. Salah satu metode yang dapat digunakan untuk navigasi

perjalanan berbasis J2ME adalah menggunakan Algoritma

A Star. Dan untuk mendapatkan hasil yang terbaik

digunakan fungsi heuristik yang sesuai.

4. Tujuan dari tugas akhir ini adalah mengimplementasikan

sebuah program mobile yang standalone dan offline yang

berfungsi sebagai navigasi perjalanan dan panduan dalam

menentukan jalur atau rute yang memiliki total jarak terdekat

dalam suatu peta.

Tinjauan Pustaka

Bahasa Pemrograman Java

platform Java (Jeni , 2007)

• Pemrograman computer berbasis oop

• Berisfat platform independence

Tinjauan Pustaka (Lanjut)

Arsitektur J2ME (Mardiono T, 2006 )

• Subset dari J2SE (Java 2 Standard Edition)

• Embedded System

• 2 bagian penting J2ME yaitu:

1. Profile

2. Configuration

J2ME (Java 2 Micro Edition)

Tinjauan Pustaka (Lanjut)

MIDlet

Lifecycle / Siklus Hidup MIDlet

Tinjauan Pustaka (Lanjut)Graf

Graf didefinisikan sebagai himpunan pasangan dari

node (simpul) dan edge (sisi). Graf secara formal

didefinisikan sebagai himpunan pasangan (V, E).

Dituliskan sebagai:

G = {V, E}

Menurut arah dan bobot yang dimiliki oleh edge, maka

Graf (Diestel, Reinhard., 2000) dibedakan sebagai

berikut:

• Graf berarah dan berbobot.

• Graf berarah dan tidak berbobot

• Graf tidak berarah dan berbobot.

• Graf tidak berarah dan tidak berbobot.

Tinjauan Pustaka (Lanjut)

Dalam algoritma pencarian dikenal istilah’state’ yang berarti

kondisi. Kondisi akhir yang hendak dituju dikenal dengan

istilah ‘goal state’. Contoh state antara lain, dalam game

catur misalnya, adalah letak tiap buah catur pada papan.

Goal state dalam kasus ini biasanya kondisi raja ter-skak

mati.

Empat kriteria yang menjadi ukuran algoritma pencarian

adalah:

• Completeness : apakah algoritma pasti dapat

menemukan solusi (bila memang ada solusi)?

• Time Complexity: berapa lama waktu yang dibutuhkan

untuk menemukan sebuah solusi?

• Space Complexity: berapa memori atau resource yang

diperlukan untuk melakukan pencarian?

• Optimality: apakah algoritma tersebut dapat menemukan

solusi yang terbaik jika terdapat beberapa solusi yang

berbeda?

Algoritma Pencarian (Search Algorithms)

Tinjauan Pustaka (Lanjut)

Uninformed Search adalah pencarian solusi tanpa

adanya informasi yang dapat „mengarahkan‟

pencarian untuk mencapai goal state dari current state

(state sekarang). Informasi yang ada hanyalah definisi

goal state itu sendiri, sehingga algoritma dapat

mengenali goal state bila menjumpainya.

Beberapa contoh algoritma yang termasuk Uninformed

Search antara lain adalah: Breadth Search, Uniform

Cost Search, Depth First Search, Depth Limited

Search Iterative Deepening Search dan Bidirectional

Search.

Uniformed Search / Blind Search

Tinjauan Pustaka (Lanjut)

Informed Search mempunyai informasi tentang cost /

biaya untuk mencapai goal state dari current state.

Dengan informasi tersebut, Informed search dapat

melakukan pertimbangan untuk mengembangkan atau

memeriksa node-node yang mengarah ke goal state.

Informed Search juga disebut Heuristic search karena

untuk menghitung (perkiraan) cost ke goal state,

digunakan fungsi heuristic. Funsi Heuristic berbeda

dengan algoritma, dimana heuristic lebih merupakan

perkiraan untuk membantu algoritma, dan tidak harus

valid setiap waktu.

Beberapa contoh algoritma pencarian yang

menggunakan metode Informed Search adalah: Best

first Search, Greedy Search, A* (A Star) search, dan

Hill Climbing Search.

Informed Search /Heuristic Search

Tinjauan Pustaka (Lanjut)

Pengembangan dari Best First Search Algorithm, A*

Search Algorithm menghindari dilebarkannya (expanding)

node yang diketahui memiliki biaya (cost) mahal atau

besar.

Metode A* Search Algorithm digunakan fungsi evaluasi

sebagai berikut: (Russell & Norvig, 1995)

f (n) = g(n) + h(n)

Keterangan :

• g(n) adalah biaya (cost) yang dibutuhkan oleh sebuah

jalur (path) untuk node dari node awal.

• h(n) adalah estimasi biaya (cost) sebuah jalur (path).

• f(n) adalah estimasi total biaya (cost) sebuah jalur

(path) dari node awal ke node tujuan (goal) melalui

node .

Metode A* (A Star) Search Algorithm

Metodologi Penelitian

Metode pengumpulan data yang digunakan pada penyusunan

Tugas Akhir ini adalah sebagai berikut :

Observasi Observasi yang dilakukan pada penyusunan tugas akhir ini

adalah mencari referensi mengenai bentuk-bentuk mobile apllication

sebagai navigasi perjalanan.

Studi PustakaStudi pustaka dalam penyusunan Tugas Akhir ini yaitu dengan

mencari peta Surabaya dan buku yang membahas cara pembuatan

Mobile Application menggunakan bahasa pemrograman Java.

1. Hierarki.

2. Input

3. Proses

4. Output

Metode Pengumpulan Data

Hierarki perancangan Input Proses Output (HIPO)

Metodologi Penelitian (lanjut)Deskripsi Sistem

Aplikasi merupakan sebuah sistem navigasi perjalanan kota

surabaya yang dirancang untuk memberikan kemudahan dan layanan

yang murah kepada pengguna jalan dalam mencari jalan terpendek.

Pengguna aplikasi juga dapat mengetahui rute terpendek yang dilalui

dengan bantuan peta. Deskripsi sistem meliputi :

1. Deskripsi subsistem peta surabaya

Dalam subsistem peta pengguna dapat memasukkan input titik

awal dan titik tujuan, disamping itu pengguna dapat men-drag /

menggeser peta.

2. Deskripsi subsistem algoritma A star

Setelah pengguna memberikan input subsistem algoritma A star

akan langsung memproses pencarian rute terpendek yang akan

ditampilkan pada subsistem peta.

3. Deskripsi subsistem show result

Show result adalah sebuah proses dimana pencarian rute yang

ditampilkan akan di konversi menjadi sebuah informasi tentang

jalan terurut dari input titik awal sampai titik tujuan.sistem ini akan

berjalan setelah pengguna selesai mencari rute yang diinginkan.

4. Deskripsi subsistem search

Search adalah sebuah proses yang dilakukan oleh pengguna untuk

mencari informasi tentang jalan dan lokasi tertentu.

5. Deskripsi subsistem help

Metodologi Penelitian (lanjut)Spesifikasi AplikasiAplikasi yang dibuat memiliki kemampuan sebagai berikut

1. Menampilkan peta jalan-jalan surabaya beserta sebagian tempat-

tempat penting.

2. Menampilkan informasi urutan rute yang dicari.

3. Menampilkan navigasi peta seperti mencari lokasi dan jalan.

4. Mendukung aplikasi touchscreen, sehingga proses navigasi bisa

dilakukan dengan klik.

Spesifikasi PenggunaMobile Application ini ditujukan untuk digunakan untuk semua pihak

yang ingin melakukan perjalanan dan mencari rute terpendek yang

dapat dilalui di kota surabaya.

Metodologi Penelitian (lanjut)Pencarian Rute Terpendek pada Aplikasi Navigasi

Perjalanan

Metodologi Penelitian (lanjut)Activity diagram Aplikasi

Metodologi Penelitian (lanjut)Class Diagram Aplikasi

Terdapat delapan Class Diagram aplikasi beserta hubungan

asosiasi antar kelas, yaitu:

Metodologi Penelitian (lanjut)

Rancangan Desain Antarmuka

Perancangan antarmuka adalah proses membuat perancangan

form-form tampilan layar pada mobile device yang akan

diaplikasikan.

Form Antarmuka Utama Form antarmuka menu Utama

Form Antarmuka Form Input Desain Antarmuka Form Search

Uji Coba dan Pembahasan

1. Desain Pembuka Aplikasi

2. Desain Utama Aplikasi

Implementasi Program

Uji Coba dan Pembahasan (lanjut)

3. Desain Tampilan Input

4. Desain Tampilan Search

Implementasi Program (Lanjut)

Uji Coba dan Pembahasan (lanjut)

5. Desain Tampilan Cari Rute

6. Desain Tampilan Info Path dan Help

Implementasi Program (Lanjut)

Uji Coba dan Pembahasan (lanjut)Pengujian pada emulator

Pengujian aplikasi akan dilakukan pada beberapa emulator yang

mendukung aplikasi touchscreen pada ponsel yaitu dengan konfigurasi

CLDC 1.1 dan profile MIDP 2.1.

Beberapa emulator platform yang akan menjadi lingkungan uji coba

aplikasi yaitu:

1. Java (tm) ME SDK 3.0 (emulator Standar)

2. S60 5th SDK v0.9

Pengujian yang dilakukan akan meliputi pengujian tampilan pada

masing-masing platform emulator beserta menu-menu yang ada dan

pengujian pencarian jarak terpendek pada program.

Uji Coba dan Pembahasan (lanjut)• Pengujian pada emulator Java ME SDK 3.0

Uji coba pada paltform java ME SDK 3.0 menggunakan device

“DefaultTouchPhone1” berjalan dengan lancar dan baik. Dengan

resolusi layar 320 x 240 pixel tampilan pada semua gambar

merata.

Uji Coba dan Pembahasan (lanjut)• Pengujian pada emulator S60

Uji coba pada platform S60 5th SDK v9.0 menggunakan device default

dapat berjalan pada ponsel yang berkonfigurasi CLDC 1.1 dan MIDP

2.1. Emulator ini bisa digunakan untuk Nokia 5800, N97, 5530, C6,

5230, X6 and Samsung I8910

Tampilan layar pada emulator ini beresolusi 360 x 640 pixel sehingga

peta yang ditampilkan akan lebih besar. Namun load program cukup

lama sekitar 7 detik dikarenakan emulator ini di setting semirip mungkin

dengan aplikasi ponsel sebenarnya yang memiliki memori yang kecil.

PenutupKesimpulan :Dari hasil uji coba yang telah dilakukan dapat diambil beberapa kesimpulan

sebagai berikut :

1. Program aplikasi navigasi perjalanan dapat dijadikan oleh pengguna jalan

sebagai alternatif murah dalam menentukan jarak terpendek dan menemukan

lokasi dalam kota.

2. Pencarian jarak terpendek dengan menggunakan algoritma A* selalu dapat

menemukan solusi rute yang optimal berdasarkan jarak terpendek, apabila

memang terdapat rute dari titik awal ke tujuan.

3. Program aplikasi ini hanya dapat menampilkan peta jalan-jalan besar di kota

Surabaya dan merupakan aplikasi stand alone yang tidak mendukung data

eksternal.

4. Program aplikasi panduan rute dapat dijalankan pada ponsel yang

mendukung java MIDP 2.1.

Saran :Dari hasil yang telah dicapai dalam penelitian tugas akhir ini, terdapat beberapa

hal yang perlu dipertimbangkan untuk melakukan pengembangan pada penelitian

ini, diantaranya sebagai berikut :

1. Perlu dilakukan pengembangan berupa penambahan fasilitas dari aplikasi

supaya dapat mendukung penggunaan aplikasi dan penyampaian informasi.

2. Untuk menambahkan peta yang lebih lengkap dan detail, maka Tugas Akhir

ini dapat dilanjutkan dengan metode Client Server.

Daftar Pustaka1. Feng Y, Zhu J.,(2001), Wireless Java Programming with Java 2 Micro

Edition, SAMS, Indianapolish.

2. Hartanto 1, A. A., (2003), Java 2 Micro Edition Mobile Interface Device

Programming, PT. Elex Media Computindo, Jakarta.

3. Mardiono, T., (2006), Membangun Solusi Mobile Business dengan Java,

Jakarta: PT. Elex Media Komputindo.

4. Russel, Stuart J., dan Norvig, Peter, (1995), Artificial Intellegence : A

Modern Approach, New Jersey : Prentice Hall.

5. Budi R, Imam H dan Arif H.,(2007), Mudah Belajar Java. Bandung :

Informatika Bandung.

6. Yuniar, Supardi,(2008), Pemrograman Handphone dengan J2ME, PT elex

Media Komputindo. Jakarta.

7. Diestel, Reinhard., (2000), Graph Theory: Electronic Edition 2000,

http://www.math.unihamburg.de/home/diestel/books/graph

8. Lester, Patrick., (2005), A* Pathfinding for Beginners,

http://www.gamedev.net/reference/article/article2003.asp

Sekian

Terimah Kasih