Show simple item record

dc.contributor.advisorSilva, Arinei Carlos Lindbeck da, 1960-pt_BR
dc.contributor.authorSchmidt, Carise Elisane, 1982-pt_BR
dc.contributor.otherUniversidade Federal do Paraná. Setor de Tecnologia. Programa de Pós-Graduação em Métodos Numéricos em Engenhariapt_BR
dc.date.accessioned2020-03-30T14:56:47Z
dc.date.available2020-03-30T14:56:47Z
dc.date.issued2019pt_BR
dc.identifier.urihttps://hdl.handle.net/1884/66355
dc.descriptionOrientador: Prof. Dr. Arinei Carlos Lindbeck da Silvapt_BR
dc.descriptionTese (doutorado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa : Curitiba, 17/12/2019pt_BR
dc.descriptionInclui referências: p. 93-98pt_BR
dc.descriptionÁrea de concentração: Programação matemáticapt_BR
dc.description.abstractResumo: O problema de localização e roteamento é amplamente estudado na literatura. Sua popularidade se deve, principalmente, à importância da logística integrada e aos crescentes esforços para fornecer soluções eficientes para sua resolução. Ao integrar decisões de localização de instalações e roteamento de veículos, o problema visa minimizar o custo total a elas associado. Contudo, ao considerar o custo de roteirização apenas a partir da distância, assume-se uma simplificação que não traduz apropriadamente a realidade. Isso porque há mudanças no tráfego que alteram sensivelmente o tempo de viagem, fazendo com que o percurso mais curto nem sempre seja o mais rápido. Essa alegação deu origem ao problema de roteamento de veículos dependente do tempo e, apesar do interesse crescente por essa variante, a questão ainda apresenta lacunas na área de logística integrada. Diante disso, propõe-se integrar dois tópicos populares da pesquisa: o problema de roteamento de veículos dependente do tempo e o problema de localização e roteamento. O objetivo é definir, modelar e resolver problemas para os quais a velocidade não é considerada constante. O trabalho apresenta a primeira formulação matemática para o problema de localização e roteamento dependente do tempo, fortalecida por um conjunto de desigualdades válidas. Assume-se frota homogênea e limitada, e horário fixo de saída dos veículos para atendimento aos clientes. Busca-se definir o depósito com a melhor localização e as rotas que devem ser executadas para minimizar o tempo total de viagem. Propõe-se ainda um algoritmo mateurístico, que combina heurísticas construtivas com um modelo de particionamento de conjuntos. Extensivos testes computacionais foram conduzidos para comparar as abordagens propostas, em um conjunto de instâncias gerado com base em dados reais de tráfego. Usando um solver comercial, o modelo foi capaz de fornecer soluções para instâncias com até 100 clientes e 15 intervalos de tempo, enquanto as desigualdades válidas melhoraram os limites inferiores. Os resultados evidenciam a importância da integração entre métodos heurísticos e exatos. Além disso, este trabalho contempla ainda uma extensão do problema, com dimensionamento de frota heterogênea. Nela, consideram-se depósitos capacitados, custos fixos de utilização de depósitos e veículos, frota heterogênea e não limitada, e flexibilidade no momento de saída dos veículos nos depósitos. Novamente, duas abordagens de resolução são propostas: uma formulação matemática com um conjunto de desigualdades válidas, e um algoritmo meta-heurístico de três fases baseado em busca evolucionária. Experimentos computacionais foram conduzidos para comparar essas abordagens. Os resultados reforçam a importância das desigualdades válidas na melhoria dos limites inferiores. Eles também mostram que a abordagem meta-heurística é capaz de reduzir consideravelmente o tempo de processamento e elevar a quabdade média das soluções. Palavras-chave: Logística integrada. Roteamento de veículos dependente do tempo. Localização de instalações. Dimensionamento de frota heterogênea.pt_BR
dc.description.abstractAbstract: Location-routing problem is a widely studied problem in the literature. Its popularity is m ainly due to the importance of the integrated logistics and the increasing efforts to provide efficient solutions to these problems. It integrates facihty location and vehicle routing decisions and as such, it minimizes the facility as well as the routing costs. However, assuming that the routing cost only depends on the distance traveled is an oversimplification which is inconsistent with the reality. In fact, changes in the traffic pattern significantly influence the travel time. Therefore, the shortest route is not always the fastest one. This argument has given rise to the emergence of the time-dependent vehicle routing problem. Despite the recent growing interest for this variant, there is a gap in the integrated logistics and models with this regard. To fulfill this lack of the literature, this thesis proposes to integrate two popular research areas: the time-dependent vehicle routing and the location-routing problems. The purpose of this thesis is to define, model, and solve integrated routing problems in which the speed is not considered constant over time. It presents the first mathematical formulation for the time-dependent location-routing problem, which is strengthened by a set of valid inequalities. A homogeneous and limited fleet is considered while the departure time from the depot to serve the customers is fixed. The objective is to minimize the total travel time while identifying the best location for a single depot and the routes that must be taken to serve customers. Moreover, a matheuristic algorithm Is proposed, which combines constructive heuristics with a set partitioning model. Using a set of instances generated based on real traffic data, extensive computational experiments were conducted to assess the performance of proposed methods. With a commercial solver, the mathematical model was able to provide solutions for instances with up to 100 customers and 15 time intervals, obtaining improved lower bounds using valid inequalities. The results show the benefits of combining heuristic and exact methods. Furthermore, this research extends the problem to the case with heterogeneous fleet sizing. In this problem setting, capacitated depots, fixed costs of depots and vehicles, heterogeneous and non-limited fleet, and flexibility for the vehicle departure time from depots are considered. Once more, two different approaches to solve the problem are proposed: a mathematical formulation, with a set of valid inequalities, and a three-phase evolutionary search-based metaheuristic algorithm. Computational experiments were conducted on a set of instances to compare the performance of the developed methods. The results highlight the importance of valid inequalities to improve the lower bounds. They further indicate how the proposed metaheuristic considerably reduces the execution time and improves the quality of the obtained solutions. Keywords: Integrated logistics. Time-dependent vehicle routing. Facility location. Fleet size and mix.pt_BR
dc.format.extent100 p. : il.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.subjectCadeia de logística integradapt_BR
dc.subjectLogísticapt_BR
dc.subjectProgramação heuristicapt_BR
dc.subjectOtimização combinatoriapt_BR
dc.subjectAnálise Numéricapt_BR
dc.titleProblemas de localização e roteamento dependentes do tempopt_BR
dc.typeTese Digitalpt_BR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record