Improving the Nearest Neighbor Algorithm by Genetic Algorithm for the Capacitated Vehicle Routing Problem

Abstract

The capacitated vehicle routing problem (CVRP) is the problem of transportation of goods from the depot to customers at each location by receiving the transportation service only one time per customer and there are different distances and shipping costs. The objective of this study is to minimize the cost of transportation and can deliver products to all customers. We usually apply the nearest neighbor algorithm (NN) to solve CVRP because the nearest neighbor algorithm is easy to implement and quick to execute. However, the response from the nearest neighbor algorithm is less efficient because it searches for the shortest path in the neighborhood without considering the sum of all travel distances. In order to improve the system, we propose to apply the genetic algorithm (GA) with the nearest neighbor algorithm. This proposed algorithm is called the improved nearest neighbor algorithm using a genetic algorithm for the capacitated vehicle routing problem or NNGA. The proposed algorithm was tested on five cases that we created from Google Maps. The results from the experiment showed that the distance of the proposed algorithm can be reduced by 6.66% compared to the distance of the nearest neighbor algorithm.