Biblioteca Digital da UEM: Sistema Nou-Rau
Pgina Principal  Portugus   English  Español   Aumentar Texto  Texto Normal  Diminuir Texto
  Principal | Apresentao | Objetivos | Instrues Autores | Estatsticas | Outras Bibliotecas Digitais
  Sistema Integrado de Bibliotecas - SIB / UEM
Entrar | acessos | verso 1.1  
ndice
Pgina principal
Documentos
Novidades
Usurios

Aes
Consultar
Procurar
Exibir estatsticas

Procurar por:
Procura avanada

Dvidas e sugestes


Consultar: Programa de Ps-Graduao em Cincia da Computao

Incio > Dissertaes e Teses > Cincias Exatas e da Terra > Cincia da Computao > Programa de Ps-Graduao em Cincia da Computao

Ttulo [PT]: Algoritmos baseados na meta-heurstica VNS aplicados ao problema de escalonamento de motoristas de nibus
Ttulo [EN]: Algorithms based on the VNS meta-heuristic applied on the bus driver schedule problem
Autor(es): Allainclair Flausino dos Santos
Palavras-chave [PT]:

Problema de escalonamento de motoristas de nibus. Escalonamento. Motoristas de nibus. Meta-heurstica VNS. Tripulao. Problema de Escalonamento de Tripulao. Brasil.
Palavras-chave [EN]:
Bus driver scheduling problem. Crew scheduling problem. VNS. Metaheuristic. Brazil.
Titulao: Mestre em Cincia da Computao
Banca:
Ademir Aparecido Constantino [Orientador] - UEM
Wesley Romo - UEM
Silvio Alexandre de Araujo - UNESP
Resumo:
Resumo: Para que o sistema de transporte pblico seja prestado com qualidade necessrio investigar e resolver inmeros problemas, e dentre os problemas computacionais, existe o Problema de Escalonamento de Motoristas de nibus (PEMO), o qual NP-difcil. Este trabalho apresenta quatro novos algoritmos da meta-heurstica VNS para o PEMO, um GVNS e trs VNS denominados adaptativos. Os quatro algoritmos possuem uma fase construtiva em comum e uma fase melhorativa que os diferem, tal que na fase melhorativa, os mtodos Processo de Corte e Recombinao (PCR) e k-swap foram aplicados. Os algoritmos foram avaliados ao serem aplicados em instncias da cidade de Maring, PR. Na avaliao dos algoritmos propostos, foi constatado que todos so competitivos, pois eles geraram solues melhores em relao funo de custo ao serem comparados uma outra abordagem recente, tal que o melhor algoritmo proposto obteve melhores solues na faixa de 4% a 14%. E em relao a um limite inferior o melhor algoritmo ficou na faixa de 12% a 25% acima desse limite.

Abstract: For the public transport system being provided with quality, it is need to tackle numerous problems and one of them is the Bus Driver Schedule Problem (BDSP) which is NP-hard. This work presents four new algorithms of the VNS meta-heuristic for the BDSP, one GVNS and three VNS named adaptatives. The four algorithms have a constructive common phase and an improved phase that differs them, such that in the improved phase, the Cut and Combine Process and k-swap were applied. The algorithms were evaluated applying them on instances of Maring, PR, Brazil city. In the algorithm evaluations was found that all are competitive when they were compared with another recent approach, because they generated better solutions with respect to the cost function, such that the best algorithm obtained better solutions in the range of 4% to 14%. With respect to a lower bound the best algorithm got the range of 12% to 25% over this bound.
Data da defesa: 16/12/2016
Cdigo: vtls000225252
Informaes adicionais:
Idioma: Portugus
Data de Publicao: 2016
Local de Publicao: Maring, PR
Orientador: Prof. Dr. Ademir Aparecido Constantino
Instituio: Universidade Estadual de Maring . Centro de Tecnologia . Programa de Ps-Graduao em Cincia da Computao
Nvel: Dissertao (mestrado em Cincia da Computao)
UEM: Departamento de Informtica

Responsavel: edson
Categoria: Aplicao
Formato: Documento PDF
Arquivo: Allainclair Flausino dos Santos.pdf
Tamanho: 15178 Kb (15542270 bytes)
Criado: 12-04-2017 16:54
Atualizado: 12-04-2017 17:24
Visitas: 278
Downloads: 6

[Visualizar]  [Download]

Todo material disponvel neste sistema de propriedade e responsabilidade de seus autores.