Kombinasi Ant Colony Optimization dengan Local Triangular Kernel Clustering untuk Permasalahan Vehicle Routing dengan Time Windows

Routing merupakan permasalahan yang dapat ditemukan dalam bidang pengelolaan transportasi (Vehicle Routing Problem), yang didalamnya terdapat penentuan rute perjalanan suatu barang atau paket dari tempat asal ke suatu tujuan. Vehicle Routing Problem with Time Windows (VRPTW) merupakan varian dari VRP yang menggunakan konsep routing dalam proses pelayanan pada interval waktu tertentu. Saat ini, telah banyak metode yang digunakan untuk menyelesaikan permasalahan optimasi tersebut, salah satunya Ant Colony Optimization (ACO). Metode yang menerapkan konsep populasi pada perilaku sosial koloni semut tersebut, memiliki permasalahan pada kompleksitas yang rumit serta penentuan waktu yang dibutuhkan untuk pemusatan solusi. Local Triangular Kernel Clustering (LTKC) melakukan pengelompokan berdasarkan kepadatan populasi tanpa menggunakan jumlah kelas sebagai parameter. Kombinasi LTKC-ACO dikembangkan untuk meningkatkan solusi dari ACO, dengan menerapkan LTKC di awal proses untuk memperoleh sejumlah kelas yang selanjutnya digunakan sebagai candidate list pada ACO. Local Search Heuristics juga digunakan untuk mencegah ACO terjebak pada lokal optimum serta meningkatkan solusi. Pada penelitian ini dikembangkan 2 tipe LTKC-ACO yaitu yang menggunakan parameter time windows dalam pengelompokan (Tipe 1) dan yang tidak menggunakannya (Tipe 2). Hasil pengujian LTKC-ACO (Tipe 1 dan 2) terhadap 56 data uji diamati berdasarkan jarak tempuh rute, jumlah kendaraan, waktu eksekusi, dan standar deviasi. Selanjutnya solusi dari LTKC-ACO dibandingkan dengan ACO dan beberapa metode dari penelitian sebelumnya. Diperoleh hasil bahwa LTKC-ACO (khususnya Tipe 2) dapat meningkatkan solusi ACO pada 73,21 % dari data uji dan menghasilkan solusi yang lebih baik dari 2 hingga 3 metode lainnya, terutama pada data uji yang memiliki karakteristik waktu pelayanan yang renggang. Routing is a problem that can be found in the transportation management fields (Vehicle Routing Problem), including determination a route of products from source to destination. Vehicle Routing Problem with Time Windows (VRPTW) is the VRP variation that use routing concepts in the serving process at certain time interval. Recently, many methods are used to solve these optimization problems, for example Ant Colony Optimization (ACO). ACO, the algorithm based on the population of ant colonies social behavior, faced the problem on hard complexity and difficulties on determination of time required for the solution concentration. Local Triangular Kernel Clustering (LTKC) creates groups based on the population density without using the class number as a parameter. Combination of LTKC-ACO was developed to improve the ACO solutions, that applies LTKC to obtain a number of classes that are considered as candidate list in ACO. Local Search Heuristics is also used to avoid ACO getting stuck in the local optimum and improve solutions. In this study, 2 types of LTKC-ACO are developed that's related to time windows parameter usage in clustering. The experimental result of LTKC-ACO (Type 1 and 2) to 56 datasets are observed by traveled distance, number of vehicles, execution time, and standard deviation. Furthermore, the LTKC-ACO solutions are compared to ACO and some methods from previous study. The results showed that LTKC-ACO (especially Type 2) can improve the ACO solution on 73,21% of datasets and can out performed then the other methods, especially on the datasets that have longer service time.