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.

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.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Jessica L. Heier Stamm / The main goal of public health emergency preparedness efforts is to mitigate the impact of events on the health of the population. However, decision-makers must also remain conscientious of the costs associated with these efforts. Planning is further complicated by uncertainty about the location and volume of demand that will need to be met in an emergency, the speed with which demand must be met, and the potential scarcity of needed items once an emergency occurs. To address these challenges, public health emergency planners often keep inventory stockpiles that are distributed when an event happens. Managing these stockpiles is a difficult task, and inefficient stockpile location and equipment distribution strategies can be costly both in terms of cost and public health impact. This research is motivated by challenges faced by state public health departments in creating stockpile location and equipment distribution strategies. The primary emphasis is on facemasks and respirators used by health workers during an influenza pandemic, but the approach is generalizable to other scenarios. The model proposed here uses a two-stage approach to generate a holistic solution to the problem. The first stage uses a pull distribution strategy to make stockpile location decisions. Additionally, it determines how counties should be assigned to stockpiles to minimize both storage and distribution costs. The second stage adopts a push distribution strategy to determine optimal delivery routes based on the county assignments made in stage one. This stage offers guidance for public health planners who have made location-allocation decisions but who then face a different distribution scenario than what was anticipated in the original planning phase. Recourse methods for managing demand uncertainty are also proposed. A case study of the state of Kansas is conducted using the methods introduced in the thesis. The computational results yield several significant insights into the tradeoffs and costs of various facility location-allocation and vehicle routing decisions: • For the tested range of storage and distribution cost parameters, multiple stockpile locations are preferred over a single location. • In a pull distribution system, storage costs play a greater role in location-allocation decisions than distribution costs. • In the push distribution system, finding an optimal vehicle routing plan is computationally intensive for stockpiles with a large number of assigned counties. • Efficient heuristics perform well to design recourse routing plans when realized demand is greater than expected. • In the event that planners wish to specify routes well in advance, the results of this research suggest adopting a robust routing plan based on higher-than-expected demand levels. This thesis makes three important contributions. The first is an optimization approach that considers multiple distribution strategies. This is especially relevant when stockpiling for an influenza pandemic where stockpiles need to be located significantly before the material is needed, during which time the distribution strategy may change. Second, the case study demonstrates that the proposed methods are applicable to a large-scale problem arising in practice. Finally, this research illustrates for decision-makers the tradeoffs between different stockpile management strategies and between optimal and heuristic methods.

Crew pairing and vehicle routing are combinatorial optimization problems that have been studied for many years by researchers worldwide. The aim of this research work is to investigate effective methods for solving large scale crew pairing problems and vehicle routing problems. In the airline industry, to address the complex nature of crew pairing problems, we propose a duty tree method followed by a primal-dual subproblem simplex method. The duty tree approach captures the constraints that apply to crew pairings and generate candidate pairings taking advantage of various proposed strategies. A huge number of legal pairings are stored in the duty tree and can be enumerated. A set partitioning formulation is then constructed, and the problem is solved using a primal-dual subproblem simplex method tailored to the duty tree approach. Computational experiments are conducted to show the effectiveness of the methods. We also present our efforts addressing the capacitated vehicle routing problem (CVRP) that is the basic version of many other variants of the problem. We do not attempt to solve the CVRP instances that have been solved to optimality. Instead, we focus on investigating good solutions for large CVRP instances, with particular emphasis on those benchmark problems from the public online library that have not yet been solved to optimality by other researchers and determine whether we can find new best-known solutions. In this research, we propose a route network that can store a huge number of routes with all routes being legal, a set partitioning formulation that can handle many columns, and the primal-dual subproblem simplex method to find a solution. The computational results show that our proposed methods can achieve better solutions than the existing best-known solutions for some difficult instances. Upon convergence of the primal-dual subproblem simplex method on the giant-tour based networks, we use the near optimal primal and dual solution as well as solve the elementary shortest path problem with resource constraints to achieve the linear programming relaxation global optimal solution.

This thesis deals with real logistic problem of the Heineken CZ Company. The company sets down an itinerary for each vehicle to distribute its goods to particular customers on daily basis. These itineraries are created manually, only with the skill of experienced driver. The goal of this thesis is to find a solution with an algorithm, which will be able to set optimal itineraries of all vehicles, so the total distance and therefore operating costs are minimized, with only the knowledge of distances between each two nodes.

Split delivery vehicle rating problem is one of the most studied combinatorial optimization problems in operations research. According to the mathematical difficultness, there should be many problems to find the optimal solution. Therefore, there are many exact algorithms and heuristics, which tries to find the best solution in the short period of time. The theoretical part of this thesis describes the basic facts of the split delivery vehicle routing problem and its heuristics. The practical part focuses on the practical usage of the split delivery vehicle routing problem. The main goals of this thesis are the practical usage of this vehicle routing problem and assistance in strategic decision establishing of the secondary store.

