Solving the vehicle routing problem with stochastic demands using spiral optimization
Abstract
This paper presents a research work that studied a Vehicle Routing Problem with Stochastic Demands (VRPSD), in which the customer demand is the unique stochastic variable. Moreover, this variable follows a discrete distribution, and its value is only known when the vehicle arrives to the customer location.
To solve this problem, we implemented the metaheuristic called Spiral Optimization, with an apriority approach and the preventing restocking strategy by only one vehicle.
In order to improve that methodology, the Nearest Neighbor heuristic methodology was used, and later the Mutation, an evolutionary operator to widen the search points’ exploration zone.
Besides, the mutation and exchange 2-Opt (a local search heuristic) were applied for enhancing algorithm search strategies of diversification and intensification, respectively.
On the other hand, it was carried out a design of experiments 23, in order to determine the effect of each input parameter on the objective function. The eight different instances used for this DOE, were designed and developed by Galván et al. [1].
The final solutions obtained were compared with the ones obtained using the hybrid algorithm EPSO for proving the efficacy and efficiency of the developed method. The comparison showed that the proposed method, obtains better solutions in all instances and improvements of up to 5,71 %.
Keywords
metaheuristics, spiral optimization, stochastic demands, vehicle routing
References
- S. Galván, J. Arias and H. Lamos, “Optimización por simulación basado en un sistema evolutivo de optimización de enjambre de partículas para el problema de ruteo de vehículos con demandas estocásticas”. Tesis de Maestría. Universidad Industrial de Santander, Bucaramanga, Colombia. 2013.
- R. H. Ballou, Logística. Administración de la cadena de suministro. México: Prentice Hall, 2004.
- J. Sourabh and K. Sarabjit, “Comparative analysis of two different heuristics for model of VRP”, Advances in Computing and Communication Engineering (ICACCE), Dehradun (India), pp. 124-127, May. 2015. DOI: http://dx.doi.org/10.1109/ICACCE.2015.87. DOI: https://doi.org/10.1109/ICACCE.2015.87
- J. M. Daza, J. R. Montoya and F. Narducci, “Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases”, Revista EIA, n° 12, pp. 23-38. Dec. 2009.
- N. Secomandi, “A rollout policy for the vehicle routing problem with stochastic demands”, Operations Research, vol. 49 (5), pp. 796-802, Oct. 2001. DOI: http://dx.doi.org/10.1287/opre.49.5.796.10608. DOI: https://doi.org/10.1287/opre.49.5.796.10608
- M. Dror, G. Laporte and P. Trudeau, “Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks”, Transportation Science, vol. 23 (3), Aug. 1989. DOI: http://dx.doi.org/10.1287/trsc.23.3.166. DOI: https://doi.org/10.1287/trsc.23.3.166
- K. Tamura and K. Yasuda, “Spiral Optimization. A new multipoint search method”, Systems, Man, and Cybernetics (SMC), Anchorage (Alaska), pp. 1759-1764, Oct. 2011. DOI: http://dx.doi.org/ 10.1109/ICSMC.2011.6083926. DOI: https://doi.org/10.1109/ICSMC.2011.6083926
- S. Geetha, G. Poonthalir and P. T. Vanathi, “A Hybrid Particle Swarm Optimization with Genetic Operators for Vehicle Routing Problem”, Journal of Advances in Information Technology, vol. 1 (4), pp. 181–188, Nov. 2010. DOI: http://dx.doi.org/10.4304/jait.1.4.181- DOI: https://doi.org/10.4304/jait.1.4.181-188
- B. Liu, L. Wang and Y. Jin, “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers”, Computers & Operations Research, vol. 35 (9), pp. 2791-2806, Sep. 2008. DOI: http://dx.doi.org/10.1016/j.cor.2006.12.013. DOI: https://doi.org/10.1016/j.cor.2006.12.013