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.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.

Este trabalho teve como objetivo a avaliação de um software comercial de roteirização de veículos. Tal software, o Delivery, se propõe a ser uma ferramenta de apoio à decisão na escolha da rotina operacional de coleta e/ou distribuição física de produtos, através da criação de roteiros alternativos, o que possibilita analisar a viabilidade de implantação da rotina operacional. A proposta original consistia em desenvolver uma metodologia para testar e avaliar a qualidade das soluções geradas pelo algoritmo deste sistema. O trabalho foi conduzido através de uma pesquisa bibliográfica dos problemas clássicos de roteirização e programação de veículos, abordando suas classificações, estratégias e técnicas de solução. Um estudo em empresas que utilizam procedimentos sistemáticos de roteirização foi realizado, com a intenção de caracterizar o cenário em que se desenvolve a atividade de distribuição física. Neste estudo foi possível identificar as características mais relevantes para sistemas comerciais de roteirização de veículos, bem como caracterizar os software utilizados pelas empresas em questão. Finalmente, realizou-se uma análise empírica comparativa entre os software Delivery e TransCAD através da aplicação de problemas testes encontrados na literatura que representam algumas classes do problema de roteirização de veículos, além da aplicação de um caso real. Resultados demonstraram que a heurística do software TransCAD apresenta melhor desempenho que a do software Delivery. / The aim of this work is to evaluate a commercial computer program for vehicle routing. The software, named Delivery, has been designed to be a decision-support tool for planning goods collection and/or distribution. Its capacity for creating several alternative routes is very useful in the analysis of possible operational schemes before their actual implementation. A methodology for testing and evaluating the quality of the solution generated by the algorithm has been applied in this work, after a comprehensive literature review of the traditional vehicle routing and scheduling problems, their classification, and solution techniques and strategies. A field study in some companies that actually use a similar tool for routing their fleets has been carried out, in order to better understand how the activity is performed in real world conditions. The most important characteristics of commercial vehicle routing systems has been also identified in the field study, as well as the software used by the studied companies. Finally, a comparative empirical analysis with the software Delivery and TransCAD has been carried out. In order to compare them, test problems available in the literature, that correspond to some of the most common vehicle routing problems, and a real case application were employed. The results have shown that the heuristic of TransCAD had a better performance than the one used in Delivery.