Home Healthcare Routing & Scheduling - Handbook

Type: IP (Integer Programming)

This handbook explains the Home Healthcare Routing sample problem in the LP Black Box platform.

Home healthcare agencies need to optimize their caregivers' daily routes to serve as many patients as possible while managing time and budget constraints.

---

The Problem

Scenario

A home healthcare agency has one caregiver who needs to visit 4 different patient locations throughout the day.

Patient	Priority Score	Time per Visit (min)	Travel Cost ($)
Patient A	10	45	5
Patient B	15	60	8
Patient C	12	30	3
Patient D	8	45	6

Your Goal

Maximize the total priority score (value of care provided) while staying within time and budget limits.

The Constraints

1. Time Limit: The caregiver has only 8 hours (480 minutes) per day

   Formula: 45×visit_A + 60×visit_B + 30×visit_C + 45×visit_D ≤ 480

2. Fuel Budget: Cannot exceed $150 for travel

   Formula: 5×visit_A + 8×visit_B + 3×visit_C + 6×visit_D ≤ 150

3. Minimum Patients: Must serve at least 6 patients (or partial visits weighted)

   Formula: visit_A + visit_B + visit_C + visit_D ≥ 6

   Note: In this simplified model, each variable represents a "unit" of visit. You can adjust the RHS based on whether partial visits are allowed.

4. Patient B Limit: Cannot visit Patient B more than 5 times (due to availability)

   Formula: visit_B ≤ 5

---

How to Use in LP Black Box

Step 1: Load the Sample

1. Go to the Operation tab in the Admin Dashboard
2. In "Load Sample Problem", select Home Healthcare Routing
3. The form will populate with the problem data

Step 2: Examine the Problem

You should see:

Variables:

Name	Type	Lower Bound
visit_A	Integer	0
visit_B	Integer	0
visit_C	Integer	0
visit_D	Integer	0

Objective:

• Type: Maximize
• Coefficients: visit_A=10, visit_B=15, visit_C=12, visit_D=8

Constraints:

• time_limit: 45×A + 60×B + 30×C + 45×D ≤ 480
• fuel_budget: 5×A + 8×B + 3×C + 6×D ≤ 150
• min_patients: A + B + C + D ≥ 6
• max_visits_B: B ≤ 5

Step 3: Solve

Click Solve LP to find the optimal visit schedule.

Step 4: Interpret Results

The solution will show:

• How many visits to each patient to maximize priority score
• The total maximum priority value achieved

---

Understanding the Solution

The solver will determine the optimal mix of visits that:

1. Doesn't exceed 480 minutes of available time
2. Doesn't exceed $150 travel budget
3. Serves at least 6 "patient-units"
4. Respects Patient B's maximum visits

The priority score represents the clinical importance or urgency of each patient visit. By maximizing this, the agency ensures the most important patients get care first.

---

Try It Yourself

Exercise 1: Increase Time Available

If the caregiver works 10 hours instead of 8 (600 minutes), how does the solution change?

Change time_limit RHS from 480 to 600.

Exercise 2: Add a New Patient

Add a new patient E with:

• Priority: 20
• Time: 40 min
• Cost: $7

Add a new variable visit_E with coefficient 20 in objective, 40 in time_limit, and 7 in fuel_budget.

Exercise 3: Require Minimum for High-Priority Patients

Add a constraint that Patient B must be visited at least 3 times:

• Name: min_B
• Coefficients: visit_B=1
• Type: GreaterThanOrEqual
• RHS: 3

---

Real-World Extensions

This simplified model can be extended to:

1. Multiple Caregivers: Optimize routes for multiple staff members
2. Geographic Clustering: Group patients by location to minimize travel
3. Time Windows: Patients available only at certain times
4. Skill Matching: Match caregiver skills to patient needs
5. Follow-up Visits: Multiple visits per patient over several days

---

Quick Reference

Concept	Description
Maximize Objective	Get the highest total value (priority score)
Time Constraint	Limits total working hours
Budget Constraint	Limits travel expenses
Integer Variables	Whole visits (can't do half a visit)

---

This sample demonstrates how Linear Programming can help home healthcare agencies maximize patient care with limited resources.