����

A. R. Uguina, A. Martínez-Gavara, and M. Laguna

We introduce the 𝑘-Group 𝑝-Dispersion Problem ((𝑘, 𝑝)-GDP) as a new mathematical model that extends the well-studied 𝑝-dispersion problem (𝑝-DP). The proposed model forms 𝑘 teams, each comprising 𝑝 diverse individuals, such that the minimum pairwise diversity within each group is maximized. This problem has practical applications in workforce management, consulting, and interdisciplinary research teams, where diversity is essential for decision-making and creative problem-solving. Given the NP-hard nature of the problem, we develop an advanced solution methodology that integrates heuristic and exact approaches. We formulate the (𝑘, 𝑝)-GDP as an integer programming problem and adapt three linear formulations of the 𝑝-DP. Additionally, we propose a step-by-step formulation inspired by existing exact methods to improve computational efficiency. Furthermore, we introduce a novel matheuristic based on the Biased Greedy Randomized Adaptive Search Procedure (B-GRASP) combined with a mathematical combination method (MCM). Through extensive computational experiments, we evaluate the performance of our proposed methods, analyze the structural properties of the solutions, and compare them to the traditional 𝑝-dispersion problem. Our findings demonstrate the effectiveness of the proposed approach in generating high-quality diverse teams, providing valuable insights for both theoretical research and practical applications.

S. Cavero, I. Lozano-Osorio, and M. Laguna

We address a production scheduling problem arising in the seat manufacturing auto industry, characterized by multiple racetracks and a wide variety of car models. The challenge is to determine the optimal sequence of molds to mount on each racetrack in order to maintain inventory levels within target ranges while minimizing the number of changeovers. To tackle this problem, we formulate a mixed-integer programming model and evaluate its computational performance using Gurobi. In addition, we develop heuristic algorithms based on the Greedy Randomized Adaptive Search Procedure (GRASP) to provide a non-commercial solver that serves as a practical alternative, while the exact model serves as a benchmark to assess solution quality. The proposed GRASP approach incorporates two specialized local search procedures: the first focuses on achieving feasibility by reducing shortages, and the second, once feasibility is reached, aims to minimize changeovers. Computational experiments on 107 instances with two racetracks show that the metaheuristic achieves an average deviation of 3.44% compared to the mathematical model, obtaining 52 optimal solutions. For 27 instances with three racetracks, the average deviation is 2.15%, with 23 optimal solutions found. This research contributes to improving production processes in automotive manufacturing and offers insights into the application of advanced optimization techniques to real-world scheduling challenges.

M. Laguna, R. Martí, and S. Cavero

Scatter search (SS) is a population-based metaheuristic designed to solve complex optimization problems through structured solution combination and adaptive memory. Unlike traditional evolutionary algorithms, SS emphasizes deterministic strategies to balance intensification and diversification. We present a comprehensive review of SS and its connection to Path Relinking (PR), covering their historical development, core methodology, and applications. Key components of SS include diversification generation, improvement, reference set updating, subset generation, and solution combination. Advanced strategies such as dynamic reference set updating, tiered memory structures, constructive and destructive neighborhoods, and vocabulary building enhance its performance and scalability. SS has been successfully applied in scheduling, routing, bioinformatics, and software engineering. Hybridizations with other metaheuristics and integration with machine learning further expand its applicability. The review concludes with a tutorial on a scatter search Python implementation for 0-1 knapsack problems that includes a Jupyter Notebook  with code, execution traces, visualizations, and didactic analyses.

Variable neighborhood search with path relinking for the periodic vehicle routing problem with driver consistency
R. Martí, A. Martínez-Gavara, M. Benito-Marimon, and M. Laguna 

The Periodic Vehicle Routing Problem (PVRP) and its variants, extend the well-known Capacitated Vehicle Routing Problem (CVRP) by adding characteristics of real scenarios in the logistic sector. In the PVRP, delivery routes are planned over multiple days, and each customer has to be served on certain days according to pre-specified visit combinations. The goal is to find the minimum cost routes satisfying customer requirements. We address a challenging extension of the PVRP in which each client must be served by the same vehicle (driver) in multiple visits during the planning horizon (driver consistency). The same-driver requirement models real-world situations in industries, such as small package shipping or dual delivery systems, where companies seek to foster driver-customer relationships and maintain service quality. We propose several heuristics for the Periodic Capacitated Vehicle Routing Problem with Driver Consistency (PVRP-DC) based on the Variable Neighborhood Search methodology, and test their performance on a set of instances for which high-quality solutions, including optimal values, have been identified. Additionally, we propose a Path Relinking post-processing for improved outcomes.  Our experimental testing shows the effectiveness of our heuristics compared with a recently published method as well as with the optimal solutions known.