Please use this identifier to cite or link to this item: http://www.repositorio.ufop.br/handle/123456789/11697
Title: Algoritmos meta-heurísticos para o problema dial-a-ride.
Authors: Souza, André Luyde da Silva
metadata.dc.contributor.advisor: Vaz Penna, Puca Huachi
Souza, Marcone Jamilson Freitas
Keywords: Transporte urbano
Trânsito urbano
Problema de roteamento de veículos
Issue Date: 2019
metadata.dc.contributor.referee: Vaz Penna, Puca Huachi
Souza, Marcone Jamilson Freitas
Santos, André Gustavo dos
Toffolo, Túlio Ângelo Machado
Citation: SOUZA, André Luyde da Silva. Algoritmos meta-heurísticos para o problema dial-a-ride. 2019. 50 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, 2019.
Abstract: Este trabalho trata do problema Dial-a-Ride, que consiste em fazer rotas para veículos com a finalidade de transportar pacientes de diferentes locais para realizar exames médicos em unidades de tratamento de saúde. O Dial-a-Ride é uma extensão do Problema de Roteamento de Veículos, possuindo características do Problema de Roteamento de Veículos com Janela de Tempo e do Problema de Roteamento de Veículos com Coleta e Entrega, combinados com restrições relativas aos pacientes. O trabalho considera a forma estática do problema e utiliza dados obtidos da Prefeitura Municipal de Ouro Preto-MG para modelagem e contextualização do problema. Para resolvê-lo, propõe-se dois algoritmos heurísticos, MS-VNS1 e VNS2, ambos baseados na meta-heurística Variable Neighborhood Search (VNS). O primeiro, MSVNS1, é guiado pela meta-heurística Multi-Start tendo como busca local o VNS. O segundo, por sua vez, é guiado apenas pelo VNS. Nos dois algoritmos o método de busca local do VNS é o procedimento heurístico Randomized Variable Neighborhood Descent (RVND), o qual usa os movimentos de realocação, troca e cruzamento para explorar o espaço de soluções do problema. Os resultados computacionais foram obtidos pela aplicação dos algoritmos em um conjunto de instâncias da literatura e comparados com os das melhores soluções desta variante do problema. Apesar de simples, os algoritmos desenvolvidos foram capazes de encontrar a solução ótima para algumas instâncias e soluções de boa qualidade para as demais. Os algoritmos também foram testados em um conjunto de instâncias criadas a partir de dados fornecidos pela Prefeitura Municipal de Ouro Preto-MG. Ambos se mostraram capazes de atender as demandas da cidade de Ouro Preto de forma automatizada, proporcionando ao setor de transporte da prefeitura uma ferramenta que possibilita reduzir os custos com o transporte de pacientes e diminuir a alocação de funcionários para cumprir essa atividade.
Description: 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/handle/123456789/11697
metadata.dc.rights.license: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 31/07/2019 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 nem a adaptação.
Appears in Collections:PPGCC - Mestrado (Dissertações)

Files in This Item:
File Description SizeFormat 
DISSERTAÇÃO_AlgoritmosMetaheuristicosProblema.pdf2,98 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons