�鶹��Ѱ�����

Variable neighborhood search with path relinking for the periodic vehicle routing problem with driver consistency
R. Martí, A. Martínez-Gavara, M. Benit-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.

Scatter search: foundations and implementations
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 uses deterministic strategies to balance intensification and diversification. This paper presents a comprehensive review of SS and its generalization, 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 scientific analyses.

Uguina, A. R., 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.