Bei einer Tourenoptimierungs-Engine geht es nicht nur darum, festzustellen, ob eine Einfügung machbar ist. Der Kern der Herausforderung besteht darin, zu bestimmen, ob diese Einfügung eine gute operative Entscheidung darstellt.

Eine solche Unterscheidung ist von grundlegender Bedeutung: In realen Systemen können mehrere Einfügungen technisch zulässig sein, dabei jedoch zu völlig unterschiedlichen Auswirkungen führen. Einige beeinträchtigen die Robustheit der Planung erheblich. Andere verlängern die Wartezeiten oder schränken die künftige Flexibilität für Umplanungen schrittweise ein. Mit anderen Worten: Die reine Machbarkeit allein reicht nicht aus.

Genau für diese Herausforderung nutzen moderne Optimierungsalgorithmen Mechanismen der multikriteriellen Bewertung. Bei AntsRoute spielt dieses Scoring eine zentrale Rolle, um potentielle Einfügungskandidaten innerhalb eines bestehenden Zeitplans präzise zu beurteilen und zu priorisieren.

Das erwartet Sie in diesem Artikel:

• Warum das Scoring in Optimierungsmodulen eine zentrale Rolle spielt
• Nicht alle zulässigen Einfügungen sind gleichwertig
• Die Rolle der Grenzkosten bei der Bewertung von Touren
• Warum die zeitliche Qualität das Scoring in der Logistik grundlegend verändert
• Geografische Kohärenz als Kriterium für Robustheit
• Hard Constraints vs. Soft Constraints: welcher Ansatz die bessere Tour liefert
• Die zukünftige Flexibilität für Umplanunen aufrechterhalten
• Wie das Scoring die Erkundung der Suchmaschine steuert
• Warum ein verständlicher Score der Schlüssel zum Erfolg ist

Das Scoring ist ein Entscheidungsmechanismus

In vereinfachten Ansätzen wird eine Einfügung oft anhand eines einzigen Kriteriums bewertet, wie beispielsweise der zusätzlichen Entfernung, der Fahrzeit oder der unmittelbaren Kosten. Im realen Betrieb erweist sich diese Logik jedoch schnell als unzureichend.

Die Suchmaschine muss gleichzeitig mehrere teilweise widersprüchliche Faktoren gegeneinander abwägen:

• die Minimierung der gefahrenen Kilometer,
• die Einhaltung optimaler Zeitpuffer,
• die Wahrung der geografischen Kohärenz,
• die Erfüllung geschäftlicher Vorgaben,
• die realistische Eingrenzung von Erwartungen,
• die Flexibilität für künftige Umstrukturierungen,
• sowie die Vermeidung störungsanfälliger Routen.

Wie Ammar Oulamara, Leiter der Forschungs- und Entwicklungsabteilung bei AntsRoute, erklärt:

„Beim Scoring geht es nicht nur um die kostengünstigste Einfügung. Gesucht wird vielmehr die Option mit den wenigsten negativen Auswirkungen auf die Gesamtqualität der Planung.“

Diese feine Nuance verändert die Arbeitsweise der Engine grundlegend.

Dieser Artikel konzentriert sich bewusst auf die Scoring- und Bewertungsmechanismen einzelner Einfügungen.

Für einen umfassenderen Überblick über die Herausforderungen der Tourenoptimierung in der Last-Mile-Logistik können Sie auch unseren vollständigen Artikel über die Tourenoptimierung lesen.

Die eigentliche Herausforderung verlagert sich dadurch auf die Frage der Aggregation.

Wie lassen sich dann drei Einfügungen miteinander vergleichen, wenn:

• die erste die Kilometerzahl leicht erhöht,
• die zweite die Zeitpuffer stark verschlechtert,
• die dritte jedoch längere Wartezeiten verursacht, dabei aber eine bessere geografische Kohärenz wahrt?

Um dieses Dilemma zu lösen, wandelt die Engine die verschiedenen Dimensionen in einen einzigen skalaren Wert um, um die in Frage kommenden Einfügungen zu priorisieren.

