PPGCC - Programa de Pós-graduação em Ciência da Computação
URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596
Navegar
2 resultados
Resultados da Pesquisa
Item Algoritmos meta-heurísticos para o problema dial-a-ride.(2019) Souza, André Luyde da Silva; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Toffolo, Túlio Ângelo MachadoEste 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.Item Metaheurísticas Busca Tabu para o problema de rodízio de tripulações de ônibus urbanos.(2013) Andrade, Suelaine Débora Gonçalves de; Silva, Gustavo PeixotoO Problema de Rodízio das Tripulações (PRT) do sistema de transporte público consiste em atribuir a cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas.Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas. Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.