Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/RVMR-794N3K
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Geraldo Robson Mateus | pt_BR |
dc.contributor.referee1 | Sérgio Ricardo de Souza | pt_BR |
dc.contributor.referee2 | Guilherme Bastos Alvarenga | pt_BR |
dc.contributor.referee3 | Sebastián Alberto Urrutia | pt_BR |
dc.creator | Francisco Henrique de Freitas Viana | pt_BR |
dc.date.accessioned | 2019-08-12T06:10:10Z | - |
dc.date.available | 2019-08-12T06:10:10Z | - |
dc.date.issued | 2007-03-05 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/1843/RVMR-794N3K | - |
dc.description.abstract | It is well-know that the final cost of commercial products is mostly due to expenses with their transport. In this context, appears the vehicle routing problem that aims to optimize the routes of a fleet which is responsible of providing pick-up and delivery services. In face of the necessity in attending requests that come during the fleet's operation time, appears the dynamic vehicle routing problem. This dissertation brings an approach to obtain good quality solutions to the time-dependent dynamic time-window vehicle routing problem. A framework was proposed based on column generation heuristic that uses a evolutionary algorithm aiming to generate a solution set to the problem. Moreover, the evolutionary algorithm generates a set of columns, or a set of routes that attends the problem's constraints, for a set partitioning problem formulation. The optimal solution for the set partitioning problem is a good solution for the vehicle routing problem. Three dynamic policies were presented to determinate the moment at which the new requests are sent to the dynamic evolutionary algorithm.The Online policy sends the request as soon as they are generated. The Size Demand policy stores the new requests in a buffer and sends them forward to the dynamic evolutionary algorithm only when the buffer is full. While the Periodic policy waits a fixed period of time before forwarding a new requests to the dynamic evolutionary algorithm. The framework was tested with the classic instances proposed by Solomon(1987). It was reported tests using the three policies presented and the results were analyzed by statistics. | pt_BR |
dc.description.resumo | É notório que o custo final das mercadorias no comércio varejista decorre, em grande parte, dos gastos com o transporte de bens.Neste contexto, surge o problema de roteamento de veículos que visa a otimizar as rotas de uma frota que tem a incumbência de prestar serviços de coleta ou de entrega em pontos de demanda.Diante da necessidade do atendimento de requisições efetuadas no decorrer do período de operação da frota, surge o problema de roteamento dinâmico de veículos. Este trabalho traz uma abordagem capaz de fornecer soluções de boa qualidade para o problema de roteamento dinâmico de veículos com janelas de tempo e tempos de viagem variáveis. Foi proposto um arcabouço, baseado em uma heurística de geração de colunas que utiliza um algoritmo evolucionário dinâmico com o intuito de gerar um conjunto de soluções para o referido problema. Associado a este algoritmo, foi utilizada uma formulação matemática do problema de partição de conjuntos que visa a obter a melhor combinação de rotas que atendem às restrições do problema, tendo como base as rotas pertencentes às soluções encontradas pelo algoritmo evolucionário. Foram apresentadas três políticas de roteamento dinâmico para determinar o momento no qual as novas requisições efetuadas são repassadas ao algoritmo evolucionário dinâmico. A política Online repassa as requisições logo que são geradas. A política Por Demanda aramazena as novas requisições em uma fila e as repassa ao algoritmo dinâmico somente quando a fila atinge o seu limite de capacidade. Já a política Periódica, por sua vez, espera um período de tempo fixo entre os repasses de novas requisições ao algoritmo evolucionário dinâmico.O arcabouço foi testado através de uma adaptação das instâncias clássicas de problemas de roteamento de veículos propostas por Solomon(1987). Foram realizados testes das três políticas de roteamento dinâmico apresentadas e os resultados foram analisados através de estatísticas. | pt_BR |
dc.language | Português | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | otimização | pt_BR |
dc.subject | roteamento de veículos | pt_BR |
dc.subject.other | Logística | pt_BR |
dc.subject.other | Otimização matemática | pt_BR |
dc.subject.other | Algoritmos de computador | pt_BR |
dc.subject.other | Computação | pt_BR |
dc.subject.other | Transporte rodoviário Processamento de dados | pt_BR |
dc.subject.other | Transporte rodoviario Controle automático | pt_BR |
dc.title | Algoritmo para o problema de roteamento dinâmico de veículos com janelas de tempo e tempos de viagem variáveis | pt_BR |
dc.type | Dissertação de Mestrado | pt_BR |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
franciscohenriqueviana.pdf | 764.19 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.