Penerapan Algoritma Bellman-Ford pada rute terpendek distribusi air mineral santri di Pasuruan

ABSTRAK:

Algoritma Bellman-Ford yang dikenal mampu menangani graf berbobot negatif, terutama pada kondisi distribusi yang kompleks. Distribusi Air Minum Dalam Kemasan (AMDK) Santri di wilayah Pasuruan menghadapi tantangan dalam penjadwalan rute yang belum optimal, sehingga dapat menyebabkan ketidakefisienan dalam pengiriman. Penelitian ini dilakukan untuk mengembangkan modifikasi Algoritma Bellman-Ford agar dapat menemukan rute optimal dengan sifat Hamiltonian Cycle serta mengimplementasikan Algoritma Bellman-Ford ke dalam model jaringan distribusi. Penelitian ini menerapkan Penelitian dilakukan menggunakan metode studi literatur serta studi lapangan melalui pemetaan rute dengan Google Maps. Hasil penelitian menunjukkan bahwa total jarak rute terpendek dengan siklus Hamiltonian Cycle adalah 97,48 km, sedangkan rute terpendek tanpa siklus Hamiltonian Cycle adalah titik A, v_12, v_13,〖 v〗_10,〖 v〗_17 sejauh 3,49 km (pulang-pergi). Kesimpulan dari penelitian ini menunjukkan bahwa penerapan Algoritma Bellman-Ford dengan siklus Hamiltonian memberikan hasil yang lebih optimal untuk kebutuhan distribusi menyeluruh dibandingkan hanya mencari rute tercepat antara dua titik. Apabila hanya menggunakan Algoritma Bellman-Ford tanpa modifikasi, maka beberapa titik distribusi tidak dapat dijangkau. Penelitian selanjutnya disarankan untuk membandingkan algoritma ini dengan pendekatan lain seperti A^* atau Floyd-Warshall guna mengevaluasi efisiensi dan keakuratannya secara lebih mendalam.

ABSTRACT:

The Bellman-Ford algorithm is known for its ability to handle graphs with negative weights, particularly in complex distribution conditions. The distribution of Santri Bottled Drinking Water in the Pasuruan region faces challenges due to suboptimal route scheduling, which can lead to inefficiencies in delivery. This research was conducted to develop a modification of the Bellman-Ford Algorithm in order to find the optimal route with the properties of a Hamiltonian Cycle and to implement the Bellman-Ford Algorithm into a distribution network model. This study was conducted using literature review and field study methods through route mapping with Google Maps. The results show that the total shortest route distance using the Hamiltonian Cycle is 97,48 km, while the shortest route without the Hamiltonian Cycle is between point A, v_12,v_13,v_10,v_(17 )with a round-trip distance of 3,49 km. The conclusion of this study indicates that applying the Bellman-Ford Algorithm with the Hamiltonian Cycle yields more optimal results for comprehensive distribution needs compared to simply finding the fastest route between two points. If the unmodified Bellman-Ford Algorithm is used, several distribution points cannot be reached.

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

تُعرف خوارزمية بيلمان-فورد بقدرتها على معالجة الرسوم البيانية ذات الأوزان السالبة، وخاصة في ظروف التوزيع المعقدة. يواجه توزيع مياه الشرب المعبأة (AMDK) سانتري في منطقة باسورووان تحديات تتعلق بجدولة المسارات التي لم تُحسّن بالشكل الأمثل، مما قد يؤدي إلى عدم الكفاءة في عمليات التوصيل. أُجري هذا البحث لتطوير تعديل على خوارزمية بيلمان-فورد بهدف إيجاد المسار الأمثل الذي يتميز بخاصية الدورة الهاميلتونية، وكذلك لتطبيق خوارزمية بيلمان-فورد في نموذج شبكة التوزيع. تم إجراء هذا البحث باستخدام منهجية الدراسة الأدبية بالإضافة إلى الدراسة الميدانية من خلال رسم خرائط المسارات باستخدام خرائط جوجل. أظهرت نتائج البحث أن المسافة الإجمالية لأقصر مسار باستخدام دورة هاميلتوني تبلغ ٩٧٫٤٨كيلومتر، في حين أن أقصر مسار بدون دورة هاميلتوني هو بين النقطة A و v_12 و〖 v〗_17 〖و v〗_10 〖 و v〗_13 يبلغ ٣٫٤٩ كيلومتر ذهابًا وإيابًا. وتشير نتائج هذا البحث إلى أن تطبيق خوارزمية بيلمان-فورد مع دورة هاميلتوني يوفر نتائج أكثر كفاءة لاحتياجات التوزيع الشاملة مقارنةً بمجرد البحث عن أسرع طريق بين نقطتين فقط. وإذا تم استخدام خوارزمية بيلمان-فورد دون تعديل، فلن يكون بالإمكان الوصول إلى بعض نقاط التوزيع. ويوصى في الأبحاث القادمة بمقارنة هذه الخوارزمية مع مناهج أخرى مثل خوارزمية A* أو فلويد-وورشال لتقييم الكفاءة والدقة بشكل أعمق.