In this dissertation, two main topics are explored, the vehicle routing problem (VRP) and model reference adaptive control (MRAC) for unknown nonlinear systems. The VRP and its extension, the split delivery VRP (SVRP), are analyzed to determine the effects of using two different objective functions, the total cost objective, and the last delivery objective. A worst-case analysis suggests that using the SVRP can improve total costs by as much as a factor of 2 and the last delivery by a factor that scales with the number of vehicles over the classical VRP. To test the theoretical worst-cases against the solutions of benchmark datasets, a heuristic is developed based on embedding a random variable neighborhood search within an iterative local search heuristic. Results suggest that the split deliveries do in fact improve total cost and last delivery times over the classical formulation. The SVRP has been developed classically for use with vehicles such as trucks which have large payload capacities and typically long ranges for deliveries, but are limited to traversing on roads. Unmanned aerial vehicles (UAVs) are useful for their high maneuverability, but suffer from limited capacity for payloads and short ranges. The classical SVRP formulation is extended to one more suitable for UAVs by accounting for limited range, limited payloads, and the ability to swap batteries at known locations. Instead of Euclidean distances, path plans which are adjusted for a known, constant wind underlie the cost matrix of the optimization problem. The effects of payload on the vehicle's range are developed using propeller momentum theory, and simulations verify that the proposed approach could be used in a realistic scenario. Two novel MRAC laws are then developed. The first, MRAC laws for prescribed performance, exploits barrier Lyapunov functions and a 2-Layer approach to guarantee user-defined performance. This control law allows unknown nonlinear systems to verify a user-defined rate of convergence of the tracking error while verifying apriori control and tracking error constraints. Numerical simulations are performed on the roll dynamics of a delta-wing aircraft. The second novel MRAC law is MRAC for switched dynamical systems which is proven in two different mathematical frameworks. Applying the Caratheodory framework, it is proven that if the switching signal has an arbitrarily small, but non-zero, dwell-time, then solutions of both the trajectory tracking error's and the adaptive gains' dynamics exist, are unique, and are defined almost everywhere, and the trajectory tracking error converges asymptotically to zero. Employing the Filippov framework, it is proven that if the switching signal is Lebesgue integrable and has countably many points of discontinuity, then maximal solutions of both the trajectory tracking error and the adaptive gains dynamics exist and are defined almost everywhere, and the trajectory tracking error converges to zero asymptotically. The proposed MRAC law is experimentally verified in the case where a UAV with tilting propellers is tasked with mounting an unknown camera onto a wall. The previous results are then combined into a novel application in construction. A method for using a UAV to measure autonomously the moisture of an exterior precast concrete envelope is developed which can provide data feedback through contact-based measurements to improve safety and real-time data acquisition through the integration with the Building Information Model (BIM). To plan the path of the vehicle, the path planning and SVRP for UAV approaches developed in previous chapters are utilized. To enable the UAS to contact surfaces, a switched MRAC law is employed to control the vehicle throughout and guarantee successful measurements. A full physics-based simulation environment is developed, and the proposed framework is used to simulate taking multiple measurements. / Doctor of Philosophy / The main goal of this dissertation is to provide an implementable approach to the routing and control problem for unmanned aerial vehicles (UAVs) tasked with delivering payloads or taking images or videos of known locations. To plan routes for the fleet of vehicles, a split vehicle routing (SVRP) approach is utilized. UAVs are useful for their high maneuverability, but suffer from limited capacity for payloads and short ranges. Before extending the SVRP to a formulation more suitable for UAVs, we study the effects of using two different objective functions on the solutions to the optimization problem through a worst-case analysis. Namely, we study the minimum total cost function and the minimum last delivery function and their effects on both the classical vehicle routing problem (VRP), where only one vehicle can visit each customer, and the SVRP, where multiple vehicles can visit each customer. A custom heuristic is developed to solve several benchmark instances, and the results suggest that using the SVRP can save in total cost and last delivery over the VRP when using the same objective functions. The classical SVRP formulation is then extended to one more suitable for UAVs by accounting for limited range, limited payloads, and the ability to swap batteries at known locations. Instead of using straight line approaches to traversing between locations, a path planning approach is utilized and wind is accounted for. The effects of payload on the vehicle's range are also considered, and simulations verify that the proposed approach could be used in a realistic scenario. After developing a routing approach for UAVs, the control problem is considered. The first control approach developed is for unknown nonlinear systems which necessitate control and tracking error constraints that can be set before the start of the mission. This result is achieved using a novel model reference adaptive control (MRAC) approach. In addition to verifying the constraints, a drawback of classical MRAC approaches, the poor performance in the transient stages, is addressed by providing the ability to guarantee a user-defined rate of convergence of the system. Numerical simulations are performed on the roll dynamics of a delta-wing aircraft. A second MRAC approach is then developed for the cases in which the UAVs may be tasked with installing a payload at the customer location. An approach is used where the vehicles are considered to have different flight states, one where the vehicle is in free flight, and one where the vehicle contacts the wall. These types of systems are denoted as switched dynamical systems, and an adaptive control law is developed for unknown nonlinear switched plants that must follow the trajectory of user-defined linear switched reference models. The proposed MRAC law is experimentally verified in the case where a UAV with tilting propellers is tasked with mounting an unknown camera onto a wall. Finally, we seek to combine the new routing and control approach into an application to improve safety within a construction site. A method for using a UAV to measure autonomously the moisture of an exterior precast concrete envelope is developed which can provide data feedback through contact-based measurements to improve safety and real-time data acquisition through the integration with the Building Information Model (BIM). To plan the path of the vehicle, the path planning and SVRP for UAV approaches developed in previous chapters are utilized. To enable the UAS to contact surfaces, a switched MRAC law is employed to control the vehicle throughout and guarantee successful measurements. A full physics-based simulation environment is developed, and the proposed framework is used to simulate taking multiple measurements.

This dissertation focuses on supply chain design and logistics problems with emphasis on biomass logistics and routing problems. In biomass logistics, we have studied problems arising in a switchgrass-based bio-ethanol supply chain encountered in the Southeast, and a corn stover harvest scheduling problem faced in the Midwest Unites States, both pertaining to the production of cellulosic ethanol. The main contributions of our work have been in introducing new problems to the literature that lie at the interface of the lot-sizing and routing problems, and in developing effective exact algorithms for their solution. In the routing area, we have addressed extensions of the well-known traveling salesman and vehicle routing problems. We have proposed new formulations and have developed exact algorithms for the single and multiple asymmetric traveling salesmen problems (ATSP and mATP), the high-multiplicity asymmetric traveling salesman problem (HMATSP) and its extensions, and the fixed-destination multi-depot traveling salesman problem with load balancing (FD-MTSPB). Furthermore, we have introduced a new strategy to reduce routing cost in the classical vehicle routing problem (VRP). / Ph. D.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

[pt] O problema de roteamento de veículos escolares, do inglês School Bus Routing Problem (SBRP), trata de planejar as rotas de uma frota de veículos para locomover os alunos dos pontos de embarque até suas respectivas escolas. O SBRP é um caso especial do problema de roteamento de veículos, do inglês Vehicle Routing Problem (VRP) e é conhecido por ser um problema NP-difícil. A maior parte da literatura referente ao SBRP se concentra, principalmente, em modelos matemáticos para resolver o problema de roteamento aplicando restrições da vida real. Já em relação à geocodificação dos endereços das escolas e alunos, bem como a busca de distâncias e tempos de deslocamentos reais, estas também são pontos de vital importância, visto que as distâncias reais se diferem da euclidiana e geodésica principalmente em áreas rurais, região de estudo deste trabalho. Neste contexto, uma metodologia é proposta para o problema, junto com um protótipo para automatizar os procedimentos necessários para à obtenção de informações, cuja a aplicação, a partir de um cenário real no contexto brasileiro, é apresentada e dividida em oito fases: definir abrangência, geocodificar o endereço de escolas, alunos e pontos de embarque, definir as características, calcular a distância e o tempo de percurso, montar o banco de dados georreferenciado e de veículos, aplicar uma ferramenta para a obtenção das rotas, geoespacilizar as rotas e elaborar diagnóstico. A proposta é testada aplicando uma ferramenta para a obtenção das rotas que utiliza a meta-heurística Adaptative Large Neighborhood Search (ALNS) para resolver instâncias do VRP. Desta forma, uma das contribuições do estudo consiste no georreferenciamento das unidades escolares estaduais, estando as informações presentes na plataforma do Google Maps para visualização do público. No estudo são localizados e roteados 150 alunos de 7 unidades escolares da cidade de Nova Friburgo. O resultado apresenta valores consistentes e satisfatórios, demonstrando economia média de 41,62 por cento nos custos praticados nas rotas. / [en] The School Bus Routing Problem (SBRP) deals with planning the routes of a fleet of vehicles to move the students from boarding points to their respective schools. The SBRP is a special case of Vehicle Routing Problem (VRP) and is known to be an NP-hard problem. Most of the SBRP literature focuses, mainly, on mathematical models to solve the routing problem by applying real-life restrictions. Regarding the geocoding of the addresses of schools and students, as well as the search for distances and times of real displacements, are also points of vital importance, since the actual distances differ from the euclidean and geodesic ones mainly in rural areas, study region this work. In this context, a methodology is proposed for the problem, along with a prototype to automate the procedures required to obtain information, whose application, based on a real scenario in the Brazilian context is presented, divided into eight phases: to define scope, to geocode the address of schools, student and boarding points, to define the characteristics, to calculate the distance and travel time, to set the georeferenced database and vehicles, to apply a tool to obtain the routes, to geospatialize the routes and elaborate diagnosis. The proposal is tested by applying a tool to obtain routes using the Adaptive Large Neighborhood Search (ALNS) meta-heuristic to solve VRP instances. Thus, one of the contributions of the study consists in the georeferencing of the state school units, with the information present in the Google Maps platform for public viewing. In the study, 150 students from 7 school units in the city of Nova Friburgo were located. The result presents consistent and satisfactory values, demonstrating savings of 41.62 percent in the costs practiced on th routes.

Die zweiphasige Stichprobe zur Stratifizierung ist ein effizientes Inventurverfahren, das seine Praxistauglichkeit in verschiedenen Waldinventuren unter Beweis stellen konnte. Dennoch sind weitere Effizienzsteigerungen wünschenswert. In der vorliegenden Arbeit werden verschiedene Ansätze die Effektivität dieses Verfahrens zu steigern separat vorgestellt, in Fallstudien mit Daten der Niedersächsischen Betriebsinventur getestet und diskutiert. Der erste Ansatz (Kapitel 2) beschäftigt sich mit der Anwendung der zweiphasigen Stichprobe zur Stratifizierung in Wiederholungsinventuren. In einem Zusammengesetzten Schätzer werden Daten eines aktuellen mit Simulationsergebnissen des vorhergehenden Inventurdurchgangs kombiniert. Dabei kann der Stichprobenumfang der aktuellen Inventur verringert werden, während die Daten aller Inventurpunkte des vorherigen Durchgangs für Simulationen genutzt werden. Zwar kann ein solcher Schätzer konstruiert werden, jedoch lässt die Fallstudie darauf schließen, dass keine, oder zumindest keine ausreichende, Effizienzsteigerung erzielt werden kann. Erklärt werden kann dies durch die großen Unterschiede zwischen den aktuellen Inventurergebnissen aus den reduzierten Inventuren und den prognostizierten Volumina aus den Simulationen. Eine Erhöhung der Effizienz dieses Verfahrens könnte nur durch Weiterentwicklungen der Waldwachstumsmodelle möglich werden. In Wiederholungsinventuren kann jedoch eine höhere Effizienzsteigerung mit einem dreiphasigen Verfahren erreicht werden, das die zweiphasige Stichprobe mit der zwei\-phasigen Regressionsstichprobe kombiniert (Kapitel 3). Mittelwert- und Varianzschätzer, die auf dem sogenannten infinite population approach in der ersten Phase beruhen, werden präsentiert. Genutzt werden dabei die Korrelationen zwischen den aktuellen Inventurergebnissen und den Wachstumssimulationen auf der Basis des vorherigen Inventurdurchgangs. Statt der Simulationsergebnisse können auch einfach die Ergebnisse des vorherigen Inventurdurchgangs zur Berechnung der Korrelationen genutzt werden. Allerdings führt die Nutzung der Simulationsergebnisse als Regressor in den meisten Fällen zu besseren Ergebnissen. Bei verringertem Stichprobenumfang der Folgeinventur und damit einhergehendem Präzisionsverlust, ist die Effizienz des dreiphasigen Verfahrens höher als die des klassischen zweiphasigen Verfahrens. Die Nutzung der Vorinventur in Form eines stratenweisen Regressionsschätzers hat sich damit als erfolgreich und gegenüber dem zusammengesetzten Schätzer als deutlich überlegen gezeigt. Als weiterer Ansatz wird die Erweiterung der zweisphasigen Stichprobe zur Stratifizierung um eine geclusterte Unterstichprobe zu einem dreiphasigen Design vorgestellt (Kapitel 4). Sowohl für den Ratio-to-Size- als auch für den unverzerrten Ansatz werden entsprechende Mittelwert- und Varianzschätzer präsentiert. Verglichen mit dem zweiphasigen Verfahren, führt dieses dreiphasige Design in der Fallstudie zu keiner Effizienzsteigerung. Gründe hierfür können in der vergleichsweise kleinen Größe der Forstämter und der hohen Stichprobendichte der Niedersächsischen Betriebsinventur gesehen werden. Sinnvolle Anwendungen dieses Verfahrens sind aber möglicherweise unter anderen Erschließungsbedingungen in Großgebieten denkbar. In einer weiteren Fallstudie wird versucht existierende Probepunkte in Clustern von homogener Größe zusammenzufassen (Kapitel 5). Eine solche Zusammenfassung soll der Optimierung der Wegzeiten bei der Aufnahme von Inventurpunkten dienen. Dazu werden sieben verschiedene Methoden getestet und deren Ergebnisse miteinander verglichen. Durch einen Vergleich mit optimierten Richtwert-Lösungen wird zudem die Qualität dieser Lösungen evaluiert. Es zeigt sich, dass drei Algorithmen des Vehicle Routing Problems gut dazu geeignet sind, Cluster von homogener Größe zu erstellen. Nicht empfohlen werden kann dagegen die Verwendung von drei anderen Cluster-Algorithmen, sowie die Nutzung von Bewirtschaftungseinheiten als Cluster, da diese Methoden zu Clustern von sehr heterogener Größe führen.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Nous considérons dans cette thèse un problème d’ordonnancement de flow-shop de permutation où un ensemble de travaux doit être ordonnancé sur un ensemble de machines. Les travaux doivent être ordonnancés sur les machines dans le même ordre. L’objectif est de minimiser le retard total. Nous proposons des algorithmes heuristiques et des nouvelles matheuristiques pour ce problème. Les matheuristiques sont un nouveau type d’algorithmes approchés qui ont été proposés pour résoudre des problèmes d’optimisation combinatoire. Les méthodes importent de la résolution exacte au sein des approches (méta) heuristiques. Ce type de méthode de résolution a reçu un grand intérêt en raison de leurs très bonnes performances pour résoudre des problèmes difficiles. Nous présentons d’abord les concepts de base d’un problème d’ordonnancement. Nous donnons aussi une brève introduction à la théorie de l’ordonnancement et nous présentons un panel de méthodes de résolution. Enfin, nous considérons un problème où un flow shop de permutation à m-machine et un problème de tournées de véhicules sont intégrés, avec pour objectif la minimisation de la somme des retards. Nous proposons un codage direct d’une solution et une méthode de voisinage. Les résultats montrent que l’algorithme Tabou améliore grandement la solution initiale donnée par EDD et où chaque voyage ne délivre qu’un travail. / We consider in this thesis a permutation flow shop scheduling problem where a set of jobs have to be scheduled on a set of machines. The jobs have to be processed on the machines in the same order. The objective is to minimize the total tardiness. We propose heuristic algorithms and many new matheuristic algorithms for this problem. The matheuristic methods are a new type of approximated algorithms that have been proposed for solving combinatorial optimization problems. These methods embed exact resolution into (meta)heuristic approaches. This type of resolution method has received a great interest because of their very good performances for solving some difficult problems. We present the basic concepts and components of a scheduling problem and the aspects related to these components. We also give a brief introduction to the theory of scheduling and present an overview of resolution methods. Finally, we consider a problem where m-machine permutation flow shop scheduling problem and a vehicle routing problem are integrated and the objective is to minimize the total tardiness. We introduce a direct coding for a complete solution and a Tabu search for finding a sequence and trips. The results show that the TS greatly improves the initial solution given by EDD heuristic where each trip serves only one job at a time.

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.

