91��ý

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 to maintain inventory levels within target ranges while mini-
mizing changeovers. To tackle this, we formulate a mixed-integer programming
model evaluated using Gurobi. Additionally, we develop a Greedy Randomized
Adaptive Search Procedure (GRASP) to provide a practical, non-commercial
alternative. The GRASP incorporates two specialized local search procedures: the
first achieves feasibility by reducing shortages, and the second aims to minimize
changeovers. Computational experiments on 133 real-world instances demon-
strate the merit of our approaches. The exact MIP solver proves optimality in
under 30 seconds on average. Given the same 30-second budget, GRASP achieves
a 2.42% average deviation, which is equivalent to fewer than a single additional
changeover, finding 77% of global optima. Extending the runtime to the 5-minute
company limit reduces deviation to 1.65%. Most importantly, compared to the
historical manual baseline, this approach reduces tool changeovers by nearly 50%,
resulting in estimated annual savings of $250,000 per plant.

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.

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 addresses real-
world situations in systems, such as beverage distribution, integrated order delivery,
retail merchandising, and healthcare services, where managers 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 perfor-
mance 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 known optimal solutions.