Combinatorial Optimization & Operations Research
Operations Research Intern — Resource Allocation, Vehicle Routing, CP-SAT Solving
Consulting team at Deloitte
From January 2024 to June 2024 (6 months)
Solving a joint Nurse Scheduling and Vehicle Routing problem — an NP-Hard challenge — to optimize healthcare delivery where assignments and travel routes are decided simultaneously.
Python, Google OR-Tools (CP-SAT), NumPy, Pandas
Overview
Every morning, home healthcare agencies solve an impossible puzzle: assign the right nurse to the right patient, at the right time, via the shortest route — while respecting labor laws, patient time windows, and individual preferences. This problem is NP-Hard. I built a solver that handles scheduling and routing simultaneously, avoiding the sub-optimality of traditional two-phase approaches.
THE PROBLEM
The standard approach in healthcare logistics is "cluster first, route second": assign patients to nurses, then optimize each nurse's travel path. But this sequential decomposition loses information — a nurse might be assigned patients that are geographically scattered because the routing wasn't considered during assignment.
The real problem is a joint NSP-VRPTW: Nurse Scheduling Problem combined with Vehicle Routing Problem with Time Windows. Hundreds of interacting constraints — legal rest periods, patient availability windows, nurse shift preferences, travel times — make brute-force search impossible.
METHODOLOGY
The problem is formulated as a Constraint Satisfaction Problem (CSP) and solved with Google OR-Tools' CP-SAT solver:
- 4D Decision Variables: Boolean variables
X(n,d,s,p)encode whether nurse n, on day d, during shift s, visits patient p — capturing the full decision space in a single model. - Hamiltonian Circuits: The
AddCircuitglobal constraint guarantees that each nurse's daily route forms a valid loop — visiting all assigned patients and returning to the starting depot. - Temporal Integrity:
AddNoOverlapon optional interval variables ensures that care tasks, travel time, and rest periods never conflict within a single shift. - Multi-Objective Optimization: The cost function balances hard constraints (legal rest, patient windows) with soft constraints (nurse shift preferences), using tunable weights.
Maximize: Σ(Nurse Preference Scores) - α × Σ(Travel Costij × Arcij)
Where soft constraints (nurse preferences) are maximized while travel costs are minimized. Hard constraints (time windows, rest periods) are enforced strictly — no trade-offs allowed.
DATA ENGINEERING
To validate the solver under realistic conditions, I built a synthetic data generator:
- Probabilistic Simulation: Patient demand and care duration are modeled using exponential and normal distributions, creating realistic workload variation to stress-test the solver.
- Distance Matrix: A dynamic cost matrix enforces the triangle inequality — ensuring the solver can't find "shortcuts" that violate physical reality.
| Time | Nurse A | Nurse B | Nurse C |
|---|---|---|---|
| 08:00 | Depart depot | Depart depot | Depart depot |
| 08:15 | Patient 3 (30 min) | Patient 1 (45 min) | Patient 7 (20 min) |
| 09:00 | Travel (12 min) | Patient 5 (30 min) | Patient 2 (40 min) |
| 09:15 | Patient 8 (45 min) | Travel (18 min) | Travel (10 min) |
| 10:00 | Patient 4 (20 min) | Patient 6 (35 min) | Patient 9 (30 min) |
| 10:45 | Return to depot | Return to depot | Return to depot |
Minute-by-minute itineraries where assignment and routing are decided jointly — no wasted travel, no scheduling conflicts.
RESULTS & IMPACT
The solver produces minute-by-minute schedules that satisfy all hard constraints (legal rest, patient windows) while maximizing nurse preferences through soft-constraint weight tuning.
By choosing CP-SAT over classical MIP, the solver achieves significantly faster convergence on highly constrained scheduling problems. The project demonstrates that Operations Research isn't just academic — it's a direct lever for improving healthcare logistics and worker satisfaction.
REFERENCES
- Perron, L., & Furnon, V. OR-Tools — Google Optimization Tools. developers.google.com/optimization
- Burke, E.K., et al. (2004). The State of the Art of Nurse Rostering. Journal of Scheduling, 7(6).
- Cordeau, J.F., et al. (2007). Vehicle Routing. Handbook in Operations Research & Management Science, Vol. 14.
TECH STACK
Optimization: Google OR-Tools (CP-SAT solver).
Modeling: Constraint Programming, Hamiltonian Circuits,
Interval Variables.
Tools: Python, NumPy, Pandas, Matplotlib.
This is an archived project. Please reach out if you have any questions.