Heterogeneous Vehicle Routing Problem with Multiple Trips

O aumento constante da quantidade de bens consumidos e os altos custos das operações de transporte fazem com que as decisões relacionadas à logística sejam cada dia mais relevantes. Nesse contexto, o Problema de Roteamento de Veículos (PRV) tem ganhado atenção especial. A fim de resolver o problema, busca-se determinar as melhores rotas a serem realizadas por uma frota de veículos de forma que todos os clientes sejam atendidos. Os problemas de roteamento que ocorrem na prática frequentemente têm características particulares. Neste trabalho, vamos abordar uma variante do PRV denominada problema de roteamento de veículos com frota heterogênea e múltiplas viagens, na qual consideramos diferentes tipos de veículos e a possibilidade de realizarem mais de uma única viagem. Inicialmente, um modelo matemático adaptado da literatura foi desenvolvido para o problema, e seus primeiros testes computacionais indicam que apenas instâncias de pequeno porte podem ser resolvidas em tempo computacional razoável, utilizando diretamente softwares comerciais de otimização. Em seguida, apresentamos um método heurístico para a solução do problema. O algoritmo possui três etapas principais: obtenção de uma solução inicial (heurística construtiva), busca por mínimos locais (ILS), e melhoria (modelo de cobertura). Na sequência, é abordado um segundo objetivo que busca minimizar o tempo da maior rota. Finalizamos a dissertação com a apresentação de uma abordagem biobjetivo para o problema, resolvida por meio de três técnicas: ponderação na função objetivo, método e-restrito e Pareto-ILS. Com isso temos como objetivo propor abordagens mono e bi objetivo para a resolução do problema.The constant increase in the consumption of goods and the high costs of transport operations make decisions related to logistics increasingly more relevant. In this context, the Vehicle Routing Problem (VRP) has been in focus. In order to solve this problem, we aim to set the best routes for a fleet of vehicles to ensure that all clients will be served. The routing problems often have particular characteristics. In this work, we will address a variant of the PRV called the vehicle routing problem with heterogeneous fleet and multiple trips, in which we consider different types of vehicles and the possibility of making more than a single trip. Initially, a mathematical model, adapted from the literature, was developed. The first computational tests showed that only small instances can be solved in reasonable computational time, using commercial optimization software. Then, we present a heuristic method for the solution of the problem. The algorithm has three main steps: obtaining an initial solution (constructive heuristic), searching for local minimums (ILS), and improving the solution (coverage model). In sequence, a second objective that seeks to minimize the time of the longest route is approached. We conclude the dissertation with the presentation of a biobjective approach to the problem, which is solved using three techniques: weighting the objective function, epsilon -restricted method and Pareto-ILS. With that we aim to propose mono and bi objective approaches to solve the problem