Chronicles on Metaheuristic Optimization: Components, Applications, and Large Language Models

Metaheuristic algorithms play a central role in solving combinatorial optimization problems, yet their empirical study and reliable application remain fragmented. The community has developed a multitude of algorithms and variants, often emphasizing competitive performance over explanatory insight. Consequently, the understanding of algorithmic behavior is limited, and available tools are typically applied only to benchmark problems. On the problem side, the literature has produced numerous variants, leading to a proliferation of isolated formulations. At the same time, emerging technologies such as Large Language Models are beginning to reshape the landscape of optimization research. This thesis addresses these challenges along four complementary directions: developing a component-level understanding of metaheuristics, extending benchmarking methodologies to real-world problems, unifying fragmented problem formulations, and exploring the integration of emerging technologies such as Large Language Models within optimization. First, by systematically analyzing the internal components of classical methods such as Tabu Search and Simulated Annealing, the work investigate how design choices shape search dynamics and demonstrates that adaptive control mechanisms can reproduce tuned performance without manual calibration. Second, attention turns to a real-world application: the Oven Scheduling Problem, a parallel batch scheduling problem. The study develops theoretical lower bounds and employs Simulated Annealing and Large Neighborhood Search. Statistical analysis and visual benchmarking techniques are integrated to reveal how instance features and search trajectories jointly explain algorithmic performance. Third, the analytical perspective is extended to the problem domain itself through a unified formulation of the Home Healthcare Routing and Scheduling Problem. We consolidate previously isolated variants and develop open tools for instance generation, analysis, translation, and validation. Additionally, transversal solution methods are introduced, with performance comparable to or exceeding that of specialized algorithms. Fourth, the thesis explores the role of Large Language Models in optimization, systematically mapping existing research. Then, we shift the focus from what these models can do to how they \emph{reason}. Their behavior and representational capabilities are empirically examined through direct querying and probing experiments. Altogether, the thesis contributes to a coherent perspective on how optimization methods can be analyzed, unified, and extended, providing both conceptual clarity and practical tools for the study of complex decision problems.