Nesta dissertação, aborda-se o Problema de Roteamento de Veículos com Coletas e Entregas Simultâneas (VRPSPD, do inglês Vehicle Routing Problem with Simultaneous Pickup and Delivery), considerando frotas homogêneas e heterogêneas, através de um algoritmo de Busca em Vizinhança de Profundidade Variável. O VRPSPD é um problema desafiador de otimização da classe NP-Difícil e que tem aplicação em áreas de forte impacto econômico, social e ambiental, tais como logística reversa, reciclagem e gestão de resíduos. Neste contexto, as operações de distribuição e de recolhimento precisam ser consideradas em conjunto para minimizar os esforços logísticos. Uma formulação em Programação Linear Inteira (PLI) é proposta para a versão do problema com frota heterogênea. Além disso, propõe-se um método híbrido com uma estrutura de vizinhança de profundidade variável explorada por meio da resolução de um modelo em PLI, de maneira similar a outras hibridizações baseadas em redução da instância do problema, como a abordagem Generate & Solve e Construct, Merge, Solve & Adapt. Faz-se uso de instâncias da literatura para testar as potencialidades do algoritmo proposto. Os resultados dos experimentos computacionais são bastante expressivos, particularmente para instâncias com frota heterogênea, para as quais novos limites superiores (soluções viáveis) e limites inferiores foram encontrados, respectivamente, por meio da aplicação do algoritmo de Busca em Vizinhança de Profundidade Variável (VDNS, do inglês Variable Depth Neighborhood Search) e da resolução da nova formulação em PLI.

Palavras-chaves: Roteamento de Veículos. Busca por Vizinhança. Programação Linear Inteira Ver menos

In this dissertation, the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is addressed, considering homogeneous and heterogeneous fleets through a Variable Depth Neighborhood Search algorithm. VRPSPD is a challenging NP Hard opti#mization problem with applications in areas of intense economic, social, and environmental impact, such as reverse logistics, recycling and waste management. In this context, distri#bution, and collection operations must be considered together to minimize logistics efforts. An Integer Linear Programming (ILP) formulation is proposed for the heterogeneous fleet version of the problem. Furthermore, a hybrid method is proposed with a neighborhood structure of variable depth explored through the esolution of a model to be explored by means of the resolution of an ILP model, similar to other hybridizations based on problem instance reduction, such as the Generate & Solve and Construct, Merge, Solve & Adapt approaches. Instances from the literature are used to test the potential of the proposed algorithm. The results of the computational experiments are quite expressive, particularly for instances with a heterogeneous fleet, for which new upper bounds (feasible solutions) and lower bounds were found, respectively, through the application of the Variable Depth Neighborhood Search (VDNS) algorithm and the resolution of the new ILP formulation.

Key-words: Vehicle Routing. Neighborhood Search. Integer Linear Programming. Ver menos