Implementasi algoritma A-Star dalam menentukan rute terpendek destinasi wisata Kota Malang

INDONESIA:

Berwisata menjadi salah satu kebutuhan setiap orang untuk merelaksasikan pikiran dari kesibukan yang dijalani di setiap harinya. Salah satu kota di Jawa Timur yang menjadi tempat primadona untuk berwisata adalah Kota Malang, kota terbesar kedua di Jawa Timur setelah Surabaya. Kota ini memiliki kurang lebih 43 destinasi wisata. Biasanya wisatawan yang ingin berkunjung tidak hanya ke salah satu tempat, namun beberapa tempat. Akibatnya dibutuhkan sebuah bantuan untuk menentukan destinasi mana saja yang harus dikunjungi terlebih dahulu agar perjalanan berwisata mereka menjadi efektif. Proses pencarian rute terpendek pada penelitian ini menggunakan Algoritma A-Star, salah satu algoritma BFS yang dalam prosesnya sangat mempertimbangkan nilai heuristik. Nilai heuristik diperoleh dari jarak setiap titik menuju titik tujuan. Proses pengujian rute terpendek dilakukan dengan memilih titik awal, kemudian memilih beberapa lokasi wisata. Selanjutnya akan dicari rute terpendek menggunakan algoritma A-star pada setiap destinasi, kemudian dipilih destinasi mana yang akan dikunjungi pertama. Begitupun seterusnya sampai destinasi terakhir. Keefektifan rute melibatkan perbandingan dengan rute yang disajikan oleh google maps. Berdasarkan hasil 30 kali percobaan pada beberapa destinasi yang bersifat menyeluruh, didapatkan hasil bahwa rata-rata pencarian rute menggunakan algoritma A-Star adalah 44,17% lebih pendek dibandingkan yang tersaji pada google maps. Hal ini dikarenakan keunikan dari algoritma di mana terdapat nilai heuristik dan penyeleksian pada tiap destinasi sehingga menjadikan rute lebih efektif.

ENGLISH:

Traveling is one of the necessary for everyone to relax the mind from the busy work daily activities. One of the most favorite cities in East Java for traveling is Malang City, the biggest city in East Java after Surabaya. This city has approximately 43 tourist destinations. The tourists usually want to visit not only just one place, but several places. As a result, an assistance is needed to determine which destinations must be visited first, so their travel trip becomes more effective. The process of finding the shortest path in this research uses the A-Star Algorithm, one of the BFS algorithms which in the process really considers the heuristic values. The heuristic values are obtained from the distance of each nodes to the destination node. The process of testing the shortest path is done by selecting a starting node, then selecting several tourist destinations. Next, the shortest path will be searched using the A-star algorithm at each destination, then which destination to visit first will be chosen. This procces will be run until the final destination has been visited. The effectiveness of the path will involve the comparison between the final path of research and final path presented by google maps. Based on the results of comprehensive 30 trials on several destinations, the result show that the average of final path using the A-Star algorithm was 44.17% shorter than presented on google maps. This is due to the uniqueness of the algorithm in which there are a selection at each destination and heuristic values, so it make the final path more effective.

ARABIC:

الرحلة هي من احتياجات للناس جميعا لإرخاء الذهن من الانشغال اليومي. مدينة مالانج هي إحدى المدن في جاوي الشرقية وهي من المدن الجملة للرحلة. وهي المدينة الكبيرة الثانية في جاوي الشرقية بعد سورابايا. وفيها هناك٤٣ وجهة سياحية. ومن العادة ، كان السياح لا يحبّ للزيارة فى مكان واحد، ولكن عدة أماكن. ولذلك ، تحتاج إلى مساعدة لتحديد الوجهات التي يجب زيارتها أولاً حتى تكون رحلات الرحلة الخاصة بهم فعالة. وأما عملية إيجاد أقصر طريق في هذه الدراسة تستخدم خوارزمية(A-Star) . إحدى خوارزميات (BFS)والتي تعتبر في العملية القيم الاستدلالية حقًا. يتم الحصول على القيمة الإرشادية من مسافة كل نقطة إلى نقطة الوجهة. تتم عملية اختبار أقصر طريق عن طريق اختيار نقطة البداية ثم اختيار عدة مواقع سياحية. بعد ذلك ، سيتم البحث عن أقصر طريق باستخدام خوارزمية (A-star) في كل وجهة ، ثم الوجهة التي سيتم زيارتها أولاً. وهكذا حتى الوجهة النهائية. ستشمل فعالية المسار المقارنة مع المسار الذي قدمته خرائط (Google). بناءً على نتائج ٣٠ تجربة على عدة وجهات شاملة ، وجد أن متوسط البحث عن المسار باستخدام خوارزمية (A-Star) كان أقصر بنسبة ٪ ٤٤,١٧ من ذلك المعروض على خرائط (Google). ويرجع ذلك إلى تفرد البحث حيث توجد قيمة إرشادية واختيار لكل وجهة لجعل المسار أكثر فعالية.