Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands

Autor(en)
Alexandre M. Florio, Richard Hartl, Stefan Minner
Abstrakt

We present a model for the single-vehicle routing problem with stochastic demands (SVRPSD) with optimal restocking. The model is derived from a characterization of the SVRPSD as a Markov decision process (MDP) controlled by a certain class of policies, and is valid for general discrete demand probability distributions. We transform this MDP into an equivalent mixed-integer linear model, which is then used to solve small instances to optimality. By doing so, we are able to quantify the drawbacks associated with the detour-to-depot restocking policy, an assumption of many exact approaches for the (multivehicle) VRPSD. We also examine the tradeoff between the deterministic a priori cost and the stochastic restocking cost for varying route load scenarios. Finally, a wait-and-see model for the SVRPSD is proposed, and is used within a parallel heuristic to solve larger literature instances with up to 150 nodes and Poisson distributed demands. Computational experiments demonstrate the effectiveness of the heuristic approach, and also indicate under which circumstances near-optimal solutions can be obtained by the myopic strategy of a priori route cost minimization.

Organisation(en)
Institut für Business Decisions and Analytics
Externe Organisation(en)
Technische Universität München
Journal
European Journal of Operational Research
Band
285
Seiten
172-182
Anzahl der Seiten
11
ISSN
0377-2217
DOI
https://doi.org/10.1016/j.ejor.2018.10.045
Publikationsdatum
10-2018
Peer-reviewed
Ja
ÖFOS 2012
502017 Logistik
Schlagwörter
ASJC Scopus Sachgebiete
Information Systems and Management, Computer Science(all), Modelling and Simulation, Management Science and Operations Research
Link zum Portal
https://ucris.univie.ac.at/portal/de/publications/optimal-a-priori-tour-and-restocking-policy-for-the-singlevehicle-routing-problem-with-stochastic-demands(61a1c068-ef3e-4d71-b145-7c2f4f929c13).html