Modelo matemático e algoritmo meta-heurístico para o problema de roteamento de veículos com frota heterogênea fixa e restrições de carregamento bidimensional

Abstract

Resumo: Os problemas integrados de roteamento e carregamento de veículos tratam simultaneamente de dois importantes problemas de otimização combinatória: o Problema de Roteamento de Veículos e o Problema do Bin Packing. Neste trabalho estudou-se o Problema de Roteamento de Veículos com Frota Heterogênea Fixa e Restrições de Carregamento Bidimensional (2L-HFFVRP - Two Dimensional Loading Heterogeneous Fixed Fleet Vehicle Routing Problem), cujo objetivo consiste em encontrar o conjunto de roteiros de mínimo custo a ser realizado por uma frota limitada de veículos de diferentes capacidades e custos, determinando ainda o arranjo geométrico da carga nos veículos, considerando os itens de demanda dos clientes e as superficies de carregamento dos veículos elementos retangulares. Além das restrições clássicas do problema de roteamento de veículos e das restrições geométricas do carregamento, considerou-se a restrição do carregamento sequencial, que garante que seja possível descarregar os itens de um cliente sem a necessidade de movimentação dos itens dos clientes que serão atendidos posteriormente no roteiro. Foi desenvolvida uma formulação matemática para o 2L-HFVRP, validada por experimentos computacionais que mostraram que a formulação proposta e capaz de representar matematicamente o problema, no entanto e possível obter soluções ótimas em tempo computacional aceitável apenas para problemas consideravelmente pequenos. Também foi proposto um algoritmo meta-heurístico baseado em Simulated Annealing e Busca Local para resolução do 2L-HFFVRP, que utiliza um conjunto de métodos heurísticos para determinar o carregamento dos veículos. O desempenho deste algoritmo foi testado sobre instancias geradas a partir das instancias da literatura, e observou-se que, embora as soluções obtidas não sejam ótimas, o algoritmo consegue encontrar boas soluções em um tempo computacional aceitável.

Abstract: Integrated vehicle routing and loading problems treat two important combinatorial optimization problems: the Vehicle Routing Problem and the Bin Packing Problem. In this work the Two-Dimensional Loading Heterogeneous Fixed Fleet Vehicle Routing Problem is studied. This problem aims at finding a set of routes of minimum cost to be performed by a limited fleet of vehicles of different capacities and costs, also determining the loading of items into vehicles, once customers demands bidimensional items. Besides the classical constraints of vehicle routing problem and geometric loading restrictions, the sequential loading constraint, that ensures that items of a customer should be unloaded without handling items of other customers, is also considered. A mathematical model for 2L-HFFVRP was developed, and validated by computational experiments, that show the proposed model can represent mathematically the problem, although it is possible to find optimal solutions in acceptable computational time just for small problems. A metaheuristic algorithm based on Simulated Annealing and local search is proposed for solving 2L-HFFVRP, and uses a pack of heuristics to generate vehicles loading. The performance of this algorithm was tested on instances generated from the instances of literature, and it was observed that although the solutions obtained are not optimal, the algorithm can find good solutions in an acceptable computational time.