Implementasi algoritma uniform cost search (UCS) untuk menentukan rute terpendek

ABSTRAK:

Pada saat ini pencarian rute terpendek menjadi kunci utama bagi mobilitas efisien, terutama di tengah kepadatan populasi dan pertumbuhan perkotaan yang pesat. Kebutuhan mendesak untuk menemukan jalur tercepat tidak hanya sekadar pemilihan jalur terpendek, melainkan juga merupakan strategi untuk mengatasi kemacetan, mengoptimalkan waktu tempuh, dan meminimalisir dampak lingkungan. Pencarian rute terpendek melibatkan aspek-aspek terkait seperti menghindari kemacetan lalu lintas, mengatur pengiriman barang, dan memastikan aksesibilitas serta keamanan dalam situasi darurat. Meskipun demikian, kendala seperti ketidakakuratan data lokasi, ketidakpastian kondisi jalan, dinamika lalu lintas yang tidak dapat diprediksi, dan ketersediaan transportasi umum yang terbatas menjadi tantangan yang perlu diatasi. Solusi untuk mengatasi kendala tersebut melibatkan peningkatan akurasi data lokasi, informasi lalu lintas waktu nyata, dan pengembangan algoritma yang mempertimbangkan preferensi moda transportasi. Kerjasama antara penyedia transportasi umum dan platform pencarian rute terpendek juga diakui dapat meningkatkan informasi yang tersedia. Salah satu algoritma yang relevan dalam pencarian rute terpendek adalah Uniform Cost Search (UCS), yang bekerja dengan mempertimbangkan biaya setiap simpul dalam graf jaringan jalan atau peta. Validasi dari pengujian kedua menunjukkan bahwa hasil aplikasi dengan rute Kecamatan Rungkut  Kecamatan Sukolilo  Kecamatan Gubeng memiliki jarak 7.600 Meter, yang kurang lebih sama dengan hasil yang diberikan oleh Google Maps dengan rute serupa dan jarak 7.700 Meter. Implementasi algoritma UCS pada pencarian rute terpendek di kota tersebut sangat efektif dan dapat meminimalkan biaya operasional. Algoritma ini berhasil mengatasi permasalahan pada pencarian rute yang awalnya memakan waktu lama dan memiliki biaya operasional tinggi, menjadi lebih efisien dengan waktu yang lebih cepat dan biaya operasional yang rendah. Hasil dari pencarian rute terpendek ini membuktikan efisiensinya dalam mengurangi biaya operasional dan mencapai tujuan dengan lebih cepat. Validasi dari hasil aplikasi juga menunjukkan kesesuaian dengan rute yang diberikan oleh Google Maps, mengukuhkan kehandalan implementasi algoritma UCS dalam konteks pencarian rute terpendek di lingkungan perkotaan.
ABSTRACT:

At this time, the search for the shortest route is the main key to efficient mobility, especially in the midst of population density and rapid urban growth. The urgent need to find the fastest path is not just about choosing the shortest path, but also a strategy to overcome congestion, optimize travel time, and minimize environmental impact. The search for the shortest route involves related aspects such as avoiding traffic jams, organizing the delivery of goods, and ensuring accessibility and safety in emergency situations. However, obstacles such as inaccurate location data, uncertainty of road conditions, unpredictable traffic dynamics, and limited availability of public transportation are challenges that need to be overcome. Solutions to overcome such constraints involve improving the accuracy of location data, real-time traffic information, and developing algorithms that consider transportation mode preferences. Cooperation between public transport providers and shortest route finding platforms is also recognized to improve the information available. One of the relevant algorithms in shortest route search is Uniform Cost Search (UCS), which works by considering the cost of each node in a road network graph or map. Validation from the second test showed that the results of the application with the route of Rungkut DistrictSukolilo DistrictGubeng District has a distance of 7,600 meters, which is approximately the same as the results provided by Google Maps with a similar route and a distance of 7,700 meters. Based on the results of research on the implementation of the UCS algorithm for the shortest route search in the city of Surabaya, it can be concluded that the implementation of the UCS algorithm on the shortest route search in the city is very effective and can minimize operational costs. This algorithm successfully overcomes the problem of route search which initially takes a long time and has high operational costs, becomes more efficient with faster time and low operational costs. The results of this shortest route search prove its efficiency in reducing operational costs and reaching destinations faster. Validation of the application results also demonstrates conformity with the routes provided by Google Maps, confirming the reliability of the UCS algorithm implementation in the context of finding the shortest route in urban environments.

مستخلص البحث:

في هذا الوقت ، يعد البحث عن أقصر طريق هو المفتاح الرئيسي للتنقل الفعال ، خاصة في خضم الكثافة السكانية والنمو الحضري السريع. إن الحاجة الملحة للعثور على أسرع مسار لا تتعلق فقط باختيار أقصر مسار ، ولكن أيضا استراتيجية للتغلب على الازدحام ، وتحسين وقت السفر ، وتقليل التأثير البيئي. يتضمن البحث عن أقصر طريق جوانب ذات صلة مثل تجنب الاختناقات المرورية ، وتنظيم تسليم البضائع ، وضمان إمكانية الوصول والسلامة في حالات الطوارئ. ومع ذلك ، فإن العقبات مثل بيانات الموقع غير الدقيقة ، وعدم اليقين في ظروف الطرق ، وديناميكيات حركة المرور التي لا يمكن التنبؤ بها ، والتوافر المحدود لوسائل النقل العام هي تحديات يجب التغلب عليها. تتضمن الحلول للتغلب على هذه القيود تحسين دقة بيانات الموقع ومعلومات حركة المرور في الوقت الفعلي وتطوير خوارزميات تأخذ في الاعتبار تفضيلات وضع النقل. ومن المسلم به أيضا التعاون بين مقدمي خدمات النقل العام وأقصر منصات البحث عن الطرق لتحسين المعلومات المتاحة. واحدة من الخوارزميات ذات الصلة في أقصر بحث عن الطريق هي البحث عن التكلفة الموحدة (UCS) ، والتي تعمل من خلال النظر في تكلفة كل عقدة في الرسم البياني لشبكة الطرق أو الخريطة. أظهر التحقق من الاختبار الثاني أن نتائج التطبيق مع مسار منطقة Rungkut منطقة Sukolilo منطقة Gubeng لها مسافة سبعة آلاف وستة مائة متر ، وهي تقريبا نفس النتائج التي قدمتها خرائط جوجل مع مسار مماثل ومسافة سبعة آلاف وسبعة مائة متر. استنادا إلى نتائج البحث حول تنفيذ خوارزمية UCS لأقصر بحث عن طريق في مدينة سورابايا ، يمكن الاستنتاج أن تنفيذ خوارزمية UCS على أقصر بحث عن الطرق في المدينة فعال للغاية ويمكن أن يقلل من تكاليف التشغيل. تتغلب هذه الخوارزمية بنجاح على مشكلة البحث عن المسار التي تستغرق وقتا طويلا في البداية ولها تكاليف تشغيلية عالية ، وتصبح أكثر كفاءة مع وقت أسرع وتكاليف تشغيل منخفضة. تثبت نتائج هذا البحث عن أقصر الطرق كفاءته في تقليل التكاليف التشغيلية والوصول إلى الوجهات بشكل أسرع. يوضح التحقق من صحة نتائج التطبيق أيضا التوافق مع المسارات التي توفرها خرائط جوجل ، مما يؤكد موثوقية تنفيذ خوارزمية UCS في سياق العثور على أقصر طريق في البيئات الحضرية.