Orientador: Luis Augusto Angelotti Meira

Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia

Resumo: A otimização do Problema de Roteamento de Veículos é vital para logística de diversas indústrias e serviços. Nesse estudo otimizamos o PostVRP, uma variante multiobjetivo baseada em um caso real de entregas de correspondências por carteiros a pé, que tem como funções objetivo minimizar o...

Resumo: A otimização do Problema de Roteamento de Veículos é vital para logística de diversas indústrias e serviços. Nesse estudo otimizamos o PostVRP, uma variante multiobjetivo baseada em um caso real de entregas de correspondências por carteiros a pé, que tem como funções objetivo minimizar o comprimento médio das rotas, o número de veículos utilizados e a variabilidade do comprimento das rotas. O problema foi resolvido de duas maneiras, com o método Cluster First Route Second (CFRS) e com o método Route First Cluster Second (RFCS), ambos usando o algoritmo GRASP com busca local 2-opt para resolução do subproblema TSP. Desenvolvemos um algoritmo para agrupar entregas em instâncias com mais de 1000 entregas, visando diminuir o custo computacional dos experimentos. Em seguida, implementamos o método CFRS, utilizando uma variação do método k-medoids com um solver de Programação Linear Inteira para particionar as entregas em clusters. Após a resolução de um TSP para cada grupo, implementamos um algoritmo iterativo para reduzir a variabilidade dos comprimentos das rotas. Para o RFCS, empregamos um fator de estreitamento para a jornada máxima de trabalho, a fim de obter soluções para diversos números de veículos. Encontramos diversas soluções em relação às três funções objetivo testadas, gerando fronteiras de soluções não-dominadas. Em todas as instâncias, quanto menor o número de veículos, maior o comprimento médio das rotas. Ambos os métodos resolveram o PostVRP em instâncias de até 10.000 pontos de entrega. O RFCS foi superior em relação a variabilidade dos comprimentos das rotas, e o CFRS foi superior em relação ao comprimento médio das rotas

Abstract: The optimization of the Vehicle Routing Problem is critical for logistics in several industries and services. In this study, we will optimize PostVRP, a multi-objective variant based in a realistic case of mail delivery by postmen on foot. The objective functions of this variant are to...

Abstract: The optimization of the Vehicle Routing Problem is critical for logistics in several industries and services. In this study, we will optimize PostVRP, a multi-objective variant based in a realistic case of mail delivery by postmen on foot. The objective functions of this variant are to minimize the average route length, minimize the number of postmen and minimize the routes length variance. The problem was solved in two different ways, with the Cluster First Route Second (CFRS) method and the Route First Cluster Second (RFCS) method, both using the GRASP algorithm with 2-opt local search for solving the TSP subproblem. We developed an algorithm to group deliveries in instances containing over 1000 deliveries, with the intent of reducing the computational costs in the experiments. Afterwards, we implemented the CFRS method using a variation of the k-medoids method to partition the deliveries in clusters, using an Integer Linear Programming solver. After solving a TSP for each group, we implemented an iterative algorithm to reduce the routes length variance. For the RFCS method, we created a narrowing factor for the maximum work hours, in order to obtain different solutions for each number of vehicles. We found various solutions to the problem regarding the three tested objective functions, generating frontiers of nondominated solutions. For every instance we found that the lower the number of vehicles, the higher the average route length. Both methods solved PostVRP in instances of up to 10,000 deliveries. The RFCS method was better regarding the routes length variance while the CFRS method was better regarding the average route lengths

Requisitos do sistema: Software para leitura de arquivo em PDF