11 dez 2023
14:00 Defesa de Doutorado Sala 53 do IC2
Tema
Algoritmos exatos e heurísticos para problemas de roteamento por cobertura
Aluno
Lucas Porto Maziero
Orientador / Docente
Fábio Luiz Usberti - Coorientador: Celso Cavellucci
Breve resumo
Os problemas de roteamento possuem diversas aplicações no mundo real, cada uma com restrições particulares como janelas de tempo, logística verde, disponibilidade de recursos e acessibilidade aos clientes. Quando se trata de disponibilidade de recursos e acessibilidade aos clientes, problemas de roteamento por cobertura são propostos para lidar com cenários reais em que regiões de difícil acesso possuem clientes que precisam ser atendidos, mas não podem ser visitados in loco. Os problemas de roteamento por cobertura visam encontrar rotas de custo mínimo cujas demandas dos clientes são atendidas servindo-os localmente ou remotamente com um veículo. Nesta tese, são propostas metodologias computacionais para dois problemas de roteamento por cobertura: Covering Salesman Problem (CSP) e Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP). Além disso, dois novos problemas de roteamento por cobertura são introduzidos: Capacitated Covering Salesman Problem (CCSP) e Electric Capacitated Covering Tour Problem (ECCTP).
O CSP é uma generalização do Problema do Caixeiro Viajante em que o objetivo é encontrar um ciclo de custo mínimo tal que todos os vértices sejam visitados ou cobertos pelo ciclo. Nesta tese, desigualdades válidas da literatura são transportadas para o CSP. Além disso, é proposto um novo conjunto de desigualdades válidas que se utilizam de aspectos únicos do problema. O primeiro branch-and-cut framework, com rotinas exatas e heurísticas para separar as desigualdades válidas, é proposto para resolver o CSP. Experimentos computacionais realizados em um benchmark de instâncias mostram que o ramework proposto foi capaz de superar metodologias do estado-da-arte da literatura, além de obter soluções ótimas para diversas instâncias anteriormente não resolvidas.
O CCSP é introduzido nesta tese com a intenção de abordar restrições de cobertura em problemas de roteamento de veículos capacitados. O objetivo do CCSP é atender os clientes usando uma frota de veículos, minimizando a distância percorrida pelos veículos. Os veículos podem atender os clientes localmente ou remotamente. Metodologias computacionais baseadas em programação linear inteira (PLI) e na metaheurística Biased Random-Key Genetic Algorithm (BRKGA) são propostas para resolver o CCSP. Além disso, uma formulação de PLI oriunda do CCSP é estendida para resolver o MDCTVRP. Os resultados dos experimentos computacionais mostram que a nova formulação para o MDCTVRP superou a melhor abordagem exata existente até então. Especificamente, soluções ótimas foram obtidas para vários instâncias
anteriormente não resolvidas.
No intuito de abordar um cenário real envolvendo logística verde, o ECCTP é introduzido nesta tese. O ECCTP é uma nova variante do problema de roteamento de veículos onde as demandas dos clientes podem
ser atendidas por veículos elétricos com autonomia limitada e os veículos elétricos podem recarregar em postos de recargas alternativos. Os veículos podem atender os clientes localmente ou remotamente. Uma formulação de PLI mista e uma metaheurística (BRKGA) são propostas para resolver o ECCTP. Com um benchmark de instâncias adaptadas da literatura, foram realizados experimentos computacionais com o objetivo de avaliar a eficácia da formulação e da metaheurística.
Banca examinadora
Titulares:
| Fábio Luiz Usberti | IC/UNICAMP |
| Pedro Belin Castellucci | UFSC |
| Pedro Henrique Del Bianco Hokama | IMC/UNIFEI |
| Washington Alves de Oliveira | FCA/UNICAMP |
| Kelly Cristina Poldi | IMECC/UNICAMP |
Suplentes:
| Guilherme Pimentel Telles | IC/UNICAMP |
| Pedro Augusto Munari Junior | CCET/UFSCar |
| Franklina Maria Bragion de Toledo | ICMC/USP |