Hybrid Genetic Algorithm with Deep Q-Learning Mutation: for Enhanced Vehicle Routing Optimization
GA with DQN for CVRP
DOI:
https://doi.org/10.5269/bspm.82819Resumo
The Capacitated Vehicle Routing Problem (CVRP) is one of the most researched NP-hard
problems, dealing with minimizing total costs while respecting vehicle capacity constraints. Genetic Algorithms (GA) provide flexibility but rely on random mutations, which may slow convergence and produce suboptimal solutions. In this work, we propose a hybrid GA–DQN approach where a pre-trained Deep Q-Network (DQN) guides mutation decisions to improve solution quality. This hybridization provides a better balance between exploration and exploitation compared with a standard GA. Experimental results show that the proposed
method converges faster and achieves better solutions across several CVRP instances, demonstrating that reinforcement learning can effectively enhance evolutionary optimization methods.
Referências
1. Métadonnées additionnelles (Dublin Core)
Type : Original Article.
Format : latex/tex.
Identifiant : https://orcid.org/0009-0001-3965-0129.
Droits (Rights) : Copyright © 2026 BSPM.
Mots-clés (Keywords) : Vehicle Routing Problem, Genetic Algorithm, Deep Q-Learning, Hybrid Metaheuristics, Optimization
2. Références
1. S. Chen et al., Particle swarm optimization for the vehicle routing problem with time windows, Expert Systems with Applications 101 (2018), 190–202.
2. N. Christofides and S. Eilon, The vehicle routing problem, Naval Research Logistics Quarterly 26 (1979), 223–247.
3. J.-F. Cordeau and G. Laporte, A tabu search heuristic for the vehicle routing problem with time windows, Transportation Science 35 (2016), no. 2, 223–247.
4. G.B. Dantzig and J.H. Ramser, The truck dispatching problem, Management Science 6 (1959), no. 1, 80–91.
5. Kun Fu, Wei Qiu, and Qiang Zhang, Generalization in traveling salesman problem with deep learning, IEEE Transactions on Neural Networks and Learning Systems 33 (2021), no. 8, 3564–3578.
6. Keld Helsgaun, An extension of the lin-kernighan-helsgaun tsp solver for the cvrp, Technical Report, Roskilde University (2017).
7. Shauharda Khadka and Kagan Tumer, Evolutionary reinforcement learning, Proceedings of the AAAI Conference on Artificial Intelligence (2018).
8. Mustafa Küçük, Araç rotalama ve çok boyutlu yükleme problemlerine entegre bir yaklaşım, Ph.D. thesis, Dokuz Eylül Universitesi, Turkey, 2023.
9. Yeong-Dae Kwon, Joonho Choo, Beomjoon Kim, and Inkeun Yoon, Pomo: Policy optimization with multiple optima for reinforcement learning, Advances in Neural Information Processing Systems 33 (2020).
10. Gilbert Laporte, Metaheuristics for vehicle routing problems, Transportation Science 43 (2009), no. 4, 408–416.
11. S. L. Lee and H. Nazif, Optimised crossover genetic algorithm for capacitated vehicle routing problem, Applied Mathematical Modelling 36 (2012), no. 5, 2110–2117.
12. Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác, Reinforcement learning for solving the vehicle routing problem, Advances in Neural Information Processing Systems 31 (2018).
13. C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31 (2004), 1985–2002.
14. L. Reyes-Rubiano et al., Ant colony optimization for vehicle routing problems, Swarm and Evolutionary Computation 37 (2017), 1–13.
15. Paolo Toth and Daniele Vigo, Vehicle routing: Problems, methods, and applications, Society for Industrial and Applied Mathematics, 2014.
16. Thibaut Vidal et al., A hybrid genetic algorithm for the capacitated vehicle routing problem, Computers & Operations Research 115 (2020), 104857.
17. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks, Advances in Neural Information Processing Systems 28 (2015).
18. Lei Yang and Hao Chen, A hybrid deep reinforcement learning and large neighborhood search approach for cvrp, Computers & Operations Research 142 (2022), 105738.
19. B. Yu and Z. Yang, An improved simulated annealing algorithm for the capacitated vehicle routing problem, Applied Soft Computing 74 (2019), 1117–1130.
20. Jingwen Yu and Yutong Li, Attention-based deep reinforcement learning for vehicle routing problems, Expert Systems with Applications 168 (2021), 114289.
21. Wenqiang Zhang, Xiaomeng Wang, Yashuan Mu, Miaolei Deng, and Peng Li, Deep reinforcement learning with evolutionary algorithm-guided imitation for capacitated vehicle routing problems, Applied Soft Computing 184 (2025),113705.
Type : Original Article.
Format : latex/tex.
Identifiant : https://orcid.org/0009-0001-3965-0129.
Droits (Rights) : Copyright © 2026 BSPM.
Mots-clés (Keywords) : Vehicle Routing Problem, Genetic Algorithm, Deep Q-Learning, Hybrid Metaheuristics, Optimization
2. Références
1. S. Chen et al., Particle swarm optimization for the vehicle routing problem with time windows, Expert Systems with Applications 101 (2018), 190–202.
2. N. Christofides and S. Eilon, The vehicle routing problem, Naval Research Logistics Quarterly 26 (1979), 223–247.
3. J.-F. Cordeau and G. Laporte, A tabu search heuristic for the vehicle routing problem with time windows, Transportation Science 35 (2016), no. 2, 223–247.
4. G.B. Dantzig and J.H. Ramser, The truck dispatching problem, Management Science 6 (1959), no. 1, 80–91.
5. Kun Fu, Wei Qiu, and Qiang Zhang, Generalization in traveling salesman problem with deep learning, IEEE Transactions on Neural Networks and Learning Systems 33 (2021), no. 8, 3564–3578.
6. Keld Helsgaun, An extension of the lin-kernighan-helsgaun tsp solver for the cvrp, Technical Report, Roskilde University (2017).
7. Shauharda Khadka and Kagan Tumer, Evolutionary reinforcement learning, Proceedings of the AAAI Conference on Artificial Intelligence (2018).
8. Mustafa Küçük, Araç rotalama ve çok boyutlu yükleme problemlerine entegre bir yaklaşım, Ph.D. thesis, Dokuz Eylül Universitesi, Turkey, 2023.
9. Yeong-Dae Kwon, Joonho Choo, Beomjoon Kim, and Inkeun Yoon, Pomo: Policy optimization with multiple optima for reinforcement learning, Advances in Neural Information Processing Systems 33 (2020).
10. Gilbert Laporte, Metaheuristics for vehicle routing problems, Transportation Science 43 (2009), no. 4, 408–416.
11. S. L. Lee and H. Nazif, Optimised crossover genetic algorithm for capacitated vehicle routing problem, Applied Mathematical Modelling 36 (2012), no. 5, 2110–2117.
12. Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác, Reinforcement learning for solving the vehicle routing problem, Advances in Neural Information Processing Systems 31 (2018).
13. C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31 (2004), 1985–2002.
14. L. Reyes-Rubiano et al., Ant colony optimization for vehicle routing problems, Swarm and Evolutionary Computation 37 (2017), 1–13.
15. Paolo Toth and Daniele Vigo, Vehicle routing: Problems, methods, and applications, Society for Industrial and Applied Mathematics, 2014.
16. Thibaut Vidal et al., A hybrid genetic algorithm for the capacitated vehicle routing problem, Computers & Operations Research 115 (2020), 104857.
17. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks, Advances in Neural Information Processing Systems 28 (2015).
18. Lei Yang and Hao Chen, A hybrid deep reinforcement learning and large neighborhood search approach for cvrp, Computers & Operations Research 142 (2022), 105738.
19. B. Yu and Z. Yang, An improved simulated annealing algorithm for the capacitated vehicle routing problem, Applied Soft Computing 74 (2019), 1117–1130.
20. Jingwen Yu and Yutong Li, Attention-based deep reinforcement learning for vehicle routing problems, Expert Systems with Applications 168 (2021), 114289.
21. Wenqiang Zhang, Xiaomeng Wang, Yashuan Mu, Miaolei Deng, and Peng Li, Deep reinforcement learning with evolutionary algorithm-guided imitation for capacitated vehicle routing problems, Applied Soft Computing 184 (2025),113705.
Downloads
Publicado
2026-07-01
Edição
Seção
Conf. Issue: Recent Advances in Applied Mathematics, Modeling, and Engineering
Licença
Copyright (c) 2026 Boletim da Sociedade Paranaense de Matemática
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
When the manuscript is accepted for publication, the authors agree automatically to transfer the copyright to the (SPM).
The journal utilize the Creative Common Attribution (CC-BY 4.0).
Como Citar
Fahim, M. (2026). Hybrid Genetic Algorithm with Deep Q-Learning Mutation: for Enhanced Vehicle Routing Optimization: GA with DQN for CVRP . Boletim Da Sociedade Paranaense De Matemática, 44(18), 1-16. https://doi.org/10.5269/bspm.82819
