Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

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

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T00:16:31Z (GMT). No. of bitstreams: 1 Zilli_PetersonKatagiri_M.pdf: 1307926 bytes, checksum: 5fe0ddfca7cce84d9e26b66106d61e8b (MD5) Previous issue date: 2011 / Resumo: O Problema de Roteamento de Veículos (VRP, em inglês) foi proposto por Dantzig e Ramser em 1959 e, desde então, um grande número de artigos foi dedicado à solução de suas variantes. O problema original consiste em determinar rotas otimais que serão usadas por veículos de capacidade limitada para servirem a um conjunto de clientes. Neste trabalho focamos o estudo e a implementação dos modelos chamados de "ricos" na literatura, os quais englobam variantes complexas do VRP e conseguem representar situações mais próximas dos problemas logísticos encontrados em sistemas de distribuição reais. A principal motivação para esta pesquisa é uma aplicação prática referente ao problema de roteamento dos ônibus fretados pela UNICAMP para o transporte de seus funcionários, que se caracteriza como um modelo rico. O objetivo final é a otimização de tal processo através da minimização da distância total percorrida ou do número de veículos empregados, com a consequente redução dos gastos incorridos pela Universidade. Portanto, além do seu aspecto científico, esta dissertação produz resultados com chances reais de trazer benefícios à administração de uma instituição pública de ensino. Para que isto venha a ocorrer, as heurísticas desenvolvidas foram inseridas em um sistema de informações geográficas, que será usado pela universidade no processo de criação e otimização das rotas a serem licitadas publicamente / Abstract: The Vehicle Routing Problem (VRP) was first proposed by Dantzig and Ramser in 1959 and, since then, a large number of papers has been devoted to the solution of its variants. The original problem consists in determining an optimal set of routes to be used by vehicles of limited capacity that serve a set of customers. In this paper we focus on the study and implementation of models called "rich" in the literature, which include complex variants of the VRP that represent situations closer to the logistical problems encountered in real distribution systems. The main motivation for this research is a practical problem concerning the routing of buses chartered by UNICAMP for transporting a part of its employees, which is characterized as a rich model. The goal is to optimize this process by minimizing the total travel distance or the number of vehicles used, with a consequent reduction of the expenses incurred by the University. Therefore, in addition to its scientific aspect, this dissertation gives results with real chances to benefit the administration of a public university. For this to happen, the heuristics developed were entered into a geographic information system, which will be used by the university in the process of creation and optimization of routes to be publicly auctioned / Mestrado / Pesquisa Operacional / Mestre em Ciência da Computação

Context: The Vehicle Routing Problem is an NP-hard problem with a combination of varieties oftopics like logistics, optimization research and data mining. There is a vast need of vehicle routingsolutions in day to day like with different constraints. According to the requirements, this problem hasbeen a field of interest to a lot of researchers who incorporate scientific methods to combine andinnovate new solutions to optimize the routing. Being an np-hard problem, it is almost impossible tocompute the solutions to optimality but years of research on this area has paid off quite significantlyand the solutions are optimized little by little and better than before. Some applications may or maynot find slight difference in the performance as a considerable affect but some applications orscenarios heavily depend on the performance of the solution where it is very vital that the solution isoptimized to the fullest. As a data mining technique clustering has been used very prominently in caseof portioning scenarios and similarly it has also began to surface in implementing VRP solutions.Although it has recently emerged into the Vehicle Routing era and shown some significant results, ithas not yet come into an open state or awareness. The awareness regarding clustering matters in ahuge extent to be considered by most of the recent researchers who formulate new algorithms to solveVRP and help them further optimize their solution. Objectives: In this study the significance of clustering has been considered to find out how the usageof clustering techniques can alter the performance of VRP based solutions favorably. Then to test theresults of two recently proposed cluster based algorithms, a comparison has been made to other typesof algorithms which prove how the algorithms stand with various methods. Methods: A literature review is performed using various articles that have been gathered from GoogleScholar and then an empirical experiment was conducted on the results available in the papers. Thisexperiment was done by performing a comparative analysis. Results: For the literature review the results were gathered from all the articles based on theirresearch, experience, use of clustering and how their result was improved by using clustering methodsin their formulations. Considering the experiment, the results of both the algorithm were comparedwith the results of five other papers who aim to solve the VRP using exactly the same instances thatwere used in the two algorithms in order to compare valid results on the same variables. Then theresults were analyzed for the purpose of comparison and conclusions were drawn accordingly. Conclusions: From the research performed in this paper we can conclude the vast significance ofclustering techniques that were drawn based on practical test results of various authors. From theexperiment performed it is clear that the Hybrid algorithm has a much higher performance than anyother algorithm it has been compared to. This algorithm has also been proven to enhance itsperformance due to the implementation of clustering techniques in their formulation. Since the resultswere only based on performance that is, in this case the total distance of the final route, future studyindicates the implementation of algorithms to compare them on basis of time complexity and spacecomplexity as well.

