Improving the Nearest Neighbor Algorithm by Genetic Algorithm for the Capacitated Vehicle Routing Problem
Keywords:
the Nearest Neighbor, Genetic Algorithm, the Capacitated Vehicle Routing ProblemAbstract
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.
References
Akbar, M. D., & Aurachmana, R. (2020). Hybrid genetic–tabu search algorithm to optimize the route for capacitated vehicle routing problem with time window. International Journal of Industrial Optimization, 1(1), 15-28. doi:10.12928/ijio.v1i1.1421
Bang-Jensen, J., Gutin, G., & Yeo, A. (2004). When the greedy algorithm fails. Discrete Optimization, 1(2), 121-127. doi:10.1016/j.disopt.2004.03.007
Bendall, G., & Margot, F. (2006). Greedy-type resistance of combinatorial problems. Discrete Optimization, 3(4), 288-298. doi:10.1016/j.disopt.2006.03.001
Gutin, G., Yeo, A., & Zverovich, A. (2002). Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics, 117(1-3), 81-86. doi:10.1016/s0166-218x(01)00195-0
Gutin, G., Yeo, A., & Zverovitch, A. (2007). Exponential neighborhoods and domination analysis for the TSP. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 223-256). doi:10.1007/0-306-48213-4_6
Ibrahim, M. F., Nurhakiki, F. R., Utama, D. M., & Rizaki, A. A. (2021). Optimised genetic algorithm crossover and mutation stage for vehicle routing problem pick-up and delivery with time windows. IOP Conference Series: Materials Science and Engineering, 1071(2021),. doi:10.1088/1757-899x/1071/1/012025
Ibrahim, M. F., Putri, M. M., Farista, D., & Utama, D. M. (2021). An improved genetic algorithm for vehicle routing problem pick-up and delivery with time windows. Jurnal Teknik Industri, 22(1), 1-17. doi:10.22219/jtiumm.vol22.no1.1-17
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (Eds.). (1985). The traveling salesman problem: A guided tour of combinatorial optimization. Chichester [West Sussex], England: John Wiley & Sons.
Masum, A. K. M., Shahjalal, M., Faruque, F., & Sarker, I. H. (2011). Solving the vehicle routing problem using genetic algorithm. International Journal of Advanced Computer Science and Applications, 2(7), 126-131. doi:10.14569/ijacsa.2011.020719
Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming, 94(2-3), 343–359. doi:10.1007/s10107-002-0323-0
Sadok, A. (2020). A genetic local search algorithm for the capacitated vehicle routing problem. International Journal of Advanced Computer Research, 10(48), 105-115. doi:10.19101/ijacr.2020.1048021
Theodoridis, S., & Koutroumbas, K. (2003). Pattern recognition (2nd ed.). Amsterdam: Academic Press.
