Optimasi Rute Pengiriman Barang dengan Metode DBSCAN dan Clarke-Wright Saving Heuristic

Abstract

Setelah pandemik Covid-19 berakhir, kecenderungan berbelanja daring meningkat pada masyarakat Indonesia. Tingginya biaya distribusi, yaitu sekitar 10-20% dari total biaya suatu produk membuat biaya yang dibebankan kepada konsumen meningkat. Salah satu upaya menarik pelanggan dengan mengurangi beban biaya yang ditanggung konsumen dapat dilakukan dengan optimasi rute distribusi. Dalam penelitian ini dilakukan optimasi rute untuk meminimalkan jarak total distribusi berkendala kapasitas dengan metode Density-Based Spatial Clustering of Applications with Noise (DBSCAN) dalam pengelompokkan data, dan Clarke Wright Saving Heuristic dalam penentuan rute. Selain itu, dilakukan juga perutean dengan pendekatan eksak yaitu Interrupted Mixed-Integer Linear Programming (MILP) yang dihitung dengan bantuan solver Gurobi di Python 3. Hasil memperlihatkan bahwa walaupun metode pendekatan eksak menghasilkan solusi yang lebih optimum, proses perhitungannya memerlukan waktu yang sangat lama, sehingga metode DBSCAN dan Clarke-Wright Saving Heuristic menawarkan solusi yang lebih cepat dan cukup mendekati optimum.

After the Covid-19 pandemic ended, the tendency to shop online increased among Indonesians. High distribution costs, which are approximately 10-20% of the total cost of a product, increase the costs charged to consumers. One effort to attract customers by reducing the cost burden borne by them can be accomplished by optimizing the distribution routes. In this research, route optimization was carried out to minimize the total distribution distance under capacity constraints using the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) method in grouping data and the Clarke-Wright Saving Heuristic method for determining routes. Routing was also carried out using an exact approach, namely Interrupted Mixed-Integer Linear Programming (MILP), which was calculated using the Gurobi solver in Python 3. The results show that although the exact approach method produces a more optimal solution, the calculation process takes a very long time. Therefore, the DBSCAN and Clarke-Wright Saving Heuristic methods offer solutions that are faster and quite close to the optimum.