Submitted by Nadir Basilio (nadirsb@uninove.br) on 2018-01-24T20:35:47Z No. of bitstreams: 1 Luigi Tavolaro Santini.pdf: 2357766 bytes, checksum: b70528f7db6bf88f1285744982eb4234 (MD5) / Made available in DSpace on 2018-01-24T20:35:47Z (GMT). No. of bitstreams: 1 Luigi Tavolaro Santini.pdf: 2357766 bytes, checksum: b70528f7db6bf88f1285744982eb4234 (MD5) Previous issue date: 2017-02-23 / The present work deals with the Capacitated Vehicle Routing Problem with Three-Dimensional Loading Constraints. This problem is difficult to solve exactly, still relatively little studied, but important in the logistics activities of movement, warehousing and transportation. This problem consists in minimizing the total traveled distance by a homogeneous fleet of vehicles that address the issue of deliveries of customer demands, in which these demands are composed of items that have three relevant spatial dimensions. The objective of the present work is to develop heuristic and metaheuristic algorithms to solve the problem in question. The algorithms are based on the Clarke & Wright and George & Robinson heuristics, and on the Iterated Local Search and Adaptive Large Neighborhood Search metaheuristics. In the proposed algorithm, the routing problem is firstly addressed by adapting the Clarke & Wright heuristic, creating routes that are used to verify the loading pattern, thus obtaining an initial solution. In the following, an extensive search in the solution neighborhood is applied with the Iterated Local Search metaheuristic. For the best results of this search, it is checked if the loading pattern is feasible using an adapted George & Robinson algorithm. If it is not feasible, the Adaptive Large Neighborhood Search metaheuristic is executed in an attempt to find a feasible solution to the loading problem. Instances from the literature are used to evaluate the efficiency of the developed methods. The results obtained for the routing problem individually were of paramount importance to ensure the effectiveness of the Iterated Local Search metaheuristic. For the loading problem individually, the tests were also satisfactory, allowing for several feasible loading patterns using the adapted George & Robinson algorithm and the Adaptive Large Neighborhood Search metaheuristic. The results obtained with the proposed algorithm for the integrated problem were also good, being very close to those in the literature and with computational time relatively lower. As perspectives for future research, it is intended to investigate more efficient ways of exploring the solution space of the integrated problem, as well as the use of other metaheuristics. / O presente trabalho trata do Problema de Roteamento de Veículos Capacitado com Restrições de Carregamento Tridimensional. Este é um problema de difícil solução exata, ainda relativamente pouco estudado, porém importante nas atividades logísticas de movimentação, armazenagem e transporte de produtos. Este problema consiste em minimizar a distância total percorrida por uma frota homogênea de veículos que supram a questão das entregas das demandas de clientes, em que tais demandas são compostas por itens que possuem três dimensões espaciais relevantes. O objetivo do presente trabalho consiste em desenvolver algoritmos heurísticos e meta-heurísticos para resolver o problema em questão. Os algoritmos são baseados nas heurísticas de Clarke & Wright e de George & Robinson, e nas meta-heurísticas Iterated Local Search e Adaptive Large Neighborhood Search. No algoritmo proposto, primeiro trata-se o problema de roteamento adaptando-se a heurística de Clarke & Wright, criando roteiros que são utilizados para a verificação do padrão de carregamento, tendo-se assim uma solução inicial. Em seguida, é aplicada uma busca extensiva na vizinhança com a meta-heurística Iterated Local Search. Para os melhores resultados desta busca, verifica-se se o padrão de carregamento é viável utilizando o algoritmo de George & Robinson adaptado. Nos casos em que não é viável, a meta-heurística Adaptive Large Neighborhood Search é executada na tentativa de se encontrar soluções viáveis para o problema de carregamento. Instâncias da literatura são utilizadas para avaliar a eficiência dos métodos desenvolvidos. Os resultados obtidos para o problema de roteamento separadamente foram de suma importância para assegurar a eficiência do meta-heurística Iterated Local Search. Para o problema de carregamento separadamente, os testes utilizando o algoritmo de George & Robinson adaptado e a meta-heurística Adaptive Large Neighborhood Search também foram satisfatórios, permitindo a obtenção de vários padrões de carregamento factíveis. Os resultados obtidos com o algoritmo proposto para o problema integrado também foram bons, sendo bastante próximos aos da literatura e com tempo computacional relativamente menor. Como perspectivas de pesquisas futuras, pretende-se estudar formas mais eficientes de se explorar o espaço de busca do problema integrado, bem como a utilização de outras meta-heurísticas.

