• Login
    View Item 
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016030P0 Programa de Pós-Graduação em Métodos Numéricos em Engenharia
    • Teses
    • View Item
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016030P0 Programa de Pós-Graduação em Métodos Numéricos em Engenharia
    • Teses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    O problema de roteamento periódico e capacitado em arcos com movimentos contínuos

    Thumbnail
    View/Open
    R - T - GUILHERME VINICYUS BATISTA.pdf (92.56Mb)
    Date
    2018
    Author
    Batista, Guilherme Vinicyus, 1989-
    Metadata
    Show full item record
    Subject
    Arcos
    Análise numérica
    Ferrovias - Trilhos
    Construção civil - Medidas de segurança
    xmlui.dri2xhtml.METS-1.0.item-type
    Tese Digital
    Abstract
    Resumo: Esse trabalho aborda o Problema de Roteamento Periódico e Capacitado em Arcos, Periodic Capacitated Arc Routing Problem (PCARP), que pode ser definido como um problema de roteamento em arcos envolvendo um horizonte de tempo composto por mais de um período, os quais podem ser formados por qualquer fração temporal desde que discretas. Um ou mais veículos, ao fazerem suas rotas, devem executar da melhor maneira possível as tarefas que estão associadas a cada arco sem exceder sua capacidade e respeitando as frequências exigidas. Esse trabalho visa classificar as pesquisas acerca do PCARP por meio de uma proposta taxonômica que considera características físicas, foco aplicável ou teórico e abordagem resolutiva. Outra contribuição é um estudo aplicado à inspeção de ferrovias, o qual é classificado como PCARP com Movimentos Contínuos. Rotas com movimentos contínuos são caracterizadas por não terem a obrigatoriedade de serem iniciadas e terminadas em um depósito. O problema tem sua formulação matemática apresentada e sua a resolução é feita utilizando métodos exato, heurístico e híbridos. O método exato consiste na utilização de um solver comercial e a heurística utilizada é um novo algoritmo de Otimização de Colônia de Formigas, Ant Colony Optimization (ACO). Ambos têm seus pontos fortes que se complementam, sendo assim foram propostas três abordagens híbridas. A primeira consiste na utilização da colônia de formigas como solução inicial para o modelo exato, e as outras duas abordagens são variações do algoritmo Busca Iterativa em Espaço Restrito, Iterative Restricted Space Search (IRSS). A IRSS é baseada na exploração estratégica do espaço de soluções de um dado problema que, nesse trabalho, será auxiliada pelo algoritmo ACO. Os resultados alcançados mostram que as estratégias de resolução propostas são capazes de superar os resultados alcançados pelo solver comercial. Palavras-chave: Problema de Roteamento Periódico e Capacitado em Arcos 1. Movimentos Contínuos 2. Otimização da Colônia de Formigas 3. Busca Iterativa em Espaço Restrito 4. Manutenção e Inspeção de Ferrovias 5.
     
    Abstract: The Periodic Capacitated Arc Routing Problem (PCARP) can be defined as an arc routing problem that involves a time horizon, which is greater than one period that can be composed by any fraction of time. One or many vehicles, while into routes, must perform, in the best way possible, all tasks in the arcs without exceeding their capacities and attending the required frequencies. This work classifies researches about PCARP using a taxonomy that considers physical features, applied or academic focus and resolution approach. An additional contribution is a study based on inspection of railroads; this one is classified as PCARP with Continuous Moves. Routes with continuous moves do not need a depot as a starting or finishing point. This work presents the mathematical formulation for the problem and tackles it with exact, heuristic and hybrid methods. The exact approach consists of the use of a commercial solver, and the heuristic is a new Ant Colony Optimization (ACO) algorithm. Both have strengths that may be combined to compose hybrid approaches, three of them are explored. The first one uses the ACO to form an initial solution to the solver, and the two others are variants of the Iterative Restricted Space Search (IRSS) framework. The IRSS strategically exploits the solution space of one problem assisted by an algorithm, in this case, the ACO. The results achieved showed that the strategies proposed are able to overcome the ones from the commercial solver. Keywords: Periodic Capacitated Arc Routing Problem 1. Continuous Moves 2. Ant Colony Optimization 3. Iterative Restricted Space Search 4. Inspection and Maintenance in Railways 5.
     
    URI
    https://hdl.handle.net/1884/59909
    Collections
    • Teses [134]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_typeThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_type

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV