Principalmente nos centraremos en resolver un problema de optimización característico de los almacenes. En los almacenes logísticos se llevan a cabo una diversa variedad de actividades las cuales generan problemas de optimización aunque en este documento nos enfocaremos principalmente en el problema de la generación de rutas en la recogida de pedidos. Este problema en específico es estudiado en la literatura y reconocido con el nombre de OPP. El primero es aquel que se realiza una búsqueda heurística mediante A*. El segundo método empleado proviene de una investigación realizada por un estudiante de la Universidad WUZI de Beijing [1] en la cual se plantea utilizar algoritmos genéticos para dar soluciones a esta cuestión. Por último tenemos dos algoritmos de la misma familia, por una parte tenemos Basic Variable Neighborhood Search (BVNS) y General Variable Neighborhood Search (GVNS). Ambos pertenecen a la familia de algoritmos Variable Neighborhood Search (VNS) los cuales son algoritmos metaheurísticos utilizados para resolver problemas de optimización mediante métodos de búsqueda local. Para comprobar cómo se desenvuelven estos algoritmos en diferentes entornos fueron diseñados inicialmente estructuras de almacenes irregulares con dimensiones pequeñas con el fin de determinar que las rutas que se siguen son los adecuados para posteriormente utilizar almacenes con un mayor volumen de artículos que se asemejan más a reales. Por otra parte para aportar una mayor variabilidad a estos diseños se utilizan diferentes disposiciones encontradas y estudiadas en la literatura acerca de almacenes irregulares entre las cuales tenemos las distribuciones chevron, fishbone, grid o parrilla, radial entre otros.
Las soluciones de estos algoritmos se comparan mediante la distancia que debe recorrer y el tiempo que tarda cada algoritmo en llegar a una solución. Para uso de los algoritmos anteriormente mencionados se plantea en un contexto de almacenes logísticos en donde se contienen estanterías con productos diversos. Por lo tanto tendremos una serie de nodos que representan el mapa del almacén y una serie de pedidos siendo los artículos que el trabajador del almacén debe recoger coincidiendo con el nodo del almacén. Al igual que para cada problema de optimización para el OPP existe un método exacto para poder determinar la solución en instancias pequeñas. La mejor solución, nos indica una cota pues nuestros algoritmos serán capaces de dar siempre soluciones iguales o peores permitiendo servir como referencia. La problemática de estos algoritmos exactos que requieren de un mayor tiempo de cómputo y en los problemas NP-difíciles el tiempo de computo crece de forma exponencial, debido a esto surge la necesidad de encontrar soluciones que a pesar de no ser las mejores puedan ser obtenidas en un tiempo razonable que permita emplear estas soluciones en entornos reales.
En cuanto a los resultados observables el algoritmo A* devuelve soluciones muy sólidas en entornos pequeños y controlados y a pesar de no dar las mejores soluciones en mapas de grandes dimensiones entrega soluciones en apenas unos milisegundos siendo mucho más rápido que el resto. De forma complementaria GVNS presentan un mayor equilibrio con aquellas instancias grandes utilizando una mayor cantidad de recursos computaciones, causando que tarden una mayor cantidad de tiempo pero siendo el coste de devolver unos resultados respectivamente mejores.
Abstract:
We will mainly focus on solving an optimization problem characteristic of warehouses. In logistics warehouses, a diverse variety of activities are carried out, which generate optimization problems, however in this document, we will focus primarily on the problem of route generation in order picking. This specific problem is studied in the literature and is recognized under the name OPP. The first approach consists of performing a heuristic search using A*. The second method used, comes from research conducted by a student at WUZI University in Beijing [1], in which the use of genetic algorithms is proposed to provide solutions to this issue. Finally, we have two algorithms from the same family: Basic Variable Neighborhood Search (BVNS) and General Variable Neighborhood Search (GVNS). Both belong to the family of Variable Neighborhood Search (VNS) algorithms, which are metaheuristic algorithms used to solve optimization problems through local search methods. To verify how these algorithms perform in different environments, irregular warehouse structures with small dimensions were initially designed to determine that the routes followed were appropriate, and subsequently, warehouses with a larger number of items were used to better resemble real cases. Moreover, to provide greater variability to these designs, different layouts found and studied in the literature on irregular warehouses were used, among which are the chevron, fishbone, grid or mesh, and radial configurations, among others.
The solutions of these algorithms are compared based on the distance that must be traveled and the time each algorithm takes to reach a solution. The previously mentioned algorithms are applied in the context of logistics warehouses containing shelves with various products. Therefore, we will have a series of nodes representing the warehouse map and a series of orders, with the items that the warehouse worker must pick corresponding to the warehouse nodes. As with any optimization problem, for the OPP there exists an exact method to determine the solution in small instances. The best solution provides a bound, as our algorithms will always be capable of producing solutions that are equal to or worse than this one, serving as a reference. The problem with these exact algorithms is that they require greater computational time, and for NP-hard problems, the computation time grows exponentially. For this reason, it becomes necessary to seek solutions that, while not necessarily optimal, can be generated within a reasonable amount of time, making them practical and applicable in real-world scenarios.
In terms of observable results, the A* algorithm delivers very solid solutions in small and controlled environments, and although it does not provide the best solutions in large-scale maps, it produces results in just a few milliseconds, making it much faster than the others. Complementarily, GVNS presents a better balance for larger instances, using a greater amount of computational resources, which causes it to take more time, but at the cost of returning comparatively better results.
Principalmente nos centraremos en resolver un problema de optimización característico de los almacenes. En los almacenes logísticos se llevan a cabo una diversa variedad de actividades las cuales generan problemas de optimización aunque en este documento nos enfocaremos principalmente en el problema de la generación de rutas en la recogida de pedidos. Este problema en específico es estudiado en la literatura y reconocido con el nombre de OPP. El primero es aquel que se realiza una búsqueda heurística mediante A*. El segundo método empleado proviene de una investigación realizada por un estudiante de la Universidad WUZI de Beijing [1] en la cual se plantea utilizar algoritmos genéticos para dar soluciones a esta cuestión. Por último tenemos dos algoritmos de la misma familia, por una parte tenemos Basic Variable Neighborhood Search (BVNS) y General Variable Neighborhood Search (GVNS). Ambos pertenecen a la familia de algoritmos Variable Neighborhood Search (VNS) los cuales son algoritmos metaheurísticos utilizados para resolver problemas de optimización mediante métodos de búsqueda local. Para comprobar cómo se desenvuelven estos algoritmos en diferentes entornos fueron diseñados inicialmente estructuras de almacenes irregulares con dimensiones pequeñas con el fin de determinar que las rutas que se siguen son los adecuados para posteriormente utilizar almacenes con un mayor volumen de artículos que se asemejan más a reales. Por otra parte para aportar una mayor variabilidad a estos diseños se utilizan diferentes disposiciones encontradas y estudiadas en la literatura acerca de almacenes irregulares entre las cuales tenemos las distribuciones chevron, fishbone, grid o parrilla, radial entre otros.
Las soluciones de estos algoritmos se comparan mediante la distancia que debe recorrer y el tiempo que tarda cada algoritmo en llegar a una solución. Para uso de los algoritmos anteriormente mencionados se plantea en un contexto de almacenes logísticos en donde se contienen estanterías con productos diversos. Por lo tanto tendremos una serie de nodos que representan el mapa del almacén y una serie de pedidos siendo los artículos que el trabajador del almacén debe recoger coincidiendo con el nodo del almacén. Al igual que para cada problema de optimización para el OPP existe un método exacto para poder determinar la solución en instancias pequeñas. La mejor solución, nos indica una cota pues nuestros algoritmos serán capaces de dar siempre soluciones iguales o peores permitiendo servir como referencia. La problemática de estos algoritmos exactos que requieren de un mayor tiempo de cómputo y en los problemas NP-difíciles el tiempo de computo crece de forma exponencial, debido a esto surge la necesidad de encontrar soluciones que a pesar de no ser las mejores puedan ser obtenidas en un tiempo razonable que permita emplear estas soluciones en entornos reales.
En cuanto a los resultados observables el algoritmo A* devuelve soluciones muy sólidas en entornos pequeños y controlados y a pesar de no dar las mejores soluciones en mapas de grandes dimensiones entrega soluciones en apenas unos milisegundos siendo mucho más rápido que el resto. De forma complementaria GVNS presentan un mayor equilibrio con aquellas instancias grandes utilizando una mayor cantidad de recursos computaciones, causando que tarden una mayor cantidad de tiempo pero siendo el coste de devolver unos resultados respectivamente mejores.
Abstract:
We will mainly focus on solving an optimization problem characteristic of warehouses. In logistics warehouses, a diverse variety of activities are carried out, which generate optimization problems, however in this document, we will focus primarily on the problem of route generation in order picking. This specific problem is studied in the literature and is recognized under the name OPP. The first approach consists of performing a heuristic search using A*. The second method used, comes from research conducted by a student at WUZI University in Beijing [1], in which the use of genetic algorithms is proposed to provide solutions to this issue. Finally, we have two algorithms from the same family: Basic Variable Neighborhood Search (BVNS) and General Variable Neighborhood Search (GVNS). Both belong to the family of Variable Neighborhood Search (VNS) algorithms, which are metaheuristic algorithms used to solve optimization problems through local search methods. To verify how these algorithms perform in different environments, irregular warehouse structures with small dimensions were initially designed to determine that the routes followed were appropriate, and subsequently, warehouses with a larger number of items were used to better resemble real cases. Moreover, to provide greater variability to these designs, different layouts found and studied in the literature on irregular warehouses were used, among which are the chevron, fishbone, grid or mesh, and radial configurations, among others.
The solutions of these algorithms are compared based on the distance that must be traveled and the time each algorithm takes to reach a solution. The previously mentioned algorithms are applied in the context of logistics warehouses containing shelves with various products. Therefore, we will have a series of nodes representing the warehouse map and a series of orders, with the items that the warehouse worker must pick corresponding to the warehouse nodes. As with any optimization problem, for the OPP there exists an exact method to determine the solution in small instances. The best solution provides a bound, as our algorithms will always be capable of producing solutions that are equal to or worse than this one, serving as a reference. The problem with these exact algorithms is that they require greater computational time, and for NP-hard problems, the computation time grows exponentially. For this reason, it becomes necessary to seek solutions that, while not necessarily optimal, can be generated within a reasonable amount of time, making them practical and applicable in real-world scenarios.
In terms of observable results, the A* algorithm delivers very solid solutions in small and controlled environments, and although it does not provide the best solutions in large-scale maps, it produces results in just a few milliseconds, making it much faster than the others. Complementarily, GVNS presents a better balance for larger instances, using a greater amount of computational resources, which causes it to take more time, but at the cost of returning comparatively better results. Read More
Related posts:
Exploring the Integration of General Variable Neighborhood Search with Exact Procedures for the Optimization of the Order Batching Problem
Basic VNS for a Variant of the Online Order Batching Problem
¿Cómo se están reinventando los almacenes en México con soluciones tecnológicas?
Valbará se une a SISLOG para revolucionar la gestión de almacenes en el Cono Sur
Brembo y Michelin se unen para mejorar la precisión de frenado
Slotting inteligente: Cómo optimizar el diseño de almacenes para agilizar la preparación de pedidos