BAB I PENDAHULUAN. menganalisa rute mana yang di anggap tepat dengan memakan waktu relatif singkat,

1

BAB I PENDAHULUAN 1.1 Latar Belakang Pencarian rute sangat erat kaitannya dengan pencarian suatu lokasi dalam sebuah pemetaan. Ketika seseorang ingin menuju ke suatu lokasi, orang tersebut akan menganalisa rute mana yang di anggap tepat dengan memakan waktu relatif singkat, dalam hal ini adalah lokasi rumah sakit. Rumah sakit merupakan tempat yang akan dituju oleh ketika akan memerlukan pertolongan medis dengan cepat. Pada saat ini handphone menjadi hal yang tidak dapat ditinggalkan dalam kegiatan sehari-hari. Seiring perkembangannya, teknologi mobile tidak hanya digunakan untuk berkomunikasi ataupun mengirim pesan singkat, tetapi dapat juga dimanfaatkan untuk membantu aktifitas sehari-hari, seperti mencari lokasi dengan layanan GPS. Android menjadi salah satu sistem operasi yang paling banyak digunakan pada jenis smartphone saat ini. Kelebihan pada sistem operasi ini ialah bersifat open source, sehinnga memungkinan para pengembang menciptakan aplikasi untuk digunakan pada smartphone. Di dalam suatu aplikasi tidak akan terlepas dari proses pengembangan dan metode algoritma untuk proses menjalankannya. Algoritma dapat didefinisikan sebagai langkah-langkah logis dan sistematis dalam mencari suatu solusi dari permasalahan yang ada. Pemecahan suatu masalah pada hakekatnya adalah 1

2

menemukan langkah-langkah tertentu yang jika dijalankan akan bisa memecahkan masalah, dalam hal ini adalah algoritma untuk menemukan jalur terpendek. Ada beberapa metode algoritma untuk menemukan jalur terpendek, antara lain algoritma A star dan algoritma shooting star. Algoritma A star merupakan algoritma pencarian untuk graph. Ciri dari algoritma ini adalah fungsi heuristik (h(x)) yang mempertimbangkan jarak untuk menentukan urutan dimana pencarian mengunjungi simpul dalam graph. Sedangkan algoritma shooting star merupakan algoritma pencarian dalam graph. Algoritma ini hampir sama dengan algoritma A star, yang membedakannya adalah dalam setiap pencarian algoritma shooting star akan mencari sisi yang terdekat bukan simpul. Sedangkan metode pengembangan perangkat lunak dalam hal ini digunakan adalah model proses Spiral. Model pengembangan ini membagi spiral ke dalam empat sektor yang masing-masing mewakili aktifitasnya, adapun empat aktifitas pada model proses spiral antara lain, perencanaan, analsis resiko, produk rekayasa, dan evaluasi pengguna. Dari uraian latar belakang di atas maka penulis mengambil judul“ Implementasi Algoritma A star dan Shooting-star Dalam Pencarian Rute Terpendek Pemetaan Rumah Sakit di Kota Palembang Berbasis Android”.

3

1.2 Perumusan Masalah Dari uraian latar belakang, peneliti merumuskan masalah “bagaimana melakukan perhitungan dengan menggunakan algoritma A star dan algoritma shooting star dalam menentukan pengambilan jalur untuk memutuskan rute terpendek menuju lokasi rumah sakit.

1.3

Batasan Masalah Pada penelitian ini akan membatasi masalah sebagai berikut :

a. Kawasan pemetaan rumah sakit yang yang dijadikan titik lokasi pencarian adalah rumah sakit di kota Palembang. b. Rute jalan yang digunakan di anggap jalan bebas hambatan atau tanpa kemacetan dan hanya jalan utama , tidak termasuk jalan-jalan kecil / gang. c. Pencarian jalur mengunakan perhitungan algoritma A star dan algoritma shooting-star. d. Pada penelitian ini peneliti mengambil 3 (tiga) titik akhir lokasi rumah sakit dan 3 (tiga) lokasi titik awal e. Pembuatan perangkat lunak ini menggunakan bahasa pemrograman Java. f. Peta yang digunakan adalah peta Google Maps.

4

1.4 Tujuan dan Manfaat Penelitian 1.4.1 Tujuan Penelitian Tujuan penelitian ini adalah melakukan perhitungan dengan menggunakan algoritma A star dan algoritma shooting star dalam pengambilan jalur untuk menentukan rute terpendek menuju lokasi rumah sakit yang akan diimplementasikan ke dalam perangkat smartphone android. 1.4.2 Manfaat Penelitian Manfaat yang diharapkan pada penelitian ini adalah : a. Diharapkan memberikan pengetahuan mengenai algoritma pencarian rute A star dan algoritma shooting-star. b. Membantu pengguna dalam menganalisa rute terpendek dalam menuju lokasi rumah sakit dengan perhitungan algoritma A star dan algoritma Shooting star.

1.5 Metodologi Penelitian 1.5.1 Tempat dan Waktu Penelitian Penelitian ini dilakukan di Kota Palembang Sumatera Selatan, yang terletak diantara 2o 52, sampai 3o 5, Lintang Selatan dan 104o 37, sampai 104o 52, bujur timur dengan luas wilayah Kota Palembang sebesar 400,61 km2 . Penelitian ini dimulai sejak bulan Oktober 2015 sampai dengan bulan Desember 2015.

5

1.5.2 Alat dan Bahan Adapun alat dan bahan yang digunakan peneliti dalam melaksanakan penelitian ini adalah sebagai berikut: a. Perangkat Keras (Hardware) Hardware yang peneliti gunakan adalah laptop dengan OS windows 7 dengan spesifikasi core i3 1.50 GHz, RAM 2 Gb, dan Hardisk 500Gb. b. Perangkat Lunak (Software) Software yang peneliti gunakan adalah sebagai berikut: a. Microsoft Windows 7. b. Java(jdk-6u22-windows-i586) sebagai aplikasi pendukung pemrograman android c. Android SDK (Sofware Development Kit) sebagai pemrograman android. d. Eclipse Juno v. 23 IDE for Java Developers sebagai aplikasi desain android e. Microsoft Word 2010 f. MySQL sebagai database aplikasi g. PHP sebagai service penghubung android dan MySQL .1.5.3 Metode Pengumpulan Data a. Dokumentasi Metode Dokumentasi adalah mencari data mengenai hal-hal atau variable yang berupa catatan, transkrip, buku, surat kabar, majalah, prasasti, notulen rapat, lengger, agenda, dan sebagainya. (Prof. Dr. Suharsimi Arikunto, 2010 : 274).

6

b. Observasi Metode Observasi adalah suatu usaha sadar untuk mengumpulkan data yang dilakukan secara sistematis, dengan prosedur yang berstandar. (Prof. Dr. Suharsimi Arikunto, 2010 : 265). Disini peneliti memastikan beberapa lokasi rumah sakit yang akan dijadikan sebagai titik tujuan lokasi pencarian dengan melihat langsung ke lapangan serta melalui website dan google maps. 1.5.4 Metode Penelitian Pada penelitian ini peneliti menggunakan metode deskriptif dengan penelitian komparasi. Menurut Dra. Aswani penelitian komparasi akan dapat menemukan persamaan-persamaan dan perbedaan tentang benda-benda, tentang orang, tentang prosedur kerja, tentang ide-ide, kritik terhadap orang, kelompok, terhadap suatu ide atau suatu prosedur kerja. Dapat juga membandingkan kesamaan pandangan dan perubahan-perubahan pandangan orang, grup atau negara, terhadap kasus, terhadap orang, peristiwa atau terhadap ide-ide. (Prof. Dr. Suharsimi Arikunto, 2010:310). 1.5.5 Metode Pengembangan Perangkat Lunak Metode pengembangan perangkat lunak yang digunakan pada pembuatan aplikasi ini adalah Spiral model. Pengembangan sistem model Spiral adalah pengembangan yang mengadopsi fitur penting milik model Waterfall dan Prototyping. Meskipun demikian model ini memiliki fitur tersendiri yang tidak dimiliki oleh model-model yang menjadi rujukannya (Eddy Prahasta, 2014:476).

7

Model pengembangan ini membagi spiral ke dalam empat sektor yang masingmasing mewakili aktifitasnya. Adapun empat aktifitas sebagai berikut: 1. Perencanaan Disini peneliti mengumpulkan data mengenai akses jalan yang dijadikan sebagai rute menuju lokasi rumah sakit dan menentukan beberapa lokasi yang akan dijadikan sebagai titik awal pencarian. 2. Analisis Resiko Analisa resiko pada penelitian ini perhitungan jarak antar pengambilan simpang pada google maps dan perhitungan langsung ke lapangan yang dijadikan sebagai node pada perhitungan algoritma. 3. Produk rekayasa (pengembangan produk) Dari data dan bahan seta rancangan pehitungan dengan algoitma selesai dilakukan, padan tahap ini proses pengimplementasian ke perangkat smartphone akan dilakukan. 4. Evaluasi pengguna Pada tahap ini proses dimana pengujian pada perangkat lunak akan dilakukan.

1.6 Sistematika Penulisan Dalam penulisan Tugas Akhir ini yang merupakan laporan hasil penelitian, direncanakan terdiri dari lima bab, masing-masing bab berisi :

8

BAB I

: PENDAHULUAN Dalam bab ini akan diuraikan secara ringkas pembahasan tentang latar belakang, perumusan masalah, batasan masalah, tujuan dan manfaat penelitian, metode penelitian, dan sistematika penulisan.

BAB II

: LANDASAN TEORI Dalam bab ini akan membahas tentang teori-teori yang mendukung untuk melaksanakan penelitian seperti penelitian-penelitian yang sudah pernah dilakukan sebelumnya mengenai pencarian rute dengan Algoritma A star dan Shoting-star. Dalam bab ini juga diuraikan teori mengenai dasar-dasar dan konsep pemrograman Android.

BAB III

: ANALISIS DAN PERANCANGAN Pada bab ini dijelaskan dan diuraikan mengenai algoritma A star dan algoritma Shooting-star dalam perhitungan dalam menentukan jalur yang akan di simpulkan sebagai rute terpendek menuju lokasi dan perancangan sistem yang juga disertai komponen-komponen perangkat lunak dalam membangun aplikasi berbasis Android.

BAB IV

: HASIL DAN PEMBAHASAN Pada bab ini menguraikan tentang hasil perhitungan dengan algoritma A star

dan

algoritma

Shoting-star

dan

pengujian

pengimplementasian pada perangkat smartphone Android.

dalam

9

BAB V

: KESIMPULAN DAN SARAN Bab terakhir ini berisi tentang kesimpulan atau ringkasan dari penelitian perancangan Perangkat Lunak dengan menggunakan perhitungan algoritma A star dan Shooting-star dengan memanfaatkan metode pengembangna Spiral. Serta akan memberikan saran mengenai penelitian yang akan dilakukan selanjutnya.

10

