Optimasi rute wisata Kabupaten Mojokerto menggunakan algoritma a-star untuk penentuan rute terpendek

ABSTRAK

Berwisata menjadi pilihan populer untuk mengisi waktu liburan sambil menikmati keindahan alam dan mengunjungi tempat-tempat bersejarah. Kabupaten Mojokerto, yang terletak di Jawa Timur, menjadi salah satu destinasi favorit karena kaya akan wisata budaya. Dengan lebih dari 25 destinasi wisata alam dan sejarah, wisatawan sering kali ingin mengunjungi beberapa tempat sekaligus dalam satu perjalanan. Oleh karena itu, diperlukan metode yang membantu merencanakan rute kunjungan agar lebih efisien. Penelitian ini memanfaatkan Algoritma A-Star untuk menemukan rute terpendek antara destinasi-destinasi wisata, dengan mengandalkan perhitungan nilai heuristik yang diperoleh dari jarak antar titik menggunakan formula haversine. Prosesnya dimulai dengan pemilihan titik awal perjalanan, dilanjut menentukan urutan destinasi yang menghasilkan rute terpendek menggunakan algoritma A-Star. Proses ini terus berlanjut hingga semua destinasi yang diinginkan terkunjungi. Efektivitas rute yang dihasilkan kemudian diuji terhadap rute yang disediakan oleh Google Maps. Dari 10 uji coba rute wisata, Algoritma A-Star menghasilkan rute rata-rata 32,1% lebih pendek. Pengujian juga menunjukkan bahwa A-Star mengungguli metode Greedy dan Dijkstra dalam menemukan rute terpendek. Algoritma ini diharapkan membantu wisatawan merancang perjalanan yang lebih efisien, menghemat waktu dan energi.

ABSTRACT

Traveling is a popular choice to fill your vacation time while enjoying the beauty of nature and visiting historical places. Mojokerto Regency, located in East Java, is one of the favorite destinations for its rich cultural tourism. With more than 25 natural and historical tourist destinations, tourists often want to visit several places in one trip. Therefore, there is a need for a method that helps plan visit routes more efficiently. This research utilizes the A-Star Algorithm to find the shortest route between tourist destinations, relying on the calculation of the heuristic value obtained from the distance between points using the haversine formula. The process begins with the selection of the starting point of the trip, followed by determining the sequence of destinations that produce the shortest route using the A-Star algorithm. This process continues until all desired destinations are visited. The effectiveness of the resulting route is then tested against the route provided by Google Maps. From 10 trials of tourist routes, the A-Star algorithm produces an average route that is 32.1% shorter. The test also shows that A-Star outperforms the Greedy and Dijkstra methods in finding the shortest route. This algorithm is expected to help tourists design more efficient trips, saving time and energy.

مستخلص البحث

يُعد السفر خياراً شائعاً لملء وقت عطلتك أثناء الاستمتاع بجمال الطبيعة وزيارة الأماكن التاريخية. تُعد محافظة موجوكيرتو، الواقعة في جاوة الشرقية، إحدى الوجهات المفضلة بسبب غنى معالمها الثقافية. مع وجود أكثر من ٢٥ وجهة سياحية طبيعية وتاريخية، غالباً ما يرغب المسافرون في زيارة عدة أماكن في رحلة واحدة. لذلك، هناك حاجة إلى طريقة تساعد في تخطيط مسارات الزيارة بشكل أكثر كفاءة. يستخدم هذا البحث خوارزمية A-Star لإيجاد أقصر طريق بين الوجهات السياحية، بالاعتماد على حساب القيمة الاستدلالية التي يتم الحصول عليها من المسافة بين النقاط باستخدام صيغة الهافرسين. وتبدأ العملية باختيار نقطة بداية الرحلة، يليها تحديد تسلسل الوجهات التي تنتج أقصر طريق باستخدام خوارزمية .A-Star تستمر هذه العملية حتى تتم زيارة جميع الوجهات المطلوبة. ثم يتم اختبار فعالية المسار الناتج مقابل المسار الذي توفره خرائط .Google من خلال ١٠ تجارب للطرق السياحية، أنتجت خوارزمية A-Star مساراً أقصر بنسبة ٣٢,١٪ في المتوسط. أظهرت الاختبارات أيضاً أن خوارزمية A-Star تفوقت على طريقتَي Greedy و Dijkstra في إيجاد أقصر طريق. من المتوقع أن تساعد هذه الخوارزمية المسافرين على تصميم رحلات أكثر كفاءة، مما يوفر الوقت والطاقة.