Formulations and a heuristic approach for logistics problems with d-relaxed priority rule

• Ano de defesa: 2024
• Autor(a) principal: Teixeira, Eduardo dos Santos
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Estadual Paulista (Unesp)
• Palavras-chave em Português: Programação inteira mista; Problema do caixeiro viajante; Problema de roteamento de veículos; Prioridades; Heurística; Mixed integer programming; Traveling salesman problem; Vehicle routing problem; Priorities; Heuristic
• Link de acesso: https://hdl.handle.net/11449/254860

Esta tese considera extensões de dois problemas clássicos de pesquisa operacional no campo da logística em que regras de prioridade são incorporadas às versões clássicas, dando origem ao Problema do Caixeiro Viajante Clusterizado com Regra de Prioridade d-Relaxada (CTSP-d) e ao Problema de Roteamento de Veículos Clusterizado com Regra de Prioridade d-Relaxada (CluVRP-d), que corresponde a um caso particular do Problema de Roteamento de Veículos com Regras de Prioridade Relaxadas (VRP-RPR). Em ambos os problemas, a ordem em que os vértices são visitados é relevante porque é necessário considerar, além da distância percorrida, algum tipo de prioridade de visita entre os vértices, com base em diferentes situações reais. Neste estudo, formulações propostas na literatura para o CTSP-d são melhoradas utilizando-se desigualdades válidas, bem como novas formulações baseadas em variáveis de precedência são propostas. Outra contribuição desta tese é expandir a literatura sobre o VRP-RPR propondo o CluVRP-d, uma versão do problema onde todos os vértices devem ser visitados exatamente uma vez e os veículos possuem limitações de capacidade. Duas novas formulações matemáticas são propostas para o problema, considerando os casos Local e Global Timing, e uma abordagem heurística é apresentada para tratar de instâncias maiores do caso Local Timing. Por fim, resultados computacionais, baseados em dados da literatura, são apresentados para demonstrar a competitividade das formulações propostas quando resolvidas por um pacote de otimização e, no caso do CluVRP-d, comparamos a formulação do caso Local Timing com os resultados obtidos através da abordagem heurística.