Das Ziel besteht nicht darin, das Problem künstlich auf eine einzige Metrik zu reduzieren, sondern einen kohärenten Abwägungsmechanismus zwischen mehreren heterogenen Betriebskosten zu schaffen.

Nicht alle zulässigen Einfügungen sind gleichwertig

Betrachten wir eine neue Aufgabe τ, die in einen bereits erstellten mehrtägigen Zeitplan eingefügt werden soll. Die Engine muss dann einen Entscheidungsraum der Form (Tag d) × (Route rᵢ) × (Position p) durchforsten. Jedes in Frage kommende Tripel muss anschließend bewertet werden.
Bestimmte Optionen werden in diesen Fällen sofort ausgeschlossen:

• Kapazitätsüberschreitunen,
• unvereinbare Qualifikationen,
• Verstöße gegen Vorschriften oder
• zeitliche Unmöglichkeiten.

In den meisten Fällen sind jedoch mehrere Einfügungen zulässig.
Die Rolle des Scorings wird dabei entscheidend: Lösungen werden verglichen, ihre relative Qualität wird gemessen und schließlich werden die besten Kandidaten priorisiert. Die Engine argumentiert also nicht nach binärer Logik – machbar oder unmöglich –, sondern nach der Qualität der Optionen.

Erste Scoring-Ebene: die Grenzkosten der Einfügung

Die erste Komponente des Scorings bilden die geografischen Kosten. Bei AntsRoute bewertet die Engine insbesondere die Grenzkosten, die durch das Hinzufügen einer Aufgabe entstehen, nach folgender Formel:
Δc = c(vₚ₋₁, τ) + c(τ, vₚ) − c(vₚ₋₁, vₚ)

Mit dieser Kennzahl lassen sich die direkten Mehrkosten quantifizieren, die durch das Einfügen zwischen zwei aufeinanderfolgenden Knoten einer Tour entstehen. Je geringer diese Kosten sind,

• desto geografisch sinnvoller ist die Einfügung und
• desto besser bleibt die räumliche Kompaktheit der Route erhalten.

Diese Komponente macht jedoch nur einen Teil des Gesamtwerts aus.
Wie Ammar Oulamara betont:

„Die Kosten pro Kilometer allein sind bei Touren mit strengen Restriktionen ein sehr schlechter Leistungsindikator.“

Die zeitliche Tourenqualität: eine fundamentale Scoring-Komponente

In einem VRPTW-Kontext (Vehicle Routing Problem with Time Windows) spielen zeitliche Einschränkungen eine entscheidende Rolle. Eine einzige Einfügung kann:

• Wartezeiten verlängern,
• Sicherheitszeitpuffer verkürzen,
• Zeitfenster überlasten oder
• die zeitliche Stabilität der Tour erheblich beeinträchtigen.

Die Engine bestraft dann auch unnötige Wartezeiten gemäß folgendem Ziel:
min Σᵢ max(0, eᵢ − tᵢ)

In dieser Formulierung stehen „eᵢ“ für die Öffnungsdauer des Zeitfensters und „tᵢ“ für die geschätzte Ankunftszeit (ETA).

Solche möglichen Verzögerungen spielen beim Scoring eine wichtige Rolle: Sie beinträchtigen nicht nur die operative Produktivität und die Tourendichte, sondern auch die zukünftige Fähigkeit, Störereignisse aufzufangen.

Eine der größten Schwierigkeiten bei einem multikriteriellen Scoring liegt in der Heterogenität der gewichteten Kennzahlen. Zusätzliche Kilometer, Wartezeiten, Strafkosten oder auch Auslastungsunterschiede haben weder dieselben Einheiten noch dieselben Größenordnungen. Die Engine muss daher diese verschiedenen Dimensionen normieren, um zu verhindern, dass ein Kriterium die anderen allein aufgrund seiner numerischen Größenordnung künstlich dominiert.

