Using Safety Stocks and Simulation to Solve the Vehicle Routing Problem with Stochastic Demands

Abstract

After introducing the Vehicle Routing Problem with Stochastic Demands (VRPSD) and some related work, this paper proposes a flexible solution methodology. The logic behind this methodology is to transform the issue of solving a given VRPSD instance into an issue of solving a small set of Capacitated Vehicle Routing Problem (CVRP) instances. Thus, our approach takes advantage of the fact that extremely efficient metaheuristics for the CVRP already exists. The CVRP instances are obtained from the original VRPSD instance by assigning different values to the level of safety stocks that routed vehicles must employ to deal with unexpected demands. The methodology also makes use of Monte Carlo simulation (MCS) to obtain estimates of the reliability of each aprioristic solution - that is, the probability that no vehicle runs out of load before completing its delivering route - as well as for the expected costs associated with corrective routing actions (recourse actions) after a vehicle runs out of load before completing its route. This way, estimates for expected total costs of different routing alternatives are obtained. Finally, an extensive numerical experiment is included in the paper with the purpose of analyzing the efficiency of the described methodology under different uncertainty scenarios.

Department(s)

Engineering Management and Systems Engineering

Sponsor(s)

IN3-UOC Knowledge Community Program
NVIDIA Corporation
Navarre and Catalan Governments

Keywords and Phrases

Hybrid Algorithms; Metaheuristics; Monte Carlo Simulation; Reliability Indices; Vehicle Routing Problem with Stochastic Demands

International Standard Serial Number (ISSN)

0968-090X

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2011 Elsevier, All rights reserved.

Publication Date

01 Aug 2011

Link to Full Text

Share

 
COinS