Michel Bierlaire, Mohammad Yousef Maknoon, Iliya Dimitrov Markov, Sacha Varone
We solve a rich logistical problem inspired from practice, in which a heterogeneous fixed fleet of vehicles is used for collecting recyclable waste from large containers over a finite planning horizon. Each container is equipped with a sensor, which communicates its level at the start of the day. Given a history of observations, a forecasting model is used to estimate the point demand forecasts as well as a forecasting error representing the level of uncertainty. The problem falls under the framework of the stochastic inventory routing problem. We introduce dynamic probabilistic information in the solution process, which impacts the cost through the probability of container overflows on future days and the probability of route failures. We cast the problem as a mixed integer non-linear program and, to solve it, we implement an adaptive large neighborhood search algorithm, which integrates a specialized forecasting model, tested and validated on real data. Computational testing demonstrates that our algorithm performs very well on inventory routing and vehicle routing benchmarks from the literature. We are able to evaluate the benefit of including uncertainty in the objective function on rich IRP instances derived from real data coming from the canton of Geneva, Switzerland. Our approach performs significantly better compared to alternative policies in its ability to limit the occurrence of container overflows for the same routing cost. We also analyze the solution properties of a rolling horizon approach and derive empirical lower and upper bounds.
2016
