Formulations and a heuristic approach for logistics problems with d-relaxed priority rule
Carregando...
Arquivos
Data
2024-03-06
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Resumo
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.
This thesis considers extensions of two classical operations research problems in the logistics field where priority rules are embedded to the classical versions, defining the Clustered Traveling Salesman Problem with d-Relaxed Priority Rule (CTSP-d) and the Clustered Vehicle Routing Problem with d-Relaxed Priority Rule (CluVRP-d), that corresponds to a particular case of the Vehicle Routing Problem with Relaxed Priority Rules (VRP-RPR). In both problems, the order in which the vertices are visited is relevant because it is necessary to consider, in addition to the distance traveled, some kind of visiting priorities among the vertices, based on different real situations. In this study, formulations for the CTSP-d are improved using valid inequalities as well as new formulations based on precedence variables are proposed. Another contribution of this thesis is to extend the literature on VRP-RPR by proposing the CluVRP-d, a version of the problem where all vertices must be visited exactly once and the vehicles have capacity limitations. Two new mathematical formulations are proposed considering local and global timing cases, and a heuristic approach is presented to tackle bigger instances for the local timing case. Finally, computational results, based on data from the literature, are presented to demonstrate the competitiveness of the proposed formulations running the models on an optimization package and, in the CluVRP-d case, we compare the Local Timing case formulation to the results obtained by the heuristic approach.
This thesis considers extensions of two classical operations research problems in the logistics field where priority rules are embedded to the classical versions, defining the Clustered Traveling Salesman Problem with d-Relaxed Priority Rule (CTSP-d) and the Clustered Vehicle Routing Problem with d-Relaxed Priority Rule (CluVRP-d), that corresponds to a particular case of the Vehicle Routing Problem with Relaxed Priority Rules (VRP-RPR). In both problems, the order in which the vertices are visited is relevant because it is necessary to consider, in addition to the distance traveled, some kind of visiting priorities among the vertices, based on different real situations. In this study, formulations for the CTSP-d are improved using valid inequalities as well as new formulations based on precedence variables are proposed. Another contribution of this thesis is to extend the literature on VRP-RPR by proposing the CluVRP-d, a version of the problem where all vertices must be visited exactly once and the vehicles have capacity limitations. Two new mathematical formulations are proposed considering local and global timing cases, and a heuristic approach is presented to tackle bigger instances for the local timing case. Finally, computational results, based on data from the literature, are presented to demonstrate the competitiveness of the proposed formulations running the models on an optimization package and, in the CluVRP-d case, we compare the Local Timing case formulation to the results obtained by the heuristic approach.
Descrição
Palavras-chave
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
Como citar
TEIXEIRA, Eduardo dos Santos. Formulations and a heuristic approach for logistics problems with d-relaxed priority rule. (Doutorado em Matemática ). 2024. 115 f. - Universidade Estadual Paulista (Unesp), Instituto de Biociências Letras e Ciências Exatas (Ibilce), São José do Rio Preto, 2024.