19 dez 2022
15:00 Defesa de Doutorado Auditório do IC3
Tema
Abordagens para Problemas de Roteamento de Veículos com Considerações de Energia e Backhauls Seletivos
Aluno
Mauro Henrique Mulati
Orientador / Docente
Orientador: Flávio Keidi Miyazawa / Coorientador: Ricardo Fukasawa
Breve resumo
A ampla categoria de Problemas de Roteamento de Veículos (VRPs) originou-se do VRP Capacitado (CVRP) proposto no fim dos anos 1950, que consiste em encontrar a maneira mais econômica de servir um conjunto de clientes com uma frota de veículos de uma dada capacidade. Nesta tese, são abordados problemas de otimização combinatória em dois grupos de VRPs: um considerando consumo de energia e outro que considera backhauls. Além de sua relação com custos de transporte, o interesse no consumo de energia em roteamento de veículos está crescendo nas últimas décadas devido ao seu potencial de mitigar impactos ambientais. Enquanto custos no CVRP são mensurados em termos de distância, o VRP Cumulativo (CmVRP) é uma variante que objetiva minimizar uma medida simplificada de consumo de energia dependente de carga. Combinando os conceitos de duas formulações pré-existentes, este trabalho propõe uma nova formulação de programação linear inteira para o CmVRP, cuja relaxação de programação linear (LP) é mais forte que ambas as relaxações de LP das originais. Além disso, visando resolver a versão inteira do problema, é empregado um algoritmo branch-cut-and-price (BCP) baseado em uma formulação da literatura a fim de apresentar resultados em estado-da-arte para o CmVRP. Adicionalmente, um pequeno resultado de aproximação sobre o problema é apresentado. Também lidando com um outro aspecto do consumo de energia, este trabalho propõe variantes do CVRP e CmVRP que consideram limites de energia dependente de carga por veículo, o que pode restringir o alcance de cada veículo sem reabastecer ou recarregar energia. Para resolvê-los, este trabalho propõe formulações baseadas em partição de conjuntos que fazem uso de cargas discretizadas por arco e também apresenta abordagens BCP baseadas nestes modelos. No melhor do nosso conhecimento, esta é a primeira vez que um consumo de energia dependente de carga dos veículos é limitado por meio do subproblema de pricing. São mostrados vastos resultados computacionais comparando o CVRP, CmVRP, e suas variantes com energia limitada. Por fim, este trabalho aborda a variante do CVRP denominada VRP com Backhauls Seletivos, no qual, depois de visitar clientes, cada veículo pode visitar um único backhaul para coletar um valor de receita. Nesta abordagem, considera-se que as receitas são incertas. Para lidar com esta incerteza, um modelo de otimização robusta é elaborado e analisado para este problema. São resolvidos os modelos determinístico e robusto por um algoritmo branch-and-cut (BC) e são apresentados resultados computacionais comparando-os com uma abordagem heurística.
Banca examinadora
Titulares:
Flávio Keidi Miyazawa IC/UNICAMP
Kelly Cristina Poldi IMECC/UNICAMP
Eduardo Uchoa Barboza TEP/UFF
Rafael Martinelli Pinto DEI/PUC-Rio
Reinaldo Morabito Neto PET/UFSCar
Suplentes:
Mário César San Felice DC/UFSCar
Pedro Henrique Del Bianco Hokama IMC/UNIFEI
Pedro Augusto Munari Junior DEP/UFSCar