Made available in DSpace on 2016-06-02T19:50:20Z (GMT). No. of bitstreams: 1 5182.pdf: 6075915 bytes, checksum: 91596b4ab6b9108e05799c5f3c87831d (MD5) Previous issue date: 2013-05-17 / Financiadora de Estudos e Projetos / The object of this study are combined problems of the Vehicle Routing Problem and the Container Loading Problem, recently addressed as Integrated Vehicle Routing and Loading Problems. In these problems, the objective is to optimize simultaneously the planning of the vehicles routes and the arrangement of the cargo inside them, while considering a series of practical constraints from both vehicle routing and container loading. The objectives of this study are: (i) to study the integration between the Vehicle Routing Problem and the Container Loading Problem; (ii) to develop mathematical programming models to represent Integrated Vehicle Routing and Loading Problems; (iii) to develop and implement heuristics and metaheuristics to solve some of these problems; (iv) to analyze and compare the performance of the proposed models, by means of modeling languages and optimization solvers, as well as the heuristic methods, when solving instances from the literature and real-world situations. Besides being hard and relatively less studied problems, the main reason for this study is that with effective solution methods for optimizing the vehicle routing and the cargo loading, operational and tactical decisions could be made with more reliability, accuracy, quickness and with less uncertainty in real situations, besides of an improved use of the staff tasked to load and unload the cargo. On the other hand, these methods can also be usefull to reduce fixed and variable costs in a company that might use them. Computational experiments with some of the proposed models were performed with an optimization software and randomly generated instances. The results show that the models are consistent and properly represent the practical situations treated, although this approach (in its current version) is limited to solve to optimality only problems of moderate size, that is, situations with few customers, few vehicles, and mainly with a relatively reduced number of possible positions to load the boxes. This has motivated the development of heuristic and metaheuristic methods to solve more realistic vehicle routing and loading problems. The algorithms are based on the combination of classical heuristics from both the vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. Computational experiments were performed with these methods considering instances based on the vehicle routing literature and actual customers orders, as well as instances based on a real-world situation where the problem occurs. / O objeto de estudo deste trabalho são problemas combinados do Problema de Roteamento de Veículos com o Problema de Carregamento de Contêineres, tratados mais recentemente na literatura como Problemas Integrados de Roteamento e Carregamento de Veículos. Nestes problemas, genericamente, busca-se otimizar simultaneamente o planejamento dos roteiros dos veículos e o arranjo da carga dentro dos mesmos, respeitando-se uma série de considerações práticas que advêm tanto do Problema de Roteamento de Veículos como do Problema de Carregamento de Contêineres. Os objetivos deste trabalho são: (i) estudar a integração do Problema de Roteamento de Veículos com o Problema de Carregamento de Contêineres; (ii) desenvolver modelos de programação matemática para representar Problemas Integrados de Roteamento e Carregamento de Veículos; (iii) desenvolver e implementar métodos heurísticos e meta-heurísticos para resolver alguns destes problemas; (iv) analisar e comparar o desempenho da solução dos modelos, via linguagens de modelagem e aplicativos de otimização, e dos métodos heurísticos desenvolvidos ao resolver exemplos baseados na literatura e em situações reais em que este problema ocorre. Além de serem problemas difíceis e relativamente pouco estudados, a principal justificativa para o estudo destes problemas é que, com métodos de solução eficazes para a otimização do roteamento dos veículos e do carregamento das cargas, decisões operacionais e táticas podem ser tomadas com maior segurança, acurácia, rapidez e menor incerteza em situações reais, além de possibilitar um melhor desempenho do pessoal encarregado da montagem e descarregamento da carga. Por outro lado, estes métodos também podem ser úteis na redução de custos fixos e variáveis de uma empresa que venha a utilizá-los. Experimentos computacionais com alguns dos modelos propostos foram realizados utilizando um aplicativo de otimização e aplicados a exemplos gerados aleatoriamente. Estes resultados mostram que os modelos são coerentes e representam adequadamente as situações tratadas, embora esta abordagem (na sua versão atual) esteja limitada a resolver otimamente apenas problemas de tamanho bem moderado, isto é, em que haja poucos clientes, poucos veículos, e que o número de possíveis posições para se arranjar as caixas dentro de cada veículo seja relativamente pequeno. Isso motivou o desenvolvimento de métodos heurísticos e meta-heurísticos para resolver problemas mais realistas de roteamento e carregamento de veículos. Os algoritmos são baseados na combinação de heurísticas clássicas das literaturas de Roteamento de Veículos e de Carregamento de Contêineres, bem como em duas estratégias meta-heurísticas, e no uso delas em procedimentos mais elaborados. Embora não haja garantias de que as soluções obtidas para os respectivos problemas sejam ótimas, tratam-se de heurísticas relativamente simples, suficientemente rápidas para resolver problemas reais, razoavelmente flexíveis para incorporar aspectos práticos, e que normalmente garantem soluções relativamente boas em tempos computacionais aceitáveis na prática. Experimentos computacionais foram realizados com estes métodos considerando exemplos baseados na literatura de Roteamento de Veículos e em pedidos reais de cargas, bem como exemplos baseados em um caso real em que o problema ocorre.