[pt] Como em toda grande empresa da indústria de óleo e gás, fortemente integrada e altamente rentável, várias são as oportunidades de buscar e encontrar processos logísticos com reais possibilidades de otimização e melhoria. Neste tipo de companhia, encontramos diversas cadeias de suprimento subjacentes ao processo, que por seu porte e complexidade, seriam consideradas principais em diversas outras indústrias ou ramos de serviços. Neste contexto, a presente dissertação se propõe a analisar as etapas e percalços para implantação e manutenção de um software de roteirização como ferramenta para planejamento de frota e rota de transporte de funcionários em regime de turno de uma refinaria. O cenário escolhido para o piloto é uma refinaria de grande porte do estado do Rio de Janeiro. O estudo revisa a bibliografia existente, descreve as principais etapas de coleta e tratamento de dados, mede através do software TRANSCAD as distâncias das rotas propostas e verifica se o potencial ganho obtido em relação à solução em análise justificaria a aquisição de uma ferramenta para este fim. / [en] As in many big oil and gas companies, there are a lot of opportunities to search and find logistics processes with real possibilities for optimization and improvement. In this kind of company there are some supply chains, that are not core chains wich could be considered as main chains in many other industries or service areas due to their size and complexity. Regarding that issue, the present work proposes to analyze the steps and problems related to launching and maintaining a routing software as a solution for vehicle fleet planning and refinery s employees transportation routing. A big refinery placed in Rio de Janeiro state is the chosen scenario. This study reviews the present literature on the theme, describes the main steps on this research and data treatment, uses the software TRANSCAD to measure de length of the proposed routes and finds out if the potential gain with the software solution justifies the acquisition of this tool.