Nach dieser Harmonisierung können Einfügungen mit unterschiedlichen operativen Aspekten objektiv verglichen werden. Die Engine kann diese normierten Komponenten dann zu einem globalen skalaren Score aggregieren, der zur Einstufung der potenziellen Einsätze verwendet wird.

Der Score misst auch die geografische Kohärenz

Eine Route kann mathematisch optimiert sein, sich in der Praxis jedoch nur schwer umsetzen lassen. Dies gilt insbesondere für fragmentierte Touren mit:

• • häufigen Überschneidungen,
  • zerstückelten geografischen Gebieten,

• unnötigen Hin- und Rückfahrten und
• einer unübersichtlichen Einsatzverteilung.

Unser Scoring bei AntsRoute berücksichtigt daher auch Kriterien der räumlichen Konzentration.
Ziel ist es, Folgendes zu fördern:

• die geografische Bündelung der Kunden,
• die Tourenkontinuität sowie
• die operative Übersichtlichkeit der Planung.

Wie Ammar Oulamara erklärt:

„Eine geografisch kohärente Tour ist oft robuster und operativ einfacher zu handhaben.“

Hard Constraints vs. Soft Constraints: zwei sehr unterschiedliche Ansätze

Eines der zentralen Elemente des Scoring-Verfahrens beruht auf der Unterscheidung zwischen harten und weichen Restriktionen.

Bestimmte Verstöße sind verboten und führen zum sofortigen Ausschluss der Option durch die Engine, insbesondere:

• unvereinbare Kompetenzen,
• Verstöße gegen gesetzliche Vorschriften,
• zeitliche Inkompatibilität von Abholung und Zustellung oder
• Überschreitung der Fahrzeugkapazität.

Andere Abweichungen hingegen sind technisch akzeptabel, beeinträchtigen aber die gesamte Planungsqualität. Die Optimierungsengine berücksichtigt sie dann in Form von „Punkteabzügen“ in der Gesamtbewertung. Dies betrifft beispielsweise:

• übermäßige Wartezeiten,
• zeitliche Überlastungen,
• eine geringe Robustheit sowie
• Eine unausgewogene Tourenverteilung.

Allerdings haben nicht alle Beeinträchtigungen die gleichen betrieblichen Auswirkungen. Eine leichte Verdichtung einer Tour kann akzeptabel bleiben. Dagegen kann eine übermäßige Verringerung der Zeitpuffer oder eine starke Konzentration kritischer Einsätze auf denselben Zeitrahmen die allgemeine Robustheit der Planung erheblich beeinträchtigen.

Die Engine wendet daher progressive Strafwerte an, deren Höhe von der geschätzten Schwere der durch die Einfügung verursachten Beeinträchtigung abhängt. Dieser Ansatz ermöglicht es, allzu starre Abwägungen zu vermeiden und gleichzeitig mehrere unvollkommene Lösungen intelligent miteinander zu vergleichen.

Letztendlich haben nicht alle Kriterien bei der abschließenden Bewertung das gleiche Gewicht. Je nach betrieblichem Kontext können bestimmte Ansätze dominieren:

• die zeitliche Stabilität,
• die Minimierung der gefahrenen Kilometer,
• die geografische Dichte oder
• die Fähigkeit, Notfälle zu bewältigen.

Die Gewichtung dient genau dazu, diese betrieblichen Prioritäten bei der Berechnung der Punktzahl widerzuspiegeln. Das Berechnungsmodell strebt also kein universelles Optimum an, sondern einen Kompromiss, der mit den tatsächlichen Zielen des Betriebs im Einklang steht.

Der Erhalt der zukünftigen Flexibilität für Planungsänderungen

Einer der größten Herausforderungen dynamischer Scoringssysteme betrifft die zukünftige Anpassungsfähigkeit der Planung. Bestimmte Einfügungen scheinen kurzfristig sehr effizient zu sein, erschweren es anschließend jedoch erheblich, die Touren neu zu optimieren. Es kann zu folgenden Auswirkungen führen:

