COMPARING DYNAMIC PROGRAMMING AND SIMULATION-OPTIMIZATION APPROACHES FOR SOLVING THE SINGLE VRPSD WITH RESTOCKING

Abstract

The single Vehicle Routing Problem with Stochastic Demands (VRPSD) looks to find the best vehicle route with the minimum expected cost. This paper presents two approaches to evaluate the objective function of the VRPSD with preventive restocking using Genetic Algorithms (GA). The first approach is dynamic programming (DP) using a recursion that moves backward from the last node of the sequence. The second approach is based on a simulation model in which Monte Carlo simulation is implemented for this purpose. The presented approaches were compared in order to establish which one offers a better estimation of the objective function values. The computational results show that although the DP approach provides better estimations in terms of objective function values than Monte Carlo simulation, the second approach gives results close to the DP and with a significant reduction of the computational time with regard to DP.