KOMBINASI ANT COLONY OPTIMIZATION DENGAN LOCAL TRIANGULAR KERNEL CLUSTERING UNTUK PERMASALAHAN VEHICLE ROUTING DENGAN TIME WINDOWS; COMBINATION OF ANT COLONY OPTIMIZATION WITH LOCAL TRIANGULAR KERNEL CLUSTERING FOR VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

Kesuma, Rahman Indra, Reza M.I. Pulungan

2015 | Disertasi | FMIPA

Routing is a common problem that can be found in the transportation management fields (Vehicle Routing Problem), including determination a route of products or packages from source to the desired destination. Vehicle Routing Problem with Time Windows (VRPTW) is one of the VRP variation that use routing concepts in the serving process at the 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 concentration of the solution. Local Triangular Kernel Clustering (LTKC) creates the groups based on the population density without using the class number as a parameter. Combination of LTKC-ACO was developed to improve the solutions that is obtained by using ACO, that applies LTKC at the beginning to obtain a number of classes that are considered as the candidate list in ACO at the next process. Local Search Heuristics is also used in LTKC-ACO to avoid the ACO getting stuck in the local optimum and to improve the solutions. In this study, 2 types of LTKC-ACO are developed, i.e. using time windows parameter in clustering (Type 1) and without time windows parameter in clustering (Type 2). 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 solution of LTKC-ACO 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 (the others was in around and under the ACO solution) and can out performed then the other methods, especially on the datasets that have longer scheduling of service time.

Kata Kunci : Routing; Vehicle Routing Problem with Time Windows; Ant Colony Optimization; Local Triangular Kernel Clustering