Examinando por Autor "G. Pardo, Eduardo"

Mostrando 1 - 5 de 5

Efficient Iterated Greedy for the Two-Dimensional Bandwidth Minimization Problem
(Elsevier, 2022) Cavero, Sergio; G. Pardo, Eduardo; Duarte, Abraham
Graph layout problems are a family of combinatorial optimization problems that consist of finding an embedding of the vertices of an input graph into a host graph such that an objective function is optimized. Within this family of problems falls the so-called Two-Dimensional Bandwidth Minimization Problem (2DBMP). The 2DBMP aims to minimize the maximum distance between each pair of adjacent vertices of the input graph when it is embedded into a grid host graph. In this paper, we present an efficient heuristic algorithm based on the Iterated Greedy (IG) framework hybridized with a new local search strategy to tackle the 2DBMP. Particularly, we propose different designs for the main IG procedures (i.e., construction, destruction, and reconstruction) based on the trade-off between intensification and diversification. Additionally, the improvement method incorporates three advanced strategies: an efficient way to evaluate the objective function of neighbor solutions, a tiebreak criterion to deal with “flat landscapes”, and a neighborhood reduction technique. Extensive experimentation was carried out to assess the IG performance over state-of-the-art methods, emerging our approach as the most competitive algorithm. Specifically, IG finds the best solutions for all instances considered in considerably less execution time. Statistical tests corroborate the merit of our proposal.
Evaluación del rendimiento de técnicas heurísticas para el S-labeling
(2024-06-19) Robles, Marcos; Cavero, Sergio; G. Pardo, Eduardo
El problema de S-labeling es un problema de etiquetado de grafos que asigna etiquetas numéricas a los vértices de un grafo, con el objetivo de minimizar una función objetivo. Concretamente, para cada par de vértices adyacentes se anota la etiqueta más pequeña del par. Una vez que se han revisado todos los pares, la función objetivo se calcula como la suma de todas las etiquetas anotadas. En este trabajo preliminar se realiza una propuesta que utiliza la metaheurística GRASP. Concretamente, se analizan un total de cuatro métodos constructivos aleatorizados, dos de ellos tomados de la literatura y dos de esta propuesta. Como método de mejora se proponen dos búsquedas locales y el uso de VND para combinarlas. El mejor algoritmo propuesto se compara con el mejor algoritmo del estado del arte (PIG), utilizando un conjunto de instancias de referencia. Los resultados muestran que uno de los métodos constructivos presentados es capaz de obtener soluciones competitivas con una desviación baja. También se comprueba que la fase de mejora es capaz de refinar las soluciones propuestas por el constructivo, obteniendo soluciones similares a las que se consiguen utilizando el algoritmo del estado del arte. Finalmente, se discuten los puntos fuertes y débiles de esta propuesta y se sugieren algunas líneas de investigación futuras.
Un marco general para el diseño de heurísticas constructivas para problemas de embebidos de grafos
(XX Conferencia de la Asociación Española para la Inteligencia Artificial (CAEPIA 24), 2024-06-19) Cavero, Sergio; G. Pardo, Eduardo; Resende, Mauricio G. C.
Los problemas de embebido de grafos (GLP, por sus siglas en inglés, Graph Layout Problems) son una familia de problemas de optimización combinatoria que buscan asignar los vértices de un grafo de entrada a los vértices de un grafo huésped, satisfaciendo restricciones específicas y optimizando una función matemática. Debido a su complejidad computacional, se suelen utilizar algoritmos aproximados, como las heurísticas. Este artículo presenta una revisión de las heurísticas constructivas que se utilizan para generar soluciones de partida para algunos de los GLP más estudiados de la literatura. A partir de la revisión realizada, se propone un marco general para la propuesta de heurísticas constructivas para esta familia de problemas u otros problemas relacionados, así como un conjunto de posibles trabajos futuros.
Order batching problems: Taxonomy and literature review
(Elsevier, 2023) G. Pardo, Eduardo; Gil-Borrás, Sergio; Alonso-Ayuso, Antonio; Duarte, Abraham
Order Batching is a family of optimization problems related to the process of picking items in a warehouse as part of supply chain management. Problems classified into this category are those whose picking policy consists of grouping the orders received in a warehouse into batches, prior to starting the picking process. Once the batches have been formed, all items within the same batch are picked together on a single picking route. In this survey we review the optimization problems known in this family, focusing on manual picking systems and rectangular-shaped warehouses with only parallel and cross aisles, which is the most common warehouse configuration in the literature. First, we identify the decisions within the strategic, tactical, and operational levels that influence the picking task. Then, we characterize the optimization problems belonging to this family, whose objective function might differ. The identified problems are classified into a taxonomy proposed in this paper, which is designed to host future problems within this family. We also review the most outstanding papers by category and the strategies and algorithms proposed for the most relevant activities: batching, routing, sequencing, waiting, and assigning. To conclude, we outline the open issues and future paths of the topic under study.
Wordle in the Classroom: a Game-changing Approach to Active Learning
(IATED, 2024) Cavero, Sergio; G. Pardo, Eduardo; María T., González de Lena
This work presents an innovative approach to engage student participation through active learning, using the popular online word-guessing game, named Wordle. Wordle is a word-guessing game where players have six attempts to guess a five-letter word. With each guess, the letters turn the background color to indicate correctness: green for correct letters in the right position, yellow for correct letters in the wrong position, and gray for incorrect letters. Players aim to deduce the mystery word using logic and word association within the given attempts, making it both challenging and rewarding. The method proposed here involves students through the challenge of solving a set of personalized Wordle puzzles, at the end of the class, which include key concepts studied on the previous lecture. In this case, the words might have a different length. Students compete in a Wordle league, that is active during the whole semester accumulating points for each word guessed, fostering competition and motivation. The standings of the league are publicly available for all students. In addition, students are asked, at the end of the course, to create a concept map with all the keywords found, following the Unified Modeling Language (UML) standard, which is a fundamental topic of the subject. This activity aids in consolidating acquired knowledge and developing synthesis and information organization skills. The proposal was validated in the academic year 2022/2023, in the Engineering of Requirements (ER) course, which is a subject within the Software Engineering degree at Universidad Rey Juan Carlos (Madrid, Spain). The results showed a positive correlation between Wordle participation and academic performance. Furthermore, they suggested that students who actively engaged in the activity demonstrated a greater commitment to the subject and a better understanding of the key concepts. The benefits of this active learning proposal are manifold. It encourages class attendance, improves attention in class, and increases students’ motivation. It also aids in consolidating acquired knowledge and developing synthesis and information organization skills. Further research is needed to understand the impact of this strategy, but preliminary results are encouraging and suggest a promising path towards innovation in digital education.