L’objectif de cette thèse est de développer un cadre méthodologique pour les problèmes de tournées de véhicules riches (RVRPs). Nous présentons d’abord une taxonomie et une définition élaborée des RVRPs basée sur une analyse typologique réalisée en fonction de deux critères discriminatoires. Dans cette thèse, nous nous intéressons à la résolution du problème de tournées de véhicules multi-dépôt multi-compartiment multi-produits avec fenêtres de temps (MDMCMCm-VRPTW). Nous proposons une heuristique de génération de colonnes unifiée qui inclut une matheuristique de type VNS. La matheuristique combine plusieurs heuristiques de routage de type destruction et insertion ainsi que des procédures efficaces de contrôle de réalisabilité des contraintes afin de résoudre le MDMCMCm-VRPTW pour un seul véhicule. Deux voisinages de chargement, basés sur la résolution de programmes mathématiques sont proposées. Des études expérimentales approfondies sont conduites sur un ensemble de 191 instances pour des VRPs moins complexes. Les expérimentations valident la compétitivité de la matheuristique unifiée. Une analyse de sensibilité révèle l’importance de certains choix algorithmiques et des voisinages de chargement pour parvenir à des solutions de très bonne qualité. La matheuristique basée sur la méthode de VNS est intégrée dans l’heuristique de génération de colonnes pour résoudre le MDMCMCm-VRPTW. Nous proposons une méthode exacte de post-traitement capable d’optimiser l’affectation des clients aux tournées de véhicules. Enfin, nous résolvons un RVRP qui survient dans le processus de collecte de l’huile d’olive en Tunisie à l’aide d’un algorithme exact de type branch-and-cut / The purpose of this thesis is to develop a solution framework for Rich Vehicle Routing Problems (RVRPs). We first provide a comprehensive survey of the RVRP literature as well as a taxonomy. Selected papers addressing various variants are classified according to the proposed taxonomy. A cluster analysis based on two discriminating criteria is performed and leads to define RVRPs. In this thesis we are interested in solving a multi-depot multi-compartment multi-commodity vehicle routing problem with time windows (MDMCMCm-VRPTW). We propose a unified column generation heuristic cooperating with a variable neighborhood search (VNS) matheuristic. The VNS combines several removal and insertion routing heuristics as well as computationally efficient constraint checking. Two loading neighborhoods based on the solution of mathematical programs are proposed to intensify the search. On a set of 191 instances of less complex routing problems, the unified matheuristic turns to be competitive. A sensitivity analysis, performed on more complex generated instances reveals the importance of some algorithmic features and of loading neighborhoods for reaching high quality solutions. The VNS based matheuristic is embedded in a column generation heuristic to solve the MDMCMCm-VRPTW. We propose an exact post-processing method to optimize the assignment ofcustomers to vehicle routes. Last, we introduce, model and solve to optimality a RVRP arising in the olive oil collection process in Tunisia. We propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios