Rich Vehicle and Inventory Routing Problems with Stochastic Demands

This thesis develops a unified framework for modeling and solving various classes of rich routing problems with stochastic demands, including the VRP and the IRP. The work is inspired by the problem of collecting recyclables from sensorized containers in Geneva, Switzerland. We start by modeling and solving the deterministic single-period version of the problem, which extends the class of VRPs with intermediate facilities. It is formulated as an MILP which is enhanced with several valid inequalities. Due to the rich nature of the problem, general-purpose solvers can only tackle instances of small to medium size. To solve realistic instances, we propose a meta-heuristic approach which achieves optimality on small instances, exhibits competitive performance in comparison to state-of-the-art methods, and leads to important savings in the state of practice. Moreover, it highlights and quantifies the savings from allowing open tours, in which the vehicles' origin and destination depots do not coincide. To integrate demand stochasticity, we extend the problem to an IRP over a finite planning horizon. Demand can be non-stationary and is forecast with any model that provides the expected demands and the standard deviation of the error terms, where the latter are assumed to be iid normal. The problem is modeled as an MINLP, in which the dynamic stochastic information impacts the cost through the probability of container overflows and route failures. The solution methodology is based on Adaptive Large Neighborhood Search (ALNS) which integrates a specialized forecasting model, tested and validated on real data. The computational experiments demonstrate that our ALNS exhibits excellent performance on VRP and IRP benchmarks. The case study, which uses a set of rich IRP instances from Geneva, finds strong evidence of the added value of including stochastic information in the model. Our approach performs significantly better compared to alternative deterministic policies in limiting the occurrence of overflows for the same routing cost. We also analyze the solution properties of a rolling horizon approach in terms of empirical lower and upper bounds. This approach is generalized in a unified framework for rich routing problems with stochastic demands, where we drop the assumption of iid normal error terms. We elaborate on the effects of the stochastic dimension on modeling, with a focus on stock-outs/overflows and route failures, and the cost of the associated recourse actions. Tractability is achieved through the ability to precompute or partially preprocess the bulk of the stochastic information, which is possible for a general inventory policy under mild assumptions. We propose an MINLP formulation, illustrate applications to various problem classes from the literature and practice, and demonstrate that certain problems, e.g. facility maintenance, where breakdown probabilities accumulate over the planning horizon, can be seen through the lens of inventory r