PPGCC - Mestrado (Dissertações)

URI permanente para esta coleçãohttp://www.hml.repositorio.ufop.br/handle/123456789/597

Navegar

Filtros

2020 - 20213

Configurações

Data inicial: 2020Assunto: search.filters.subject.Heurística

Resultados da Pesquisa

Agora exibindo 1 - 3 de 3
  • Nenhuma Miniatura Disponível
    Item
    Exact and heuristic approaches for traveling salesman problems with drones.
    (2021) Freitas, Júlia Cária de; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Souza, Marcone Jamilson Freitas; Subramanian, Anand
    The technological advances concerning drones have encouraged the market to consider drone applications in different areas including last mile delivery. However, limitations due to battery capacity, maximum weight, and legal regulations restrict the effective operational range of drones in many practical applications. To overcome the battery issue, hybrid operations involving one or more drones launching from a larger vehicle have emerged, in which the larger vehicle operates as a mobile depot and a recharging platform. In this dissertation, we describe a routing model that leverage the drone and truck working as a synchronized unit. The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery system composed by a truck and a drone. The drone launches from the truck with a single package to deliver to a customer. Each drone must return to the truck to recharge batteries, pick up another package, and launch again to a new customer location. This work proposes two novel Mixed Integer Programming (MIP) formulations and a heuristic approach to address the problem. The proposed MIP formulations yields better linear relaxation bounds than previously proposed formulations for all instances, and was capable of optimally solving several unsolved instances from the literature. We developed a hybrid heuristic based on the General Variable Neighborhood Search metaheuristic to tackle a generalization of the FSTSP called Multiple Traveling Salesman Problem with Drones, in which multiple trucks and drones are considered as part of the delivery system. The heuristic obtained high-quality solutions for large-size instances. The efficiency of the algorithm was evaluated on 410 benchmark instances from the literature, and over 80% of the best known solutions were improved.
  • Nenhuma Miniatura Disponível
    Item
    Problema de roteamento de veículos elétricos capacitados com localização de estações de troca de baterias.
    (2021) Souza, Afrânio de Castro; Penna, Puca Huachi Vaz; Souza, André Luyde da Silva; Penna, Puca Huachi Vaz; Moreira, Gladston Juliano Prates; Gonçalves, Luciana Brugiolo
    O aumento do número de veículos movidos a combustíveis fósseis, principalmente nos meios urbanos, elevou consideravelmente a quantidade de poluentes lançados ao meio ambiente. Com a criação da área de pesquisa denominada Logística Verde, foi possível propor soluções para a linha de produção e distribuição de produtos onde o impacto ao meio ambiente sejam reduzidos. Uma alternativa sustentável para a distribuição de produtos em grandes centros urbanos é a utilização de veículos elétricos. Neste trabalho, apresenta-se o Problema de Roteamento de Veículos Elétricos (PRVE) juntamente com a definição de locais estratégicos para a instalação de estações de trocas de baterias, considerando a autonomia limitada das baterias. Para tratar o problema, foi desenvolvido um algoritmo heurístico, baseado na meta-heurística Iterated Local Search (ILS). Na fase de construção da solução inicial foram utilizados dois métodos gulosos: o método do vizinho mais próximo e um segundo que considera maior demanda. No método de busca local, foi utilizado o Randomized Variable Neighborhood Descent (RVND) com um conjunto de 9 (nove) vizinhanças. Experimentos computacionais em instâncias da literatura mostram que foi possível obter resultados de alta qualidade, evidenciando a eficiência da abordagem proposta.
  • Nenhuma Miniatura Disponível
    Item
    Heurísticas matemáticas aplicadas ao problema de carregamento de contêineres.
    (2020) Oliveira, Kelly Márcia de; Toffolo, Túlio Ângelo Machado; Toffolo, Túlio Ângelo Machado; Penna, Puca Huachi Vaz; Silva, Everton Fernandes da
    Este trabalho tem seu foco no Problema de Carregamento de Contêineres (CLP, do inglês Container Loading Problem). Neste problema, deseja-se alocar caixas de forma retangular em contêineres de modo que todas as caixas sejam alocadas e o volume total dos contêineres usados seja o menor possível. Devido ao crescente número de encomendas enviadas mundialmente, há uma demanda por parte das empresas e da sociedade por métodos para alocar caixas em contêineres de forma eficiente. Ao realizar o carregamento de caixas, as seguintes restrições devem ser satisfeitas: todas as caixas devem ser alocadas; caixas não podem se sobrepor dentro de um contêiner; e caixas devem ser alocadas inteiramente dentro da área do contêiner. Este trabalho propõe duas heurísticas matemáticas para o CLP, baseadas em Relax-and-fix e Local Branching. As duas estratégias utilizam métodos construtivos para produzir uma solução inicial e, em seguida, realizam uma busca local utilizando um modelo de programação inteira mista. Embora o Local Branching, assim como o Relax-and-fix, tenha sido capaz de encontrar uma solução até pouco tempo desconhecida para uma instância, resultados indicam que o Relax-and-fix é um método mais promissor, pois é capaz de gerar mais soluções de qualidade, igualando por muitas vezes o melhor resultado conhecido na literatura.