Solving the vehicle routing problem with stochastic demands using spiral optimization

Main Article Content

Autores

Natalia Alejandra Gelves-Tello
Ricardo Andrés Mora-Moreno
Henry Lamos-Díaz

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:

Article Details

Licence

The journal authorizes the total or partial reproduction of the published article, as long as the source, including the name of the Journal, author(s), year, volume, issue, and pages are cited.

The ideas and assertions expressed by the authors are their solely responsibility and do not represent the views and opinions of the Journal or its editors.

All articles included in the Revista Facultad de Ingeniería are published under the Creative Commons (BY) license.

Authors must complete, sign, and submit the Review and Publication Authorization Form of the manuscript provided by the Journal; this form should contain all the originality and copyright information of the manuscript.

The authors  keep copyright, however, once the work in the Journal has been published, the authors must always allude to it.

The Journal allows and invites authors to publish their work in repositories or on their website after the presentation of the number in which the work is published with the aim of generating greater dissemination of the work.

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.

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.

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.

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.

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-
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.

Downloads

Download data is not yet available.