Estudo das Propriedades Geométricas das Soluções do Problema de Roteirização de Veículos Usando Visão Computacional

Abstract

The Vehicles Routing Problem (VRP) is an NP-hard problem, and when the number of clients is very large, the task of finding the optimal solution is extremely complex. Several heuristic methods have been used to solve this problem, however, it is still necessary to find an effective way to evaluate the quality of solutions when there is no known optimal solution to the problem. This work presents a suggestion to analyze the quality of vehicle routes, based only on their geometric shapes analysis. The proposed descriptors aim to be invariants in relation to the amount of clients, vehicles and the size of the covered area. Applying the methodology proposed in this work it is possible to apply heuristic methods to obtain the route and, then, to evaluate the quality of solutions obtained. Despite being assessed problems with different configurations for the number of clients, vehicles, and service area, the results obtained with the experiments show that the proposal was useful to classify the routes on good or bad classes and obtained an accuracy rate of 99.87 %.