Use este identificador para citar ou linkar para este item: http://www.repositorio.ufop.br/jspui/handle/123456789/14549
Título: Algoritmos heurísticos para o problema de roteamento de unidades móveis de mamografia.
Autor(es): Rosa, Otávio Augusto Souza
Orientador(es): Souza, Marcone Jamilson Freitas
Penna, Puca Huachi Vaz
Palavras-chave: Mamografia
Veículos - roteamento
Logística - saúde
Data do documento: 2021
Membros da banca: Souza, Marcone Jamilson Freitas
Penna, Puca Huachi Vaz
Coelho, Igor Machado
Carvalho, Marco Antonio Moreira de
Referência: ROSA, Otávio Augusto Souza. Algoritmos heurísticos para o problema de roteamento de unidades móveis de mamografia. 2021. 48 f. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2021.
Resumo: Este trabalho introduz o Problema de Roteamento de Unidades Móveis de Mamografia (MMURP). Este problema consiste em roteirizar um conjunto de Unidades Móveis de Mamografia (MMU) para atender a demanda de localidades desprovidas de mamógrafos fixos ou com número insuficiente deles. O objetivo é maximizar a demanda atendida e minimizar a distância total percorrida pelas MMUs. Para tratar o problema, propomos os algoritmos Smart IGS-VND e Smart IGS-RVND, ambos baseados na metaheurística Iterated Greedy Search. Nestes algoritmos, uma solução inicial é gerada por meio de um procedimento de três passos. Para refinar uma solução, usamos os procedimentos Randomized Variable Neighborhood Descent (RVND) e Variable Neighborhood Descent (VND). Para não ficar preso em ótimos locais e explorar diferentes regiões do espaço de soluções do problema, aplicamos um procedimento para destruir a solução atual e outro para construí-la de forma gulosa. Para testar os algoritmos propostos, usamos instâncias com 579 localidades, dois depósitos, até 56 MMUs e 180 km entre dois locais no máximo. Realizamos os testes considerando três cenários diferentes. Esses cenários diferem entre si pelo número de localidades candidatas a serem atendidas, o número de MMUs disponíveis em cada depósito e a capacidade dessas MMUs. Os resultados mostraram que os dois algoritmos encontraram soluções que atendem integralmente a demanda da região estudada. O Smart IGS-VND obteve um melhor desempenho para encontrar um valor alvo de demanda previamente definido. No entanto, quando foram comparadas a distância total percorrida pelas MMUs com a cobertura de exames, o Smart IGS-RVND mostrou ser capaz de encontrar soluções de melhor qualidade, reduzindo a distância total percorrida pelos veículos. No último cenário, apresentamos um plano de serviço mensal para uma MMU, variando de um a doze meses.
Resumo em outra língua: This work introduces the Mobile Mammography Units Routing Problem (MMURP). This problem consists of defining routes for a set of Mobile Mammography Units (MMU) to cover the demand of locations without fixed mammography units or with an insufficient number of them. The objective is to maximize the demand attended and minimize the total distance traveled by the MMUs. To treat the problem, we propose two algorithms, named Smart IGS-VND and Smart IGS-RVND, which are based on the Iterated Greedy Search metaheuristic. We generated an initial solution through a three-phase procedure. We used the Randomized Variable Neighborhood Descent (RVND) and Variable Neighborhood Descent (VND) methods to refine the solution. To not get stuck in the local optimum and explore different regions of this search space, we applied one procedure to destroy the current solution and another to construct it greedily. To test the proposed algorithms, we used instances with 579 locations, two depots, up to 56 MMUs, and 180 km between two locations at maximum. We performed the tests considering three different scenarios. These scenarios differ from each other concerning the number of candidate locations to be attended, the number of MMUs available in each deposit, and the capacity of these MMUs. The results showed that the algorithms found solutions that reach the whole demand of the studied area. The Smart IGS-VND algorithm had a better performance to find a target value of demand previously defined. However, when we compare the total distance traveled by the MMUs with the exam coverage, the Smart IGS-RVND showed to be able to find better quality solutions, reducing the total distance traveled by the vehicles. In the last scenario, we present a monthly MMU service plan, ranging from one to twelve months.
Descrição: Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
URI: http://www.repositorio.ufop.br/jspui/handle/123456789/14549
Licença: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 15/02/2022 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais.
Aparece nas coleções:PPGCC - Mestrado (Dissertações)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
DISSERTAÇÃO_AlgoritmosHeurísticosProblema.pdf1,94 MBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons