Capacitated vehicle routing problem with simulated annealing algorithm with initial solution improved with fuzzy c-means algorithm

Abstract

In this study, a popular problem, the Vehicle Routing Problem, has been studied. Simulated annealing, a meta-heuristic method, was used to solve the problem. In general, the simulated annealing algorithm is an iterative process according to the variable temperature parameter, which mimics the annealing process of metals. The biggest problem with this method for our study is that it randomly generates the initial solution used to start the algorithm. For this reason, since the search space used to reach the optimum solution is large, the solution time (or number of iterations) will increase. With a better initial solution, it will take less time to reach the optimum solution. Since the optimum solution we want to reach is the minimum distance, the routes are clustered using fuzzy c mean to improve the initial solution. Due to fuzzy logic, the case that each data can be included in more than one cluster between 0-1 will approach the optimum solution since it will change the initial solution in each solution of the algorithm. By using the same data and the same parameters, the initial solution is improved with fuzzy c mean using a random initial solution, and the problem is solved with Simulated Annealing. Fuzzy c mean method reduced the initial search space by 57%. Therefore, Fuzzy c mean gave results closer to the optimum solution in the same solution time and the same iteration number.