A general framework for routing problems with stochastic demands

Markov, Iliya (École Polytechnique Fédérale de Lausanne, Switzerland) ; Bierlaire, Michel (École Polytechnique Fédérale de Lausanne, Switzerland) ; Cordeau, Jean-François (CIRRELT, Canada ; HEC Montréal, Canada) ; Maknoon, Yousef (Delft University of Technology, The Netherlands) ; Varone, Sacha (Haute école de gestion de Genève, HES-SO // Haute Ecole Spécialisée de Suisse Occidentale)

We introduce a unified modeling and solution framework for various classes of rich vehicle and inventory routing problems as well as other probability-based routing problems with a time-horizon dimension. Demand is assumed to be stochastic and non-stationary, and is forecast using any forecasting model that provides expected demands over the planning horizon, with error terms from any empirical distribution. We discuss possible applications to various problems from the literature and practice: from health care, waste collection, and maritime inventory routing, to routing problems based on event probabilities, such as facility maintenance where the breakdown probability of a facility increases with time. We provide a detailed discussion on the effects of the stochastic dimension on modeling and the solution methodology. We develop a mixed integer non-linear model, provide examples of how it can be reduced and adapted to specific problem classes, and demonstrate that probability-based routing problems over a planning horizon can be seen through the lens of inventory routing. The optimization methodology is heuristic, based on Adaptive Large Neighborhood Search. The case study is based on waste collection and facility maintenance instances derived from real data. We analyze the cost benefits of open tours and the availability of better forecasting methodologies. We demonstrate that relaxing the distributional assumptions on the error terms and calculating probabilities using simulation information has only a minor impact on computation time. Simulating the error terms on the final solution further allows us to verify the low level of occurrence of undesirable events, such as stock-outs, overflows or breakdowns, with a moderate impact on the routing cost compared to alternative realistic policies. What is more, simulating the objective of the final solution shows that it is an excellent representation of the real cost.

Type de conférence:
full paper
Economie et Services
HEG GE Haute école de gestion de Genève
CRAG - Centre de Recherche Appliquée en Gestion
Adresse bibliogr.:
Ascona, Switzerland, 17-19 May 2017
Ascona, Switzerland
17-19 May 2017
41 p.
Titre du document hôte:
Proceedings of the 17th Swiss Transport Research Conference
Ressource(s) externe(s):
Le document apparaît dans:

 Notice créée le 2017-11-23, modifiée le 2018-02-15

Télécharger le document

Évaluer ce document:

Rate this document:
(Pas encore évalué)