Optimization of relief networks in humanitarian logistics often exemplifies the need for solutions that are feasible given a hard constraint on time. For instance, the distribution of medical countermeasures immediately following a biological disaster event must be completed within a short time-frame. When these supplies are not distributed within the maximum time allowed, the severity of the disaster is quickly exacerbated. Therefore emergency response plans that fail to facilitate the transportation of these supplies in the time allowed are simply not acceptable. As a result, all optimization solutions that fail to satisfy this criterion would be deemed infeasible. This creates a conflict with the priority optimization objective in most variants of the generic vehicle routing problem (VRP). Instead of efficiently maximizing usage of vehicle resources available to construct a feasible solution, these variants ordinarily prioritize the construction of a minimum cost set of vehicle routes. Research presented in this dissertation focuses on the design and analysis of efficient computational methods for optimizing high-consequence variants of the VRP for relief networks. The conflict between prioritizing the minimization of the number of vehicles required or the minimization of total travel time is demonstrated. The optimization of the time and capacity constraints in the context of minimizing the required vehicles are independently examined. An efficient meta-heuristic algorithm based on a continuous spatial partitioning scheme is presented for constructing a minimized set of vehicle routes in practical instances of the VRP that include critically high-cost penalties. Multiple optimization priority strategies that extend this algorithm are examined and compared in a large-scale bio-emergency case study. The algorithms designed from this research are implemented and integrated into an existing computational framework that is currently used by public health officials. These computational tools enhance an emergency response planner's ability to derive a set of vehicle routes specifically optimized for the delivery of resources to dispensing facilities in the event of a bio-emergency.

