BEST PAPER AWARD

Os investigadores Telmo Pinto, Cláudio Alves e José Valério de Carvalho do Centro ALGORITMI da Universidade do Minho foram galardoados com o Prémio “Best Paper Award” pelo artigo “Variable Neighborhood Search for the Elementary Shortest Path Problem with Loading Constraints”.

Trabalho desenvolvido visa a optimização integrada de operações de transporte através de algoritmos eficientes. O artigo foi apresentado na “International Conference on Computational Science and Its Applications (ICCSA 2015)” que decorreu em Banff, Alberta, Canadá entre os dias 22 e 25 de junho. Nesta conferência, participaram representantes de diferentes países e foram apresentados mais de 220 trabalhos.

Telmo Pinto, aluno do Programa Doutoral em Engenharia Industrial e de Sistemas da Escola de Engenharia da Universidade do Minho, encontra-se em fase final do seu projeto de doutoramento com o tema "Models and advanced optimization algorithms for the integrated management of logistics operations", sob orientação do Professor Doutor Cláudio Alves e Professor Doutor José Valério de Carvalho, ambos docentes do Departamento de Produção e Sistemas da Escola de Engenharia da Universidade do Minho.


Variable Neighborhood Search for the Elementary Shortest Path Problem with Loading Constraints
Telmo Pinto, Cláudio Alves, J.M. Valério de Carvalho

Abstract
In this paper, we address the elementary shortest path problem with 2-dimensional loading constraints. The aim is to find the path with the smallest cost on a graph where the nodes represent clients whose items may have different heights and widths. Beyond its practical relevance, this problem appears as a subproblem in vehicle routing problems with loading constraints where feasible routes have to be generated dynamically. To the best of our knowledge, there are no results reported in the literature related to this problem. Here, we explore a variable neighborhood search approach for this problem. The method relies on constructive heuristics to generate feasible paths, while improved incumbents are sought in different neighborhoods of a given solution through a variable neighborhood search procedure. The resulting variants of the algorithm were tested extensively on benchmark instances from the literature. The results are reported and discussed at the end of the paper.

Keywords
Shortest path problem, Loading constraints, Variable neighborhood search, Computational study.

Referência
Telmo Pinto, Cláudio Alves, and José Valério de Carvalho. "Variable Neighborhood Search for the Elementary Shortest Path Problem with Loading Constraints." Computational Science and Its Applications--ICCSA 2015. Springer International Publishing, 2015. 474-489.

Contactos
Escola de Engenharia da Universidade do Minho
Departamento de Produção e Sistemas
Telmo Pinto (telmo@dps.uminho.pt)
Cláudio Alves (claudio@dps.uminho.pt)
José Valério de Carvalho (vc@dps.uminho.pt)