• dem Wegfall von Zeitpuffern,
• einer Überlastung bestimmter Ressourcen,
• der Blockierung von Nachbarschaften und
• einer starken lokalen Verdichtung.

Bei AntsRoute berücksichtigt das Scoring daher auch das lokale Verbesserungspotenzial der in Frage kommenden Einfügungen. Wie Ammar Oulamara betont:

„Ein guter Einfügungsvorschlag muss auch die zukünftige Flexibilität des Systems gewährleisten, Tourenpläne effizient neu zu organisieren.“

In einem dynamischen Umfeld ist der Score einer Einfügung niemals festgeschrieben. Er entwickelt sich kontinuierlich weiter, sobald:

• sich der Fahrplan verdichtet,
• neue Restriktionen auftreten oder
• wichtige Zeitpuffer wegfallen.

Diese Logik ist in Echtzeitumgebungen von entscheidender Bedeutung.

Das Scoring dient auch dazu, die algorithmische Suche zu steuern

Das Scoring dient nicht nur der Klassifizierung von Lösungen, sondern steuert auch gezielt den Einsatz der Rechenleistung der Engine. Nicht jede Option erfordert das gleiche Rechenbudget.

Wenig vielversprechende Ansätze werden durch begrenzte lokale Bewertungen schnell aussortiert. Umgekehrt werden die Einfügungen mit den besten Scores gezielt bevorzugt:

• bei tiefgreifenderen Nachbarschaftssuchen,
• durch lokale Suchmechanismen sowie
• bei rechenintensiven Optimierungsstrategien.

Somit wird das Scoring zu einem echten Mechanismus zur Priorisierung des Suchraums. Nach Abschluss der Bewertung können alle potenziellen Zeitfenster nach ihrer operativen Qualität geordnet werden, um die Auswahl der sinnvollsten Einfügungen automatisch zu steuern.

Diese Priorisierung ist unerlässlich, um:

• Echtzeit-Reaktionszeiten zu gewährleisten und
• gleichzeitig eine hervorragende Optimierungsqualität beizubehalten.

Der Score muss nachvollziehbar bleiben

In vielen Optimierungssystemen besteht eines der größten Schwierigkeiten in der Undurchsichtigkeit der Entscheidungen. Eine Engine, die eine Lösung liefert, ohne erklären zu können, was zur Priorisierung einer Option und Ablehnung einer anderen geführt hat, oder welche Restriktionen bei der Entscheidung eine wesentliche Rolle gespielt haben, lässt sich im operativen Einsatz nur schwer nutzen.

Unser Scoring bei AntsRoute ist daher so konzipiert, dass es verständlich bleibt. Die wichtigsten Komponenten des Scores bleiben nachvollziehbar und analysierbar, insbesondere:

• die Grenzkosten,
• die angewandten Strafpunkte,
• die Machbarkeit,
• die zeitliche Qualität und
• das Umstrukturierungspotenzial.

Dadurch steigt das Verständnis von Managern und Disponenten für die vom Motor getroffenen Abwägungen und auch ihr Vertrauen wird in die vorgeschlagenen Entscheidungen entsprechend gestärkt.

Fazit

In einer modernen Tourenoptimierungs-Engine besteht das Scoring nicht einfach darin, eine zusätzliche Entfernung zu berechnen. Als multikriterielles Bewertungssystem ist es in der Lage, Folgendes zu erfassen:

• die geografische Qualität einer Einfügung,
• ihre zeitliche Robustheit,
• ihre geschäftliche Machbarkeit,
• ihre operative Kohärenz sowie
• ihre zukünftigen Auswirkungen auf die Planung.

Basierend auf dieser Logik geht die Engine über rein lokale Überlegungen hinaus, um Lösungen auf der globalen Ebene des Systems zu priorisieren. Denn bei der „Last-Mile“-Abwicklung ist eine gute Entscheidung nicht nur eine umsetzbare Entscheidung: Es ist eine Entscheidung, die das operative Gleichgewicht der Planung nachhaltig aufrechterhalten kann.