Solving the vehicle routing problem with stochastic demands using spiral optimization
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 lo...
| Main Authors: | , , |
|---|---|
| Format: | Online |
| Language: | spa |
| Published: |
Universidad Pedagógica y Tecnológica de Colombia
2016
|
| Subjects: | |
| Online Access: | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/4626 |
| _version_ | 1801706073046908928 |
|---|---|
| author | Gelves-Tello, Natalia Alejandra Mora-Moreno, Ricardo Andrés Lamos-Díaz, Henry |
| author_facet | Gelves-Tello, Natalia Alejandra Mora-Moreno, Ricardo Andrés Lamos-Díaz, Henry |
| author_sort | Gelves-Tello, Natalia Alejandra |
| collection | OJS |
| description | 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 %. |
| format | Online |
| id | oai:oai.revistas.uptc.edu.co:article-4626 |
| institution | Revista Facultad de Ingeniería |
| language | spa |
| publishDate | 2016 |
| publisher | Universidad Pedagógica y Tecnológica de Colombia |
| record_format | ojs |
| spelling | oai:oai.revistas.uptc.edu.co:article-46262022-06-15T16:22:53Z Solving the vehicle routing problem with stochastic demands using spiral optimization Solución del problema de ruteo de vehículos con demandas estocásticas mediante la optimización por espiral Gelves-Tello, Natalia Alejandra Mora-Moreno, Ricardo Andrés Lamos-Díaz, Henry metaheuristics spiral optimization stochastic demands vehicle routing demandas estocásticas metaheurísticas optimización por espiral ruteo de vehículos 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 %. El artículo presenta los resultados del estudio de un problema de ruteo de vehículos con demandas estocásticas (Vehicle Routing Problem with Stochastic Demands, VRPSD), en el cual la única variable estocástica es la demanda de los clientes, esta variable sigue una distribución discreta, y su valor solo es conocido cuando el vehículo llega a la ubicación del cliente. Para su solución, se implementó la metaheurística denominada Optimización por Espiral, con el enfoque a priori y la estrategia de reabastecimiento preventivo para un solo vehículo. Para mejorar el método se inicializaron las rutas mediante la heurística del vecino más cercano, y posteriormente se utilizó la mutación, un operador evolutivo, para ampliar la zona de exploración de los puntos de búsqueda. Adicionalmente, se utilizó el intercambio 2-Opt, una heurística de búsqueda local, con el fin de intensificar la búsqueda en la vecindad de soluciones óptimas encontradas. Por otra parte, se realizó un diseño de experimentos 23, con el fin de determinar la influencia de cada factor en la función objetivo. Este análisis se llevó a cabo en 8 instancias diferentes que fueron diseñadas y desarrolladas por Galván et al. [1]. Finalmente, se compararon los resultados obtenidos con los arrojados por el algoritmo híbrido EPSO, con el objetivo de probar la eficiencia y eficacia del algoritmo desarrollado. Esta comparación evidenció que el método propuesto obtiene mejores resultados en todas las instancias, con mejoras de hasta el 5,71 %. Universidad Pedagógica y Tecnológica de Colombia 2016-05-03 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion investigation investigación application/pdf text/html https://revistas.uptc.edu.co/index.php/ingenieria/article/view/4626 10.19053/01211129.4626 Revista Facultad de Ingeniería; Vol. 25 No. 42 (2016); 7-19 Revista Facultad de Ingeniería; Vol. 25 Núm. 42 (2016); 7-19 2357-5328 0121-1129 spa https://revistas.uptc.edu.co/index.php/ingenieria/article/view/4626/3807 https://revistas.uptc.edu.co/index.php/ingenieria/article/view/4626/5048 |
| spellingShingle | metaheuristics spiral optimization stochastic demands vehicle routing demandas estocásticas metaheurísticas optimización por espiral ruteo de vehículos Gelves-Tello, Natalia Alejandra Mora-Moreno, Ricardo Andrés Lamos-Díaz, Henry Solving the vehicle routing problem with stochastic demands using spiral optimization |
| title | Solving the vehicle routing problem with stochastic demands using spiral optimization |
| title_alt | Solución del problema de ruteo de vehículos con demandas estocásticas mediante la optimización por espiral |
| title_full | Solving the vehicle routing problem with stochastic demands using spiral optimization |
| title_fullStr | Solving the vehicle routing problem with stochastic demands using spiral optimization |
| title_full_unstemmed | Solving the vehicle routing problem with stochastic demands using spiral optimization |
| title_short | Solving the vehicle routing problem with stochastic demands using spiral optimization |
| title_sort | solving the vehicle routing problem with stochastic demands using spiral optimization |
| topic | metaheuristics spiral optimization stochastic demands vehicle routing demandas estocásticas metaheurísticas optimización por espiral ruteo de vehículos |
| topic_facet | metaheuristics spiral optimization stochastic demands vehicle routing demandas estocásticas metaheurísticas optimización por espiral ruteo de vehículos |
| url | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/4626 |
| work_keys_str_mv | AT gelvestellonataliaalejandra solvingthevehicleroutingproblemwithstochasticdemandsusingspiraloptimization AT moramorenoricardoandres solvingthevehicleroutingproblemwithstochasticdemandsusingspiraloptimization AT lamosdiazhenry solvingthevehicleroutingproblemwithstochasticdemandsusingspiraloptimization AT gelvestellonataliaalejandra soluciondelproblemaderuteodevehiculoscondemandasestocasticasmediantelaoptimizacionporespiral AT moramorenoricardoandres soluciondelproblemaderuteodevehiculoscondemandasestocasticasmediantelaoptimizacionporespiral AT lamosdiazhenry soluciondelproblemaderuteodevehiculoscondemandasestocasticasmediantelaoptimizacionporespiral |
