An Enhanced Genetic Algorithm with Problem-Aware Crossover and Local Search Mutation for the Capacitated Vehicle Routing Problem
محورهای موضوعی : Computer EngineeringMohammad Jamshidi 1 , Mehdi Alirezanejad 2 , Homayun Motameni 3 , Rasul Enayatifar 4
1 - Department of Computer Engineering, Sar.C., Islamic Azad University, Sari, Iran
2 - Department of Computer Engineering, Fi.C, Islamic Azad University, Firouzkouh, Iran
3 - Department of Computer Engineering, Sar.C., Islamic Azad University, Sari, Iran
4 - Department of Computer Engineering, Fi.C, Islamic Azad University, Firouzkouh, Iran
کلید واژه: Capacitated Vehicle Routing Problem (CVRP), Genetic Algorithm, Metaheuristics, Crossover Operator.,
چکیده مقاله :
The Capacitated Vehicle Routing Problem (CVRP) is a well-known, complex challenge in logistics and supply chain management. Genetic Algorithms (GAs) are often used to solve the CVRP, but their success depends on how their genetic operators are designed. Standard crossover and mutation can sometimes break apart good solutions. In this paper, we introduce an Improved Genetic Algorithm (IGA) that uses problem-specific genetic operators to improve both search efficiency and solution quality. Our main contribution is a two-part method: Route-Based Merge Crossover (RBMX) and a Two-Stage Local Search Mutation. RBMX keeps entire feasible routes from parent solutions, which helps maintain sub-tour structure, and uses a cheapest-insertion heuristic to add the remaining customers. The mutation operator works as a local search tool, sometimes applying intra-route (2-opt) and inter-route (string exchange) changes to improve solutions. Tests on standard benchmark problems show that our IGA performs much better than a standard GA with traditional operators like Order Crossover and Swap Mutation. These results show that using problem-specific genetic operators helps the algorithm find better solutions more quickly by making better use of the CVRP solution space.
The Capacitated Vehicle Routing Problem (CVRP) is a well-known, complex challenge in logistics and supply chain management. Genetic Algorithms (GAs) are often used to solve the CVRP, but their success depends on how their genetic operators are designed. Standard crossover and mutation can sometimes break apart good solutions. In this paper, we introduce an Improved Genetic Algorithm (IGA) that uses problem-specific genetic operators to improve both search efficiency and solution quality. Our main contribution is a two-part method: Route-Based Merge Crossover (RBMX) and a Two-Stage Local Search Mutation. RBMX keeps entire feasible routes from parent solutions, which helps maintain sub-tour structure, and uses a cheapest-insertion heuristic to add the remaining customers. The mutation operator works as a local search tool, sometimes applying intra-route (2-opt) and inter-route (string exchange) changes to improve solutions. Tests on standard benchmark problems show that our IGA performs much better than a standard GA with traditional operators like Order Crossover and Swap Mutation. These results show that using problem-specific genetic operators helps the algorithm find better solutions more quickly by making better use of the CVRP solution space.
1] Landete, M., et al., The Capacitated Vehicle Routing Problem with Planned Downtime. Computational Optimization and Applications, 2025. 92(2): p. 655-681.
[2] Rezaei, B., et al., Exploring dynamic population Island genetic algorithm for solving the capacitated vehicle routing problem. Memetic Computing, 2024. 16(2): p. 179-202.
[3] Jamshidi, M., et al., A Parallel Hybrid Genetic Search for Solving the Capacitated Vehicle Routing Problem. International Journal of Computational Intelligence Systems, 2025. 18(1): p. 306.
[4] Gu, W., et al., Vehicle routing problems with multiple commodities: A survey. European Journal of Operational Research, 2024. 317(1): p. 1-15.
[5] Slowik, A. and H. Kwasnicka, Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications, 2020. 32(16): p. 12363-12379.
[6] Dasgupta, D. and Z. Michalewicz, Evolutionary Algorithms in Engineering Applications. 2014: Springer Publishing Company, Incorporated.
[7] Rezaei, B., et al., Combining genetic local search into a multi-population Imperialist Competitive Algorithm for the Capacitated Vehicle Routing Problem. Applied Soft Computing, 2023. 142: p. 110309.
[8] Kumari, M., et al., Utilizing a hybrid metaheuristic algorithm to solve capacitated vehicle routing problem. Results in Control and Optimization, 2023. 13: p. 100292.
[9] Katoch, S., S.S. Chauhan, and V. Kumar, A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 2021. 80(5): p. 8091-8126.
[10] Muriyatmoko, D., A. Djunaidy, and A. Muklason, Heuristics and Metaheuristics for Solving Capacitated Vehicle Routing Problem: An Algorithm Comparison. Procedia Computer Science, 2024. 234: p. 494-501.
[11] Ojeda Rios, B.H., et al., Recent dynamic vehicle routing problems: A survey. Computers & Industrial Engineering, 2021. 160: p. 107604.
[12] Kuptametee, C., Z.-H. Michalopoulou, and N. Aunsri, A review of efficient applications of genetic algorithms to improve particle filtering optimization problems. Measurement, 2024. 224: p. 113952.
[13] Srinivas, M. and L.M. Patnaik, Genetic algorithms: A Survey. Computer, 1994. 27(6): p. 17–26.
[14] Fitzpatrick, J., D. Ajwani, and P. Carroll, A scalable learning approach for the capacitated vehicle routing problem. Computers & Operations Research, 2024. 171: p. 106787.[
[15] Bernardino, R. and A. Paias, The family capacitated vehicle routing problem. European Journal of Operational Research, 2024. 314(3): p. 836-853.
[16] Sajid, M., et al. A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities. Symmetry, 2021. 13, DOI: 10.3390/sym13101923.
