Routing and Scheduling in Home Health Care: The Power of Online Time Slot Selection

In the modern healthcare landscape, patient-centricity is transitioning from a marketing slogan to an operational necessity. An increasing number of home healthcare (HHC) providers now offer patients the option of booking appointment time slots online. This shift significantly enhances patient convenience, but it also introduces a massive operational headache behind the scenes.

How can an HHC agency offer flexible choice options to patients without sending their caregiver travel costs and schedules into absolute chaos?

To solve this, our recent study, "Routing and scheduling in home health care with time slot selection," published in Transportation Research Part E: Logistics and Transportation Review, establishes a mathematically rigorous optimization framework that simultaneously selects which time slots to offer online and plans the subsequent routing and scheduling of caregivers.

---

The Strategic Conflict: Convenience vs. Cost

In traditional HHC systems, scheduling is entirely top-down. The agency assigns a caregiver and a time window, and the patient must adapt. While highly efficient for minimizing travel distances, it completely ignores patient preferences.

Online booking changes the game. When patients are allowed to select their preferred time slots online, their choices are driven by multiple factors:

1. Time Window Convenience: Does the slot fit their daily routine?
2. Caregiver Skill Level: Does the assigned caregiver have the required specialized training?
3. Familiarity: Have they built a relationship of trust with this caregiver over past visits?

However, if an agency displays all possible time slots to every patient, it creates a scheduling nightmare. Two patients living far apart might book consecutive slots, forcing caregivers to cover long distances in short periods, increasing travel costs and risking late arrivals. Therefore, the agency must strategically restrict the options offered. The challenge is to identify the optimal subset of time slots to post online for each patient.

---

Modeling Patient Choice with Multinomial Logit

To address this challenge, our study integrates behavioral science into logistics optimization. We capture patient choice behavior using a Multinomial Logit (MNL) model.

The Mathematical Formulation

For each patient $i$, let $S_i$ be the set of time slots posted online by the agency, and $S_0$ be the opt-out option (e.g., choosing not to book or seeking care elsewhere). The probability $P_{ik}$ of patient $i$ selecting time slot $k \in S_i$ is formulated as:

$$P_{ik} = \frac{\exp(V_{ik})}{\sum_{j \in S_i} \exp(V_{ij}) + \exp(V_{i0})}$$

Where the deterministic utility $V_{ik}$ represents the patient's satisfaction with slot $k$, which is a function of:

• Caregiver Familiarity: Higher utility if the caregiver has visited before.
• Skill Level Match: Maximizing caregiver-patient compatibility.
• Time Slot Preference: The inherent attractiveness of slot $k$ based on the patient's daily routine.

The agency's goal is to minimize a multi-objective function that balances three key dimensions:

$$\text{Minimize } Z = \text{Caregiver Routing Costs} + \text{Time Window Deviation Penalties} - \text{Expected Patient Satisfaction}$$

This represents a classic Stackelberg (leader-follower) problem: the agency (leader) decides which slots to offer, and patients (followers) make their choices according to their utility functions.

---

The Solution: A Tailored ALNS Algorithm

This integrated problem is classified as NP-hard, combining discrete choice probabilities with a complex Vehicle Routing Problem with Time Windows (VRPTW). Standard commercial solvers like Gurobi can only handle small-scale instances and fail when scaled to realistic city-wide networks.

To achieve computational tractability, we designed a tailored Adaptive Large Neighborhood Search (ALNS) algorithm, enhanced with two novel features:

1. Time-Slot Perturbation Mechanism: Dynamically adjusting the set of posted time slots to explore the trade-offs between patient choice probabilities and routing flexibility.
2. Tailored Large Neighborhood Operators: Customized ruin-and-recreate operators that exploit the specific structure of the HHC problem, ensuring the search doesn't get trapped in sub-optimal local minima.

---

Managerial Insights: Finding the "Sweet Spot"

By performing extensive sensitivity analyses on key parameters, our study provides valuable, actionable guidelines for home healthcare administrators:

1. The Paradox of Choice: The "Sweet Spot" of Slot Availability

Intuitively, one might assume that offering more time slots always increases patient satisfaction. However, our results reveal a clear trade-off.

Slots Offered ($\vert S_i \vert$)	Patient Satisfaction	Caregiver Routing Cost	Operational Verdict
1 Slot	Low	Low	Too rigid; patients opt out
2 Slots	Medium-Low	Low-Medium	Sub-optimal patient retention
3 – 4 Slots	High (Near-Plateau)	Moderate (Controlled)	Optimal Balance (Sweet Spot)
5+ Slots	Marginal Gain	Extremely High	Routing fragmentation; high costs

As shown in the table, offering 3 to 4 slots strikes the optimal balance. It captures over 90% of the maximum potential patient satisfaction while keeping caregiver travel distances manageable. Offering more than 4 slots yields diminishing returns in satisfaction but causes exponential increases in routing costs due to scheduling fragmentation.

2. The High Value of Caregiver Familiarity

Our sensitivity analysis indicates that patient familiarity is the strongest driver of satisfaction. Patients are highly willing to accept less-convenient time slots if it guarantees a visit from a familiar caregiver. HHC agencies should leverage this by prioritizing continuity of care in their booking systems, which paradoxically allows for more flexible daily routing.

3. Skill Level Management

Restricting caregiver assignments strictly to high-skill matches ensures quality but severely restricts routing flexibility. We find that establishing a moderate skill-deviation threshold protects care standards while unlocking significant routing cost savings.

---

Conclusion

Routing and scheduling in home healthcare is no longer just a mathematical routing problem; it is a complex behavioral coordination challenge. By combining discrete choice modeling with advanced metaheuristic search, our framework proves that agencies do not have to choose between patient convenience and system cost-efficiency. With the right algorithms, we can achieve both.

For full mathematical formulations, convergence proofs, and comprehensive experimental data, read the complete study in Transportation Research Part E.