JIRE (Jurnal Informatika & Rekayasa Elektronik.
http://e-journal.
id/index.
php/jire Volume 2.
No 2.
Nopember 2019
PERBANDINGAN PERHITUNGAN MANUAL DENGAN ALGORITMA A
STAR DALAM PENCARIAN JALUR TERPENDEK UNTUK PENGIRIMAN
PESANAN DODOL KHAS LOMBOK
Mayadi1.
Raisul Azhar2 1,Ilmu Komputer.
Universitas Bumigora, 2,Ilmu Komputer.
Universitas Bumigora Jl.
Ismail Marzuki No.
Cilinaya.
Kec.
Cakranegara.
Kota Mataram 83127 1 mayadi.
yadot@universitasbumigora.
id, 2 Raisul.
azhar@universitasbumigora.
Abstract Existing order delivery officer PT Phonix orders shipments from warehouses to otlets in the city of Mataram by passing or crossing the same road, to minimize the distance and destination to be addressed, it is necessary to find the shortest path from warehouse to outlets and outlets -drivers are in the city of Mataram.
The shortest path search is the right solution for sending Dodol Lombok special orders to customers and private outlets in the city of Mataram, the shortest path search is to determine which path is the fastest to be traversed or traversed.
Algorithm A * is one method that can be used to search for the shortest path, using this method it is expected that dispatchers in existing warehouse can more quickly find the path which is the shortest and faster to find a goal in the search for the shortest path of sending customer orders in the area chili using the A * algorithm.
From this study conducted two testing processes, namely testing using manual calculations and testing using the A * algorithm, from which in the test obtained the shortest path of 15,750 and using the A * algorithm obtained the smallest path of 14,500, to the search using a fairly multiply algorithm calculation.
Keywords : Searching.
Heuristic.
Graf.
Algoritma *, the shortest.
Abstrak Petugas pengiriman pesanan yang ada PT Phonix melakukan pengiriman pesanan dari gudang ke otletotlet yang ada di kota mataram dengan melewati atau melintasi jalan yang sama, untuk meminimalkan jarak dan tujuan yang akan dituju maka diperlukan pencarian jalur terpendek dari gudang ke otlet-otlet dan gerai-gerai yang ada dikota mataram.
Pencarian jalur terpendek adalah solusi yang tepat untuk mengirimkan pesanan dodol khas Lombok ke pelanggan dan otlet persendirian yang ada dikota mataram, pencarian jalur terpendek adalah yaitu dapat menentukan jalur mana yang paling cepat untuk dilalui atau Algoritma A* adalah salah satu metode yang bisa digunakan untuk pencarian jalur terpendek, dengan menggunakan metode ini diharapkan petugas pengiriman pesanan yang ada gudang dapat lebih cepat menemukan jalur mana yang paling singkat dan lebih cepat untuk menemukan goal pada pencarian jalur terpendek pengiriman pesanan pelanggan di daerah lombok dengan menggunakan algoritma A*.
Dari penelitian ini melakukan dua proses pengujian yaitu pengujian menggunakan perhitungan manual dan pengujia menggunakan algoritma A*, dari pengujian secara manaual didapatkan jalur terpendek 750 dan dengan menggunakan algoritma A* didapatkan jalur terkecil 14.
500, hingga pencarian dengan menggunakan perhitungan algoritma cukup biak.
Kata kunci : Searching.
Heuristic.
Graf.
Algoritma *, the shortest ISSN.
2620-6900 (Onlin.
2620-6897 (Ceta.
JIRE (Jurnal Informatika & Rekayasa Elektronik.
http://e-journal.
id/index.
php/jire Pendahuluan Pada era teknologi dan informasi saat ini sangat membantu dan memudahkan dalam semua kegiatan khususnya dengan teknologi google map yang bisa mempermudah untuk menemukan lokasi yang akan kita tuju, bukan hanya perkembagan perangkat lunak perangkat keras pun dengan cepatnya evolusi mulai dengan computer sampai handpone berbasis android yang bisa digunakan layaknya kemudahan itu pada penelita ini mencoba algoritma A* untuk penentuan jalur terdekat dan istimasi biaya yang dikeluarkan dengan memperkitakan biaya yang terkecil untuk dilewati sehingga bisa menghemat biaya pengiriman, pada penelitian ini melakukan analisis pada Phoenix food yang bergerak dibidang penyedia dan penyaplai oleh-oleh khas Lombok.
PT Phonix merupakan perusahaan yang bergerak dalam bidang jasa pengolahan makanan yang berupa dodol khas Lombok yang terbuat dari rumput laut yang berlokasi di candu baya dasan cermen matarm NTB.
Perusahan ini mendistribusikan hasil produksinya ke gerai gerai atau ke otlet otlet yang sudah ditentukan seperti pusat oleh oleh khas Lombok.
Karna dalam hal ini Phonik sebagai pihak pruduksi harus melakukan pengiriman kepada pihak pemesan atau pihak pihak yang sudah terdaftar sebagai pelanggan di samping itu PT Phonix memiliki cabang otletotlet sendiri di beberapa wilayah di Lombok sehingga perlu adanya suplay barang ke lokasi lokasi tersebut begitu juga dengan otlet-otlet dan grai-grai lainnya.
Jalur terpendek dapat kombinatorial dalam grafik dengan bobot terbatas, atau sebagai masalah optimasi yang terus berkelanjutan dalam Geometri Euclidian .
Pada penacarian jalur terpendek untuk menentuka jalur yang dilewati bukan hanya berdasarkan jarak tapi ada beberapa hal yang perlu dipertimbangkan seperti estimasi biaya dan jumlah trafik light di setiap jalan yang dilewati dan berapa lama waktu dari masing masing lampu jalan yang leati.
Tinjauan Pustaka dan Teori Tinjauan Pustaka Dalam penelitan ini ada beberapa tinjauan pustaka yang digunakan untuk memaksimalkan menambah bahan pada penelitian ini yaitu:
ISSN.
2620-6900 (Onlin.
2620-6897 (Ceta.
Volume 2.
No 2.
Nopember 2019 Talai.
tentang Aplikasi Pencarian Jalur Terpendek Pada Rumah Sakit Umum Bahteramas Menggunakan Algoritma A* (A-Sta.
melakukan penelitian mengenai jalur terpendek menuju gedung pelayanan dirumah sakit kendari dengan menerapkan Algoritma A* dalam hal ini dibutuhkan beberapa data yaitu, berhubungan .
ost antar nod.
dan koordinat setiap node.
Dengan data tersebut, maka pencarian jalur terpendek pada ruangan dapat diimplementasikan .
Pramono.
penelitian bertujuan untuk menghasilkan sebuah produk game tiga dimensi sebagai upaya untuk menyampaikan informasi mengenai konsep pertanian higienis.
Dalam game RPG diperlukan suatu penerapan suatu algoritma pathfinding sebagai implementasi penghalang Model perancangan yang digunakan adalah model prosedural, merupakan model penelitian yang bersifat deskriptif, yang menggariskan langkahlangkah yang harus di ikuti untuk menghasilkan sebuah produk.
Pengumpulan data dilakukan dengan cara studi literatur mengenai algoritma pathfinding A* dan game komputer, serta identifikasi target audiens dan produk Tahap ujicoba pada penerapan algoritma A* ini dilakukan dengan 2 pola yaitu uji coba internal dan uji coba eksternal.
Berdasarkan hasil ujicoba yang telah dilakukan terhadap algoritma A* dalam game higienis dapat disimpulkan algoritma A* dapat diimplementasikan dengan perancangan game tanaman organis terutama pada pergerakan penghalang .
Irsyad, .
penelitiannya menjelaskan mengenai pencarian jalur gedung dan ruangan pada Universitas Islam Negeri Sultan Syarif Kasim Riau dimana pada penelitian ini membuat sebuah aplikasi peta digital untuk mempermudah mengetahui lokasi dan jalur yang akan di cari dan dilewati .
Syukriyah.
mempelajari cara kerja algoritma A* dalam mencari jarak tercepat, yang disimulasikan seperti kondisi ketika seorang mencari rute dalam keadaan jalanan macet.
Simulasi ini memberikan gambaran yang lebih realistis terhadap perilaku algoritma A dalam pencarian jarak tercepat, dan untuk itu, akan dibangun sebuah aplikasi sebagai pendukung proses simulasi tersebut .
JIRE (Jurnal Informatika & Rekayasa Elektronik.
http://e-journal.
id/index.
php/jire Karim.
melakukan penelitian mengenai pencarian jalur pengiriman barang ke pos daerah medan dengan menggunakan algoritma A* dimana tujuannya ingin melihat jalur yang mana yang singkat dan dekat untuk dilewati saat pengiriman barang ke pos medan .
Algoritma * Algoritma A* (A sta.
dikenal sebagai salah satu algoritma yang paling sering digunakan untuk pencarian jalur .
ath findin.
dan penerusan grafis .
raph traversa.
, yaitu proses plotting jalur yang paling efisien antar titik, yang disebut dengan nodes.
Metode A* adalah metode yang merupakan hasil pengembangan dari metode dasar Best First Search.
Metode ini mengevaluasi setiap titik dengan mengkombinasikan dengan g.
, nilai untuk mencapai titik n dari titik awal, dan h.
, nilai perkiraan untuk mencapai tujuan dari titik n tersebut.
Dalam hal ini algoritma dapat digunakan sebagai metode untuk mengetahui langkah-langkah secara urut untuk mencapai Setiap algortima memiliki perbedaan dalam mencapai tujuan seperti algoritma A Star.
Fungsi f.
sebagai estimasi fungsi evaluasi terhadap noden Metodologi Penelitian Pengumpulan Data Google Data Rute Gambar 2.
Jalur Yang Akan Dilewati Keterangan:
Lokasi A Gudang PT Phonix Food Lokasi B Otlet Sasaku Lokasi C Gendrung Sasak Lokasi D Pasar seni Lokasi E Mall Mataram Lokasi F Bundaran jempong Lokasi G Ampenan Lokasi H Meninting oleh-oleh Lokasi I Senggigi Pada tahap ini merupakan awal dalam mengolah data input sebelum memasuki proses tahapan utama.
Disini data rute akan dihitung menggunakan Algoritma A* dan dihitung secara manual utuk melihat hasil apakah proses jalur yang dilewati menggunakan Aloritma A* menghasilkan nilai yang akurat dengan perhitungan secara manual.
Proses Algoritma A* Proses Algoritma A* Pengumpulan Data Pada tahap ini dilakukan pengumpulan data yang akan digunakan untuk pecarian rute.
Gambar 2 berikut ini merupakan bentuk data biaya setiap lokasi yang di lewati yang didapat dari lapangan.
Preprocessing Metode penelitian yang digunakan pada penelitian ini adalah studi kasus dengan alur seperti Gambar 1 berikut:
Phoenix Food Volume 2.
No 2.
Nopember 2019 Hitung Manual Hasil Proses Implementasi Gambar 1.
Alur Penelitian ISSN.
2620-6900 (Onlin.
2620-6897 (Ceta.
Algoritma A* merupakan penggabungan dari algoritma Best First Search.
Uniform Cost Search dan Greedy Best-First Search yang digunakan untuk mencari lintasan terpendek pada suatu graf, sama seperti hal nya best fist searh, uniform cost search dan greedy best-fist searh algoritma A* juga menggunakan fungsi- fungsi hiuristik dan biaya yang diperhitungkan didapat dari biaya sebenar nya ditambah dengan biaya perkiraan lintasa .
JIRE (Jurnal Informatika & Rekayasa Elektronik.
http://e-journal.
id/index.
php/jire Volume 2.
No 2.
Nopember 2019 Fungsi f.
sebagai estimasi fungsi evaluasi terhadap noden Dimana f.
= Biaya evaluasi g.
= Biaya yang sudah dikeluarkan dari keadaan awal sampai keadaan n.
= Estimasi biaya untuk sampai pada suatu tujuan mulai dari n.
Sedangkan untuk biaya perkiraan (Jarak Garis Luru.
dari masing masing vertex terhadap titk A menuju vertex akhir I dapat di lihat pada gambar 3.
Gambar 3.
Tabel rincian Perkiraan biaya dari Masing- Masing Vertex Terhadap Titik Awal A Menuju Vertex Akhir I.
Untuk mengetahui biaya dan jarak yang terdekat akan dilewati perlu melakukan perhitungan dengan menggunakan Algoritma A*.
Hasil dan Pembahasan Perhitungan Dengan A* Dalam terpendek pada proses pengiriman Dodol dengan menggunakan Algoritma A* terdiri dari beberapa langkah:
Langkah 1 Pada awal list OPEN hanya terdapat satu vertex Awal yaitu A diaman A merupakan loaksi awal perjalanan.
Sehingga A terpilih sebagai Not awal untuk prose,selanjutnya dipindahkan ke list CLOSED, kemudian bangkitkan semua tetangga terdekat dari A, yaitu: B.
E dan C.
karena ke tetangga tedekat tidak ada pada open maupun list CLOSED, maka ketiganya dimasukkan ke bagian list OPEN.
Langkah 1 ini menghasilkan list turunan maka OPEN= [B.
C dan E] dan A CLOSED kemuadian Evaluasi:
F(B) = g(A) g (A ke B) h(B) = 0 3.
150 300 = 3.
F(C) = g(A) g (A ke C) h(C) = 0 4.
150 1000 = 5.
F(E) = g(A) g (A ke E) h(E) = 0 5.
000 = 7000
ISSN.
2620-6900 (Onlin.
2620-6897 (Ceta.
Gambar: 4.
Proses 1 Langkah 2 mencari nilai terkecil dari tentangga terdekat dari B Dari perhitungan langkah pertama ditemuakan B memilikijarak terkecil yaitu 3.
sehingga terpilih menjadi not terbaik untuk dilewati dan not B dipindahkan ke CLOSED.
Kemudian anak tangga B dibangkitkan, yaitu: F belum pernah ada di Bagian OPEN maupun list CLOSED, maka F dimasukkan ke bagian OPEN, dan langkah kedua ini menghasilkan anak tangga OPEN= [F] dan CLOSED= [A.
E].
Evaluasi:
f(F) = g(F) g (B ke F) h(F) = 3.
500 = 6.
Gambar: 5.
Langkah Proses 2 Langkah 3 mencari nilai terkecil dari anak tetangga F Dari pencarian langkah ke dua didapatkan lintasan nilai terkecil adalah F dari anak tangga B dengan jarak terkecil, yaitu 6.
650 terpilih sebagai jalur terkecil dan dipindahkan ke list CLOSED.
Lalu, semua anak tangga dari F dibangkitkan, yaitu: E dan G karena E sudah JIRE (Jurnal Informatika & Rekayasa Elektronik.
http://e-journal.
id/index.
php/jire pernah ada di list OPEN maka E di CLOSED dan G
belum pernah ada di list OPEN maupun CLOSED, maka G dimasukkan ke list OPEN pada langkah
ke tiga menghasilkan OPEN= [G] dan CLOSED
=[F]
f(E) = g(D) g(D ke E ) h(E) Volume 2.
No 2.
Nopember 2019 Karena memiliki I memiliki biaya terkecil, 500 terpilih sebagai Best Node karena BestNode sama dengan Goal, berarti solusi sudah ditemukan.
Sehingga hasil dari jalur yang dilewati adalah A.
G dan I dengan garis warna merah sebagai jalur terdekat seperti terlihat pada gambar 8.
= 6.
150 2000 = 11.
Gambar 8.
Rute berdasarkan Algoritma A*.
Gambar: 6 Proses 3 Langkah 4 mencari nilai terkecil dari anak Jalur G merupakan jalaur terkecil dari turunan F dengan jarak terkecil, yaitu 11.
terpilih sebagai jalur lintasan terbaik kemudian dipindahkan ke bagian CLOSED.
Lalu, semua turunan G dibangkitkan, yaitu: E.
H, dan I karena E sudah pernah dilewati maka E di CLOSED dan H, dan I belum pernah ada di list OPEN, maka H, dan I dimasukkan ke list OPEN dan langkah emapt ini menghasilkan OPEN= [H.
I] dan CLOSED = [E] Evaluasi:
f(H) = g(H) g (G ke H) h(H) = 11.
200 1000 = 16.
f(G) = g(I) g (G ke I) h(I) = 11.
350 0 = 14.
Gambar: 7.
Gambar Jalur terbaik Pencarian ISSN.
2620-6900 (Onlin.
2620-6897 (Ceta.
Perhitungan Manual Pada proses ini merupakan proses perhitungan manual yang diguanakan untuk melihat perbandingan akurasi dari algoritma A*, apakah dari perhitungan manual tersebut terdapat hasil yang lebih kecil dari algoritma A*.
Jalur A.
I A ke E F(E) = g(A) g (A ke E) h(E) = 5.
000 = 7.
E ke G F(G) = g(E) g (E ke G) h(G) = 7.
000 = 13.
G ke I F(I) = g(G) g (G ke I) h(I) = 13.
000 0 2.
500 = 15.
Jadi jumlah biaya menggunakan jalur A.
G, dan I secara hitungan manual adalah Jalur A.
D I A ke E F(E) = g(A) g (A ke E) h(E) = 0 5.
000 = 7.
E ke D F(D) = g(E) g (E ke D) h(H) = 7.
500= 13.
D ke H F(H) = g(D) g (D ke H) h(H) JIRE (Jurnal Informatika & Rekayasa Elektronik.
http://e-journal.
id/index.
php/jire = 13.
000= 17.
H ke I F(I) = g(H) g (H ke I) h(I) = 17.
900 900 0= 18.
Dari hasil perhitungan berdasarakan hitungan manul dengan rute A.
D dan I didapat jumlah biaya yang dikeluarkan Jalur A.
I A ke E F(E) = g(A) g (A ke E) h(E) = 0 5000 2.
000 = 7.
E ke F F(F) = g(E) g (E ke F) h(F) = 7.
500= 11.
F ke G F(G) = g(F) g (F ke G) h(G) = 11.
500 = 17.
Volume 2.
No 2.
Nopember 2019 Dari penyelesaian mencarai rute dengan hitungan secara manual didapatkan hasil seperti pada tabel 1, dimana biaya yang paling minimal adalah rute no 1 sebesar 15.
000, sedangkan perhitungan dengan menggunakan Algoritma A* dengan rute A.
G dan I sebesar 14.
Tabel 1.
Hasil pencarian rute secara manual.
Jalur A.
I A.
I A.
I A.
I Setelah perhitungan dengan Algoritma A* dengan perhitungan manual maka Algoritma A* sangat baik diterapkan dalam pencarian dimana hasil perhitungan secara manual mendapatkan biaya terkecil sebesar 15.
750 sedangkan Algoritma A* 500 maka algoritma A* bisa dikatakan sangat sesuai ditrapkan dalam G ke I Implementasi Dengan Program F(I) = g(G) g (G ke I) h(I) Setelah melakukan perhitungan secara manual dengan jalur A.
G dan I maka didapat jarak dengan total biaya sebesar 19.
Setelah melakukan perhitungan dengan implementasi ini memaparkan tampilan aplikasi menggunakan Bahasa pemrograman java dengan NetBeans.
Jalur A.
I Halaman Utama A ke C Form ini berfungsi sebagai halaman paling utama dari aplikasi dimaan pada bagian ini terdiri dari menu menu yang akan diproses seperti halaman input dan halaman pencarian seperti terlihat pada gambar 9:
= 17.
350 0 = 19.
F(C) = g(C) g (A ke C) h(C) = 0 4.
150 1000 = 5.
C ke D F(D) = g(C) g (C ke D) h(D) = 5.
500 = 10.
D ke H F(H) = g(D) g (D ke H) h(H) = 10.
500 1000 = 15.
H ke I F(I) = g(H) g (H ke I) h(I) = 15.
250 900 0 = 15.
Setelah melakukan perhitungan secara manual dengan jalur A.
H dan I maka didapat jarak dengan total biaya sebesar 15.
ISSN.
2620-6900 (Onlin.
2620-6897 (Ceta.
Gambar: 9.
Form Menu Utama Halaman Input Jarak Pada form ini digunakan sebagai halaman untuk input nama jalan/objek baru serta jarak dari objek, sepeti terlihat pada gambar 10 dibawah ini:
JIRE (Jurnal Informatika & Rekayasa Elektronik.
http://e-journal.
id/index.
php/jire Volume 2.
No 2.
Nopember 2019 Food karna dari hasil perhitungan menggunakan A* didapatkan hasil untuk biaya yang di keluarkan sebesar 14.
sedangkan hasil perhitungan secara manual biaya terendah sebesar 15.
Saran Aplikasi ini ada kekurangan perlu dikembangkan dengan menggunakan data atau lokasi yang luas sehingga bisa lebih Gambar: 11 Form Jarak dan Tujuan Halaman Input Koordinat Pada form ini digunakan untuk membuat dan mengubah koordinat dari sebuah jalur/peta,sebagaimana telihat pada gambar 11.
Daftar Pustaka: