Vehicle routing problem with service windows, heterogeneous fleet and split deliveries

Este trabalho apresenta uma solução para o problema de roteirização de veículos com janelas de atendimento, frota de veículos heterogêneas e entregas fracionadas. A construção de rotas baseia-se na heurística de economia utilizando inserção sequencial, inspirado em algoritmos clássicos, como o desenvolvido por Clarke e Wright em 1964. O diferencial do trabalho aborda quatro pontos, número finito de veículos com capacidades de transporte distintos, estratégia de primeiro ponto da rota, avaliação de benchmarks padrões e resultado visual para as rotas elaboradas. A implementação elaborada, apresenta uma solução parcial de um sistema de roteirização de veículos para as extensões em análise, sem levar em conta as restrições de negócio das empresas e o percurso geoespacial da roteirização. Procura-se demonstrar a eficiência da metodologia e algoritmos empregados em relação a ocupação média do veículo, distância total percorrida e a demanda total de cada grupo de teste. A heurística de economia empregada faz uso de quatro algoritmos, Economia Combinada (EC), Oportunidade Otimista de Economia (OOE), Oportunidade Real de Economia (ORE) e Oportunidade Real de Economia com parâmetro modelador de rota (OREl ). Como resultado, seis grupos de testes foram preparados para os algoritmos desenvolvidos. Utilizando os critérios de eficiência para as rotas construídas, cada um desses testes apresenta o desempenho do melhor algoritmo em conjunto com sua solução gráfica baseada no antes e depois das rotas e uma discussão sobre os valores obtidos.This work presents a solution for the vehicle routing problem for time windows with multiple vehicle types and split deliveries. The construction of routes is based on savings heuristics using the insertion sequence, which is inspired on classical algorithms, such as developed by Clarke and Wright in 1964. The novelty of this work addresses four aspects, finite number of vehicles with multiple size capacities, strategy of the first point of the route, the rating of standard benchmarks and visual results for the solved routes. The software developed has implemented a partial solution to the vehicle routing problems and its extensions, without taking into account the constraints of corporate business and geospatial path information. Sought to demonstrate the efficiency of employed techniques with the average occupancy relative to the vehicle, the total distance traveled and the total demand of each tested group. The heuristics employed makes use of four algorithms, Combined Savings (CS), Optimistic Opportunity Savings (OOS), Realistic Opportunity Savings (ROS) and Realistic Opportunity Savings with a route shape parameter (ROSl ). As a result, six test groups were prepared for the algorithms developed. Using efficiency criteria for built up routes, each of this tests shows the best performance of the chosen algorithm together with its graphical results based on pre and post scenarios and a discussion of the obtained values