Optimasi algoritma cheapest insertion heuristic dengan algoritma tabu search dalam pencarian rute terpendek

INDONESIA

Masalah pencarian rute terpendek merupakan salah satu topik penting dalam teori graf dan optimasi kombinatorial, dengan aplikasi luas di bidang logistik, transportasi, dan penjadwalan. Penelitian ini bertujuan untuk meningkatkan kualitas solusi dan efisiensi waktu dalam penyelesaian masalah Traveling Salesman Problem (TSP) melalui optimasi algoritma Cheapest Insertion Heuristic (CIH) menggunakan algoritma Tabu Search. Algoritma CIH digunakan untuk membentuk solusi awal dengan menyisipkan titik berdasarkan bobot minimum, sedangkan Tabu Search diimplementasikan untuk mengoptimalkan solusi dengan menghindari jebakan pada solusi lokal melalui mekanisme daftar tabu. Data penelitian berupa jarak antar titik lokasi pengambilan retribusi parkir oleh Dinas Perhubungan Kota Malang di Kecamatan Sukun, yang diperoleh dari Google Maps. Evaluasi kinerja algoritma dilakukan dengan membandingkan total jarak tempuh sebelum dan sesudah optimasi, serta dianalisis secara statistik menggunakan uji Wilcoxon signed-rank test karena data tidak berdistribusi normal. Hasil penelitian menunjukkan bahwa optimasi algoritma CIH menggunakan algoritma Tabu Search secara signifikan menghasilkan rute dengan jarak tempuh lebih pendek dibandingkan penggunaan algoritma CIH secara tunggal. Temuan ini membuktikan bahwa optimasi algoritma CIH menggunakan algoritma Tabu Search mampu meningkatkan efektivitas dalam pencarian solusi rute terpendek.

ENGLISH:

The shortest route finding problem is a significant topic in graph theory and combinatorial optimization, with wide applications in logistics, transportation, and scheduling. This research aims to improve the quality of the solution and time efficiency in solving the Traveling Salesman Problem (TSP) by optimizing the Cheapest Insertion Heuristic (CIH) algorithm using the application of the Tabu Search algorithm. The CIH algorithm constructs an initial solution by inserting points based on minimum weight. At the same time, the Tabu Search algorithm is applied to enhance the solution by avoiding local optima using a tabu list mechanism. The research data, consisting of the distances between parking retribution collection points by the Malang City Transportation Agency in Sukun Sub-district, were obtained from Google Maps. The algorithm performance evaluation is done by comparing the total mileage before and after optimization, and statistically analyzed using the Wilcoxon signed-rank test because the data does not follow a normal distribution. The results showed that optimizing the CIH algorithm using the Tabu Search algorithm significantly resulted in routes with shorter travel distances than using the CIH algorithm alone. This finding proves that optimizing the CIH algorithm with Tabu Search increases the effectiveness of finding the shortest route.

ARABIC:

تعد مشكلة العثور على أقصر طريق من إحدي الموضوعات المهمة في نظرية الرسم البياني والتحسين التوافقي، مع تطبيقات واسعة في الخدمات اللوجستية والنقل والجدولة. هدف هذا البحث إلى تحسين جودة الحل وكفاءة الوقت في
Traveling Salesman Problem (TSP) من خلال تحسين خوارزمية Cheapest Insertion Heuristic (CIH) باستخدام الخوارزمية Tabu Search. تم استخدام خوارزمية CIH لتكوين حل الاولي عن طريق إدخال النقاط بناءً على الحد الأدنى للوزن، بينما يتم تنفيذ Tabu Search لتحسين الحل عن طريق تجنب الوقوع في فخ الحلول المحلية من خلال آلية tabu list. بيانات البحث هي في شكل المسافة بين نقاط تجميع جزاءات مواقف السيارات من قبل وكالة النقل في مدينة مالانج في منطقة سوكون الفرعية، والتي تم الحصول عليها من Google Maps. تم تقييم أداء الخوارزمية من خلال مقارنة إجمالي المسافة المقطوعة قبل التحسين وبعده، ويتم تحليلها إحصائيًا باستخدام اختبار
Wilcoxon signed-rank test لأن البيانات ليست موزعة بشكل طبيعي. أظهرت النتائج أن تحسين خوارزميةCIH باستخدام خوارزمية Tabu Search أدى إلى مسار أقصر مسافة مقطوعة بشكل ملحوظ من استخدام خوارزميةCIH وحدها. وثتت هذه النتيجة أن تحسين خوارزمية CIH باستخدام الخوارزمية Tabu Search يمكن أن يزيد فقاليتها في إيجاد أقصر حل للمسار.