Electric Vehicle Routing as a Multi-Objective Evolutionary Problem
Resumo
A transição para frotas logísticas elétricas introduz complexos desafios operacionais devido à autonomia limitada dos veículos e necessidade de recargas. O Problema de Roteamento de Veículos Elétricos com Janelas de Tempo (EVRPTW) reflete essa realidade, exigindo o balanceamento de múltiplos critérios conflitantes: tamanho da frota, distância e atrasos. Este artigo contribui com uma comparação sistemática e estatisticamente rigorosa de três paradigmas de Algoritmos Evolutivos Multiobjetivo, NSGA-II, SMS-EMOA e MOEA/D, aplicados ao EVRPTW. Experimentos conduzidos em 50 instâncias comprovam que o SMS-EMOA produz frentes de Pareto de qualidade global superior. Adicionalmente, os resultados demonstram que o NSGA-II é o mais eficaz em atrasos extremos, enquanto o MOEA/D apresenta inadequação estrutural severa devido à natureza discreta e estratificada do problema.
Referências
Azadi, A. H. S., Khalilzadeh, M., Antucheviciene, J., Heidari, A., and Soon, A. (2024). A sustainable multi-objective model for capacitated-electric-vehicle-routing-problem considering hard and soft time windows as well as partial recharging. Biomimetics, 9(4):242.
Bergstra, J. and Bengio, Y. (2012). Random search for hyper-parameter optimization. J. Mach. Learn. Res., 13(10):281–305.
Beume, N., Naujoks, B., and Emmerich, M. (2007). Sms-emoa: Multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res.
Castro-Gutierrez, J., Landa-Silva, D., and Moreno Pérez, J. (2011). Nature of real-world multi-objective vehicle routing with evolutionary algorithms. In Proc. IEEE Int. Conf. Syst., Man, Cybern. (SMC), pages 257–264. IEEE.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Trans. Evol. Comput., 6(2):182–197.
Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res., 7:1–30.
Eiben, A. E. and Smith, J. E. (2015). Introduction to Evolutionary Computing. Springer, 2 edition.
Erdelić, T. and Carić, T. (2022). Goods delivery with electric vehicles: Electric vehicle routing optimization with time windows and partial or full recharge. Energies, 15(1):285.
García, S. and Herrera, F. (2008). An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. J. Mach. Learn. Res., 9:2677–2694.
Haddad, A., Tlili, T., Dahmani, N., and Krichen, S. (2025). Integrating nsga-ii and q-learning for solving the multi-objective electric vehicle routing problem with battery swapping stations. Int. J. Intell. Transp. Syst. Res. Online first, DOI: 10.1007/s13177-025-00486-9.
Ishibuchi, H., Imada, R., Setoguchi, Y., and Nojima, Y. (2017). Reference point specification in hypervolume calculation for fair comparison and efficient search. In Proc. Genet. Evol. Comput. Conf. (GECCO), pages 585–592. ACM.
Ishibuchi, H., Masuda, H., Tanigaki, Y., and Nojima, Y. (2015). Modified distance calculation in generational distance and inverted generational distance. In Proc. Int. Conf. Evol. Multi-Criterion Optim. (EMO). Springer.
Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2):221–227.
Mao, H., Shi, J., Zhou, Y., and Zhang, G. (2020). The electric vehicle routing problem with time windows and multiple recharging options. IEEE Access, 8:114864–114875.
Oliver, I. M., Smith, D. J., and Holland, J. R. C. (1987). A study of permutation crossover operators on the travelling salesman problem. In Proc. 2nd Int. Conf. Genet. Algorithms, pages 224–230. Lawrence Erlbaum.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res., 31(12):1985–2002.
Qi, Y., Hou, Z., Li, H., Huang, J., and Li, X. (2015). A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows. Comput. Oper. Res., 62:61–77.
Qin, H., Su, X., Ren, T., and Luo, Z. (2021). A review on the electric vehicle routing problems: Variants and algorithms. Front. Eng. Manag., 8(3):370–389.
Schneider, M., Stenger, A., and Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transp. Sci., 48(4):500–520.
Vieira, D. A. G., Adriano, R., de Vasconcelos, J. A., and Krähenbühl, L. (2004). Treating constraints as objectives in multiobjective optimization problems using niched pareto genetic algorithm. IEEE Trans. Magn., 40(2):1188–1191.
Ye, C., He, W., and Chen, H. (2022). Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review. Environ. Sci. Pollut. Res., 29:57067–57090.
Zhang, Q. and Li, H. (2007). Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput., 11(6):712–731.
Zheng, Z., Liu, S., and Ong, Y.-S. (2025). Hybrid memetic search for electric vehicle routing with time windows, simultaneous pickup-delivery, and partial recharges. arXiv preprint.
Zhou, Y., Lei, Q., Li, L., and Wu, Z. (2025). An overview of energy replenishment strategies for the electric vehicle routing problem: Models and solution algorithms. Energies, 18(23):6196.
Zitzler, E. and Thiele, L. (1998). Multiobjective optimization using evolutionary algorithms: A comparative case study. In Proc. Int. Conf. Parallel Probl. Solving from Nat. (PPSN V), volume 1498, pages 292–301. Springer.
Bergstra, J. and Bengio, Y. (2012). Random search for hyper-parameter optimization. J. Mach. Learn. Res., 13(10):281–305.
Beume, N., Naujoks, B., and Emmerich, M. (2007). Sms-emoa: Multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res.
Castro-Gutierrez, J., Landa-Silva, D., and Moreno Pérez, J. (2011). Nature of real-world multi-objective vehicle routing with evolutionary algorithms. In Proc. IEEE Int. Conf. Syst., Man, Cybern. (SMC), pages 257–264. IEEE.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Trans. Evol. Comput., 6(2):182–197.
Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res., 7:1–30.
Eiben, A. E. and Smith, J. E. (2015). Introduction to Evolutionary Computing. Springer, 2 edition.
Erdelić, T. and Carić, T. (2022). Goods delivery with electric vehicles: Electric vehicle routing optimization with time windows and partial or full recharge. Energies, 15(1):285.
García, S. and Herrera, F. (2008). An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. J. Mach. Learn. Res., 9:2677–2694.
Haddad, A., Tlili, T., Dahmani, N., and Krichen, S. (2025). Integrating nsga-ii and q-learning for solving the multi-objective electric vehicle routing problem with battery swapping stations. Int. J. Intell. Transp. Syst. Res. Online first, DOI: 10.1007/s13177-025-00486-9.
Ishibuchi, H., Imada, R., Setoguchi, Y., and Nojima, Y. (2017). Reference point specification in hypervolume calculation for fair comparison and efficient search. In Proc. Genet. Evol. Comput. Conf. (GECCO), pages 585–592. ACM.
Ishibuchi, H., Masuda, H., Tanigaki, Y., and Nojima, Y. (2015). Modified distance calculation in generational distance and inverted generational distance. In Proc. Int. Conf. Evol. Multi-Criterion Optim. (EMO). Springer.
Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2):221–227.
Mao, H., Shi, J., Zhou, Y., and Zhang, G. (2020). The electric vehicle routing problem with time windows and multiple recharging options. IEEE Access, 8:114864–114875.
Oliver, I. M., Smith, D. J., and Holland, J. R. C. (1987). A study of permutation crossover operators on the travelling salesman problem. In Proc. 2nd Int. Conf. Genet. Algorithms, pages 224–230. Lawrence Erlbaum.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res., 31(12):1985–2002.
Qi, Y., Hou, Z., Li, H., Huang, J., and Li, X. (2015). A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows. Comput. Oper. Res., 62:61–77.
Qin, H., Su, X., Ren, T., and Luo, Z. (2021). A review on the electric vehicle routing problems: Variants and algorithms. Front. Eng. Manag., 8(3):370–389.
Schneider, M., Stenger, A., and Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transp. Sci., 48(4):500–520.
Vieira, D. A. G., Adriano, R., de Vasconcelos, J. A., and Krähenbühl, L. (2004). Treating constraints as objectives in multiobjective optimization problems using niched pareto genetic algorithm. IEEE Trans. Magn., 40(2):1188–1191.
Ye, C., He, W., and Chen, H. (2022). Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review. Environ. Sci. Pollut. Res., 29:57067–57090.
Zhang, Q. and Li, H. (2007). Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput., 11(6):712–731.
Zheng, Z., Liu, S., and Ong, Y.-S. (2025). Hybrid memetic search for electric vehicle routing with time windows, simultaneous pickup-delivery, and partial recharges. arXiv preprint.
Zhou, Y., Lei, Q., Li, L., and Wu, Z. (2025). An overview of energy replenishment strategies for the electric vehicle routing problem: Models and solution algorithms. Energies, 18(23):6196.
Zitzler, E. and Thiele, L. (1998). Multiobjective optimization using evolutionary algorithms: A comparative case study. In Proc. Int. Conf. Parallel Probl. Solving from Nat. (PPSN V), volume 1498, pages 292–301. Springer.
Publicado
19/10/2026
Como Citar
MOURA, Rafael do Nascimento; SOARES, Rodrigo Gabriel Ferreira.
Electric Vehicle Routing as a Multi-Objective Evolutionary Problem. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 23. , 2026, Cuiabá/MT.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 2739-2750.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2026.30555.