BAB II TINJAUAN PUSTAKA 2.1 Tinjauan Umum 2.1.1 Letak Geografis Kota Palembang Palembang merupakan salah satu kota metropolitan di Indonesia dan secara geografis terletak diantara 2o 52, sampai 3o 5, Lintang Selatan dan 104o 37, sampai 104o 52, bujur timur dengan ketinggian rata-rata 8 meter dari permukaan laut. Luas wilayah Kota Palembang sebesar 400,61 km2 yang secara administrasi terbagi atas 16 kecamatan dam 107 kelurahan. Kota Palembang merupakan ibukota Provinsi Sumatera Selatan dengan batas wilayah yaitu sebelah utara, timur, dan barat dengan Kabupaten banyu asin, sedangkan sebelah selatan berbatasan dengan Muara Enim.

2.2 Landasan Teori 2.2.1 Pengenalan Android Android adalah system operasi untuk perangkat mobile berasis sistem operasi linux yang mencakup sistem operasi, middleware dan aplikasi. Android menyediakan platform terbuka bagi para pengembang untuk menciptakan aplikasi mereka. Awalnya, Google Inc. membeli Android Inc. yang merupakan pendatang baru yang membuat piranti lunak untuk ponsel/smartphone. Kemudian untuk mengembangkan Android, dibentuknya Open Handset Alliance, konsorsium dari 34 perusahaan piranti 10

11

keras, peranti lunak, dan telekomunikasi, termasuk Google. HTC, Intel, Motorola, Qualcomm, T-Mobile, dan Nvidia. Pada saat iniperilisan perdana Android, 5 November 2007, Android bersama Open Handset Alliance menyatakan mendukungpengembangan open source pada perangkat mobile. Di lain pihak, Google merilis kode-kode Android di bawah lisensi Apache, sebuah lisensi perangkat lunak dan open platform perangkat selular. Di dnia ini terdapat dua jenis distributor sistem operasi Android. Pertama yang mendapat dukungan penuh dari Google atau Google Mail Services (GMS) dan kedua adalah yang benar-benar bebas distribusinya tanpa dukungan langsung dari Goolge atau dikenal dengan Open Handset Distribution (OHD). (Nazruddin Safaat, 2014). 2.2.2 Google Maps Google Maps adalah peta online atau membuka peta secara online, dapat dilakukan dengan mudah melalui layanan gratis dari Google. Bahkan layanan ini menyediakan API (Aplication Programming Interface) yang memungkinkan Developer lain memanfaatkan aplikasi ini di aplikasi buatannya. Tampilan Google Maps pun dapat dipilih, berdasarkan foto asli atau peta gambar rute saja. Google Maps adalah layanan gratis yang diberikan oleh Google Maps dan sangat popular. Google Maps adalah suatu peta dunia yang dapat kita gunakan untuk melihat suatu daerah. Dengan kata lain, Google Maps merupakan suatu peta yang dapat dilihat dengan menggunakan browser. Kita dapat menambahkan fitur Google Maps dalam web yang telah kita buat atau pada blog yang berbayar maupun gratis

12

sekalipun dengan Google Maps API. Google Maps API adalah suatu library yang berbentuk javascript. 2.2.3 Global Positioning System (GPS) GPS adalah singkatan dari Global Positioning System, yang merupakan sistem navigasi menggunakan teknologi satelit yang dapat menerima sinyal dari satelit. Sistem ini menggunakan 24 satelit yang mengirimakn sinyal gelombang mikro ke bumi. Sinyal ini diterima oleh laat penerima (receiver) di permukaan, dimana receiver ini akan mengumpulkan informasi dari satelit GPS seperti : a. Waktu. GPS receiver menerima informasi waktu dari jam atom yang mempunyai keakurasian sangat tinggi. b. Lokasi. GPS memberikan informasi dalam tiga dimensi : Latitude, Longitude dan Elevasi. c. Kecepatan. Ketika berpindah tempat, GPS dapat menunjukkan informasi kecepatan berpindah tersebut. d. Arah perjalanan. GPS dapat menunjukkan arah tujuan. e. Simpan lokasi. Tempat-tempat yang sudah pernah atua ingin dikunjungi bisa disimpan oleh GPS receiver. f. Komunikasi data. GPS receiver dapat menyimpan informasi track, seperti total perjalanan yang sudah pernah dilakukan, kecepatan rata-rata, kecepatan paling tinggi, kecepatan paing rendah, waktu/jam sampai tujuan, dan sebagainya. (Wishnu, 2012).

13

2.2.4 Android SDK (Software Develoment Kit) Android SDK adalah Tools API (Aplication Programming Interfaces) yang diperlukan untuk memulai pengembangan aplikasi pada platform Android menggunakan bahasa pemrograman Java. Android merupakan subset perangkat lunak untuk ponsel yang meliputi system operasi, middleware dan aplikasi kunsi yang direlase oleh Google. Saat ini disediakan Android SDK (Software Develoment Kit) sebagai alat bantu dan API untuk mulai pengembangan aplikasi pada platform Android menggunakan bahasa pemrograman Java. Sebagai aplikasi-netral, Android memberi anda kesempatan untuk membuat Aplikasi yang kita butuhkan yang bukan merupakan aplikasi bawaan Handphone/Smartphone. Beberapa fitur Android yang penting adalah : a. Framework Aplikasi yang mendukung penggantian komponen dan reusable. b. Mesin Virtual Dalvik dioptimalkan untuk perangkat mobile. c. Integrated Browser berdasarkan engine open source Webkit. d. Grafis yang dioptimalkan dan didukung oleh libraries grafis 2D, grafis 3D berdasarkan spesifikasi opengl ES 1,0 (opsional akselerasi hardware). e. SQLite untuk menyimpan data. f. Media Suport yang mendukung audio, video, dan gambar (MPEG4, H.264, MP3, AAC, AMR, JPG, PNG, GIF), GSM Telephony (tergantung hardware). g. Bluotooth, EDGE, 3G, WiFi (tergantung hardware). h. Kamera, GPS, kompas, accelerometer (tergantung hardware).

14

i. Lingkungan Development yang lengkap dan kaya termasuk perangkat emulator, tools untuk debugging, profil, dan kinerja memori, dan plugin untuk IDE Eclipse. (Nazruddin Safaat, 2014). 2.2.5 ADT (Android Development Tools) Android Development Tools (ADT) adalah plugin yang didesain untuk IDE Elipse yang memberikan kita kemudahan dalam mengembangan aplikasi android dengan menggunakan IDE Eclipse. Dengan menggunakan ADT untuk Eclipse akan memudahkan kita dalam membuat aplikasi project android, membuat GUI aplikasi, dan menambahkan komponen-komponen yang lainnya, begitu juga kita dapat melakukan running aplikasi menggunakan Android SDK melalui Eclipse. Dengan ADT juga kita dapat melakukan pembuatan package android (.apk) yang digunakan untuk distribusi aplikasi android yang kita rancang. (Nazruddin Safaat, 2014) 2.2.6 Algoritma A star A* merupakan bentuk yang paling dari Best First Search (BFS). A* mengevaluasi node dengan menggabungkan g(n), yaitu cost untuk mencapai node, dan h(n), yaitu cost yang diperlukan dari node untuk mencapai tujuan, sehingga: f(n) = g(n) + h(n) g(n) merupakan cost suatu path dari node awal ke node n, dan h(n) adalah perkiraan cost terendah dari node n ke tujuan. f(n) adalah perkiraan solusi dengan cost termurah melalui n.

15

Dengan demikian, untuk menemukan solusi termurah, hal yang pertama yang dicoba adalah node dengan nilai g(n)+h(n) terendah. Strategi ini jelas lebih baik dengan disediakannya fungsi heuristik h(n) yang dapat memenuhi kondisi tertentu sehingga A* menjadi optimal. Perlu disadari bahwa algoritma Dijsktra adalah subset dari algoritma A*. Dalam A*, akan dihitung perkiraan total cost dari node dengan menambahkan nilai heuristik pada cost sejauh ini. A* kemudian memilih sebuah node untuk diproses berdasarkan nilai tersebut. Jika heuristik selalu menghasilkan 0, maka perkiraan total cost selalu akan sama dengan cost sejauh ini. Saat A* memilih node dengan perkiraan total costterkecil, node dengan cost sejauh ini terkecil dipilih. Hal ini sangat mirip dengan Dijkstra. A* dengan heuristik adalah versi pathfinding dari Dijkstra. function A* (start, goal) closedset :- the empty set / / the set of nodes already evaluated openset := (start) / / The set of tentative nodes tobe evaluated / / initially containing the start node came_from := the empty map g_score [start] := 0; / / cost from start along best know path / / estimated total cost from start to goal throught f_score := g_score + heuristic_cost_estimate (start, goal) while openset is not empty current := the node in openset havong the lowes f_score[] value if current = goal return reconstruc_path(came_from, goal) remove current from openset add current to closedset for each neighbor in neighbor_nodes (current) if neighbor in closedset continue

16

