VRP for Ambulances – Modeling Questions

[fodzal]

Heterogeneous Fleet Multi Pickup and Delivery Problem with Time Windows and Crew Scheduling

Hi everyone,

First, thanks a lot for this beautiful open-source solver!

I'm working on a Vehicle Routing Problem (VRP) for ambulance planning and would appreciate feedback on modeling approaches, especially regarding driver–vehicle decoupling and vehicle switching.

🧩 Problem overview

This is a day-ahead planning problem (all demand is known the day before), with the following key characteristics:

Core constraints

• Single depot
• Around 1000 visits for 50 vehicles
• Multi Pickup & Delivery with Time Windows
  • Each request consists of a pickup at location X and a delivery at location Y
  • Both pickup and delivery have strict time windows
  • Routes can mix pickups and deliveries arbitrarily (so this is not reducible to a classical CVRP)

Fleet & resources

• Heterogeneous fleet
  • Different vehicle capacities
  • Different required skills/competencies
• Multi-driver requirements
  • Some visits require 2 drivers in the same vehicle
• Drivers are not permanently assigned to a vehicle
  • Drivers can change vehicles up to 3 times per day
  • This could be performant for example when:
    • Only part of the day requires 2 drivers
    • A driver only works a partial shift

Break constraints

• Breaks are flexible but penalized:

  • Penalty if:
    • Not taken at the depot
    • Duration < 1 hour
  • However, shorter or off-depot breaks may still be optimal

  ---

✅ What I’m comfortable with

• Multi pickup & delivery modeling
  • Using custom moves similar to:
    https://github.com/ge0ffrey/optaplanner-mixedvrp-experiment/tree/master/src/main/java/org/optaplanner/examples/vehiclerouting/domain
• Break handling

  • Using a propagation approach:

    • Try to insert a “long break”
    • If infeasible, fallback to a “short break” with penalty

    ---

❗ Main challenge: driver ↔ vehicle decoupling

The main difficulty is modeling the fact that drivers can switch vehicles during the day.

I am currently considering two approaches:

🔁 Option 1: Two-stage optimization

1. First stage: vehicle routing
   • Optimize ambulance routes (vehicle-centric)
2. Post-process: split routes into trips
   • Split routes into feasible sub-trips (e.g., when near depot)
3. Second stage: driver assignment
   • Assign trips to drivers (PlanningList of trips)

Pros:

• Cleaner separation of concerns
• Easier to reason about

Cons:

• Potential loss of global optimality
• Harder to propagate constraints across stages

🔗 Option 2: Integrated model with trips

• Each ambulance is modeled as a sequence of trips
• Trips are:
  • Sequentially constrained (via variable listener)
  • Assigned to drivers via a planning variable
• Using inverse shadow variables:
  • Retrieve all trips per vehicle
  • Enforce temporal consistency

Pros:

• Fully integrated optimization
• Better global optimality

Cons:

• More complex model
• Potential performance concerns

---

🤔 Open questions

I’d really appreciate feedback on the following:

1. Is there a recommended pattern in Timefold for modeling driver–vehicle decoupling?
   Especially when drivers can switch vehicles multiple times
2. Has anyone modeled something similar?
3. Which option looks like the best? Do you think about another modelization?

Thanks a lot for your help!
Any feedback, examples, or pointers would be greatly appreciated 🙏