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