tentative_g_score := g_score [current] + dist_between [current,neighbor] if neighbor not in openset or Tentative_g_score <= g_score[neighbor] came_from[neighbor] := current g_score[neighbor] := tentative g_score f_score[neighbor] := g_score [neighbor] + heuristic_cost_estimate(neighbor,goal) if neighbor not in openset add neigbor to openset / / end of while return failure end of function function reconstruct_path (came_from, current_node) if came_from[current_node in set p := reconstruct_path(came_from, came_from[current_node] return (p+current_node) else Return current_node / /end of function

Gambar 2.1 Pseucode Algoritma A* 2.2.6.1 Sejarah Algoritma A* Algoritma A* yang menggabungkan cost path saat ini dengan heuristic search, dikembangkan oleh Hart, Nilsson, dan Raphael, dengan beberapa koreksi lanjutan. Dechter dan Pearl mendemonstrasikan efisiensi secara optimal dari A*. Tulisan mengenai A* yang asli memperkenalkan kondisi konsistensi pada fungsi heuristik. Kondisi onoton diperkenalkan oleh Pohl sbagai pengganti yang lebih sederhana, namun Pearl menunjukkan bahwa keduanya ekuivalen. Pohl mempelopori pembelajaran tentang hubungan antara galat (error) dalam fungsi heuristik dengan kompleksitas waktu A*. Hasil dasar yang diperoleh untuk tree search dengan unit steps costs dan node tujuan jamak. “Effective branching

17

factor” diusulkan oleh Nilsson sebagai pengukuran empiris dan efisiensi; ekuivalen dengan mengasumsikan time cost dari O((b)^d). Karena tree search diaplikasikan pada graf, Kort et al. menentang bahwa tie cost lebih baik dimodelkan sebagai O(b^(d-k)), dimana k tergantung pada akurasi heuristik; sehingga analisis ini menghasilkan beberapa kontroversi. Untuk graph search, Helmert dan Roger mencatat beberapa permasalahan yang terkenal yang mengandung banyak node secara eksponen dalam path solution optimal, menyiratkan kompleksitas waktu eksponen untuk A* bahkan dengan galat mutlak konstan pada h. 2.2.6.2 Langkah-Langkah Algoritma A* Algoritma ini bekerja dengan cara yanag mirip dengan Dijkstra. Daripada mempertimbangkan open node dengan nilai cost sejauh ini terendah, node yang paling mungkin untuk menuju path terpendek secara keseluruhan dipilih yang dikendalikan oleh heuristik. Jika heuristik akurat, maka algorita tersebut akan efisien. Jika heuristik tidak tepat, maka algoritma akan bekerja lebih buruk dari Dijkstra. Berikut merupakan langkah-langkah algoritma A*. a. Memproses Current Node Selama iterasi, A* mempertimbangkan setiap koneksi yang keluar dari current node. Untuk setiap koneksi, A* menemukan end node dan menyimpan total cost dari path sejauh ini dan koneksi yang sampai ke sana, sama seperti sebelumnya. Sebagai tambahan, A* menyimpan satu nilai lagi:

18

perkiraan dari cost total untuk sebuah path dari start node menuju current node dan menuju tujuan (selanjutnya disebut perkiraan total cost). Perkiraan ini merupakan jmlah dari dua nilai: cost sejauhini dan seberapa jauh dari node tersebut hingga tujuan. perkiraan ini dihasilkan dari potongan kode yang terpisah dan bukan bagian dari algoritma tersebut. Perkiraan-perkiraan ini disebut “nilai heuristik” dari suatu node, dan nilainya tidak dapat negatif (karena cost dalam graf tidak negatif, dan tidak masuk akal jika perkiraan negatif). Penggenerasian dari nilai heuristik adalah perhatian utama dalam mengimplementasikan algoritma A*. b. Node List Seperti sebelumnya, algoritma ini menyimpan daftar dari open node yang telah dikunjungi namun belum diproses dan closed node yang telah diproses. Node dipindahkan ke open list saat mereka ditemukan pada ujung koneksi. Node dipindahkan ke closed list setelah diproses dalam iterasi masing-masing. Tidak seperti sebelumnya, node dari open list dengan perkiraan total cost terkecil dipilih pada setiap iterasi, yang hampir selalu berbeda dengan cost terkecil sejauh ini. Perubahan ini mengijinkan algoritma tersebut memeriksa node yang lebih menjanjikan terlebih dahulu. Jika node memilik perkiraan total cost yang kecil, maka node tersebut pasti memiliki cost sejauh ini yang relatif pula. Jika perkiraanny akurat, maka nodes yang lebih dekat ke tujuan akan dipertimbangkan terlebih dahulu, mempersempit pencarian ke area yang yang paling menguntungkan.

19

c. Menghitung Jarak sejauh ini untuk Open dan Closed Nodes Seperti sebelumnya, setelah sampai pada open dan closed node selama iterasi, dan nilai yang terekam harus direvisi. Nilai cost sejauh ini terhitung wajar, dan jika nilai baru lebih rendah dari nilai untuk node yang sudah ada, maka nilainya perlu diupdate. Dilakukan perbandingan ini secara ketat berdasarkan nilai cosr sejauh ini (hanya nilai yang dapat diandalkan, karena tidak mengandung nilai perkiraan apapun), bukan perkiraan total cost. Tidak seperti Dijkstra, algoritma A* dapat menemukan rute yang lebih baik menuju node yang sudah ada pada closed list. Jika nilai sebelumnya sangat optimis, maka node mungkin telah diproses untuk berpikir bahwa itu adalah pilihan terbaik, yang pada kenyataannya bukan. Hal ini mengakibatkan knock-on problem. Jika node yang meragukan telah diprose dan dimasukkan dalam closed list, maka berarti semua koneksinya telah dipertimbangkan. Mungkin saja seluruh himpunan node memiliki cost sejauh ini berdasarkan node sejauh ini dari node yang diragukan. Meng-update nilai dari node yang meragukan tidaklah cukup. Seluruh koneksinya juga harus diperiksa kembali untuk mendistribusikan nilai baru tersebut. Dalam kasus perevisian node dalam open list, hal ini tidak diperukan, karena diketahui bahwa koneki dari sebuah node dalam open list belum diproses. Namun ada cara sederhana untuk memaksa algoritma untuk menghitung kembali dan menyebarkan nilai baru tersebut. Node dari closed list dapat dipindahkan kembali ke open list, yang kemudian akan menunggu sampai tertutup dan koneksinya telah

20

dipertimbangkan kembali. Node yang bergantung pada nilainya kemudian akan diproses sekali lagi. Jadi, closed node nilainya telah direvisi dikeluarkan dari closed list dan ditempatkan ke open list. Open nodes yang memiliki nilai terevisi tetap pada open list, seperti sebelumnya. d. Mengakhiri Algoritma Dalam banyak implementasi, A* berakhir saat node tujuan adalah node terkecil pada open list. Namun node yang memiliki nilai perkiraan total cost terkecil (dan oleh karena itu akan diproses pada iterasi berikutya dan dimasukkan dalam closed list) mungin saja nilainya harus direvisi nanti. Tidak ada lagi jaminan bahwa hanya karena node tersebut paling kecil di open list, maka shortest path akan didapatkan disana. Maka mengakhiri A* saat node tujuan merupakan terkecil di open list tidak menjamin rute terpendek telah ditemukan.

Gambar 2.2 Contoh Algoritma A* bekerja

21

Oleh karena itu, wajar untuk bertanya apakah A* dapat dijalankan sedikit lebih lama untk menghasilkan hasil yang terjamin optimal. Hal ini dapat dilakukan dengan memerintahkan algoritma tersebut untuk berakhir hanya jika node di open list dengan cost sejauh ini (bukan perkiraan total cost) terkecil memiliki nilai cost sejauh ini lebih besar dari cost path yang ditemui menuju tujuan. Dengan cara itu, dan hanya dengan cara itu dapat terjamin bahwa tidak ada path masa depan akan ditemukan yang membentuk shortcut. Ini merupakan kondisi pengakhiran efektif yang dapat dilihat pada Dijkstra, dan dapat ditunjukkan bahwa menerapkan kondisi akan menghasilkan jumlah fill yang sama layaknya menggunakan algoritma pathfinding Dijkstra. Node mungkin saja dicari dengan urutan yang berbeda, dan mungkin saja ada sedikit perbedaan dalam himpunan node di open list, namun tingkat fill rata-rata sama. Dengan kata lain, Dijkstra mengambil seluruh kelebihan performa dari A* dan membuatnya tidak bernilai.Implementasi A* seluruhnya bergantung pada kenyataan bahwa A* dapat menghasilkan hasil yang tidak optimal secara teoritis. Untungnya, hal ini dapat dikendalikan dengan fungsi heuristik. Tergantung pada pemilihan fungsi heuristik, hasil optimal akan terjamin atau hasil sub-optimal yang memberikan eksekusi yang lebih cepat dapat dengan sengaja diijinkan. Karena A* sering berhubungan dengan hasil sub-optimal, implementasi A* dalam jumlah besar malah berakhir saat node tujuan dikunjungi pertama tanpa menunggunya untuk menjadi terkecil di open list.

22

Kelebihan performa A* tidak sebesar melakukan hal yang sama pada Dijkstra, namun banyak pengembang merasa setiap bit berharga, terutama saat algoritma tidak dibutuhkan untuk menjadi optimal. e. Mengambil path Path berakhir didapat dengan cara yang benar-benar sama seperti sebelumnya, dengan memulai dari tujuan dan mengkumulasi koneksi saat bergerak mundur ke start node. Koneksi-koneksi tersebut kemudian dibalikkan kembali untuk membentuk path yang benar. 2.2.6.3

Memilih Fungsi Heuristik Semakin akurat heuristik yag digunakan, semakin sedikit fill yang akan dialami

oleh A*, dan semakin cepat dijalankan. Jika heuristik yang sempurna digunakan (yang selalu mengembalikan jarak path minimum antara 2 node yang sangat tepat), A* akan langsung mengarah pada jawaban yang tepat, algoritma akan menjadi O(p), dimana p adalah jumlah langkah dalam path. Sayangnya, untuk menemukan jarak yang tepat antara dua nodes, biasanya rute terpendek di antara kedua node tersebut harus ditemukan, yang mungkin berarti menyelesaikan pemasalahan pathfinding. Untuk heuristik yang tidak sempuna, A* berlaku sedikit berbeda tergantung pada apakah heuristik tersebut terlalu rendah atu terlalu tinggi, berikut adalah penjelasannya: a. Heuristik yang terlalu rendah

Jika heuristik terlalu rendah, maka A* memperkirakan terlalu rendah panjang path aktual, A* membutuhkan waktu lebih lama untuk dijalankan. Perkiraan total cost akan codong ke arah cost sejauh ini (karena nilai heuristik terlalu kecil dari

23

kenyataan). Jadi A* lebih memilih untuk memeriksa node yang lebih dekat ke start node, daripada yang lebih dekat ke tujuan. ini akan meningkatkan waktu yang diperlukan untuk menemukan rute menuju tujuan. Jika heuristik terlalu rendah, maka hasil yang dihasilkan akan menjadi path terbaik yang memungkinkan, dan akan menjadi path yang benar benar sama dengan yang dihasilkan oleh Dijkstra. b. Heuristik yang terlalu tinggi Jika heuristik terlalu tinggi, maka diperkirakan panjang path aktual terlalu panjang. A* mungkin tidak menghasilkan path terbaik. A* akan cenderung menghasilkan path dengan nodes yang lebih sedikit, bahkan jika koneksi di antara nodes terlalu tinggi. Nilai perkiraan total cost akan membias kepada heuristik. Algoritma A* akan lebih tidak memperhatikan secara proporsional cost sejauh ini dan akan cenderung lebih menyukai nodes yang memiliki sisa jarak yang lebih kecil. Hal ini akan menggeser fokus pencarian ke tujuan lebih cepat, namun dengan resiko kehilangan rute terbaik. Ini berarti bahwa panjang total dari path mungkin lebih besar dari panjang total dari path terbaik. Untungnya, tidak berarti bahwa akan langsung didapat path yang buruk. Dapt ditunjukkan bahwa jika heuristik memandang terlalu tinggi oleh sebagian besar x (yakni x adalah pandangan terlalu tinggi terbesar untuk setiap node dalam graf) dan final path tidak akan lebih besar dari x.

24

2.2.7 Algoritma Shooting-star Shooting-star Algoritms (Shortest Path Algoritms) adalah algoritma untuk menemukan jarak terpendek dari suatu edge ke edge yang lainnya pada suatu graph yang berbobot. Algoritma shooting-star mencari jarak terpendek untuk tiap edge dari suatu graph yang berbobot. Algoritma ini mencari jarak terpendek dari edge asal ke edge terdekatnya, kemudian kedua, dan seterusnya. Secara umum, sebelum dilakukan literasi, algoritma sudah mengidentifikasikan jarak terdekat dari i-l edge terdekatnya. Selama seluruh edge berbobot tertentu yang (positif), maka edge terdekat berikutnya dari node asal dapat ditemukan selama edge berdekatan dengan edge Ti. Edge inilah yang merupakan kandidat dari algoritma shooting-star untuk memilih edge berikutnya dari node asal.

2.3 Penelitian Sebelumnya Penelitian yang dilakukan oleh Doni Widagdo, Maman Somantri dan R. Rizal Isnanto (2013) dalam jurnalnya yang berjudul Pencarian Rute Terpendek Menggunakan Algoritma Shooting-Star (Shooting*) dan A Star (A*) Pada Berbasis Web Untuk Pemetaan Pariwisata Kota Semarang, menyimpulkan Aplikasi ini berhasil menemukan rute terpendek jalan yang ada di Kota Semarang yaitu kurang lebih sebanyak 107 Jalan menggunakan algoritma Shooting-star dan Astar dan aplikasi ini menghasilkan presentase kesuksesan untuk algortima Shooting-star 31,76 %, sedangkan untuk algortima Astar 41,17 %, sedangkan sisa yang lain merupakan

25

eror dalam pemetaan. Sehingga algortima Astar merupakan algortima terefektif dalam pencarian rute terpendek. Penelitian yang dilakukan oleh Akbar Juang Saputra (2013) dalam jurnalnya yang berjudul Penerapan Algoritma A* Pada Google Map, menyimpulkan algoritma A* menggunakan informasi tambahan (nilai heuristik) dalam pencarian solusi. Oleh karena itu, solusi yang optimal sangat tergantung kepada fungsi heuristik yang diterapkandan algoritma A* dapat diterapkan dalam menentukan shortest path pada Google Map dengan menelusuri tiap nodenya. Penelitian yang dilakukan oleh Zahratul Ainiyah (2014) dalam jurnalnya yang berjudul Pencarian rute Terpendek Pada Pemetaan Lokasi Pendidikan Formal di Kota Bangkalan, menyimpulkan algoritma shooting-star menghasilkan rute perjalanan yang tidak selalu sama karena algoritma shooting-star bersifat random, namun dari segi waktu pencarian yang diperlukan untuk memperoleh rute terpendek.

26

BAB III ANALISA DAN PERANCANGAN

3.1 Perencanaan Pada tahap ini, peneliti mengumpulkan data dan bahan yang akan diperlukan dalam pembuatan aplikasi serta menganalisa permasalahan yang akan muncul dan mendefenisikan permasalahan secara rinci, kemudian menentukan tujuan pembuatan sistem. 3.1.1 Identifikasi Masalah Deskripsi masalah merupakan suatu gambaran yang akan diangkat dalam penulisan tugas akhir tentang implementasi perhitungan algoritma A star dan Shooting star dalam menemukan rute. Algoritma A star merupakan bentuk yang paling dari Best First Search (BFS). A star mengevaluasi node (dalam hal ini adalah persimpangan jalan yang diambil) dengan menggabungkan g(n), yaitu biaya untuk mencapai node, dan h(n), yaitu cost yang diperlukan dari node untuk mencapai tujuan, sehingga : f(n) = g(n) + h(n), sedangkan algoritma Shooting star merupakan algoritma yang digunakan untuk menemukan jarak terpendek dari suatu graph yang berbobot. Algoritma ini akan mencari jarak terpendek dari edge (dalam hal ini adalah ruas jalan raya) asal ke edge terdekatnya, kemudian kedua dan seterusnya.

26

27

Perhitungan kedua algoritma akan di diterapkan dalam pencarian rute terpendek pada peta google maps. Pencarian jalur ini akan diamsumsikan dengan titik awal (posisi pertama) dan titik akhir (posisi tujuan) yang diimplementasikan pada pencarian jalur yakni jalan raya besar ( tidak termasuk jalan-jalan kecil/gang). 3.1.2 Identifikasi Kebutuhan Dari identifikasi masalah-masalah diatas dapat kita identifikasi apa yang dibutuhkan pengguna atau kita dapat membantu pengguna untuk megurangi masalah yang ada dan mempermudah kinerja mereka. Adapun identifikasi kebutuhan pengguna sistem sebagai berikut: 1. Perangkat lunak pemetaan rumah sakit menggunakan mobile android untuk membantu pengguna dalam pencarian rute terpendek dengan rute yang sebenarnya yang menekankan pada perhitungan menggunakan algoritma A star dan Shooting star.

3.2. Analisa Pada tahap ini penulis melakukan analisis kebutuhan-kebutuhan dalam pembuatan aplikasi pemetaan rumah sakit dalam pencarian rute terpendek menggunakan android. 1.

Analisa Kebutuhan Perangkat Lunak Analisis kebutuhan sistem merupakan tahap yang menguraikan secara rinci

tentang spesifikasi struktur, konten, dan kebutuhan data yang berhubungan dengan sistem yang akan dibuat sebelum melakukan tahap perancangan. Seorang perancang

28

aplikasi harus menganalisis apa saja kebutuhan yang diperlukan untuk membangun sistem informasi yang nantinya akan dibuat sebagai aplikasi pencarian rute pada pemetaan rumah sakit Kota Palembang dalam pencarian rute terpendek yang diakses melalui smartphone android. a. Perangkat Keras (Hardware) Perangkat keras (hardware) yang dimaksud adalah sebuah perangkat keras yang digunakan dalam membangun aplikasi pencarian rute dalam pemetaan rumah sakit Kota Palembang dalam pencarian rute terpendek dengan spesifikasi laptop sebagai berikut : a. Processor Intel Dual Core b. RAM 2 GB c. Hardisk 500 GB d. Monitor Intel HD Graphics e. CDRW Eksternal f. Mouse, Keyboard b. Perangkat Lunak (Software) Perangkat lunak ini merupakan sebuah perangkat lunak yang digunakan dalam membuat aplikasi, adalah sebagai berikut : a. Microsoft Windows 7. a. Java(jdk-6u22-windows-i586) sebagai aplikasi pendukung pemrograman android. b. Android SDK (Sofware Development Kit) sebagai pemrograman android.

29

c. Eclipse Juno v. 23 IDE for Java Developers sebagai aplikasi desain android. d. Microsoft Word 2010. e. MySQL sebagai database aplikasi. f. PHP sebagai service penghubung android dan MySQL. 2.

Analisa Algoritma A* Terdapat beberapa hal yang perlu didefinisikan terlebih dahulu dalam kasus

pencarian rute terpendek dengan penerapan Algoritma A star. Adapun istilah-istilah yang akan di bahas yaitu path, open list, closed list, nilai f, g, dan n. Algoritma A star menggunakan dua senarai yaitu OPEN dan CLOSED. OPEN adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih sebagai simpul terbaik (best node) dengan kata lain, OPEN berisi simpul-simpul masih memiliki peluang untuk terpilih sebagai simpul terbaik, sedangkan CLOSED adalah senarai untuk menyimpan simpul-simpul yang suda pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup). 1. OPEN LIST adalah list yang menyimpan kemungkinan path yang akan diperiksa. OPEN LIST dibuat terurut berdasarkan nilai f. OPEN LIST digunakan untuk menentukan secara selektif (berdasarkan nilai f) jalan yang dikira lebih dekat menuju path tujuan. OPEN berisi simpul-simpul yang masih memiliki peluang untuk terpilih sebagai simpul terbaik.

30

2. CLOSED adalah senarai (list) untuk menyimpan simpul-simpul yang sudah pernah dibangkaitkan dan sudah pernah terpilih sebagai simpul terbaik (best node) atau meyimpan senarai yang menyimpan jalan yang sudah diperiksa dari open list. Artinya, CLOSED berisi simpul-simpul yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup). Kedua list (OPEN LIST dan CLOSED LIST) ini bertujuan juga untuk menghindar penelusuran berkali-kali jalan (rute) yang memang sudah diidentifikasikan agar tidak masuk lagi ke dalam OPEN LIST. 3. Nilai F adalah cost perkiraan suatu path yang teridentifikasi, Nilai F merupakan hasil dari f(n). 4. Nilai G hasil dari fungsi g(n), adalah banayaknya langkah yang diperlukan untuk menuju path sekarang. 5. Setiap simpul (node) harus memiliki informasi nilai h(n), yaitu estimasi harga simpul tersebut dihitung dari simpul tujuan yang hasilnya menjadi H. Fungsi f sebagai estimasi fungsi evaluasi terhadap node n, dapat dituliskan : f(n) = g(n)+h(n) dimana : f(n) : fungsi evaluasi (jumlah g(n) dengan h(n) ) g(n) : biaya (cost) yang dikeluarkan dari keadaan awal sampai keadaan n h(n) : estimasi biaya untuk sampai pada tujuan nilai n.

