Penyelesaian Capacitated Vehicle Routing Problem with Time Windows menggunakan Sweep Algorithm Clustering dan Genetic Algorithm

Abstract

Permasalahan distribusi paket pada perusahaan ekspedisi umumnya terjadi karena keterlambatan pengiriman dan ketidakefesienan rute pengiriman. Penelitian ini bertujuan untuk menentukan rute distribusi yang optimal dengan meminimalkan total wktu tempuh kendaraan serta memenuhi kendala kapasitas dan time windows pelanggan. Dengan pendekatan dua tahap, yaitu clustering menggunakan Sweep Algorithm (SA) untuk mengelompokkan pelanggan berdasarkan kedekatan geografis, dan Genetic Algorithm (GA) untuk menentukan urutan kunjungan pelanggan dalam setiap cluster. Hasil penelitian menunjukkan bahwa SA dan GA mampu menghasilkan pembagian wilayah pelanggan yang terstruktur serta rute distribusi yang lebih efisien dari segi waktu tempuh. Selain itu, seluruh rute yang dihasilkan tetap memenuhi kendala kapasitas kendaraan dan time windows pelayanan. Implikasi dari penelitian ini menunjukkan bahwa kombinasi metode SA dan GA menjadi solusi efektif dalam mengoptimalkan sistem distribusi pada permasalahan Capacitated Vehicle Routing Problem with Time Windows.

The package distribution problem in courier companies is commonly associated with delivery delays and inefficient routing. This study aims to determine optimal distribution routes by minimizing the total transportation time while satisfying vehicle capacity constraints and customer time windows. A two-stage approach is employed, consisting of clustering using the Sweep Algorithm (SA) to group customers based on geographical proximity, and the Genetic Algorithm (GA) to determine the sequence of customer visits within each cluster. The results show that SA and GA are capable of generating well-structured customer groupings and more efficient distribution routes in terms of travel time. In addition, all generated routes satisfy vehicle capacity constraints and customer time window requirements. The findings indicate that the combination of SA and GA provides an effective solution for optimizing distribution systems in the Capacitated Vehicle Routing Problem with Time Windows.