Inventory routing under uncertainty

Abstract

To survive and stand out in a market that has become more and more competitive, the companies are forced to optimize their processes to increase profits and reduce costs. Some of those processes often involve both inventory and routing decisions, making the Inventory Routing Problem (IRP) very important in operations research. Uncertainty is inherent to many IRPs and ignoring the uncertain nature of some parameters may result in poor decisions. The IRPs are, in general, complex and become even more complex when uncertain parameters are considered. To deal with the uncertainty, several approaches, such as stochastic programming and robust optimization, have been proposed in the literature. In this thesis we study several IRPs where some parameters, such as travel times and demands, are assumed uncertain. Such problems are studied from both a theoretical and a practical point of view, leading to several important contributions. Different approaches to deal with the uncertainty in the travel times in the maritime IRP are studied and compared. For the studied approaches, both exact methods and heuristic algorithms are proposed, and strategies to enhance them are discussed. The stochastic production IRP is used to test a new proposed heuristic called Adjustable Sample Average Approximation, specially designed for general two-stage stochastic problems. This heuristic uses the information of several feasible solutions to identify variables that are frequently fixed to zero or to one and gradually constructs a high quality solution based on relax-and-fix ideas. A new Lagrangian dual approach for a class of robust problems (for which the inventory problem is a particular case) is also proposed. This approach allows to relate some of the most important approaches usually used to handle robust problems and to design powerful heuristic schemes based on the interpretation of the Lagrangian multipliers. Furthermore, we also propose a new heuristic called Weighted Proximity Search, to solve a wide range of optimization problems (either deterministic or subject to uncertainty).

Para sobreviverem e se afirmarem num mercado que é cada vez mais competitivo, as empresas são forçadas a otimizar os seus processos com vista ao aumento dos lucros e à redução dos custos. Alguns desses processos envolvem frequentemente decisões associadas quer a gestão de stocks quer a roteamento de veículos, tornando assim o problema de gestão de stocks e roteamento muito importante em investigação operacional. A incerteza está associada a vários problemas de gestão de stocks e roteamento e ignorar a natureza incerta de alguns parâmetros pode resultar em fracas tomadas de decisão. Os problemas de gestão de stocks e roteamento são, em geral, complexos tornando-se ainda mais complexos quando alguns dos seus parâmetros são considerados incertos. Várias abordagens para lidar com a incerteza têm sido propostas na literatura, tais como a programação estocástica e a otimização robusta. Nesta tese estudamos vários problemas de gestão de stocks e roteamento onde alguns parâmetros, tais como os tempos de viagem e as procuras, são considerados incertos. Tais problemas são estudados de um ponto de vista teórico e prático originando várias contribuições importantes. São estudadas e comparadas diferentes abordagens para lidar com a incerteza associada aos tempos de viagem no problema de transporte marítimo. Para as abordagens estudadas são propostos métodos exatos e heurísticos, sendo também discutidas estratégias de melhoramento dos mesmos. O problema estocástico de produção, gestão de stocks e roteamento é usado para testar uma nova heurística proposta chamada Adjustable Sample Average Approximation, especialmente desenhada para problemas estocásticos com dois estados.Esta heurística usa informação recolhida de várias soluções admissíveis para identificar variáveis que são frequentemente fixadas a zero ou a um e constrói gradualmente uma solução de alta qualidade baseada em ideias the relaxamento e fixação de variáveis. Uma nova abordagem dual Lagrangiana para uma classe de problemas robustos (que incluem o problema de gestão de stocks como caso particular) é também proposta. Esta abordagem permite relacionar algumas das mais importantes abordagens usadas para lidar com problemas robustos, bem como desenhar heurísticas poderosas baseadas na interpretação dos multiplicadores Lagrangianos. Além disso, propomos também uma nova heurística chamada Weighted Proximity Search, para resolver uma vasta amplitude the problemas de otimização (quer determinísticos quer sujeitos a incerteza).