31

3.

Analisa Pemecahan Kasus Algoritma A* Pada analisa kasus pertama, pencarian lokasi awal dimulai dari lokasi asal

Plaju, disini peneliti mengambil lokasi kampus UBD sebagai lokasi asal dan rumah sakit PT PUSRI sebagai tujuan. Berikut adalah flowchart dari algoritma A*

Gambar 3.1 Flowcahrt algoritma A* 4.

Pengaturan Bobot Node Peta Pengaturan bobot node-node peta dapat dikatakan adalah salah satu hal yang

paling penting pada perhitungan dengan Algoritma ini. Bobot pada peta yang sebenarnya merupakan jarak antara simpul (node) yang terdapat pada OPEN LIST

32

dan CLOSED LIST. Penentuan bobot dan pemberian nilai pada bobot ini sangat berpengaruh pada ketepatan pencarian rute optimal pada peta yang bersangkutan. Berikut adalah flowchart pengaturan bobot node peta.

Gambar 3.2 Flowcahrt Pengaturan bobot node peta

5.

Pemecahan Kasus dengan Algoritma A* Perhitungan algoritma ini akan diterapkan pada analisa kasus pencaian rute

terpendek menuju loksai tujuan rumah sakit pada peta dengan memanfaatkan google maps untuk mencari jalan, jarak dan langkah menuju tujuan persimpangan dan ruas jalan yang diperiksa.

33

Kali ini peneliti mengambil tiga studi kasus yang dijadikan sebagai titik awal pencarian adalah Terminal Perumnas Sako, Terminal KM.12 dan Universitas Bina Darma Palembang. Dan titik tujuan Rumah Sakit Dr. Mohd. Hosein, Rumah Sakit Muhammadiyah, Rumah Sakit PT. PUSRI.

Gambar 3.3 Lokasi asal kampus UBD dan tujuan RS PUSRI Pada gambar 3.3, marker yang berwarna kuning merupakan daerah Plaju dengan lokasi asal kampus Bina Darma dan marker yang berwarna kuning merupakan tujuan lokasi RS PT PUSRI. Berdasarkan hasil analisa pada peta , terdapat rute jalan yang memungkinkan menuju lokasi tujuan RS PUSRI dari lokasi asal kampus Bina Darma. Berikut adalah hasil rute yang yang dapat dilihat pada gambar 3.4

34

Gambar 3.4 Rute dan persimpangan lokasi menuju RS PUSRI Pada gambar 3.4, node A merupakan lokasi asal kampus Bina Darma dan node R merupakan lokasi tujuan RS PUSRI, sedangkan node B-C-D-F-G-H-I-J-K-L-M-NO-P-Q merupakan nodes yang memungkin menuju lokasi tujuan. Keterangan pada gambar diatas dapat dilihat pada table 3.1 . Node

Nama

Titik Koordinat

A

Universitas Binadarma

-2.997250, 104.774010

B

Simpang Flyover Jakabaring

-2.999804, 104.768953

C

Simpang Bundaran Air Mancur 1

-2.988560, 104.761424

D

Simpang Bundaran Air Mancur 2

