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]: Avaliao da Meta-heurstica VNS para um problema de planejamento operacional do transporte pblico
Ttulo [EN]: Study of heuristics algorithms for a operational planning problem of public transport
Autor(es): Rubens Zenko Sakiyama
Palavras-chave [PT]:

Transporte pblico. Escalonamento. Algoritmos. Algoritmos heursticos. Meta-heurstica VNS. Problema de escalonamento de motoristas (PEM). Brasil.
Palavras-chave [EN]:
Public transport. Bus driver. Scheduling problem. Large real-world. Heuristic. VNS Metaheuristic. Brazil.
Titulao: Mestre em Cincia da Computao
Banca:
Ademir Aparecido Constantino [Orientador] - UEM
Wesley Romo - UEM
Arinei Carlos Lindbeck da Silva - MAT/UFPR
Resumo:
Resumo: o Problema de Escalonamento de Motoristas (PEM) consiste em gerar uma escala de trabalho de motoristas, para cobrir uma escala de veculos com o menor custo, satisfazendo restries impostas pelas leis trabalhistas, acordos sindicais e normas da empresa. Esse processo uma etapa fundamental para o planejamento operacional de empresas do setor de transporte coletivo visto que o custo com motoristas atinge uma parcela significativa no custo global da empresa. Considerado como NP-Difcil, vrios trabalhos abordam a resoluo do PEM atravs de algoritmos heursticos devido s limitaes dos algoritmos exatos para tratar com instncias de grande porte. O presente trabalho prope uma abordagem para a soluo do PEM envolvendo dois procedimentos de busca local em uma estrutura de vizinhana, denominados PCR e k-swap, de forma determinstica e em conjunto com a meta-heurstica VNS. Para validao da proposta foram utilizadas instncias reais com mais de 2300 viagens e instncias aleatrias extradas das instncias reais. Os experimentos realizados comprovam a eficincia da meta-heurstica VNS para instncias de grande porte, onde os resultados obtidos so comparados com resultados apresentados por outros trabalhos que utilizaram os procedimentos PCR e k-swap sem a utilizao da meta-heurstica VNS.

Abstract: The Bus Driver Scheduling Problem (BDSP) consists to generate a set of drivers schedule to cover a set of vehicles schedule at the lowest cost, satisfying constraints imposed by labor laws, trade union agreements and company standards. This process is vital to the operational planning of public transportation companies since the drivers cost afIects a significant portion ofthe overall cost ofthe company. Considered NP-Hard, several works address the resolution of PEM through heuristic algorithms due to the limitations of the exact algorithms to work with large instances. The present work propose a approach for solving the BDSP involving two local search procedures in a neighborhood structure, called PCR and k-swap, in a deterministic way and in conjunction with VNS meta-heuristic. To validate the work is proposed real instances with over 2300 travei and random instances extracted of real instances. The experiments demonstrated the efficacy of VNS meta-heuristic for large instances, where the present results are compared with results reported by other studies that used PCR and k-swap procedures without the use ofVNS meta-heuristic.
Data da defesa: 14/02/2014
Cdigo: vtls000212899
Informaes adicionais:
Idioma: Portugus
Data de Publicao: 2014
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: beth
Categoria: Aplicao
Formato: Documento PDF
Arquivo: Rubens Zenko Sakiyama.pdf
Tamanho: 7264 Kb (7438636 bytes)
Criado: 01-04-2016 16:02
Atualizado: 01-04-2016 16:16
Visitas: 383
Downloads: 5

[Visualizar]  [Download]

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