Praxis-KPI: Pflegedienst NRW spart 12-15 zusätzliche Patienten pro Tour. Krankentransport NRW reduziert Leerfahrten um 30% (Pickup-Delivery-Constraint korrekt aufgelöst). Setup-Zeit 5-7 Tage, BAFA Pflege 4.0 50% gefördert.
Warum Greedy versagt
Naive Greedy-Heuristik (immer nächster Stop) findet bei realistischen Touren-Größen typisch 70-80% der optimalen Tour-Länge. Bei 25+ Stops divergiert es schnell:
- Pickup-Delivery: Patient muss VOR Klinik abgeholt werden, Greedy kann das nicht respektieren
- Time-Windows: Patient X muss zwischen 9:00-9:30 Uhr ankommen, Greedy kennt keine Constraints
- Multi-Vehicle: 3 Fahrzeuge mit unterschiedlicher Kapazität (Liegend/Sitzend/Rollstuhl)
- Lunch-Break: Pflegekraft hat 30-min-Pause zwischen 12:00-13:00
Tourenplanung: CP-SAT vs. Routing-Solver
→ Tabelle seitlich scrollbar
| Solver | Stärke | Schwäche | Anwendungsfall |
|---|---|---|---|
| CP-SAT (Constraint-Programming) | komplexe Constraints, optimal in 0.01-1s bei <30 Stops | skaliert nicht über 100 Stops | Schichtplan-KI, Krankentransport <50 Aufträge |
| Routing-Solver | skaliert auf 1000+ Stops mit Heuristiken | nicht garantiert optimal | Pflegedienst-Tour, Kurier-Same-Day |
| Hybrid (Routing + Local-Search) | beide Welten kombiniert | Setup-Komplexität | Sicherheitsdienst-Streifen |
Pickup-and-Delivery Bug + Fix
Häufiger Implementierungs-Fehler bei Krankentransport: AddDisjunction([pickup, delivery]) als ein Set führt dazu, dass der Solver beide Stops als "skipbar zusammen" interpretiert — er hängt sich auf oder findet keine Lösung.
Korrekter Pattern: getrennte Disjunctions pro Stop + AddPickupAndDelivery-Constraint:
routing.AddDisjunction([pickup_idx], penalty) routing.AddDisjunction([delivery_idx], penalty) routing.AddPickupAndDelivery(pickup_idx, delivery_idx) routing.solver().Add(routing.VehicleVar(pickup_idx) == routing.VehicleVar(delivery_idx)) routing.solver().Add(distance_dim.CumulVar(pickup_idx) <= distance_dim.CumulVar(delivery_idx))
DripBack-Module mit Tourenplanung
- Schichtplan-KI: CP-SAT für 6-MA / 12-Schichten. Optimum in 0.01s mit ArbZG-Konformität (Pause, Ruhezeit).
- Pflegedienst-Tour-Optimizer: Routing-Solver für 30 Patienten-Stops mit Time-Windows.
- Krankentransport-Dispatch: Pickup-and-Delivery mit Multi-Vehicle (Liegend/Sitzend/Rollstuhl) + Pre-LLM 112-Trigger.
- Taxi-Dispatch-KI: Real-Time-Routing mit Driver-Match.
- Sicherheitsdienst-Tour-Routing: Streifen mit Pre-LLM Alarm-Trigger.
Förderung
Eigene Tourenplanungs-Implementierungen sind FZulG-fähig wenn die Engine-Eigenentwicklung Forschungs-Charakter hat (Custom-Constraints, eigene Heuristiken, Performance-Optimierung). Plus:
- BAFA Pflege 4.0 50% (Pflegedienst)
- BAFA Logistik 4.0 (Krankentransport, Logistik-KI-Suite)
- NRW.BANK MID-Digitalisierung 50% bis 15.000 €
- FZulG 35% bei eigener Solver-Entwicklung