Inventory routing under uncertainty - Rodrigues, Filipe Manuel Gonçalves (2020)
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).