New Heuristics for the Operation of an Ambulance Fleet under Uncertainty

This paper proposes and evaluates a set of new heuristics for ambulance selection and reassignment decisions under uncertainty, demonstrating through a rollout approach applied to real-world emergency medical service data that these methods significantly outperform existing strategies in reducing response times while maintaining real-time computational efficiency.

The Gist

Imagine the city's ambulance fleet as a team of superheroes patrolling a giant chessboard. Their job is to rush to emergencies (like a fire or a medical crisis) and save the day. But here's the catch: the city is chaotic. Emergencies pop up randomly, traffic changes, and some heroes are better equipped than others (some have advanced medical gear, others are basic).

The big question is: How do you decide which superhero goes where, and what they should do next, without knowing exactly what will happen in the next hour?

This paper proposes a new set of "rules of thumb" (called heuristics) to help the dispatchers make these split-second decisions. Here is the breakdown in plain English:

1. The Two Big Decisions

Every time a call comes in or a hero finishes a job, the dispatcher has to make two choices:

• The "Who Goes?" Decision: A new emergency happens. Which ambulance should we send? Do we send the closest one, or the one with the best medical skills?
• The "What's Next?" Decision: An ambulance just finished a job. Do we send it back to its home base (like a garage)? Do we send it to a cleaning station? Or do we send it to wait near a spot where we think another emergency might happen soon?

2. The Problem with Old Rules

For a long time, dispatchers used simple rules like "Send the closest available ambulance."

• The Flaw: Imagine a basic ambulance is 2 minutes away from a heart attack victim, but a high-tech ambulance is 10 minutes away. The old rule sends the basic one because it's closer. But the heart attack needs the high-tech one!
• The Other Flaw: After saving a patient, the ambulance might just go home to its garage. But if the garage is in a quiet part of town, and the next emergency is in a busy part, that ambulance is useless when it's needed most.

3. The New "Smart" Strategies

The authors created four new strategies (heuristics) to fix this. Think of them as different ways a coach might tell their players to move:

• The "Best Myopic" (BM) Strategy: This is the "Look at the Now" coach. It picks the ambulance that minimizes the cost right this second, considering both distance and whether the ambulance has the right tools for the job. It doesn't worry about the future; it just wants to win the current point.
• The "Non-Myopic" (NM) Strategy: This is the "Chess Master" coach. It looks a few moves ahead. It asks, "If I send this ambulance to this call, will it leave us stranded for a bigger emergency coming in 5 minutes?" It tries to balance the current job with future needs.
• The "Greedy" Strategies (GHP1 & GHP2): These are like a "First Come, First Served" line manager, but with a twist. If there are multiple emergencies waiting in line, these rules decide which one gets the ambulance first based on how long they've been waiting or how urgent they are.

4. The "Crystal Ball" Trick (Rollout Approach)

This is the coolest part of the paper. The authors realized that even the smartest coach can't predict the future perfectly. So, they added a "Simulation Game."

Every time a decision needs to be made, the computer runs a mini-simulation 100 times in a split second.

• Imagine this: The dispatcher pauses time. They say, "Okay, what if a fire happens here? What if a car crash happens there?" They run through 100 different "what-if" scenarios using their new rules.
• Then, they pick the decision that works best across all those imaginary futures.
• The Result: It's like having a crystal ball that shows you 100 possible futures, helping you pick the path that is most likely to succeed, even though you can't see the real future yet.

5. The "Best Station" Rule

When an ambulance is idle, where should it wait?

• Old Way: Go home to your assigned garage.
• New Way (Best Station Rule): The computer looks at the map and says, "The North side of town usually gets a lot of calls at 6 PM. Let's send the idle ambulance to the North garage, even if it's not its home." It's like a soccer team shifting their defense to the side where the opponent is attacking.

6. The Results: Why It Matters

The authors tested these new rules using real data from Rio de Janeiro (a massive, busy city).

• Speed: The computer makes these complex decisions in a few seconds. This is fast enough for real-time use.
• Performance: The new methods saved more lives (in terms of faster response times) and handled emergencies better than the old "closest ambulance" rule or other methods found in textbooks.
• Flexibility: They handle different types of emergencies (heart attacks vs. minor cuts) and different types of ambulances (basic vs. advanced) much better.

The Bottom Line

This paper is about teaching ambulance dispatchers to stop playing "Whac-A-Mole" (just hitting the nearest emergency) and start playing chess. By using smart, quick calculations that look at the future and the specific needs of each patient, we can get the right help to the right person, faster.

It turns out that the best way to manage a fleet of ambulances isn't just about being fast; it's about being strategic.

Technical Summary

Here is a detailed technical summary of the paper "New Heuristics for the Operation of an Ambulance Fleet under Uncertainty" by Guigues, Kleywegt, and Nascimento.

1. Problem Definition

The paper addresses the dynamic management of an ambulance fleet within Emergency Medical Services (EMS). The core challenge is making real-time decisions under uncertainty regarding:

• Ambulance Selection: Determining which available ambulance (and crew) to dispatch to a new emergency call.
• Ambulance Reassignment: Deciding what an ambulance should do after completing a service (e.g., which queued emergency to attend next, or which station to return to for staging).

Key Complexities:

• Uncertainty: Future emergency calls (location, type, arrival time) and travel/service times are stochastic.
• Heterogeneity: Emergencies vary by type (e.g., cardiac arrest vs. minor injury) requiring specific response times and crew capabilities (Basic Life Support - BLS vs. Advanced Life Support - ALS). Ambulances and crews also vary in capability.
• Service Sequences: The paper models four distinct service sequences (C1–C4) based on whether the patient is transported to a hospital and whether the ambulance requires cleaning at a station.
• Queueing: Unlike many previous models that assume immediate dispatch or transfer to other services, this model allows for a queue of emergencies when no ambulances are available, or when a conscious decision is made to wait for a better resource match.