-2.988942, 104.759608

E

Simpang Bundaran Air Mancur 3

-2.988139, 104.758833

F

Simpang Bundaran Air Mancur 4

-2.987022, 104.760330

G

Simpang Pasar Cinde

-2.979871, 104.755627

H

Simpang Veteran

-2.976731, 104.754078

I

Simpang Kol.Atmo

-2.982687, 104.759573

J

Simpang Rajawali

-2.975827, 104.764293

35

K

Simpang Dempo

-2.980413, 104.764857

L

Simpang Pasar Kuto

-2.980808, 104.771446

M

Simpang Veteran-M.Isa

-2.975549, 104.770716

N

Simpang Bom Baru

-2.977621, 104.778760

O

Simpang Pasar Lemabang

-2.972037, 104.783436

P

Simpang Sekojo

-2.968374, 104.786694

Q

Simpang May.Zen-Abdul Rozak

-2.966155, 104.798462

R

Rumah sakit PT.PUSRI

-2.967987, 104.818329

Tabel 3.1 Titik Kordinat antar node Berikut adalah hasil pohon pencarian yang didapat pada gambar 3.4 , dari lokasi asal kampus Bina Darma menuju RS PUSRI.

H

J

M N

G K

L

I

O

F E P

D C R B

A

Q

36

6.

Menghitung bobot node menuju node tujuan Pada algoritma A*, dilakukan perhitungan bobot antar node yang lebih dekat

dengan node tujuan. Dalam hal ini digunakan rumus Euclidean Distance

Dimana ; x : koordinat latitude titik 1 x1 : koordinat latitude titik 2 y : koordinat longitude titik 1 y1: koordinat longitude titik 2 Sebagai inisialisasi awal pada perhitungan ini, algoritma A* sudah memasukkan node dalam OPENlist ke dalam CLOSED list.

A

B

C

D

E F

Langkah Pertama Simpul B (Simpang FlyOver Jakabaring) menuju simpul C (Bundaran AirMancur1) B (-2.999804, 104.768953) ke C (-2.988560, 104.761424)

=√

(-2.999804-2.988560)2 + (104.768953-104.761424)2 x 111.319

37

Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.999804-2.988560)^2 + (104.768953-104.761424)^2)*111.319)) =1,22734 km Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node B menuju node C adalah 1,22734 km. Langkah Kedua Simpul C (bundaran AirMancur 1) menuju D (bundaran AirMancur2) C (-2.988560, 104.761424) ke D (-2.988942, 104.759608)

=√ (-2.988560-2.988942)2 + (104.761424-104.759608)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.988560-2.988942)^2 + (104.761424-104.759608)^2)*111.319)) =0,20658 Km. Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node C menuju node D adalah 0,20658 km.

38

Langkah Ketiga Simpul D(Bundaran AirMancur2) menuju simpul E(Bundaran AirMancur3) D (-2.988942, 104.759608) ke E (-2.988139, 104.758833)

=√ (-2.988942-2.988139)2 + (104.759608-104.758833)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: = ((SQRT((2.988942-2.988139)^2 + (104.759608-104.758833)^2)*111.319)) =0,124231 km Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node D menuju node E adalah 0,124231 km. Langkah Keempat Simpul E(Bundaran AirMancur3) menuju simpul F (Bundaran AirMancur4) E (-2.988139, 104.758833) ke F (-2.987022, 104.760330)

=√ (-2.988139-2.987022)2 + (104.758833-104.760330)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.988139-2.987022)^2 + (104.758833-104.76033)^2)*111.319))

39

=0,207922 Km. Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node E menuju node F adalah 0,207922 km Langkah Kelima Simpul F(Bundaran AirMancur4) menuju simpul G(Simpang Pasar Cinde) F (-2.987022, 104.760330) ke G (-2.979871, 104.755627)

=√ (-2.987022-2.979871)2 + (104.760330-104.755627)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((-2.987022-2.979871)^2 + (104.76033-104.755627)^2)*111.319)) =0,95277 km Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node F menuju node G adalah 0,95277 km. Maka sejauh ini simpul yang terpadat pada OPENlist dan telah dimasukkan ke dalam CLOSEDlist dapat dilihat pada tabel 3.2 berikut: Langkah

OPEN

CLOSED

1

[(B),(C)]

[(B),(C)]

2

[(C),(D)]

[(B),(C),(D)]

40

3

[(D),(E)]

[(B),(C),(D),(E)]

4

[(E),(F)]

[(B),(C),(D),(E),)(F)]

5

[(F),(G)]

[(B),(C),(D),(E),)(F),(G)]

Sejauh ini maka simpul yang terlah dimasukkan ke dalam CLOSEDlit dari posisi asal simpul A ,adalah B-C-D-E-F-G. Langkah selanjutnya adalah menghitung jarak dari simpul yang telah dimasukkan kedalam CLOSEDlist yaitu simpul G, menuju simpul yang berada dalam OPENlist yakni, simpul H dan simpul I. H

G

I

Langkah Keenam Simpul G( Simpang Pasar Cinde) menuju Simpul H ( Simpang Veteran) G (-2.979871, 104.755627) ke H (-2.976731, 104.754078)

=√ (-2.979871-2.976731)2 + (104.755627-104.754078)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut:

41

=((SQRT((2.979871-2.976731)^2 + (104.755627-104.754078)^2)*111.319)) =0,38976 km Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node G menuju node H adalah 0,38976 km. Langkah Ketujuh Simpul G (Simpang Pasar Cinde) menuju simpul I (Simpang Kol.Atmo) G (-2.979871, 104.755627) ke I(-2.982687, 104.759573)

=√ (-2.979871-2.982687)2 + (104.755627-104.759573)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.979871-2.982687)^2+(104.755627-104.759573)^2)*111.319)) =0,539648 km Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node G menuju node I adalah 0,539648 km. Pada langkah keenam dan ketujuh adalah menghitung bobot node dari simpul yang telah dimasukkan ke dalam CLOSEDlist yaitu simpul G menuju simpul H dan simpul I, hasil perhitungan dapat dilihat pada tabel 3.3 berikut:

42

Langkah

OPEN

CLOSED

6

[(H)]

[(G)]

7

[(I)]

[(G),(H)]

Pada langkah ini simpul H dimasukkan ke dalam CLOSED list, karena simpul H memiliki nilai bobot lebih kecil dibandingkan simpul I. Langkah selanjutnya adalah menghitung jarak dari simpul yang telah dimasukkan kedalam CLOSEDlist yaitu simpul H, menuju simpul yang berada dalam OPENlist yakni, simpul J, simpul M, dan simpul K. H

J

M

Langkah Kedelapan Simpul H (Simpang Veteran) menuju simpul J (Simpang Rajawali) H (-2.976731, 104.754078) ke J (-2.975827, 104.764293)

=√ (-2.976731-2.975827)2 + (104.754078-104.764293)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut:

43

=((SQRT((2.976731-2.975827)^2 + (104.754078-104.764293)^2)*111.319)) =1,141568 Km. Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node H menuju node J adalah 1,142568 km. Langkah Kesembilan Simpul J (Simpang Rajawali) menuju simpul M (Simpang Veteran-M.Isa) J(-2.975827, 104.764293) ke M (-2.975549, 104.770716)

=√ (-2.975827-2.975549)2 + (104.764293-104.770716)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.975827-2.975549)^2 + (104.764293-104.770716)^2)*111.319)) =0,715671 Km. Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node J menuju node M adalah 0,715671 km. Langkah Kesepuluh Simpul J(Simpang Rajawali) menuju K (Simpang Lingkaran-Dempo) J(-2.975827, 104.764293) ke K (-2.980413, 104.764857)

44

=√ (-2.975827-2.980413)2 (104.764293, 104.764857)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.975827-2.980413)^2+(104.764293-104.764857)^2)*111.319)) =0,514355 Km. Pada perhitungan diatas nilai 111.319 diperoleh dari konversi 1 derajat (1o) bumi kedalam kilometer, jadi hasil yang diperoleh dari node J menuju node K adalah 0,514355 km. Maka sejauh ini simpul yang telah dimasukkan ke dalam OPENlist dan CLOSEDlist dapat dilihat pada tabel 3.5 berikut : Langkah

OPEN

CLOSED

8

[(J)]

[(H),(J)]

9

[(M)]

[(H),(J)]

10

[(K)]

[(H),(J),(K)]

Simpul K dimasukkan ke dalam CLOSEDlist karena nilai bobot node K lebih kecil di bandingkan nilai bobot pada node M yakni, 0,514355 Km. Langkah selanjutnya adlah menghitung simpul searah yang telah dimasukkan ke dalam OPEN list dari node K. Langkah Kesebelas Simpul K (Simpang Lingkaran-Dempo) menuju L (Simpang Pasar Kuto) K (-2.980413, 104.764857) ke L (-2.980808, 104.771446)

45

=√ (-2.980413-2.980808)2 + (104.764857-104.771446)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.980413-2.980808)^2 + (104.764857-104.771446)^2)*111.319)) =0,743798 km. Langkah Keduabelas Simpul L(simpang pasar kuto) menuju N (Simpang Bom Baru) L (-2.980808, 104.771446) ke N (-2.977621, 104.778760)

=√ (-2.980808-2.97762)2+(104.771446-104.778760)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.980808-2.97762)^2+(104.771446-104.778760)^2)*111.319)) =0,888619km. Langkah Ketigabelas Simpul N(Simpang Bom Baru) menuju simpul O (Simpang Lemabang) N (-2.977621, 104.778760) ke O (-2.972037, 104.783436)

= √ (-2.977621-2.972037)2+(104.778760-104.783436)2x111.319

46

Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.977621-2.972037)^2+(104.77876-104.783436)^2)*111.319)) =0,810766 km. Langkah keempatbelas Simpul O (Simpang Lemabang) menuju simpul P (Simpang Soekojo) O (-2.972037, 104.783436) ke P(-2.968374, 104.786694)

=√ (-2.972037-2.968374)2 + (104.783436-104.786694)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.972037-2.968374)^2 + (104.783436-104.786694)^2)*111.319)) =0,545714 km. Langkah kelimabelas Simpul P (Simpang Sekojo) menuju simpul Q (Simpang May.Zen-Abdul.Rozak) P(-2.968374, 104.786694) ke Q(-2.966155, 104.798462)

=√ (-2.968374-2.966155)2 + (104.786694-104.798462)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut:

47

=((SQRT((2.968374-2.966155)^2 + (104.786694-104.798462)^2)*111.319)) =1,333088 km. Langkah keenambelas Simpul Q (Simpang M.Zen-Abdul.Rozak) menuju R (Rumah sakit PUSRI) Q(-2.966155, 104.798462) ke R(-2.967987, 104.818329)

