LLM-Guided Genetic Search for the Home Healthcare Routing and Scheduling Problem

This paper investigates whether Large Language Models (LLMs) can effectively support combinatorial optimization in home healthcare scheduling. As a case study, we consider the Home Health Care Routing and Scheduling Problem (HHCRSP), a challenging healthcare logistics problem with strict temporal and skill constraints. Our experiments show that a standalone LLM is unreliable on this problem, but becomes effective when integrated as a perturbation component within a Biased Random-Key Genetic Algorithm (BRKGA). In the proposed hybrid approach, called LLM-BRKGA, the LLM provides high-level guidance by identifying spatial outliers and hotspots for targeted search perturbations. Results on benchmark instances show that LLM-BRKGA improves solution quality over the BRKGA baseline, especially on medium-to-large and large instances, suggesting that LLMs can effectively complement traditional optimization methods by injecting structured, problem-aware perturbations beyond purely stochastic operators.