2. Methodology

The authors propose a Rollout Approach combined with new Heuristics.

A. Stochastic Optimization Framework

The problem is modeled as a stochastic process where decisions are made at two trigger events:

1. Arrival of a new emergency call.
2. Completion of service by an ambulance.

The authors utilize a Rollout Policy. At any decision time $t_0$, for a feasible decision $x_0$, the system evaluates the immediate cost plus the expected future cost over a time horizon. This future cost is approximated by simulating $N$ scenarios (sample paths) and applying a base policy (heuristic) to these scenarios. The decision $x_0$ that minimizes the average cost over these scenarios is selected.

$$\min_{x_0 \in S} \left( f(x_0) + \frac{1}{N} \sum_{i=1}^{N} Q_H(x_0, \xi^i_{t_0}) \right)$$

Where $Q_H$ is the cost computed by the rollout policy $H$ over scenario $\xi$.

B. Proposed Heuristics

The paper introduces four new heuristics to serve as the base policy $H$ for the rollout approach:

1. Best Myopic (BM):

   • Selects the ambulance that minimizes the immediate allocation cost (response time penalty + capability mismatch cost).
   • It considers the current status of all ambulances (busy, traveling to station, or at a station) to calculate the earliest possible arrival time.
   • It prioritizes "least advanced" ambulances if costs are equal (e.g., using a BLS ambulance for a low-priority call to save an ALS ambulance for high-priority needs).

2. NonMyopic (NM):

   • A non-anticipative policy that looks ahead at calls arriving before the selected ambulance becomes available again.
   • It evaluates if assigning the "best" ambulance to the current call prevents a better assignment for a future call arriving before the ambulance is free. It allocates the ambulance to the call (current or future) that yields the highest "marginal benefit" (minimizing the worst-case allocation cost).

3. Greedy Heuristic with Priorities 1 (GHP1):

   • Maintains a queue of unassigned emergencies.
   • Sorts the queue by penalized waiting time (how long the call has waited, weighted by urgency).
   • Assigns available ambulances to the highest-priority waiting calls first.

4. Greedy Heuristic with Priorities 2 (GHP2):

   • Similar to GHP1 but sorts the queue by the minimum allocation cost (the cost if the best available ambulance were assigned) rather than waiting time. This prioritizes calls that are "expensive" to delay.

C. Ambulance Reassignment (Station Selection)

When an ambulance finishes service and no queue exists, the paper proposes three rules for where to send the ambulance:

• Home Station Rule (HSR): Returns to a pre-assigned home station.
• Closest Station Rule (CSR): Goes to the nearest station.
• Best Station Rule (BSR): A novel heuristic that sends the ambulance to the station with the highest forecasted deficit. It calculates the difference between the forecasted demand (based on a Poisson process) and the forecasted supply of ambulances at each station over a lookahead interval.

3. Key Contributions

1. Integrated Decision Making: Unlike many prior works that focus solely on dispatch or assume ambulances return to home stations, this method jointly optimizes dispatch selection and reassignment (including station choice and handling of queues).
2. Granular Capability Matching: The model explicitly accounts for different emergency types (beyond simple priority levels) and specific ambulance/crew capabilities (BLS, ALS, stroke units, etc.), optimizing the "match" quality.
3. Rollout Implementation: The authors demonstrate that solving a two-stage stochastic program via rollout with these heuristics is computationally feasible (decisions made in seconds) and significantly outperforms static heuristics.
4. Open Source & Visualization: The authors provide C++ and Matlab code on GitHub and a web visualization tool for the Rio de Janeiro EMS, allowing for real-time management and performance metric visualization.

4. Numerical Results

The methods were tested using real data from the Rio de Janeiro EMS (Jan 2016–Feb 2018) and synthetic data.

• Performance Metrics: Allocation cost (weighted response time + capability mismatch) and response times.
• Comparison: The proposed heuristics (BM, NM, GHP1, GHP2) were compared against 8 existing heuristics from literature (e.g., Closest Available, Andersson & Värbrand, Lee, Mayorga, etc.).
• Findings:
  • Superiority: The proposed heuristics, particularly when used within the rollout framework, consistently outperformed all literature benchmarks in terms of mean allocation costs and response times across various fleet sizes (10 to 30 ambulances).
  • Rollout Benefit: Using the rollout approach (simulating future scenarios) yielded significantly better results than applying the heuristics directly (myopic application).
  • Computation Time: All decisions were computed in milliseconds, making the approach viable for real-time operations.
  • Reassignment Impact: The Best Station Rule (BSR) showed significant improvements in specific scenarios with shifting demand patterns compared to the Home Station Rule, reducing response times by approximately 50% in tested instances.
  • Uncertainty: The methods remained robust when travel times were modeled as random variables (Lognormal distribution).

5. Significance

This paper represents a significant advancement in EMS operations research by moving beyond static location models and simple "closest available" dispatch rules.

• Practical Applicability: The ability to compute high-quality decisions in seconds allows for the deployment of these algorithms in live EMS control centers.
• Resource Optimization: By explicitly modeling the trade-off between response time and crew capability, the methods ensure that critical resources (like ALS crews) are not wasted on low-priority calls, thereby improving overall system efficiency and patient outcomes.
• Dynamic Adaptation: The inclusion of queueing and dynamic station reassignment allows the system to adapt to fluctuating demand patterns throughout the day, a critical feature for large urban centers.

In conclusion, the authors successfully demonstrate that a combination of tailored heuristics and a rollout framework provides a computationally efficient and highly effective solution for the stochastic, dynamic problem of ambulance fleet management.