| dc.description.abstract | The capacitated vehicle routing problem (CVRP) is one of the most challenging problems in the optimization of distribution which is used to design least cost delivery routes for a fleet of vehicles from depot to service a set of customers subject to a set of constraints. To overcome the limitation and minimize the total length traveled by vehicles, this research presents a novel two-phase heuristic approach: cluster first, routing later to solve the CVRP. In phase 1, an improved density-based clustering problem (DBSCAN) is introduced to decrease the problem’s size into groups of which total demand does not exceed the capacity of the vehicle and identify “closely spaced” clusters. A modified knapsack 0/1 problem is also applied to distribute noise nodes into other clusters still having total capacity less than maximum capacity. Then, in phase 2, we assign clusters to vehicles. In each of these clusters, we used a well-known traveling salesman problem (TSP) which is modified insert nearest neighbor algorithm. We evaluated the performance of three initial points selecting method based on – Geometrical Order, Close to Depot and Far from Depot. Additionally, this paper will conduct a comparison between our improved density-based clustering algorithm and best-known or optimum results. From many test cases, we have observed that Far from Depot outperformed other methods, while Close to Depot performs the worst; and Geometrical Order performs somewhat in between the other two methods. For the future research, we plan to apply DBSCAN to solve TSP problems.
Keywords: Capacitated Vehicle Routing Problem, Optimization, DBSCAN, Heuristic, Logistic Management | en_US |
