An ILS algorithm with RVND for the green vehicle routing problems with time-varying speeds

  • Darci José Mendes Júnior UFJF
  • Luciana Brugiolo Gonçalves UFJF
  • Stênio Sã R. F. Soares UFJF


The environmental impacts of human action have led several countries to create stricter laws and tax breaks to reduce this damage. Thereby, the Green Logistic has been increasingly sought to meet the requirements and needs for a more sustainable development. This work presents an ILS (Iterated Local Search) algorithm combined with RVND (Random Variable Neighborhood Search) and compare it with a GRASP (Greed Randomized Search Procedure) algorithm where each one has two variations: minimize distance and minimize emission. The results show the effectiveness of the ILS approach and heuristics that minimize the total distance covered do not present themselves as good solutions in terms of sustainability.


Cordeau (2013). Capacitated vrp with time windows instances , Acessado em: 30 de Março 2017.

Department for Environment, Food and Rural Affairs (2010). Guide lines to Defra/DECC’s green house gas conversion factors for company reporting. Acessado em: 28 de Outrubro 2014.

Lin, C., Choy, K., Ho, G., Chung, S., and Lam, H. (2014). Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications, pages 1118–1138.

Lourenço, H. R., Martin, O. C., and Stützle, T. (2010). Handbook of Metaheuristics, chapter Iterated Local Search: Framework and Applications. Springer New York, Editors: M. Gendreau and J.Y. Potvin.

McKinnon, A., Cullinane, S., Browne, M., and Whiteing, A. (2010). Green Logistics: Improving the environmental sustainability of logistics. Kogan Page Limited.

Mendes Júnior, D. J. (2017). Metaheurística aplicada ao problema de roteamento verde de veículos com velocidades variáveis no tempo. Trabalho de Conclusão de Curso, Ciência da Computação, Universidade Federal de Juiz de Fora.

Molina, J. C., Eguia, I., Racero, J., and Guerrero, F. (2014). Multi-objective vehicle routing problem with cost and emission functions. Procedia - Social and Behavioral Sciences, pages 254–263.

P. G. Boulter, T. J. B. and McCrae, I. S. (2009). Emissions factors 2009: Report 3 - exhaust emission factors for road vehicles in the united kingdom. Acessado em: 30 de Março 2017.

Picelli, V. C. and Georges, M. R. R. (2011). Cadeia de suprimentos reversa e logística verde: Teoria e prática. In Anais do XVI Encontro de Iniciação Científica da PUCCampinas e I Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação da PUC-Campinas.

Qian, J. and Eglese, R. (2016). Fuel emissions optimization in vehicle routing problems with time-varying speeds. European Journal of Operational Research, pages 840–848.

Rao, S., Pachauri, S., Dentener, F., Kinney, P., Klimont, Z., Riahi, K., and Schoepp, W. (2013). Better air for better health: Forging synergies in policies for energy access, climate change and air pollution. Elsevier Ltd, pages 1122–1130.

Sbihi, A. and Eglese, R. W. (2010). Combinatorial optimization and green logistics. In AAnnals of Operations Research, pages 159–1175, Spring.

Talbi, E.-G. (2009). Metaheuristics: from design to implmentation. JohnWiley and Sons, Inc.

Xiao, Y. and Konak, A. (2015). A simulating annealing algorithm to solve the green vehicle routing and scheduling problem with hierarchical objectives and weighted tardiness. Applied Soft Computing, pages 372–388.

Xiao, Y. and Konak, A. (2016). The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transportation Research Part, pages 146–166.

MENDES JÚNIOR, Darci José; GONÇALVES, Luciana Brugiolo; SOARES, Stênio Sã R. F.. An ILS algorithm with RVND for the green vehicle routing problems with time-varying speeds. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 15. , 2018, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . p. 608-619. ISSN 2763-9061. DOI: