Please use this identifier to cite or link to this item: http://repositorio.ufersa.edu.br/handle/prefix/5192
Type: Dissertação
Title: Um método para a roteirização de veículos em regiões com restrições de circulação
Authors: Vasconcelos Filho, José Weliton de
First Advisor: Aloise, Dario José
First Co-advisor: Aragão Junior, Dmontier Pinheiro
First member of the board: Liberalino, Carlos Heitor Pereira
Second member of the board: Lima Júnior, Francisco das Chagas de
Third member of the board: Thomaz, Antônio Clécio Fontenelles
Fourth member of the board: Pinheiro, Plácido Rogério
Resume: As restrições de tráfego de caminhões em centros urbanos estão sendo cada vez mais adotadas para tentar reduzir os níveis de congestionamentos. Com isso, empresas distribuidoras necessitam criar rotas otimizadas para atender a demanda dos seus clientes, mas respeitando as restrições de circulação de veículos. Este trabalho tem como objetivo propor um método para roteirização de veículos em regiões com restrições de circulação. Por se tratar de um problema NP-difícil, métodos exatos demandam tempos computacionais não aceitáveis em problemas envolvendo muitos clientes, i.e., problemas reais. Assim sendo, o método proposto utiliza, separadamente as meta-heurísticas Busca em Vizinhança Variável (VNS) e Procedimento de Busca Guloso, Aleatório e Adaptativo (GRASP) para encontrar rotas sub-ótimas, eventualmente ótimas para os veículos. Foram desenvolvidos e comparados quatro algoritmos, usando a meta-heurísticas VNS e GRASP; sendo ambas aplicadas uma vez com dependência de tempo e outra vez com clusterização. Como validação, este trabalho utilizou os dados de uma distribuidora real da cidade de São Paulo, a partir destes foram criadas 27 instâncias para a realização dos experimentos nas cidades de Fortaleza, Recife e São Paulo. Essas cidades foram escolhidas por possuírem restrições de circulação. Os resultados obtidos mostram que o método é capaz de lidar com diferentes cenários de roteirização, alcançando um bom resultado para as meta-heurísticas VNS e GRASP
Abstract: Traffic restrictions for trucks in urban centers are increasingly being adopted to try to reduce congestion levels. With this, distribution companies need to create routes optimized to meet the demand of their customers, but respecting the restrictions of tra c of vehicles. This work aims to propose a method for vehicle routing in regions with tra c restrictions. Because it is an NP-di cult problem, exact methods require unacceptable computational times in problems involving many clients, i.e. actual problems. Thus, the proposed method uses, separately, the Variable Neighborhood Search (VNS) and the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristics to find sub-optimal routes, which may be optimal for vehicles. Four algorithms were developed and compared using the VNS and GRASP metaheuristics; both being applied once with time dependence and again with clustering. As validation, this work used the data of a real distributor of the city of São Paulo, from these were created 27 instances for the accomplishment of the experiments in the cities of Fortaleza, Recife and São Paulo. These cities were chosen because they have tra c restrictions. The results show that the method is able to handle di erent routing scenarios, achieving a good result for the VNS and GRASP metaheuristics
Keywords: Problema de Roteamento de Veículos
Restrições de Tráfego
Logística Urbana
Meta-Heurísticas VNS e GRASP
Vehicle Routing Problem
Tra c Restrictions
City Logistics
VNS and GRASP metaheuristics
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA
Language: por
Country: Brasil
Publisher: Universidade Federal Rural do Semi-Árido
Institution Initials: UFERSA
Department: Centro de Ciências Exatas e Naturais - CCEN
Program Name: Programa de Pós-Graduação em Ciência da Computação
Citation: Citação com autor incluído no texto: Vasconcelos Filho (2018) Citação com autor não incluído no texto: (VASCONCELOS FILHO, 2018)
Access Type: Acesso Aberto
URI: http://repositorio.ufersa.edu.br/handle/prefix/5192
Issue Date: 30-May-2018
License Term: CC-BY-SA
Appears in Collections:Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
JoséWVF_DISSERT.pdf1.98 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.