Solving the CVRP with Reduction to Knapsack Problem and Greedy Clustering Heuristic Method

The vehicle routing problem is one of the most well-known optimization problems, which aims to design an optimum set of routes with the lowest cost for servicing the customers in a way that is consistent with the existing constraints. The wide practical application and scope of this problem has attracted much attention from researchers. But in return, the severity of solving has created difficulties and increased the need for heuristic and meta-heuristic solutions. This research represents a greedy heuristic method based on first categorizing then routing methods, to solve the capacitated vehicle routing problem (CVRP) using the capabilities of problem reduction to the knapsack problem. The advantages of this method include the consideration of effective criteria such as distance between customers, distance between customers to depot and demand of points in decision making, decent speed and quality of solution and the ability to utilize the benefits of reduction. Standard samples from CVRPLIB were used to evaluate the results and comparing them.