Robust Inventory Routing for Collection of Recyclable Materials
Responsable(s) :
Iliya Markov, Yousef Maknoon, Michel Bierlaire
Description :
We consider the logistical problem of 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 solve it using an Adaptive Large Neighborhood Search (ALNS) algorithm implemented in Java. We see the benefit of including uncertainty in the objective function on rich inventory routing 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 (Markov et al., 2016). The purpose of this project is to redefine the current model, which captures the probability of container overflows and route failures only in the objective function, in terms of a robust optimization problem (Bertsimas and Sim, 2003; 2004). The benefit of such a formulation is that it is distribution-independent, i.e. the uncertainty of the demands is represented only by bounds around the point forecasts. The reformulation will be implemented in the ALNS algorithm, tested on the same instances and compared to the model with the probabilistic objective function. ** Bertsimas, D. and Sim, M. (2003) Robust discrete optimization and network flows. Mathematical Programming, 98:49-71 ** Bertsimas, D. and Sim, M. (2004) The Price of Robustness. Operations Research, 52(1):35-53 ** Markov, I., Bierlaire, M., Cordeau, J.-F., Maknoon, Y., and Sacha (2016). Inventory routing with non-stationary stochastic demands. Technical Report TRANSP-OR 160825, Ecole Polytechnique Federale de Lausanne, Switzerland. http://transp-or.epfl.ch/documents/technicalReports/Markov_TechreportWP5.pdf
Collaboration with:
Type :
masters project, semester project
Pré-requis :
strong mathematics background, constrained optimization, experience with Java
Submitted on :
December 19, 2016