DOI: http://dx.doi.org/10.26507/rei.v9n17.318

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

Silvia Adriana Galván Núñez, Carlos Eduardo Díaz Bohórquez, Henry Lamos Díaz

Resumen


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.


Palabras clave


VRPSD; Dynamic Programming; Monte Carlo simulation; Genetic Algorithms

Texto completo:

PDF (English)





Asociación Colombiana de Facultades de Ingeniería. ACOFI.
Carrera 68 D 25B – 86 Oficina 205
Teléfono: (57 4) 425 50 68 - (57 1) 427 30 65 Extensión 103
Bogotá, Colombia. Suramérica

Email: revista@acofi.edu.co
http://www.educacioneningenieria.org

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.