=√ (-2.966155-2.967987)2 + (104.798462-104.818329)2111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.966155-2.967987)^2 + (104.798462-104.818329)^2)*111.319)) =2.220957 km. Dari hasil perhitungan jarak menggunakan Euclidean Distance Formula pada algoritma A star dalam menentukan rute terpendek dari lokasi asal kampus Bina Darma menuju Lokasi tujuan RS PUSRI, adalah A-B-C-D-E-F-G-H-J-K-L-M-N-OP-Q-R pada graph dan pada peta sebenarnya adalah dengan rute Jl. Jend. A. Yani – Jl. Jembatan Ampera – Jl. Merdeka – Jl. Jend Sudirman – Jl.Veteran – Jl. Lingkaran – Jl. Slamet Riyadi – Jl. Perintis kemerdekaan – Jl. Letkol Nuamin – Jl. Yos Sudaso – Jl.R.E Martadinata – Jl. Mayor Zen. Dengan jarak tempuh 11,307468 km.

48

7.

Analisa Kasus Algoritma Shooting* Algoritma Shooting star (Shortest Path Algoritms) merupakan algoritma untuk

menemukan jarak terpendek dari suatu edge ke edge lainnya pada suatu graph yang berbobot. Kerja algoritma Shooting star hampir sama dengan perhitungan algoritma A star, hanya saja algoritma ini hanya mengutamakan perhitungan dalam pencariannya pada pencarian edge (pada kasus ini edge adalah sisi jalan raya). M I

O

G

K

N

H

Q

P

F

J

E

L R

D S C B

A

T

Berikut adalah keterangan pada graph pohon pencarian berdasarkan rute pada peta sebenarnya dapat dilihat pada tabel 3.6 berikut:

49

No.

Sisi (Edge)

Jalur

1

A

Jl.Jend. A. Yani menuju FlyOver Jakabaring

2

B

Jl. Jembatan Ampera menuju Bundaran 1

3

C

Bundaran 1 menuju Bundaran 2

4

D

Bundaran 2 menuju Bundaran 3

5

E

Bundaran 3 menuju Bundaran 4

6

F

Bundaran 4 menuju simpang pasar cinde

7

G

Simpang pasar cinde menuju simpang veteran

8

H

Simpang pasar cinde menuju simpang atmo

9

I

Simpang veteran menuju simpang rajawali

10

J

Simpang atmo menuju simpang dempo

11

K

Simpang rajawali menuju simpang dempo -Simpang dempo menuju simpang rajawali

12

L

Simpang dempo menuju simpang psr kuto

13

M

Simpang rajawali menuju simpang M.Isa

14

N

Simpang M.Isa menuju simpang psr kuto

15

O

Simpang M.Isa menuju simpang bom baru

16

P

Simpang psr kuto menuju simpang bom baru

17

Q

Simpang bom baru menuju simpang lmabang

18

R

Simpang lemabang menuju simpang soekojo

19

S

Simpang soekojo menuju simpang M.Zen

50

20

T

Simpang M.Zen menuju RS PUSRI

Tabel 3.6 Keterangan edge pohon pencarian 2 Sebagai perhitungan awal dengan Shooting star, algoritma ini sudah menginisialisasi sisi awal yang sangat memungkinkan menuju lokasi tujuan berdasarkan rute sebenaranya pada peta. Langka pertama A

B

Sisi A (Jl. Jend A.Yani) Nilai Sisi A (kampus UBD menuju FlyOver Jakabaring) (-2.997250, 104.774010) ke (-2.999804, 104.768953)

= √ (-2.997250-2.999804)2 + (104.774010-104.768953)2x111.319 =((SQRT((2.99725-2.999804)^2+(104.77401-104.768953)^2)*111.319)) =0,630661 km. Sisi B (Jl. Jembatan Ampera) Nilai sisi B ( FlyOver Jakabaring menuju bundaran air mancur 1) (-2.999804, 104.768953) ke (-2.988560, 104.761424)

=√

(-2.999804-2.988560)2 + (104.768953-104.761424)2 x 111.319

51

Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.999804-2.988560)^2 + (104.768953-104.761424)^2)*111.319)) =1,22734 km Langkah Kedua C

D

Sisi C (Jln. Merdeka) Nilai sisi C(Bundaran 1 menuju Bundaran 2) (-2.988560, 104.761424) ke (-2.988942, 104.759608)

=√ (-2.988560-2.988942)2 + (104.761424-104.759608)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.988560-2.988942)^2 + (104.761424-104.759608)^2)*111.319)) =0,20658 Km. Sisi D (Jl. Merdeka) Nilai sisi D (Bundaran 2 menuju Bundaran 3) (-2.988942, 104.759608) ke (-2.988139, 104.758833)

=√ (-2.988942-2.988139)2 + (104.759608-104.758833)2x111.319

52

Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: = ((SQRT((2.988942-2.988139)^2 + (104.759608-104.758833)^2)*111.319)) =0,124231 km Langkah Ketiga E

F

Sisi E (Jln. Faqih Jalaludin) Nilai sisi E (bundaran 3 menuju bundaran 4) (-2.988139, 104.758833) ke (-2.987022, 104.760330)

=√ (-2.988139-2.987022)2 + (104.758833-104.760330)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.988139-2.987022)^2 + (104.758833-104.76033)^2)*111.319)) =0,207922 Km. Sisi F (Jl.Jend. Sudirman) Nilai sisi F( bundaran 4 menuju simpang pasar cinde) (-2.987022, 104.760330) ke (-2.979871, 104.755627)

53

=√ (-2.987022-2.979871)2 + (104.760330-104.755627)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((-2.987022-2.979871)^2 + (104.76033-104.755627)^2)*111.319)) =0,95277 km Langkah Keempat

G

H

Sisi G (Jalan Jend. Sudirman) Nilai Sisi (Simpang pasar cinde menuju simpang veteran) (-2.979871, 104.755627) ke (-2.976731, 104.754078)

=√ (-2.979871-2.976731)2 + (104.755627-104.754078)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.979871-2.976731)^2 + (104.755627-104.754078)^2)*111.319)) =0,38976 km

54

Sisi H (Jalan Kol. Atmo) Nilai Sisi H (simpang pasar cinde menuju simpang atmo) (-2.979871, 104.755627) ke (-2.982687, 104.759573)

=√ (-2.979871-2.982687)2 + (104.755627-104.759573)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.979871-2.982687)^2+(104.755627-104.759573)^2)*111.319)) =0,539648 km Pada langkah ke keempat nilai sisi G lebih kecil dibandingkan nilai pada sisi H, sehingga sisi G dimasukkan ke dalam CLOSEDlist. Maka, sejauh ini sisi yang telah dimasukkan dimasukkan ke dalam CLOSED list adalah sisi A-B-C-D-E-F-G. Langkah Kelima M I K

Isis I (Jalan Veteran) Nilai sisi I (simpang veteran menuju simpang rajawali) (-2.976731, 104.754078) menuju (-2.975827, 104.764293)

55

=√ (-2.976731-2.975827)2 + (104.754078-104.764293)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.976731-2.975827)^2 + (104.754078-104.764293)^2)*111.319)) =1,141568 Km. Sisi M (jalan Veteran) Nilai sisi M ( simpang rajawali menuju simpang M.Isa) (-2.975827, 104.764293) ke (-2.975549, 104.770716)

=√ (-2.975827-2.975549)2 + (104.764293-104.770716)2x111.319 Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.975827-2.975549)^2 + (104.764293-104.770716)^2)*111.319)) =0,715671 Km. Sisi K (Jalan May. HM. Rasyid Nawawi) Nilai sisi K (Simpang rajawali menuju simpang dempo) (-2.975827, 104.764293) ke (-2.980413, 104.764857)

=√ (-2.975827-2.980413)2 (104.764293, 104.764857)2x111.319

56

Sehingga penulisan program pengukuran Euclidean dalam excel adalah sebagai berikut: =((SQRT((2.975827-2.980413)^2+(104.764293-104.764857)^2)*111.319)) =0,514355 Km. Pada langkah kelima, terdapat sisi yag telah dimasukkan ke dalam CLOSED list , yakni sisi I menuju sisi M dan sisi I menuju sisi K. Pada perhitungan di atas, karena sisi K memiliki nilai yang lebih kecil dibandingkan dengan nilai pada sisi M , sehingga jalur yang akan dilalui setelah sisi I adalah sisi K. Kesimpulan dari hasil perhitungan rute dengna menggunakan algoritma Shooting star, rute yang akan ditempuh pada graph adalah, sebagai berikut : M I

G

O K

N

H

Q

P

F J

E

L R

D S C B

A

T

57

Pada graph diatas, tanda merah merupakan sisi yang dilalui dengan perhitungan Shooting star, yaitu A-B-C-D-E-F-G-I-K-L-P-Q-R-S-T Dengan rute sebenarnya pada peta adalah Jl. Jend. A. Yani-Jl. Jembatan Ampera-Jl. Merdeka-Jl. Faqih JalaluddinJl. May.Tjik Agus Kiemas. Sh.-Jl. Jend. Sudirman- Jl. Veteran-Jl. May. HM. Rasyid Nawawi-Jl. Slamet Riyadi-Jl. Perintis Kemerdekaan-Jl. Letkol Nuramin-Jl. Yos Sudarso-Jl. RE. Martadinata- Jl. Mayor Zen. Dengan jarak tempuh 11,307468 km. 3.3

Produk rekayasa Dari data dan bahan yang telah dikumpulkan, padan tahap ini proses

perancangan aplikasi akan dilakukan. 1. Use Case Diagram Diagram use case digunakan untuk memperlihatkan hubungan-hubungan yang terjadi antara aktor-aktor dengan use case-use case yang ada dalam sistem administrasi baru, sehingga calon penguna sistem/perangkat lunak mendapatkan pemahaman tentang sistem yang akan dikembangkan, lihat pada gambar dibawah ini :

58

Melihat Peta

Menentukan lokasi asal dan tujuan

Melihat Hasil Rute A* Star

Melihat Hasil Rute Shooting Star User

About

Keluar

Gambar 3.5 Use Case Diagram 2. Diagram Activity Diagram Activity yaitu menjelaskan tentang proses kegiatan yang dilakukan oleh pengguna terhadap sistem yang akan digunakan, rancangannya seperti gambar dibawah ini :

59

User

Sistem

Membuka Aplikasi

Menampilkan Halaman Aplikasi Pemetaan

Melihat Peta

Menampilkan Halaman Peta

Melihat Hasil Rute A*

Menampilkan Hasil A*

Melihat Hasil Shooting Star

Melihat About Aplikasi

Menampilkan Hasil Rute Shooting Star

Menampilkan Informasi Pembuat Aplikasi

Keluar

Gambar 3.6. Diagram Activity 3. Class Diagram Class Diagram menggambarkan struktur sistem dan segi pendefinisian kelaskelas yang akan dibuat untuk membangun sistem. Berikut ini class diagram pada aplikasi pencarian rute dalam pemetaan rumah sakit kota Palembang android.

60

tbrumah_sakit -idrumah_sakit -nama -koordinat +Insert() +Update() +Delete()

1

1..* 1..* tblrute -idrute -rute -jarak +Insert() +Update() +Delete()

1

tbgraph -id_graph -simpul_awal -simpul_akhir -jalur -bobot +Insert() +Update() +Delete()

Gambar 3.7 Class Diagram

61

3.4 Perancangan Antar Muka Perangkat Lunak Pada bagian ini,spesifikasi logis diubah ke dalam detail teknologi dimana pemrogram dan pengembangan sistem bisa diselesaikan, dan pada tahap ini aktifitas ini dilakukan. 1. Rancangan Halaman Utama