Dedicating less transport resources by grouping goods to be shipped together, or pooling as we name it, has a very crucial role in saving costs in transport networks. Nonetheless, it is not so easy to estimate pooling among different groups of shipments or understand why these groups are poolable. The typical solution would be to consider all shipments of both groups as one and use some Vehicle Routing Problem (VRP) software to estimate costs of the new combined group. However, this brings with it some drawbacks, such as high computational costs and no pooling explainability. On this work we build a tool that estimates the different types of pooling using demand data. This solution includes mapping shipment data to a lower dimension, where each poolability trait corresponds to a latent dimension. We tested different dimensionality reduction techniques and found that the best performing are the autoencoder models based on neural networks. Nevertheless, comparing shipments on the latent space turns out to be more challenging than expected, because distances in these latent dimensions are sometimes uncorrelated to the distances in the real shipment features. Although this limits the use cases of this approach, we still manage to build the full poolability tool that incorporates the autoencoders and uses metrics we designed to measure each poolability trait. This tool is then compared to a VRP software and proves to have close accuracy, while being much faster and explainable. / Att optimera transportresurser genom att gruppera varor som ska skickas tillsammans, även kallat poolning, spelar en avgörande roll för att spara kostnader i transportnätverk. Trots detta är det inte så enkelt att uppskatta poolning mellan olika grupper av försändelser eller förstå varför dessa grupper kan poolas. Den vanliga lösningen skulle vara att betrakta alla försändelser från båda grupperna som en enda enhet och använda mjukvara för att lösa problemet med fordonsschemaläggning (Vehicle Routing Problem, VRP) för att uppskatta kostnaderna för den nya sammanslagna gruppen. Detta medför dock vissa nackdelar, såsom höga beräkningskostnader och bristande förklarbarhet när det kommer till poolning. I detta arbete bygger vi ett verktyg som med hjälp av efterfrågedata uppskattar olika typer av poolning. Lösningen innefattar kartläggning av försändelsedata till en lägre dimension där varje egenskap för poolbarhet motsvarar en dold dimension. Vi testade olika tekniker för att minska dimensionerna och fann att de bäst presterande är autoencoder-modeller baserade på neurala nätverk. Trots detta visade det sig vara mer utmanande än förväntat att jämföra försändelser i det dolda rummet eftersom avstånden i dessa dolda dimensioner ibland inte korrelerar med avstånden i de faktiska försändelseegenskaperna. Trots att detta begränsar användningsområdena för denna metod lyckades vi ändå bygga ett komplett verktyg för poolbarhet som inkluderar autoencoders och använder metriker som vi har utformat för att mäta varje egenskap för poolbarhet. Detta verktyg jämförs sedan med en VRP-mjukvara och visar sig ha liknande noggrannhet samtidigt som det är betydligt snabbare och mer förklarligt. / Dedicare meno risorse di trasporto raggruppando insieme le merci da spedire, o creando un pool come lo chiamiamo noi, svolge un ruolo cruciale nel risparmio dei costi nelle reti di trasporto. Tuttavia, non è facile stimare il grado di aggregazione tra diversi gruppi di spedizioni o comprendere perché tali gruppi siano aggregabili. La soluzione tipica consisterebbe nel considerare tutte le spedizioni di entrambi i gruppi come una sola entità e utilizzare un software di Problema di Routing dei Veicoli (VRP) per stimare i costi del nuovo gruppo combinato. Tuttavia, ciò comporta alcuni svantaggi, come elevati costi computazionali e la mancanza di spiegazioni riguardo all'aggregazione. In questo lavoro abbiamo sviluppato uno strumento che stima i diversi tipi di aggregabilità utilizzando i dati di domanda. Questa soluzione prevede la mappatura dei dati delle spedizioni in una dimensione inferiore, in cui ciascuna caratteristica di aggregabilità corrisponde a una dimensione. Abbiamo testato diverse tecniche di riduzione dimensionale e abbiamo constatato che i modelli autoencoder basati su reti neurali sono i più efficaci. Tuttavia, confrontare le spedizioni nello spazio latente si è rivelato più complesso del previsto, poiché le distanze in queste dimensioni latenti talvolta non sono correlate alle distanze nelle caratteristiche reali delle spedizioni. Sebbene ciò limiti le applicazioni di questo approccio, siamo comunque riusciti a sviluppare uno strumento completo per l'aggregabilità che incorpora gli autoencoder e utilizza metriche da noi progettate per misurare ciascuna caratteristica di aggregabilità. Successivamente, abbiamo confrontato questo strumento con un software VRP e dimostrato che presenta un'accuratezza simile, pur essendo più veloce e fornendo spiegazioni chiare.