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.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável. / Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável. / Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

[pt] Os problemas advindos da área de logística de transportes, em especial no que diz respeito ao uso racional de frotas de veículos, são amplamente estudados na área de otimização combinatória. A natureza intrinsicamente combinatorial desses problemas sugere que boa parte deles pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos atualmente disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O sucesso desses algoritmos tem sido limitado, em parte devido ao fato dos mesmos não explorarem avanços recentes na área de programação linear inteira. Algumas dessas novas técnicas e suas aplicações a problemas de roteamento de veículos são o objeto de estudo desta dissertação. Primeiro são apresentadas as técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and- cut-and-price. Em seguida são descritos problemas de roteamento onde essa metodologia foi aplicada. Inicialmente, é apresentado o problema de roteamente do veículos com restrição de capacidade, o PRVC. Em seguida são apresentados problemas de roteamento de veículos com janela de tempo e frota heterogenea. Para cada problema, descrevemos como as técnicas descritas acima foram aplicadas e os resultados computacionais para um grande número de instâncias. Finalmente, no último capítulo, mostramos um caso real da aplicação do problema de roteamento de veículos com janela de tempo e frota heterogênea, que é o caso do problema de distribuição de jornais numa grande empresa de comunicação do Rio de Janeiro. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of several problems related to this area seggests integer programming as a natural approach to solve them. Nevertheless, there are many cases in which instances of reasonable size are still beyond the resolution capability of the algotithms presented in the literature. The sucess of the known algotithms have therefore been limited partly to the fact that most of them have not incorporated any recent relevant advances in the combinatorial optimization field. Some of these new techniques and their applications are the main subject of this dissertation. Firstly, basic decomposition techniques for linear and integer programming problems, as well as the relates column generation approach are addressed. This is followed by the presentation of a reformulation technique for linear and integer programming, which is alternative to the well known Dantzig-Wolfe master program. The new possibilities arousing from this approach are explored and the resulting consequences to the standard branch-and-bound algotithm and its variations branch-and- cut, branch-and-prince and branch-and-cut-and-price are presented. Later, routing problems where this methodology was applied were addressed with the capacitated vehicle routing problems - CVRP and followed by vehicle routing problems with time windows and heterogeneous fleet. For each problem, it is described how the techniques mentioned above were reported. Finally, in the last time windows and heterogeneous fleet, which is the case of a newspaper distribution in a major communication company in Rio de Janeiro.

O presente trabalho aborda o sistema logístico usualmente denominado Vendor Managed Inventory (VMI), no qual o fornecedor controla e coordena as decisões de reabastecimento, sendo responsável por manter os estoques de seus clientes dentro de limites fixados de antemão. O modelo proposto incorpora ainda as decisões relativas à produção e manutenção de estoque por parte do fornecedor, além da utilização de frota heterogênea na distribuição, e busca a minimização dos custos totais do sistema. Quatro heurísticas de duas etapas são propostas para a resolução do problema abordado. A primeira etapa, comum a todas as heurísticas, baseia-se em uma heurística recentemente publicada na literatura e fornece uma solução inicial viável, utilizada como ponto de partida para a etapa de melhoria subsequente, na qual é utilizada a metaheurística busca tabu ou busca em vizinhança variável. As heurísticas propostas foram avaliadas em um conjunto de teste, sendo obtidos resultados melhores que os reportados na literatura em todas as instâncias testadas. Dentre as estratégias de solução avaliadas, destaca-se a heurística baseada em busca tabu com diversificação, que demonstrou ser superior às demais heurísticas propostas. Os resultados obtidos indicam ainda que, no caso da frota disponível ser heterogênea, é vantajosa a utilização de uma adaptação do procedimento de obtenção da solução inicial, como forma de privilegiar a utilização de veículos de maior eficiência. / This thesis deals with the logistic system usually called Vendor Managed Inventory (VMI). In this system the supplier controls and coordinates the supply decisions and is responsible for keeping the inventory of each of his clients within predetermined minimum and maximum levels. Heterogeneous fleet and production/stocking decisions at the supplier are considered as well, and the proposed model seeks to minimize the total system cost. Four two-stage heuristics are proposed for this problem. The first stage consists in an adaptation of a heuristic found in the bibliography, which provides an initial viable solution that will be improved in the second stage by means of the metaheuristics tabu search or variable neighborhood search. The proposed heuristics were tested on a set of benchmark instances with improvements found on the best known results in all of the tested instances. The obtained results indicate that the tabu search based heuristic with diversification strategy is clearly superior to the other proposed heuristics and that a better fleet utilization can be obtained in the case of heterogeneous fleet by a simple improvement in the first stage, that favors the selection of more efficient vehicles.

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 trata do problema de roteirização de veículos para o abastecimento de linhas de produção, o qual pode ser entendido como uma particularização do problema clássico de roteirização de veículos (VRP Vehicle Routing Problem). Neste problema, peças estão armazenadas em um estoque central, chamado de supermercado, de onde são transferidas para pontos de uso localizados ao longo da linha de produção. O ritmo de fabricação na linha de produção é suposto constante, o que torna periódica a necessidade de reposição das embalagens com peças. Uma frota de rebocadores transporta as embalagens, dispostas sobre plataformas com rodas puxadas pelo mesmo e configurando um comboio. O objetivo do problema é roteirizar a frota de rebocadores, maximizando sua utilização e garantindo o atendimento da demanda gerada pela linha de produção. O problema é comum a muitas empresas de manufatura de bens de consumo e possui impacto direto nos custos operacionais. A literatura sobre o tema é escassa e as soluções empregadas na indústria habitualmente se baseiam na experiência prática de operadores ou responsáveis pela movimentação de materiais. Este trabalho propõe uma heurística para obtenção de uma solução para o problema, baseada em métodos de inserção. A heurística proposta foi aplicada a um caso na indústria automobilística e a comparação entre a solução obtida e aquela formulada por operadores demonstrou ganho no número de rotas. / This work studies the routing of vehicles for material delivery to assembly lines, which consists of a generalization of the classic Vehicle Routing Problem (VRP). In this problem, parts are stored in central depot called supermarket and from where they are distributed to points of use placed along the production line. Production rate in the assembly line is considered constant, which means that parts are delivered to points of use periodically. A fleet of tow cars transfers the boxes or containers of parts using wheeled towed carts. The objective of this problem is to route the fleet of the tow cars maximizing their utilization and fulfilling the assembly line demand for parts. This problem is common to several companies and has direct impacts in material handling costs. The theme is poorly explored in routing studies and many companies use operator experience to configure tow cars routes. This work proposes a heuristic based on insertion methods to find a solution for the problem. The heuristic was applied to a real problem and resulted in the reduction of the number of routes when compared to former operator solution.

O presente trabalho trata da solução para o problema da elaboração de programações de transporte do sistema de distribuição de materiais da Força Aérea Brasileira (FAB). Essas programações de transporte consistem em definir os roteiros de entrega e coleta de materiais a serem realizadas simultaneamente em cada local de entrega/coleta a partir de um centro de distribuição, considerando-se a frota de veículos homogênea. Isto é característico de um Problema de Roteirização de Veículos com Coletas e Entregas Simultâneas (PRVCES). A gestão do sistema de distribuição física da FAB considera a complexidade desse sistema e os dados relativos às demandas de transporte de carga em cada um desses locais para elaborar as programações de transporte. Essas programações são elaboradas tendo em vista os limites de capacidade dos veículos, as características físicas das cargas e as prioridades de embarque. O gestor desse sistema possui boa visibilidade das demandas de transporte, porém, devido à grande quantidade de informações disponíveis e à elevada complexidade desse sistema, é impossível elaborarem-se manualmente programações de transporte que resultem em viagens de distribuição eficientes. O PRVCES foi resolvido por meio da meta-heurística Busca Dispersa (do inglês Scatter Search) integrada com a meta-heurística Descida em Vizinhança Variável (do inglês Variable Neighborhood Descent) utilizada como método de melhoria das soluções. Os resultados superaram ou se igualaram a alguns dos obtidos por outros autores para os mesmos problemas de teste com as mesmas restrições, o que demonstra que a Busca Dispersa implementada é competitiva para solucionar o PRVCES. Quanto à aplicação na FAB, os resultados mostraram que a utilização do método de solução desenvolvido resultará em programações de transporte elaboradas em curto tempo de processamento e que estas incidirão positivamente sobre a eficiência do sistema de distribuição de materiais da FAB. / This work deals with the solution to the problem of drawing up transport schedules in the material distribution system of the Brazilian Air Force (BAF). These transport schedules consist in defining the routes for material pickup and delivery to be accomplished simultaneously in each delivery/pickup location from a distribution center, considering a homogeneous fleet of vehicles. This is characteristic of a Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP). The management of the physical distribution of BAF considers the complexity of this system and the data regarding the cargo transport demands in each one of those locations to draw up transport schedules. These schedules are drawn up regarding the capacity limits of the vehicles, the physical characteristics of the cargoes and the shipping priorities. A good visibility of transport demands in each location is available to the manager of this system, but due to the great quantity of data to deal with and the high complexity of the physical distribution system of BAF, it is impossible to draw up transport schedules that result in efficient distribution trips. The VRPSDP was solved by means of the Scatter Search meta-heuristic integrated with the Variable Neighborhood Descent meta-heuristic as the solution improvement method. The results exceeded or equaled some of those obtained by other authors using the same test problems with the same restrictions, what indicates that the implemented Scatter Search is competitive to solve the VRPSDP. As for the application in the BAF, the results showed that using the solution method developed will result in schedules drawn up in short processing time and focused on the efficiency of the material distribution system of the BAF.

Apesar de serem utilizados com sucesso em problemas de roteirização clássicos como o do caixeiro-viajante e o de roteirização de veículos com janelas de tempo, os algoritmos genéticos não apresentavam bons resultados nos problemas de roteirização de veículos sem janelas de tempo. Utilizando-se de uma tendência recente de hibridização de algoritmos genéticos, Prins (2004) elaborou um algoritmo para o problema de roteirização de veículos sem janelas de tempo, monoperíodo, e que obrigatoriamente atenda a todos os clientes cujos resultados, quando aplicado a instâncias de Christofides et al. (1979) e de Golden et al. (1998), são comparáveis aos melhores códigos elaborados com base na busca tabu. Diferentemente da maioria dos algoritmos genéticos apresentados para solução de problemas de roteirização de veículos, no método desenvolvido por Prins (2004) o cromossomo é composto apenas pelos pontos a serem atendidos, não contendo delimitadores de rotas. Estas são definidas a partir de um método de particionamento do cromossomo. Este trabalho implementa o algoritmo descrito por Prins (2004) e propõe a este melhorias em diversas de suas etapas, como inicialização, operação de crossover, operação de mutação, reinicialização e particionamento do cromossomo. As alterações implantadas são aplicadas às instâncias de Christofides et al. (1979) e comparadas com o algoritmo inicial em termos de qualidade de solução e tempo de processamento. Finalmente, é elaborado um algoritmo genético que contempla as alterações que obtiveram resultados positivos. / In the Vehicle Routing Problem (VRP) we seek for a set of minimum-cost vehicle routes for a fleet of identical vehicles, each starting and ending at a depot, such that each customer is visited exactly once and the total demand of any route does not exceed the vehicle capacity. Several families of heuristics have been proposed for the VRP. They can be broadly classified into two main classes: classical heuristics developed between 1960 and 1990, and, more recently, metaheuristics. Among them, tabu search plays an key role, being acknowledged by most authors as the most successful approach for the VRP. In the literature some successful implementations of metaheuristic Genetic Algorithm (GA) can be found for classic routing problems such as the traveling salesman and vehicle routing problems with time windows. However, until recently, the same did not apply for the VRP. In this thesis we develop a genetic algorithm without trip delimiters, and hybridized with a local search procedure, for the solving the VRP, which is based on the work of Prins (2004). At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence) by means of a splitting procedure, in which the chromosome sequence, representing a giant tour, is partitioned into feasible routes in terms of vehicle capacities. Starting with the procedure originally proposed Prins (2004), we then introduce new improvements in terms of the different components of the GA, aiming to obtain improved solutions. These include how we determine the initial population, different partitioning approaches, alternative reproduction (crossover) processes, a granular tabu mechanism similar to the one proposed by Toth and Vigo (2003 and, finally, in changes in the reinitialization process, aiming to reestablish diversity. Computational experiments are presented, based on the 14 classical Christofides instances for the VRP. The results show that the proposed improved versions of the GA allow us to obtain better solutions when compared to the original approach by Prins (2004).

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