Gambar 3.8 Rancangan Halaman Menu Utama

62

2. Rancangan Halaman Tampilan Rumah Sakit

Gambar 3.9 Rancangan Halaman Daftar Rumah Sakit 3. Rancangan Halaman Tampilan pilihan Algoritma

Gambar 3.10 Tampilan Rancangan pilihan algoritma

63

4. Rancangan Tampilan Lokasi Asal dan Tujuan

Gambar 3.11 Rancangan Tampilan Lokasi Asal dan Tujuan 5. Rancangan Tampilan Hasil Pencarian

Gambar 3.12 Rancangan Hasil Pencarian

64

BAB IV HASIL DAN PEMBAHASAN 4.1

Hasil Setelah melakukan analisa sistem, perancangan sistem dan berakhir dengan

pembuatan program yang sesungguhnya, maka hasil yang dicapai oleh penulis adalah sebuah perangkat lunak pencarian rute terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android dengan menggunakan bahasa pemrograman java dan xml sebagai desain halaman layout, perangkat lunak pencarian rute terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android ini bermanfaat untuk masyarakat agar mempermudah dalam pencarian sebuah rumah sakit di Kota Palembang pada tiga daerah yaitu daerah perumnas, KM 12 dan plaju. 4.2

Pembahasan Perangkat lunak pencarian rute terpendek pemetaan rumah sakit dengan

perhitungan algoritma A* dan Shooting* berbasis android ini mempunyai halaman utama atau halaman depan yaitu halaman peta lokasi, menu perhitungan A* dan menu perhitungan rute shooting * yang berfungsi untuk memanggil halaman-halaman yang lain secara otomatis pada saat halaman ini diakeses. Pada bab ini akan dibahas bahwa perangkat lunak pencarian rute terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android ini terdapat halaman-halaman lain yang dapat saling berhubungan satu sama lain.

64

65

Hasil dari perangkat lunak pencarian rute terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android ini adalah halaman-halaman informasi yang nantinya dijalankan: 1. Menu Peta Lokasi merupakan link ke halaman saat pertama kali diakses untuk menampilkan peta lokasi berupa 6 titik lokasi. 2. Menu A* merupakan link ke halaman untuk menampilkan dalam pencarian rute dengan algoritma A*. 3. Menu Shooting* merupakan link ke halaman untuk menampilkan dalam pencarian rute dengan algoritma Shooting*. 4.2.1. Tampilan Halaman Menu utama Tampilan ini menjelaskan tentang menu awal perangkat lunak pencarian rute terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android, pada halaman utama perangkat lunak dibuka maka akan tampil halaman peta lokasi, tombol menu A* dan Shooting*. Pada peta lokasi akan menampilkan sebuah peta yang dilengkapi titik informasi 3 daerah yaitu daerah perumnas, KM 12 dan plaju, rancangannya seperti gambar 4.1 di bawah ini :

66

Gambar 4.1 Tampilan Halaman Utama 4.2.2. Tampilan Daftar Rumah Sakit Tampilan ini menjelaskan tentang menu A*, Shooting * dan daftar rumah sakit seperti rumah sakit muhammadiyah, rumah sakit umum dan rumah sakit pusri pada perangkat lunak pencarian rute terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android, tampilannya seperti gambar 4.2 di bawah ini :

67

Gambar 4.2 Tampilan Halaman Daftar Rumah Sakit 4.2.3. Tampilan Lokasi Awal Rute Tampilan ini menjelaskan tentang lokasi awal rute dengan tujuan rumah sakit muhammadiyah, pada tampilan kategori awal rute terdapat 3 bagian yaitu rute awal plaju, rute terminal perumnas dan rute terminal km 12. Berikut ini adalah tampilan rute awal lokasi pada gambar 4.3 dibawah ini :

68

Gambar 4.3 Tampilan Halaman Tujuan Lokasi 4.2.4. Tampilan Peta Lokasi Plaju Menuju Rumah Sakit Muhammadiyah Tampilan ini menjelaskan tentang peta rute daerah plaju dengan tujuan rumah sakit muhammadiyah, pada halaman peta terdapat beberpa titik simpul dan tombol next, pada tombol berfungsi untuk menuju kehalaman hasil jarak antar simpul, begitu juga untuk node-node simpul yang berfungsi untuk menampilkan nama-nama titik lokasi. Berikut ini adalah tampilan awal peta lokasi awal plaju dengan tujuan rumah sakit muhammadiyah pada gambar 4.4 dibawah ini :

69

Gambar 4.4 Tampilan Halaman Rute Awal Lokasi Bina Darma Menuju Rs Muhammadiyah 4.2.5. Tampilan Hasil Jarak Plaju Menuju Rumah Sakit Muhammadiyah Tampilan ini menjelaskan tentang hasil jarak daerah plaju dengan tujuan rumah sakit muhammadiyah, pada halaman hasil jarak plaju menuju rumah sakit muhammadiyah ini terdapat informasi yang menjelaskan jarak antar lokasi awal dengan tujuan dan dilengkapi dengan tombol A star dan Shooting Star pada tombol A star berfungsi untuk menampilkan halaman peta dengan algoritma A star sedangkan tombol shooting star berfungsi untuk menampilakn peta dengan algoritma shooting star, tampilannya pada gambar 4.5 dibawah ini :

70

Gambar 4.5 Tampilan Hasil Rute Bina Darma Menuju Rs Muhammadiyah 4.2.6. Tampilan Peta Algoritma A* Dari Universitas Bina Darma Menuju Rumah Sakit Muhammadiyah Tampilan ini menjelaskan tentang peta algoritma A* dari Universitas Bina Darma menuju rumah sakit muhammadiyah, pada halaman peta algoritma A* dari Universitas Bina Darma menuju rumah sakit muhammadiyah ini terdapat maker simpul hijau dan orange, untuk maker warna hijau merupakan maker awal lokasi sedangkan maker yang berwana orange merupakan tujuan lokasi, tampilannya pada gambar 4.6 dibawah ini :

71

Gambar 4.6 Tampilan Peta Algoritma A* Dengan Rute Bina Darma Menuju Rs Muhammadiyah 4.2.7. Tampilan Peta Algoritma Shooting* Dari Universitas Bina Darma Menuju Rumah Sakit Muhammadiyah Tampilan ini menjelaskan tentang peta algoritma Shooting* dari Universitas Bina Darma menuju rumah sakit muhammadiyah, pada halaman peta algoritma Shooting* dari Universitas Bina Darma menuju rumah sakit muhammadiyah ini terdapat pilihan untuk menentukan tujuan, setelah tujuan dipilih lalu lakukan dengan menyentuh peta untuk menampilkan rute algoritma shooting star, tampilannya pada gambar 4.7 dibawah ini :

72

Gambar 4.7 Tampilan Peta Algoritma Shooting* Dengan Rute Bina Darma Menuju Rs Muhammadiyah 4.2.8. Tampilan Peta Lokasi Plaju Menuju Rumah Sakit Umum Tampilan ini menjelaskan tentang peta rute daerah plaju dengan tujuan rumah sakit umum, pada halaman peta terdapat beberpa titik simpul dan tombol next, pada tombol next berfungsi untuk menuju kehalaman hasil jarak antar simpul, begitu juga untuk node-node simpul yang berfungsi untuk menampilkan nama-nama titik lokasi. Berikut ini adalah tampilan awal peta lokasi awal plaju dengan tujuan rumah sakit umum pada gambar 4.8 dibawah ini :

73

Gambar 4.8 Tampilan Halaman Rute Awal Plaju Menuju Rumah Sakit Umum 4.2.9. Tampilan Hasil Jarak Plaju Menuju Rumah Sakit Umum Tampilan ini menjelaskan tentang hasil jarak daerah plaju dengan tujuan rumah sakit umum, pada halaman hasil jarak plaju menuju rumah sakit umum ini terdapat informasi yang menjelaskan jarak antar lokasi awal dengan tujuan dan dilengkapi dengan tombol A star dan Shooting Star pada tombol A star berfungsi untuk menampilkan halaman peta dengan algoritma A star sedangkan tombol shooting star berfungsi untuk menampilakn peta dengan algoritma shooting star, tampilannya pada gambar 4.9 dibawah ini :

74

Gambar 4.9 Tampilan Hasil Rute Bina Darma Menuju Rs Umum 4.2.10. Tampilan Peta Algoritma A* Dari Universitas Bina Darma Menuju Rumah Sakit Umum Tampilan ini menjelaskan tentang peta algoritma A* dari Universitas Bina Darma menuju rumah sakit umum, pada halaman peta algoritma A* dari Universitas Bina Darma menuju rumah sakit umum ini terdapat maker simpul hijau dan orange, untuk maker warna hijau merupakan maker awal lokasi sedangkan maker yang berwana orange merupakan tujuan lokasi, tampilannya pada gambar 4.10 dibawah ini :

75

Gambar 4.10 Tampilan Peta Algoritma A* Dengan Rute Bina Darma Menuju Rs Umum 4.2.11. Tampilan Peta Algoritma Shooting* Dari Universitas Bina Darma Menuju Rumah Sakit Umum Tampilan ini menjelaskan tentang peta algoritma Shooting* dari Universitas Bina Darma menuju rumah sakit umum, pada halaman peta algoritma Shooting* dari Universitas Bina Darma menuju rumah sakit umum ini terdapat pilihan untuk menentukan tujuan, setelah tujuan dipilih lalu lakukan dengan menyentuh peta untuk menampilkan rute algoritma shooting star, tampilannya pada gambar 4.11 dibawah ini :

76

Gambar 4.11 Tampilan Peta Algoritma Shooting* Dengan Rute Bina Darma Menuju Rs Muhammadiyah 4.2.12. Tampilan Peta Lokasi Plaju Menuju Rumah Sakit Pusri Tampilan ini menjelaskan tentang peta rute daerah plaju dengan tujuan rumah sakit pusri, pada halaman peta terdapat beberpa titik simpul dan tombol next, pada tombol next berfungsi untuk menuju kehalaman hasil jarak antar simpul, begitu juga untuk node-node simpul yang berfungsi untuk menampilkan nama-nama titik lokasi. Berikut ini adalah tampilan awal peta lokasi awal plaju dengan tujuan rumah sakit pusri pada gambar 4.12 dibawah ini :

77

Gambar 4.12 Tampilan Halaman Rute Awal Plaju Menuju Rumah Sakit Pusri 4.2.13. Tampilan Hasil Jarak Plaju Menuju Rumah Sakit Pusri Tampilan ini menjelaskan tentang hasil jarak daerah plaju dengan tujuan rumah sakit pusri, pada halaman hasil jarak plaju menuju rumah sakit pusri ini terdapat informasi yang menjelaskan jarak antar lokasi awal dengan tujuan dan dilengkapi dengan tombol A star dan Shooting Star pada tombol A star berfungsi untuk menampilkan halaman peta dengan algoritma A star sedangkan tombol shooting star berfungsi untuk menampilakn peta dengan algoritma shooting star, tampilannya pada gambar 4.13 dibawah ini :

78