[pt] Nesta tese são propostos diversos algoritmos para resolver as versões estática e dinâmica de roteirização de veículos com janelas de tempo. Estes problemas têm como objetivo determinar rotas de custo mínimo para uma frota homogênea, atendendo a demanda de um conjunto de clientes dentro de intervalos de tempo determinados, chamados de janelas de tempos. Além disto, na versão dinâmica no problema, novos clientes podem ser atendidos durante a execução das rotas pelos veículos. Para a versão estática do problema propôs-se um algoritmo híbrido utilizando otimização por colônias de formigas e o método de descida em vizinhança variável aleatória. Os resultados computacionais mostram que o algoritmo foi capaz de encontrar soluções muito boas ou mesmo as melhores soluções conhecidas de instâncias usadas como benchmarking na literatura. Para a versão dinâmica do problema foram propostos seis algoritmos, baseados em métodos de inserção, de otimização por colônia de formigas e das versões sequencial e aleatória do método de busca em vizinhança variável. Os resultados computacionais mostram que a maior parte dos algoritmos propostos é competitiva com os algoritmos propostos na literatura, pois produzem soluções de boa qualidade e com esforço computacional reduzido. / [en] This thesis proposes several algorithms to solve the vehicle routing with time windows static and dynamic versions. These problems involve determining minimum cost routes for a homogeneous fleet in order to meet the demand of a set of customers within specified time intervals popularly called time windows. In addition, in the dynamic version of the problem, new customers can be assigned to vehicles during the execution of the routes. For the static version it was proposed a hybrid algorithm using ant colony optimization and the random variable neighborhood search method. The computational results show that the algorithm was able to find very good or even the best known solutions to benchmark instances. For the dynamic version it was proposed six algorithms, based on an insertion procedure, ant colony optimization and random and sequential versions of variable neighborhood search methods. Computational results show that most of the proposed algorithms are competitive regarding the state of the art, providing solutions of good quality with low computational effort.

Este trabalho aborda um problema ainda não explorado na literatura denominado 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), que compreende resolver simultaneamente o roteamento e carregamento tridimensional de veículos considerando frota heterogênea e janela de tempo. Foi desenvolvido um algoritmo específico para resolver o problema, denominado 3DC. Neste algoritmo foram introduzidas algumas inovações, entre elas, um novo operador de busca local (k-IntensiveSwap) e uma nova heurística de carregamento de contêiner. O algoritmo foi comparado aos melhores resultados disponíveis na literatura para problemas particulares ao apresentado. Houve bom desempenho no caso do CLP (container loading problem), bom resultado na redução do tamanho de frota no caso do 3L-VRP (threedimensional loading vehicle routing problem) e desempenho superior ao problema mais complexo estudado, o 3L-VRPTW (three-dimensional loading vehicle routing problem with time windows). Finalmente, apresentou-se um conjunto de avaliação, instâncias e soluções, para o problema completo com frota heterogênea e janela de tempo. / This work presents a problem not treated yet on the literature referenced as 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), which deals simultaneously with vehicle routing and its three-dimensional loading considering heterogeneous fleet and time windows. The algorithm developed for the specific problem is called 3DC. This algorithm introduces a new local search operator called k-IntensiveSwap and a new container loading heuristic. The results are compared with the best-known results from literature for particular problems embeeded on the general problem presented. The quality of solution was good in comparison other methods for CLP (container loading problem), it has good results in terms of reduction fleet sizing in the case of 3L-VRP (three-dimensional loading vehicle routing problem) and as for 3L-VRPTW (threedimensional loading vehicle routing problem with time windows) the performance was very superior. Finally, it is presented a solution set as benchmark for future comparison with the general problem, with heterogeneous fleet.

O objetivo deste trabalho é apresentar os conceitos da logística, em especial a logística de serviços, e algumas de suas ferramentas, como a roteirização de veículos e previsão de demanda por serviços, aplicadas aos serviços urbanos, neste caso o serviço de remendos em pavimentos, visando aumentar a eficiência desse serviço. O serviço de remendos, muitas vezes chamado de tapa-buracos, é uma atividade de manutenção comum nas cidades. Para observar a aplicação das ferramentas foi elaborado um estudo de caso na cidade de São Carlos. Dados sobre o serviço de remendos em pavimentos foram coletados e, com a ajuda de um sistema de informações geográficas – SIG, foram gerados roteiros que foram comparados com os dados originais. As rotas simuladas pelo SIG foram mais eficientes do que as praticadas na realidade, mostrando a utilidade dos conceitos da logística e também a utilidade do SIG na gerência da infra-estrutura urbana. A previsão de demanda por serviços de remendos não pôde ser observada devido à falta de dados históricos, fundamentais a essa etapa do trabalho. / The objective of this work is to introduce the concepts of logistics, especially the service logistics and some of its tools as the vehicle routing and the demand forecast for services, applied to the urban services, in this case the patching service in pavements in order to increase the efficiency of this service. The patching service, many times called tapa-buracos (in Brazil), is a common activity of maintenance in the cities. To observe the application of the tools one case study was elaborated in the city of São Carlos. Data about the patching service in pavements were collected and, helped by the geographic information system – GIS, routes were created and compared to the original data. The paths simulated by the GIS were more efficient than the real ones, showing the utility of the logistics concepts and also the utility of the GIS on the management of the urban infrastructure. The demand forecast for services of patching could not be observed due of the lack of historical data, essential to this part of the work.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.