CAMPELO JÚNIOR,José Uirton.Proposta de OTIMIZAÇÃO da Roterização dos Distritos dos Carteiros: Um Estudo de Caso no Centro de entrega de Encomendas de Fortaleza.2010.99f. Dissertação(Mestrado em Logística e Pesquisa Operacional)- Pró-Reitoria de Pesquisa e Pós-Graduação,Univesidade Federal do Ceará, Fortaleza, 2010. / Submitted by Winne Gomes da Silva (winnegomez87@gmail.com) on 2012-06-08T13:09:07Z No. of bitstreams: 1 2010_dis_jucjunior.pdf: 2046335 bytes, checksum: bfe13c991469912096b5aab9a25f41a3 (MD5) / Approved for entry into archive by Nirlange Queiroz(nirlange@gmail.com) on 2012-06-20T11:52:47Z (GMT) No. of bitstreams: 1 2010_dis_jucjunior.pdf: 2046335 bytes, checksum: bfe13c991469912096b5aab9a25f41a3 (MD5) / Made available in DSpace on 2012-06-20T11:52:47Z (GMT). No. of bitstreams: 1 2010_dis_jucjunior.pdf: 2046335 bytes, checksum: bfe13c991469912096b5aab9a25f41a3 (MD5) Previous issue date: 2010 / The Vehicle Routing Problem (VRP) involves determining a set of routes to be traveled, noting the lower cost of transport for a specified number of vehicles. Each route must start and finish in the warehouse, so as each point has to be visited by one vehicle and only once. Many versions of the problem are found in the literature, depending on the various possible restrictions such as vehicle capacity and time window. The ECT (Mail and Telegraph Company) although it is one of the world's largest companies in the business of delivering parcels and letters. Does not have an efficient computer system that performs this function, i.e. a system able to offer daily routes to distribution. In her field, she has a system capable of showing the actual and the amount and type of vehicles to be used in the distribution of their orders. This work proposes routing algorithms to be applied in order distribution of the Post. The algorithms make the division of orders into groups and then route. Was drawn up two heuristics for the group division and three heuristics for the routing phase. The heuristics are split groups were applied to a real problem, from the districts of the Center for Delivery Orders (EEC), in Fortaleza-CE, conducted in 2009. The routing heuristics were applied to two routes taken by postmen in the same EEC, with the results obtained and compared with the route taken by postmen. The results showed that the proposed algorithms supply the deficiency of routing mail, because the division of groups was satisfactory and heuristics routing paths were smaller than those proposed by postmen in 7 of 8 assessments. / O Problema de Roteamento de Veículos (PRV) implica em determinar um conjunto de rotas que deverão ser percorridas, observando o menor custo de transporte por um número determinado de veículos. Cada rota deve iniciar e terminar no depósito, como também cada ponto tem que ser visitado por um único veículo e uma única vez. Muitas versões do problema são encontradas na literatura, em função das várias restrições possíveis como capacidade do veículo e janela de tempo. A Empresa de Correios e Telégrafos, embora seja uma das maiores empresas do mundo no ramo de entrega de encomendas, cartas, etc., ainda não possui um sistema computacional eficiente que realize esta funcionalidade, isto é, um sistema capaz de propor rotas diárias para a distribuição. Em seu domínio, ela possui um sistema capaz de dimensionar o efetivo e a quantidade e tipo de veículos a serem utilizados na distribuição de suas encomendas. Esta dissertação propõe algoritmos de roteamento a serem aplicados na distribuição de encomendas dos Correios. Os algoritmos fazem a divisão das encomendas em grupos para depois rotear. Elaborou-se 2 heurísticas para a divisão dos grupos e 3 heurísticas para a fase de roteamento. As heurísticas de divisão de grupos foram aplicadas a um problema real, a partir dos distritos do Centro de Entrega de Encomendas (CEE), na cidade de Fortaleza-CE, realizado em 2009. As heurísticas de roteamento foram aplicadas em duas rotas realizadas por carteiros do mesmo CEE, com os resultados obtidos comparados entre si e com o percurso realizado pelos carteiros. Os resultados mostraram que os algoritmos propostos suprem a deficiência de roteamento dos Correios, pois a divisão de grupos foi satisfatória e as heurísticas de roteamento apresentaram percursos menores do que os propostos pelos carteiros em 7 das 8 avaliações realizadas.