Gambar 4.13 Tampilan Hasil Rute Bina Darma Menuju Rs Pusri 4.2.14. Tampilan Peta Algoritma A* Dari Universitas Bina Darma Menuju Rumah Sakit Pusri Tampilan ini menjelaskan tentang peta algoritma A* dari Universitas Bina Darma menuju rumah sakit pusri, pada halaman peta algoritma A* dari Universitas Bina Darma menuju rumah sakit pusri ini terdapat maker simpul hijau dan orange, untuk maker warna hijau merupakan maker awal lokasi dan tujuan lokasi sedangkan maker yang berwana orange merupakan titik persimpangan, tampilannya pada gambar 4.14 dibawah ini :

79

Gambar 4.14 Tampilan Peta Algoritma A* Dengan Rute Bina Darma Menuju Rs Pusri 4.2.15. Tampilan Peta Algoritma Shooting* Dari Universitas Bina Darma Menuju Rumah Sakit Umum Tampilan ini menjelaskan tentang peta algoritma Shooting* dari Universitas Bina Darma menuju rumah sakit pusri, pada halaman peta algoritma Shooting* dari Universitas Bina Darma menuju rumah sakit pusri ini terdapat pilihan untuk menentukan tujuan, setelah tujuan dipilih lalu lakukan dengan menyentuh peta untuk menampilkan rute algoritma shooting star, tampilannya pada gambar 4.15 dibawah ini :

80

Gambar 4.15 Tampilan Peta Algoritma Shooting* Dengan Rute Bina Darma Menuju Rs Pusri 4.2.16. Tampilan Menu About Tampilan ini menjelaskan tentang about aplikasi yaitu berupa informasi tentang pembuat aplikasi . Berikut ini adalah tampilan menu about yang terdapat seperti gambar 4.16 dibawah ini :

81

Gambar 4.16 Tampilan Menu About 4.3

Menguji Sistem Untuk menguji coba serta menjalankan perangkat lunak pencarian rute

terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android ini, penulis menggunakan handphone smartphone android pada versi 4.1.2 (Jellybean). Metode pengujian yang digunakan oleh penulis adalah Metode Pengujian Black-Box. Metode ini berfokus pada persyaratan fungsional perangkat lunak. Dengan demikian, pengujian balck box memungkinkan perekayasa perangkat lunak mendapatkan serangkaian kondisi input yang sepenuhnya menggunakan semua persyaratan fungsional untuk suatu program. Adapun faktor-faktor pengujian blackbox adalah :

82

1. File integrity Menekankan pada data yang dimasukkan melalui aplikasi akan tidak bisa diubah. Prosedur yang akan memastikan bahwa file yang digunakan benar dan data dalam file tersebut akan disimpan sekuensial dan benar. 2. Service levels Menekankan bahwa hasil yang diinginkan di dapat dalam waktu yang di inginkan oleh user. Untuk mencapai keinginan tersebut, harus dilakukan penyesuaian antara keinginan user dengan sumber daya yang ada. 3. Ease of use Menekankan perluasan usaha yang diminta untuk belajar, mengoprasikan dan menyiapakan inputan, dan menginterpretasikan output dari sistem. Faktor ini tersangkut dengan usability sistem terhadap interaksi antara manusia dan sistem. 4. Authorization Menjamin

data

diproses

sesuai

dengan

ketentuan

manajemen.

Authorization menyangkut proses transaksi secara umum dan khusus. Fokus Pengujian Black box testing yaitu sebagai berikut : a) Menguji fungsi-fungsi khusus dari aplikasi. b) Test input dan output untuk fungsi yang ada tanpa memperhatikan prosesnya. Beberapa jenis kesalahan yang dapat di identifikasi : 1) Fungsi tidak benar atau hilang, 2) Kesalahan antar muka,

83

3) Kesalahan pada struktur data (pengaksesan basis data), 4) Kesalahan inisialisasi dan akhir program. 4.3.1

Rencana Pengujian Rencana pengujian selengkapnya dapat dilihat pada tabel 4.1 berikut:

Item Yang Diuji

Menu Utama

Bagian Tombol Rumah Sakit Tombol About Tombol Keluar

Jenis Pengujian BlackBox BlackBox BlackBox BlackBox

BlackBox Halaman Peta Lokasi Plaju BlackBox Halaman Peta Lokasi Peta Perumnas Halaman Peta Lokasi Km- BlackBox 12 BlackBox Peta Rute A* Plaju Peta Rute Shooting* Plaju BlackBox BlackBox Peta Rute A* Perumnas BlackBox Menu A* Peta Rute Shooting* Menu Shooting* Perumnas BlackBox Peta Rute A* KM 12 BlackBox Peta Rute Shooting* KM 12 Tabel 4.1 menunjukkan bagian-bagian yang akan diuji perangkat lunak

pencarian rute terpendek pemetaan rumah sakit dengan perhitungan algoritma A* dan Shooting* berbasis android. Ada 3 bagian inti pada aplikasi yang akan diuji, yaitu menu Menu Peta, Menu A* dan Shooting* merupakan menu ketiga bagian aplikasi itu akan diuji menggunkan metode BlackBox. Tabel 4.2 Pengujian Menu Peta No

1

Item Yang Diuji

Peta Lokasi Daerah Plaju

Cara Pengujian

Klik Link

Hasil yang diharapkan

Menampilkan isi peta lokasi daerah plaju

Hasil Pengujian Sesuai Harapan

Berhasil/ Tidak Berhasil Berhasil

84

2

3

Peta Lokasi Daerah Perumnas Peta Lokasi Daerah KM-12

Klik Link

Menampilkan isi peta lokasi daerah perumnas

Sesuai Harapan

Berhasil

Klik Link

Menampilkan isi peta lokasi daerah km 12

Sesuai Harapan

Berhasil

Tabel 4.2 merupakan hasil pengujian menu rute A* RS Muhammadiyah Tabel 4.3 Pengujian Menu A* RS Muhammadiyah No

1 2

Item Yang Diuji

Cara Pengujian

Tombol A*

Klik Link

Peta A*

Klik Link

Hasil yang diharapkan Menampilkan dialog rute lokasi A* Menampilkan lokasi rute A*

Hasil Pengujian Sesuai Harapan Sesuai Harapan

Berhasil/ Tidak Berhasil Berhasil Berhasil

Tabel 4.3 merupakan hasil pengujian menu pencarian rute Shooting* RS Muhammadiyah Tabel 4.4 Pengujian Menu Shooting* RS Muhammadiyah No

1 2 3

Item Yang Diuji Menu Shooting* Plaju Pilihan Lokasi Awal Pilihan Lokasi Tujuan

Cara Pengujian

Klik Link Klik Link Klik Link

Hasil yang diharapkan

Hasil Pengujian

Berhasil/ Tidak Berhasil

Menampilkan dialog pencarian lokasi

Sesuai Harapan

Berhasil

Menampilkan lokasi awal Menampilkan lokasi tujuan

Sesuai Harapan Sesuai Harapan

Berhasil Berhasil

Tabel 4.4 merupakan hasil pengujian menu rute A* Rs Umum Tabel 4.5 Pengujian Menu A* Rs Umum No

Item Yang Diuji

Cara Pengujian

Hasil yang diharapkan

Hasil Pengujian

Berhasil/ Tidak Berhasil

85

1 2

Tombol A*

Klik Link

Peta A*

Klik Link

Menampilkan dialog rute lokasi A* Menampilkan lokasi rute A*

Sesuai Harapan Sesuai Harapan

Berhasil Berhasil

Tabel 4.5 merupakan hasil pengujian menu pencarian rute Shooting* Rs Umum Tabel 4.6 Pengujian Menu Shooting* Rs Umum No

1 2 3

Item Yang Diuji Menu Shooting* RS Umum Pilihan Lokasi Awal Pilihan Lokasi Tujuan

Cara Pengujian

Klik Link Klik Link Klik Link

Hasil Pengujian

Hasil yang diharapkan

Berhasil/ Tidak Berhasil

Menampilkan dialog pencarian lokasi

Sesuai Harapan

Berhasil

Menampilkan lokasi awal Menampilkan lokasi tujuan

Sesuai Harapan Sesuai Harapan

Berhasil Berhasil

Tabel 4.6 merupakan hasil pengujian menu rute A* Rs Pusri Tabel 4.7 Pengujian Menu A* Rs Pusri No

1 2

Item Yang Diuji

Cara Pengujian

Tombol A*

Klik Link

Peta A*

Klik Link

Hasil yang diharapkan Menampilkan dialog rute lokasi A* Menampilkan lokasi rute A*

Hasil Pengujian Sesuai Harapan Sesuai Harapan

Berhasil/ Tidak Berhasil Berhasil Berhasil

Tabel 4.7 merupakan hasil pengujian menu pencarian rute Shooting* Rs Pusri Tabel 4.8 Pengujian Menu Shooting* Rs Pusri No

1 2 3

Item Yang Diuji Menu Shooting* RS Pusri Pilihan Lokasi Awal Pilihan Lokasi Tujuan

Cara Pengujian

Klik Link Klik Link Klik Link

Hasil yang diharapkan

Hasil Pengujian

Berhasil/ Tidak Berhasil

Menampilkan dialog pencarian lokasi

Sesuai Harapan

Berhasil

Menampilkan lokasi awal Menampilkan lokasi tujuan

Sesuai Harapan Sesuai Harapan

Berhasil Berhasil

86

BAB V KESIMPULAN DAN SARAN 5.1 Kesimpulan Berdasarkan dari hasil penelitian yang telah dilakukan dalam membahas pencarian rute terpendek menuju rumah sakit dengan menggunakan perhitungan algoritma A star (A*) dan algoritma Shooting star (Shooting*). Adapun kesimpulan dan saran yang dapt diambil sebagai berikut : 1. Hasil Penelitian ini berupa sebuah perangkat lunak yang dapat digunakan untuk menentukan rute terpendek menuju lokasi rumah sakit yang ada dikota Palembang. 2. Perangkat lunak ini dikembangkan dengan menggunakan algoritma A star (A*) dan algoritma Shooting star (Shooting*) dalam menentukan rute terpendek menuju lokasi tujuan dengan menggunakan metode Spiral dalam proses pengembangan perangkat lunak ini. 3. Perangkat lunak ini dapat disimulasikan pada perangkat smartphone berbasis Operating System Android dengan versi Android diatas 4.2.2 (Jelly Bean).

86

87

.5.2 Saran Berdasarkan dari penelitian yang telah dilakukan maka penulis memberikan saran sebagai berikut: 1. Diharapkan Perangkat Lunak ini dapat digunakan oleh masyarakat untuk mencari rute menuju lokasi rumah sakit dengan daerah asal Plaju, Perumnas, dan daerah Km 12. 2. Perangkat Lunak ini hanya terbatas pada tiga titik tujuan lokasi dan tiga titik asal pencarian, diharapkan pada penelitian selanjutnya dapat dikembangkan dengan menambah titik tujuan dan titik asal pencarian. 3. Perangkat Lunak ini pada tampilan interface terbilang sangat sederhana, sehingga diharapkan pada penelitian selanjutnya dapat dikembangkan dengan menambahkan fitur-fitur yang menarik.