Desenvolvimento de uma abordagem híbrida entre as metaheurísticas GRASP e VNS para roteirização

Abstract

RESUMO: Quando necessitamos nos mover de um ponto inicial passando por vários outros objetivos unicamente até novamente retornarmos ao nosso local de partida, estamos diante de um obstáculo conhecido como o problema do caixeiro viajante, tema esse muito em voga hoje, relacionado a escolha da rota a ser efetuada por veículos nas entregas de mercadoria, tendo tal problemática definida como não polinomial, ou seja, de custosa resolução computacional. Entretanto, ainda há artifícios tecnológicos como metaheurísticas, que entregam uma solução viável dentro do escopo da necessidade, tendo em vista a fuga do mínimo local, que podem ser aprimoradas ainda com a hibridização de outras metaheurísticas, para que possa corroborar na obtenção do ótimo global. Dessa maneira, este trabalho busca aplicar tal medida no problema do caixeiro viajante para escolha de uma rota factível, a fim de realizar entregas por meio de veículos. Onde foi possível através dessa abordagem encontrar ótimos globais e rotas satisfatórias nas instâncias definidas, em um tempo de execução e custo do roteiro, na maioria das vezes menor que da literatura utilizada para comparação.

ABSTRACT: When we need to move from a starting point, passing through several other objectives uniquely until we return to our starting location, we are facing an obstacle known as the traveling salesman problem. This topic is very relevant today, particularly in relation to the route selection for vehicles delivering goods, with this problem being defined as non-polynomial, meaning it is computationally costly to solve. However, there are still technological tools such as metaheuristics, which provide a feasible solution within the scope of need, considering the escape from local minima. These can be further enhanced by the hybridization of other metaheuristics, to help achieve the global optimum. Thus, this work seeks to apply such measures to the traveling salesman problem for the selection of a feasible route, in order to make deliveries by vehicles. Through this approach, it was possible to find global optima and satisfactory routes in the defined instances, in an execution time and itinerary cost, most of the time less than that of the literature used for comparison.