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

Alexandre M. Florio (Corresponding author), Richard F. Hartl, Stefan Minner

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

5 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)172-182
Aantal pagina's11
TijdschriftEuropean Journal of Operational Research
Volume285
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 16 aug 2020
Extern gepubliceerdJa

Vingerafdruk

Duik in de onderzoeksthema's van 'Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands'. Samen vormen ze een unieke vingerafdruk.

Citeer dit