L'étude menée dans cette thèse porte sur la logistique multi-objectif des déchets ménagers. Elle s'est déroulée en partenariat avec une collectivité locale, la Communauté d'Agglomération du Muretain (CAM) située près de Toulouse qui nous a fournit les problématiques et les différents paramètres à prendre en compte pour le développement de l'étude. Cette thèse s'est déroulée au sein de deux équipes, dans l'équipe de Production Automatisé (PA) du Laboratoire de Génie de Production (LGP) de Tarbes ainsi que dans l'équipe de Modélisation d'Optimisation et de Gestion Intégrée de Systèmes d'Activités (MOGISA) du Laboratoire d'Analyse et d'Architecture des Systèmes (LAAS) de Toulouse. Il y a une trentaine d'année, le traitement des déchets se résumait à une simple mise en décharge. Depuis une conscience collective des problématiques environnementales a placé le traitement des déchets au cœur des préoccupations publiques. La gestion qui est faite des déchets ménagers constitue un enjeu environnemental, économique, social et de citoyennetés majeures, directement lié aux modes de consommation et à la société plus généralement. En France, les municipalités ou les collectivités locales, regroupant plusieurs municipalités, ont en charge de collecter et de convoyer les déchets vers leur lieu de traitement. Dans l'étude proposée, nous allons nous intéresser à la partie logistique, et plus précisément à la collecte et au transport des déchets ménagers et assimilés jusqu’à leur point de décharge (déchetteries, centre de transfert ou centre de traitement directement). Le but étant d’optimiser le transport de déchets tout en gardant une bonne qualité de service. Les enjeux mis en relief pour cette problématique sont les enjeux classiques imposés par toute étude visant à améliorer un service publique : un enjeu économique classique (minimiser les coûts de collecte et de transport), un enjeu environnemental évident (diminuer l'impact environnemental), un enjeu de qualité (satisfaire au mieux les usagers) et enfin un enjeu social (satisfaire les conditions de travail des employés). On va donc ici se concentrer sur l’aspect opérationnel journalier de la gestion. Lorsque celui-ci concerne une planification de trajet pour plusieurs véhicules en même temps qui doivent chacun faire leur circuit en livrant une certaine quantité de produit à chaque client cela se nomme le problème de tournées de véhicules (Vehicle Routing Problem). Ce problème pratique est souvent étudié pour des cas réels et se complexifie avec l’ajout de nombreux paramètres et contraintes, comme par exemple des contraintes d'horaire de passage sur certaines parties du réseau ; ou encore par l'ajout de plusieurs critères à optimiser en mêmes temps, comme par exemple les critères représentant les coûts et ceux représentant l'équilibrage de tournées, etc. / The study in this thesis focuses on the multipurpose logistics of household waste.

This thesis is continuation of the bachelor thesis "Model of delivery routes and placement logistics centers with opportunities of their optimization". It is about distribution problems and specifically a vehicle routing problem. The aim of this thesis is finding a solution of the vehicle routing problem which will be used repeatedly in the firm. The main task is achieving the lowest costs (total kilometers) with maximum utilization of vehicle capacity; in such conditions that all requirements of logistics centers will be satisfied and maximal capacity of vehicle will be tolerated. For calculation was used a solver Gurobi 6.0.3 in system MPL for Windows 4.2, which won't, however, provide the optimal solution and problem solving takes too long time. Next for calculation was used heuristics insert method and is written by VBA (Visual Basic for Applications) in MS Excel. Finally, there is a comparison of these methods with the original solution of the vehicle routing plan and solution of the bachelor thesis. Then the computational experiment was done, which tested effect to result, if other distribution center (starting point) will be bulit. The computational experiment was consist from heuristic insert method, solver Gurobi and heuristic saving algorithm from bachelor thesis.

In this paper,we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP).The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm out performs existing solution methods for the 2E-VRP and achieves excellent results on the LRP.

The thesis focuses on how to optimize vehicle routes for distributing logistics. This vehicle route optimization is known as a vehicle routing problem (VRP). The VRP has been extended in numerous directions for instance by some variations that can be combined. One of the extension forms of VRP is a capacitated VRP with stochastics demands (CVRPSD), where the vehicle capacity limit has a non-zero probability of being violated on any route. So, a failure to satisfy the amount of demand can appear. A strategy is required for updating the routes in case of such an event. This strategy is called as recourse action in the thesis. The main objective of the research is how to design the model of CVRPSD and find the optimal solution. The EEV (Expected Effective Value) and FCM (Fuzzy C-Means) – TSP (Travelling Salesman Problem) approaches are described and used to solve CVRPSD. Results have confirmed that the EEV approach has given a better performance than FCM-TSP for solving CVRPSD in small instances. But EEV has disadvantage, that the EEV is not capable to solve big instances in an acceptable running time because of complexity of the problem. In the real situation, the FCM –TSP approach is more suitable for implementations than the EEV because the FCM – TSP can find the solution in a shorter time. The disadvantage of this algorithm is that the computational time depends on the number of customers in a cluster.