Made available in DSpace on 2016-08-29T15:36:43Z (GMT). No. of bitstreams: 1 tese_6827_RESUMO ÁLVARO.pdf: 48381 bytes, checksum: 0f6c8db70af8f91bd25b9ca596ce6499 (MD5) Previous issue date: 2014-08-28 / O sistema logístico para distribuição de produtos acabados caracteriza-se pela integração dos serviços de comunicação, transporte e financeiros com a finalidade de atender às demandas do consumidor final. Estima-se que no estado do Espírito Santo, o consumo de carne de frango seja de 44,4 quilos per capita por ano. Para atender a esta demanda, o estado conta com matadouros-frigoríficos distribuídos pelo seu território, bem como, com a participação de outras empresas localizadas no país. Em sistemas de transportes, são característicos Problemas de Roteamento de Veículos (VRP), que precisam ser estudados, caracterizados e otimizados, normalmente, através de rotinas computacionais, que permitem avaliar maior quantidade de variáveis. O presente trabalho teve por objetivo caracterizar um VRP de um matadouro-frigorífico da região do Sul do Espírito Santo e desenvolver um aplicativo computacional que seja suporte para os gestores de logística, servindo para avaliar e propor rotas, e analisar parâmetros logísticos do processo de distribuição de produtos. No desenvolvimento do aplicativo computacional foi necessário caracterizar o sistema logístico da empresa, coletar e analisar os dados das operações logísticas, desenvolver as rotinas computacionais que representassem o sistema em estudo, verificar a confiabilidade dos resultados fornecidos pelo aplicativo, validá-lo e então, poder realizar as experimentações. O aplicativo desenvolvido permitiu reproduzir dados do sistema estudado e avaliar rotas segundo parâmetros logísticos. Pode-se concluir que o aplicativo computacional desenvolvido é útil aos gestores de logística, permitindo a avaliação das rotas praticadas e de novas configurações de rotas.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2014-12-10T17:04:36Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertacao. Alvaro Jose Herzog Siqueira.texto completo.pdf: 2272535 bytes, checksum: 03e49d1287e5ec0c2cebc91e648b73d0 (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2014-12-12T18:19:00Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertacao. Alvaro Jose Herzog Siqueira.texto completo.pdf: 2272535 bytes, checksum: 03e49d1287e5ec0c2cebc91e648b73d0 (MD5) / Made available in DSpace on 2014-12-12T18:19:00Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertacao. Alvaro Jose Herzog Siqueira.texto completo.pdf: 2272535 bytes, checksum: 03e49d1287e5ec0c2cebc91e648b73d0 (MD5) Previous issue date: 2014 / O sistema logístico para distribuição de produtos acabados caracteriza-se pela integração dos serviços de comunicação, transporte e financeiros com a finalidade de atender às demandas do consumidor final. Estima-se que no estado do Espírito Santo, o consumo de carne de frango seja de 44,4 quilos per capita por ano. Para atender a esta demanda, o estado conta com matadouros-frigoríficos distribuídos pelo seu território, bem como, com a participação de outras empresas localizadas no país. Em sistemas de transportes, são característicos Problemas de Roteamento de Veículos (VRP), que precisam ser estudados, caracterizados e otimizados, normalmente, através de rotinas computacionais, que permitem avaliar maior quantidade de variáveis. O presente trabalho teve por objetivo caracterizar um VRP de um matadouro-frigorífico da região do Sul do Espírito Santo e desenvolver um aplicativo computacional que seja suporte para os gestores de logística, servindo para avaliar e propor rotas, e analisar parâmetros logísticos do processo de distribuição de produtos. No desenvolvimento do aplicativo computacional foi necessário caracterizar o sistema logístico da empresa, coletar e analisar os dados das operações logísticas, desenvolver as rotinas computacionais que representassem o sistema em estudo, verificar a confiabilidade dos resultados fornecidos pelo aplicativo, validá-lo e então, poder realizar as experimentações. O aplicativo desenvolvido permitiu reproduzir dados do sistema estudado e avaliar rotas segundo parâmetros logísticos. Pode-se concluir que o aplicativo computacional desenvolvido é útil aos gestores de logística, permitindo a avaliação das rotas praticadas e de novas configurações de rotas. / The logistics system for distribution of finished products is characterized by the integration of communication, transport and financial services in order to meet the demands of consumers. It is estimated that in Espírito Santo state, the per capita consumption of poultry meat is 44.4 kg per year. To meet this demand, the state has slaughter plants distributed throughout its territory and, count with other companies in the country. In transport systems, vehicle routing problem (VRP) are characteristic, which need to be studied, characterized and optimized, usually through computer routines for permitting to access greater number of variables. This study aimed to characterize a VRP of a slaughter plant in South Region of Espírito Santo state, and to develop a computer program that supports logistic managers, serving to evaluate existing and proposed routes, and to analyze logistic parameters of a product distribution process. In the development of computer application was necessary to characterize the logistics system of the company, collect and analyze data of logistic operations, develop computational algorithms that represent the system under study, verify and validate the computer application, and then perform experiments. The developed application allowed represents data of the studied system and evaluate routes second logistic parameters. Thus, according to this study, can be concluded that the developed computer program is useful designed for logistic managers, for enabling the evaluation of the existing routes and new routing settings.

O problema de roteamento de veículos é um dos problemas de otimização combinatória mais estudados nas últimas décadas. Neste trabalho, é estudada uma variante do problema de roteamento de veículos capacitado em que são considerados custos adicionais em viagens que cruzam fronteiras entre estados. Duas abordagens foram apresentadas para considerar tal característica: adicionar custos fixos às viagens de clientes de estados diferentes e adicionar custos que consideram a carga do veículo ao cruzar a fronteira e, para ambas, foram apresentados modelos matemáticos. Um solver comercial foi utilizado para resolver instâncias conhecidas da literatura e devido à resolução ter atingido o tempo máximo computacional para grande parte dos testes, uma Variable Neighborhood Descent com múltiplos inícios foi desenvolvida para a resolução do problema. Os múltiplos inícios são gerados perturbando a solução inicial gerada para a heurística. Como esperado, tanto para a resolução via modelagem quanto a resolução via heurística, considerar custos de fronteira proporcionais a carga apresentaram soluções de melhor qualidade. Essa nova proposta para abordar custos reais de fronteira abre novas possibilidades para considerar custos de fronteira fixos e proporcionais a carga concomitantemente para melhor representar aplicações reais. / The vehicle routing problem is one of the most studied combinatorial optimization problems in the last decades. In this paper, a variant of vehicle routing problem was studied in which the border costs was added to trips that cross borders. In order to consider such characteristic, two approaches were made: add fixed costs for the trips which clients are from different states and add costs that consider the amount of cargo in the vehicle when it crosses the border. In order to consider such characteristics, models were presented. Instances of literature were solved with a commercial solver and due to high computational time obtained from the exact method, a heuristic with Variable Neighborhood Descent as the local search in a multiple start environment was implemented. The multiple starts were generated making a perturbation in the initial solution obtained for the heuristic. As expected, approaching the problem considering the border cost proportional to the cargo in the vehicle presented better results. This study gives the first results for solving the vehicle routing problem considering real border costs and gives the possibility for solving the problem considering real fixed and proportional costs simultaneously in order to better represent real applications.

O problema de roteamento de veículos é um dos problemas de otimização combinatória mais estudados nas últimas décadas. Neste trabalho, é estudada uma variante do problema de roteamento de veículos capacitado em que são considerados custos adicionais em viagens que cruzam fronteiras entre estados. Duas abordagens foram apresentadas para considerar tal característica: adicionar custos fixos às viagens de clientes de estados diferentes e adicionar custos que consideram a carga do veículo ao cruzar a fronteira e, para ambas, foram apresentados modelos matemáticos. Um solver comercial foi utilizado para resolver instâncias conhecidas da literatura e devido à resolução ter atingido o tempo máximo computacional para grande parte dos testes, uma Variable Neighborhood Descent com múltiplos inícios foi desenvolvida para a resolução do problema. Os múltiplos inícios são gerados perturbando a solução inicial gerada para a heurística. Como esperado, tanto para a resolução via modelagem quanto a resolução via heurística, considerar custos de fronteira proporcionais a carga apresentaram soluções de melhor qualidade. Essa nova proposta para abordar custos reais de fronteira abre novas possibilidades para considerar custos de fronteira fixos e proporcionais a carga concomitantemente para melhor representar aplicações reais. / The vehicle routing problem is one of the most studied combinatorial optimization problems in the last decades. In this paper, a variant of vehicle routing problem was studied in which the border costs was added to trips that cross borders. In order to consider such characteristic, two approaches were made: add fixed costs for the trips which clients are from different states and add costs that consider the amount of cargo in the vehicle when it crosses the border. In order to consider such characteristics, models were presented. Instances of literature were solved with a commercial solver and due to high computational time obtained from the exact method, a heuristic with Variable Neighborhood Descent as the local search in a multiple start environment was implemented. The multiple starts were generated making a perturbation in the initial solution obtained for the heuristic. As expected, approaching the problem considering the border cost proportional to the cargo in the vehicle presented better results. This study gives the first results for solving the vehicle routing problem considering real border costs and gives the possibility for solving the problem considering real fixed and proportional costs simultaneously in order to better represent real applications.

Made available in DSpace on 2014-06-12T16:00:14Z (GMT). No. of bitstreams: 2 arquivo6093_1.pdf: 741570 bytes, checksum: fdadc967604851f84c712755a38b8051 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / A alocação de veículos para uma determinada demanda de consumidores, espalhados geograficamente, está sujeita a uma explosão combinatória de possibilidades, devido às infinitas alternativas de escalonamento. Esta característica impossibilita, para grandes demandas, o tratamento deste problema por algoritmos exatos, ou seja, aqueles que buscam com garantia a solução ótima do problema. Em contrapartida, existem os métodos heurísticos, que são capazes de resolver tais problemas de forma satisfatória, mas não garantindo que a solução alcançada seja a melhor possível. Esta dissertação apresenta, como principal contribuição, um Sistema Híbrido (SH) para o conhecido Problema de Roteamento de Veículos com Janela de Tempo (PRVJT). Este SH é composto dos métodos (i) Recozimento Simulado Não Monotônico (RSNM), (ii) Subida na Encosta (SE) e (iii) Reinício Aleatório (RA). Os métodos foram combinados visando promover a diversificação e a intensificação na busca por soluções do PRVJT. Como contribuição secundária, este trabalho apresenta um arcabouço de métodos estatísticos que é capaz de ajustar parâmetros de sistemas estocásticos para otimização de desempenho. Os resultados dos experimentos realizados com o modelo proposto foram comparados com cada um dos melhores resultados individuais, alcançados anteriormente, pelos diferentes algoritmos conhecidos, para toda a base de dados de Solomon. Os resultados obtidos pelo SH se mostraram relevantes, tendo o método superado ou igualado 37 das 56 instâncias testadas, caracterizando o SH como um método eficaz e robusto no tratamento do PRVJT

Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-06-26T22:34:30Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Ademir Oliveira Santos.pdf: 1332774 bytes, checksum: 97f3be79d5e03e57a8eebe8183f21e2d (MD5) / Made available in DSpace on 2018-06-26T22:34:30Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Ademir Oliveira Santos.pdf: 1332774 bytes, checksum: 97f3be79d5e03e57a8eebe8183f21e2d (MD5) Previous issue date: 2017-02-21 / CAPES / O problema de roteamento de veículos tem grande importância dentro da logística e cadeia de suprimentos, pois tem como finalidade o desenho de rotas ótimas para ser usado por uma frota de veículos destinados a atender a um conjunto de clientes com o menor custo possível. O objetivo deste trabalho é desenvolver e aplicar o problema de roteamento de veículos com janelas de tempo envolvendo questões ambientais, atividades de manutenção preventiva e algumas restrições relativas à jornada de trabalho do condutor (ECOPRVMP) no contexto de uma empresa nacional que atua no transporte graneleiro. Para tanto, foram desenvolvidos dois modelos de Programação Linear Inteira Mista. O modelo ECOPRVPM 1 proposto é implementado e aplicado em um exemplo disponibilizado na literatura, de forma a permitir sua validação. Em seguida, o modelo ECOPRVMP 2 é testado em um exemplo real, no contexto de transporte logístico de grãos no Centro-Oeste brasileiro. Os modelos matemáticos são resolvidos de forma exata por meio de uma ferramenta que aplica o método Branch-and-Cut. Além da ordem de visitação dos fornecedores / clientes por cada veículo, sabe-se em que trechos devem ser realizadas atividades de manutenção preventiva, respeitando-se os intervalos previamente definidos (por exemplo, estabelecidos pelo fabricante dos veículos). Ainda, as rotas encontradas minimizam o custo com emissões e atendem a restrições da jornada do condutor. Dessa maneira, os resultados computacionais obtidos para os testes realizados mostram a consistência dos modelos propostos de roteamento de veículos apresentados, que são mais abrangentes sob a perspectiva da sustentabilidade do que os tradicionalmente utilizados. / The vehicle routing problem has great importance within the logistics and supply chain, as it aims at designing optimal routes to be used by a fleet of vehicles that has to meet a set of customers at the lowest possible cost. The objective of this work is to develop and apply the vehicle routing problem with time windows involving environmental issues, preventive maintenance activities and some restrictions related to the driver's hours of service regulations (ECOPRVMP) in the context of a national company that operates in bulk transportation. Therefore, two models of Mixed-Integer Linear Programming are developed. The proposed ECOPRVPM 1 model is implemented and applied to an example provided in the literature, in order to allow its validation. Next, the ECOPRVMP 2 model is tested in a real example, in the context of logistic grain transport in the Brazilian Midwest. The mathematical models are exatly solved by means of a tool that applies the Branch-and-Cut method. In addition to the order of visitation of suppliers / customers by each vehicle, the solution provides in what parts of the route preventive maintenance activities should be carried out, respecting the intervals previously defined (for example, established by the vehicle manufacturer). Yet, the routes minimize the cost of emissions and meet constraints of the driver's hours of service regulations. Thus, the computational results obtained for the tests performed show the consistency of the proposed vehicle routing proposed models, which are more comprehensive under the perspective of sustainability than those traditionally used.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T14:13:04Z (GMT). No. of bitstreams: 1 Azevedo_BrunoLuisPiresde_M.pdf: 1384772 bytes, checksum: 48aa7ca2380aaa03fd6375cb9b35aebc (MD5) Previous issue date: 2009 / Resumo: Nesta dissertação apresentamos um algoritmo exato para o Problema de Roteamento de Veículos Capacitados com Restrições Bidimensionais. Este combina o problema de carregar um conjunto de itens bidimensionais em veículos com o problema de minimizar o custo total de transporte. Existem várias aplicações práticas para este problema, dado que em muitas situações os itens não podem ser empilhados por diversas razões. Propomos um algoritmo exato baseado em uma abordagem branch-and-cut. Sete desigualdades válidas para o Problema de Roteamento de Veículos Capacitados foram adaptadas e utilizadas. As restrições de empacotamento são garantidas através de um algoritmo exato. Também apresentamos uma nova heurística de empacotamento bidimensional. Exploramos duas variantes do problema, as versões seqüencial e irrestrita. Para ambos os casos, consideramos os itens possuirem orientação fixa. Efetuamos testes computacionais e comparamos os resultados obtidos com a abordagem exata, para o caso seqüencial, apresentada por Iori, Salazar-González e Vigo. Observamos resultados satisfatórios e nove instâncias da literatura foram resolvidas à otimalidade pela primeira vez. Como o caso irrestrito ainda não havia sido abordado de modo exato, apresentamos também as soluções de cinqüenta instâncias nunca resolvidas à otimalidade / Abstract: We present an exact algorithm for the Vehicle Routing Problem with Two-dimensional Loading Constraints. This problem combines the problems of loading vehicles with two-dimensional items and minimizing transportation costs. It has many practical applications, since in many cases items can not be stacked on top of each other. We propose an exact algorithmbased on a branch-and-cut approach. Seven valid inequalities for the the Capacitated Vehicle Routing Problems were modified and used. The packing constraints are imposed by an exact algorithm. We also present a new heuristic for two-dimensional packing. We explored two variants of the problem, the sequential and the unrestricted cases. For both variants we assume the items to have fixed orientation. We performed computational tests and compared the results with the exact approach by Iori, Salazar-González and Vigo for the sequential case. We found the results to be satisfactory and nine instances from the literature were solved to optimality for the first time. Since the unrestricted case haven't been tested so far by an exact algorithm, we also present the solutions for fifty instances never solved to optimality before / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-08T17:48:26Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Manoel S. Lima Neto.pdf: 3686104 bytes, checksum: 15c2bef691f3fab24c1edc51ffd696e8 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-08T17:48:48Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Manoel S. Lima Neto.pdf: 3686104 bytes, checksum: 15c2bef691f3fab24c1edc51ffd696e8 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-08T17:49:02Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Manoel S. Lima Neto.pdf: 3686104 bytes, checksum: 15c2bef691f3fab24c1edc51ffd696e8 (MD5) / Made available in DSpace on 2017-08-08T17:49:02Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Manoel S. Lima Neto.pdf: 3686104 bytes, checksum: 15c2bef691f3fab24c1edc51ffd696e8 (MD5) Previous issue date: 2017-03-28 / The vehicle routing problem is critical when it comes to company logistics and the administration of public resources. This work proposes a hybrid approach to solve the Vehicle Routing Problem with Time Window (VRPTW). In order to evaluate this new approach, a case study was proposed with the goal to establish the school meal delivery routes in the public school system of Manaus city, Brazil. Particularly, the optimized solution (route) should minimize the distance traveled by the delivery vehicle, taking into account both capacity and time window constraints. In addition, the proposed approach is the global-local kind and it was named global-local-g method. In the global search, the metaheuristic simulated annealing (SA) is combined with a new technique to generate neighbors, named neighbors‟ generation per quadrant. In contrast, the main purpose of the local search is the refinement of all solutions found by the global search. For this reason, the A* algorithm is combined with a new heuristic, called as heuristic of the next step. It is worth noticed that the main difference between the approach presented here to others in the literature is the local optimization. In this new approach, all solutions from the global method are optimized through local searches. In similar works, the distances between the nodes of interest (i.e., schools) are already pre-calculated in terms of the Euclidean distance between these nodes. However, in this work, the distance between the nodes is calculated at run time and it takes into account the distance from the actual streets, i.e., it considers the route distance between streets in a map. In the global search, the SA method combined with the neighbors‟ generation per quadrant produces all solutions, which are formed by a sequence of the nodes of interest. Then, using the street distances, window time restrictions, and the vehicle capacity, all node clusters are defined. Thus, within each cluster, the path traveled through local searches is optimized by the A* algorithm combined with the heuristic of the next step. Experimental results with the proposed approach presented prominent results in comparison to the other existing ones regarding run time and distance traveled. / O problema de roteamento de veículos é importante quando falamos de logística, tanto da logística de uma empresa quanto da administração dos recursos públicos. Esta dissertação propõe uma abordagem híbrida para resolver o Problema de Roteamento de Veículos com Janela de tempo (VRPTW). Para avaliar esta nova abordagem, um estudo de caso foi proposto com o objetivo de determinar as rotas de entrega de merenda escolar na rede pública de ensino da cidade de Manaus – Amazonas, Brasil. A solução otimizada deve minimizar a distância percorrida pelo veículo de entrega, atendendo as restrições de capacidade e de janela de tempo. A abordagem apresentada é do tipo global local e foi denominada de método global-local-g. Onde, na busca global utiliza-se a meta-heurística recozimento simulado com uma nova técnica de geração de vizinhos, denominada geração de vizinhos por quadrante. A busca local tem a finalidade de refinar todas as soluções encontradas pela busca global. Para isso utilizou-se o algoritmo de busca A* em conjunto com uma nova heurística, denominada heurística do passo seguinte. A grande diferença entre a abordagem apresentada e outras encontradas na literatura é que nesta nova abordagem toda a solução encontrada pelo método global é otimizada através de buscas locais. Na literatura, em trabalhos semelhantes, as distâncias entre os nodos de interesse, nesse caso as escolas, já são pré-calculadas ou expressas em termos da distância Euclidiana entre esses nodos. Na dissertação ora apresentada, os cálculos de distância entre os nodos são realizados em tempo de execução e levam em conta a distância de logradouro (distância que considera o percurso das ruas em um mapa). Na busca global, o método recozimento simulado, utilizando o método geração de vizinhos por quadrante, gera soluções formadas por uma sequência contendo os nodos de interesse. Utilizando então, a distância de logradouro e as restrições da janela de tempo e de capacidade dos veículos, são definidos agrupamentos de nodos. Em seguida, dentro de cada um dos agrupamentos, otimiza-se o percurso percorrido através de buscas locais, algoritmo A* com a heurística do passo seguinte. Os resultados obtidos são comparados com outras abordagens apresentadas no trabalho. Essas comparações levam em consideração o tempo computacional e a distância total percorrida. A abordagem desenvolvida apresentou resultados relevantes em comparação com as outras abordagens, tanto em tempo de execução, quanto em distância percorrida.

Submitted by Rosa Assis (rosa_assis@yahoo.com.br) on 2017-03-21T19:17:51Z No. of bitstreams: 2 THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2017-03-22T15:10:55Z (GMT) No. of bitstreams: 2 THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-22T15:10:55Z (GMT). No. of bitstreams: 2 THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-08-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Fundo Mackenzie de Pesquisa / Combinatorial optimization problems are widely studied in the literature. On the one hand, their challenging characteristics, such as the constraints and number of potential solutions, inspire their use to test new solution techniques. On the other hand, the practical application of these problems provides support on daily tasks of people and companies. Vehicle routing problems constitute a well-known class of combinatorial optimization problems, from which the Traveling Salesman Problem (TSP) is one of the most elementary problems. Despite its simplicity, the difficulty in finding its exact solution and its direct application in practical problems in multiple areas make it one of the most studied problems in the literature. Algorithms inspired by biological phenomena are being successfully applied to optimization problems, mainly combinatorial optimization problems. Those inspired by the collective behavior of insects produce good results for solving such problems. This work proposes the VRoptBees, a framework inspired by honeybee behavior to tackle vehicle routing problems. Together with the framework, two examples of implementation are described, one to solve the TSP and the other to solve the Capacitated Vehicle Routing Problem (CVRP). Tests were conducted with benchmark instances from the literature, on which the implementation for the TSP presented the third best results in a comparison with other bee-inspired algorithms. / Problemas de otimização combinatória são largamente estudados na literatura. De um lado, suas características desafiadoras, como o número de restrições e possíveis soluções, inspiram seu uso para testar novas técnicas de solução. Por outro lado, a aplicação prática desses problemas auxilia no dia a dia de pessoas e empresas. Os problemas de roteamento de veículos constituem uma classe muito conhecida da otimização combinatória, tendo o Problema de Caixeiro Viajante (PCV) como um dos mais elementares. Apesar de sua simplicidade, a dificuldade em encontrar uma solução exata e sua direta aplicação prática em diversas áreas o faz um dos problemas mais estudados na literatura. Algoritmos inspirados em fenômenos naturais têm sido utilizados com sucesso em problemas de otimização, principalmente de natureza combinatória. Aqueles inspirados no comportamento coletivo de insetos apresentam bons resultados para esses problemas. Nesse trabalho é proposto um framework inspirado no comportamento de abelhas para a solução de problemas de roteamento de veículos, chamado de VRoptBees. Junto ao framework, dois exemplos de implementações são propostos, um para a solução do PCV e outro para o Problema de Roteamento de Veículos Capacitados (PRVC). Testes foram feitos com instâncias de benchmark comumente utilizadas na literatura, com a implementação ao PCV apresentando o terceiro melhor resultado entre os algoritmos inspirados em abelhas.