Solving the vehicle routing problem with stochastic demands using spiral optimization
DOI:
https://doi.org/10.19053/01211129.4626Keywords:
metaheuristics, spiral optimization, stochastic demands, vehicle routingAbstract
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 %.
Downloads
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-
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.
Published
How to Cite
Issue
Section
License
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 who publish in this Journal accept the following conditions:
a. The authors retain the copyright and transfer the right of the first publication to the journal, with the work registered under the Creative Commons attribution license, which allows third parties to use what is published as long as they mention the authorship of the work and the first publication in this Journal.
b. Authors can make other independent and additional contractual agreements for the non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly indicate that the work It was first published in this Journal.
c. Authors are allowed and recommended to publish their work on the Internet (for example on institutional or personal pages) before and during the process.
review and publication, as it can lead to productive exchanges and a greater and faster dissemination of published work.
d. The Journal authorizes the total or partial reproduction of the content of the publication, as long as the source is cited, that is, the name of the Journal, name of the author (s), year, volume, publication number and pages of the article.
e. The ideas and statements issued by the authors are their responsibility and in no case bind the Journal.
