MilleMiglia: realistische Benchmarks für die Middle-Mile-Logistik ohne vertrauliche Daten

Warum fehlen der Middle-Mile-Logistik öffentliche Benchmarks?

Unternehmen, die Middle-Mile-Netze betreiben, behandeln ihre Netzstrukturen und Frachtmengen als vertraulich, deshalb hatte die Forschung kaum realistische Daten zur Verfügung. Im Beitrag von Google Research, der MilleMiglia vorstellt (18. September 2026), argumentieren Aymane Lotfi und Thibaut Cuvelier, dass dieser Mangel die akademische Arbeit an jenem Abschnitt der Lieferkette gebremst hat, der die längsten Strecken umfasst und einen großen Teil der Logistikausgaben verursacht.

Die Logistikforschung hat sich lange auf die beiden Enden der Reise einer Sendung konzentriert. Die erste Meile sammelt Waren bei Herstellern ein, die letzte Meile übergibt sie an Kundinnen und Kunden, und beide werden meist als Tourenplanungsprobleme formuliert, ein Gebiet mit etablierten öffentlichen Benchmark-Bibliotheken. Die Middle Mile liegt dazwischen: Massengut, das auf regionaler oder kontinentaler Ebene zwischen Verteilzentren fließt, etwa für den Onlinehandel, die Filialversorgung, Automobilteile und temperaturgeführte Arzneimittel für Krankenhäuser.

Ohne gemeinsame Instanzen lassen sich veröffentlichte Verfahren nur schwer vergleichen und reproduzieren. MilleMiglia ist die Antwort der Autoren: ein Generator für Netze, die sich statistisch wie echte verhalten, aber nichts enthalten, was einem Betreiber gehört.

Worin unterscheidet sich die Middle Mile von der Tourenplanung?

Auf der ersten und letzten Meile bleibt ein Paket in der Regel von der Abholung bis zur Zustellung auf einem Fahrzeug, und die Planungsfrage lautet, welches Fahrzeug welche Stopps in welcher Reihenfolge anfährt, meist innerhalb eines Tages. Auf der Middle Mile wechselt ein Paket das Fahrzeug. Der Beitrag vergleicht das mit einem Staffellauf: Fracht wird in Zwischenzentren entladen, sortiert, mit anderen Sendungen gebündelt und auf die nächste Abfahrt verladen, manchmal über mehrere Tage.

Das Rechenbeispiel des Beitrags verfolgt ein Paket von einem Hersteller im niederländischen Groningen zu einem Kunden in Versailles bei Paris. Es durchläuft Regionalzentren in Utrecht, Antwerpen und Paris und wartet in Antwerpen auf den Lkw des nächsten Tages, weil der erste nach Paris bereits voll ist. Genau dieses Warten ist der Kern des Problems: Fracht, die einen Anschluss verpasst, steht bis zur nächsten planmäßigen Abfahrt, was erhebliche Verzögerungen verursachen kann.

Die Autoren nennen drei Nebenbedingungen, die sich nicht lockern lassen, ohne den Charakter des Problems zu verändern, und folgern, dass bestehende Solver für Tourenplanungsprobleme deshalb nicht unverändert auf die Middle Mile anwendbar sind.

• Feste Fahrpläne. Fahrzeuge verkehren nach festen Plänen, daher muss ein Plan die Fracht in bereits bestehende Abfahrten einpassen.
• Hub-Durchsatz. Jedes Verteilzentrum kann pro Stunde nur eine begrenzte Menge sortieren oder per Cross-Docking umschlagen.
• Synchronisierung. Eine Sendung kann erst dann mit einem Fahrzeug abfahren, wenn ein anderes Fahrzeug sie zum Hub gebracht hat.

Fracht als Fluss in einem Raum-Zeit-Graphen modellieren

Die Autoren formulieren die Middle-Mile-Zustellung als Mehrgüterflussproblem auf einem Raum-Zeit-Graphen. Jeder Knoten steht für ein Verteilzentrum zu einem bestimmten Zeitschritt. Eine Kante befördert Fracht entweder mit einem Fahrzeug zwischen Zentren oder hält sie bis zu einem späteren Zeitschritt im selben Zentrum, was Lagerung und Sortierung abbildet.

Die Konferenzpräsentation der Autoren aus dem Jahr 2024 fasst die Aufgabe knapp zusammen. Gegeben sind Hubs, Linien mit getakteten Umläufen, Fahrzeuge mit begrenzter Kapazität und eine Menge von Sendungen, jeweils mit Ursprung, Ziel und Menge, die über einen Planungshorizont bekannt werden. Ziel ist es, jede Sendung zu möglichst geringen Kosten an ihr Ziel zu bringen. Die Zeit läuft nur vorwärts, daher ist der Graph azyklisch, mit Wartekanten an jedem Hub und Fahrkanten für jeden Linienumlauf.

Die Folien beschreiben die Bibliothek als aufbauend auf früheren Arbeiten von Eberhard, Cuvelier, Valko und De Backer (2023), die das Routing von Paketen auf der Middle Mile als zielkonditionierten Markov-Entscheidungsprozess formulierten und mit einer Kombination aus graphbasierten neuronalen Netzen und modellfreiem Reinforcement Learning angingen.

Wie erzeugt MilleMiglia ein realistisches Netz?

MilleMiglia baut eine Instanz in zwei Verfahren auf: zuerst das Logistiknetz, danach die Sendungen, die es durchqueren müssen. Jeder Schritt zieht Stichproben aus statistischen Verteilungen, sodass das Ergebnis einem echten Netz in Form und Größe ähnelt, ohne Datensätze eines Betreibers zu kopieren. Laut Beitrag verbinden die Verteilungen Informationen, die Branchenakteure veröffentlichen, mit Daten, die vertraulich offengelegt wurden.

Analyse: Da jede Sendung aus einem Pfad gezogen wird, der im erzeugten Fahrplan existiert, scheint jede Sendung konstruktionsbedingt mindestens eine planmäßige Route zu haben, Kapazitäten außer Acht gelassen. Das passt gut zum Benchmarking, bedeutet aber auch, dass eine Standardinstanz kaum prüft, wie ein Solver mit Fracht ohne jede brauchbare Verbindung umgeht.

• Hub-Graph. Nutzer legen die Zahl der Hubs und die Graphdichte fest. Die Folien von 2024 und das README des Repositorys beschreiben einen Barabási-Albert-Zufallsgraphen (laut Folien in modifizierter Form), der einige stark vernetzte Hubs hervorbringt; der Beitrag beschreibt, wie Zentren mit Gravitationsmodellen oder räumlichem Clustering nach Bevölkerungs- und Industriedichte platziert werden.
• Linien und Umläufe. Linien sind Pfade durch den Hub-Graphen, wobei Kanten proportional zum Knotengrad gezogen werden. Umläufe versehen jede Linie anschließend mit Abfahrts- und Ankunftszeiten aus einer Gleichverteilung. Der Beitrag merkt an, dass Fahrpläne entweder zwei große Zentren oder ein großes Zentrum mit seinen kleineren Nachbarn verbinden, statt beliebige Paare.
• Fahrzeuge. Jeder Linienumlauf erhält ein Fahrzeug. Seine Kapazität stammt aus einer Gleichverteilung, und seine Kosten steigen proportional zu dieser Kapazität.
• Sendungen. Ursprung, Abfahrtszeit, Ziel und Ankunftszeit jeder Sendung ergeben sich aus einem zufällig gezogenen Pfad durch das Raum-Zeit-Netz, und die Sendungsgrößen folgen einer Lomax-Verteilung.

Ein Dateiformat vom Spielproblem bis zum kontinentalen Netz

Jede erzeugte Instanz wird in eine einzige Protocol-Buffers-Datei geschrieben. Das hält die Daten kompakt und für Solver in vielen Programmiersprachen lesbar. Der Generator selbst ist eine optimierte C++-Bibliothek, und laut HAL-Abstract kann er Instanzen mit vielen Hubs und Sendungen erzeugen.

Die Autoren stellen dem die Tourenplanung gegenüber, bei der getrennte Benchmark-Familien Kapazitäten (CVRP), Zeitfenster (VRPTW) oder Abholung und Zustellung mit Zeitfenstern (PDPTW) abdecken. MilleMiglia nutzt ein einziges Format, das die prägenden Middle-Mile-Nebenbedingungen gemeinsam abbilden soll: feste Fahrpläne, Durchsatzgrenzen der Hubs und Umschlagvoraussetzungen.

Das Schema im Repository definiert eine Instanz als benanntes Logistiknetz plus eine Liste von Sendungen. Das Netz enthält Hubs mit Kartenpositionen, Linien mit geordneten Stopps, Umläufe mit Ankunfts- und Abfahrtsfenstern und einem Festpreis, Fahrzeuge mit Kapazitäten und Kosten, eine Distanzmatrix sowie einen Zeitschritt für die Diskretisierung. Die erwartete Ankunftszeit einer Sendung ist als weiche Nebenbedingung markiert, ihr Erlös ist optional.

Der Beitrag verweist zudem auf maschinelles Lernen, da der Generator sehr große Datensätze für das Training von Modellen erzeugen kann. Der HAL-Abstract nennt diesen Einsatz neben dem Benchmarking und der Untersuchung, wie Netzkonfiguration und Sendungsmerkmale die Gesamteffizienz beeinflussen. Die Autoren wollen Instanzen in einer Bandbreite von Größen bereitstellen.

• Klein. Vergleichbar mit akademischen Spielproblemen und geeignet, um exakte Algorithmen zu testen.
• Industriell. Große, kontinentweite Probleme, die Heuristiken oder Metaheuristiken erfordern, um gute Lösungen zu finden.
• Dazwischen. Mittlere Größen und Schwierigkeitsgrade für abgestufte Tests zwischen den beiden Extremen.

Was zeigen die Quellen, und was bleibt offen?

Die Quellen stellen ein Werkzeug vor, keine Ergebnisse. Weder der Beitrag noch die HAL-Hinterlegung berichtet Solver-Benchmarks, Generierungszeiten oder einen quantitativen Vergleich mit echten Netzen. Der HAL-Eintrag enthält die Präsentation mit 22 Folien, die auf der 33. European Conference on Operational Research 2024 in Kopenhagen gehalten wurde, sowie einen Abstract.

Die Folien stellen zwar einen erzeugten Hub-Graphen einem echten gegenüber und zeigen die Verteilung der Sendungsgrößen, doch das stützt den Realismusanspruch visuell, nicht statistisch. Als künftige Arbeit nennen die Autoren zwei Punkte: komplexere Merkmale in den Generator aufzunehmen und Rückmeldungen aus der Forschungsgemeinschaft einzuholen, um ihn zu verfeinern.

Analyse: Drei Punkte verdienen Beachtung, bevor man MilleMiglia-Instanzen als repräsentativ behandelt. Erstens beschreiben die Quellen den Generator in unterschiedlichen Stadien: Die Folien von 2024 und das README stellen einen Barabási-Albert-Hub-Graphen in den Mittelpunkt, der Beitrag beschreibt Gravitations- und Clustering-Modelle; maßgeblich ist daher der aktuelle Code. Zweitens enthält ein Hub-Eintrag in der von uns geprüften Schemadatei nur einen Namen und eine Position; wer Durchsatzgrenzen für Hubs benötigt, sollte prüfen, wie die aktuelle Version sie abbildet. Drittens ist der Realismus konstruktiv angelegt und wurde noch nicht an zurückgehaltenen Betreiberdaten gemessen.

Warum Benchmarks für die Middle-Mile-Logistik in der angewandten Optimierung zählen

Erst gemeinsame Benchmarks machen Optimierungsverfahren vergleichbar. Die Tourenplanung hat CVRPLIB, und die Autoren sehen MilleMiglia als ersten Schritt zu einer ähnlichen Standardsammlung für die Middle-Mile-Optimierung. Setzt die Forschung sie ein, ließen sich Aussagen über einen neuen Solver oder eine gelernte Strategie an gemeinsamen Instanzen prüfen statt an privaten Daten, die niemand sonst einsehen kann.

Analyse: Für Organisationen, die Frachtnetze planen, hat ein solcher Generator praktischen Nutzen über akademische Arbeiten hinaus. Synthetische Logistikdaten dieser Art lassen sich mit externen Solver-Entwicklern teilen, ohne Hub-Standorte oder Mengen offenzulegen, sie lassen sich hochskalieren, um ein Verfahren vor dem Kontakt mit Produktionsdaten zu belasten, und systematisch variieren, um zu sehen, wie Netzdichte oder Sendungsmix die Kosten verändern. Es gilt der übliche Vorbehalt für synthetische Daten: Ergebnisse auf erzeugten Instanzen zeigen, wie sich ein Verfahren verhält, und müssen im eigenen Netz bestätigt werden, bevor operative Entscheidungen fallen.

Code, Lizenz und nächste Schritte

MilleMiglia steht auf GitHub unter der Lizenz Apache 2.0 bereit, und Release v0.0.1 enthält eine Beispielinstanz im Textformat von Protocol Buffers. Das README erklärt, wie man den Generator mit CMake baut und über die Kommandozeile startet, wobei Werte wie die Zahl der Hubs, Sendungen und Linien, die maximale Linienlänge und die maximale Zahl der Umläufe pro Linie gesetzt werden; das Beispiel verwendet 100 Hubs und 20 Sendungen.

MilleMiglia ist das Ergebnis fortlaufender gemeinsamer Arbeit von Google und akademischen Partnern an der Universität Brescia und der ENPC Paris. Die Autoren entwickeln nach eigenen Angaben einen Solver und eine API speziell für Middle-Mile-Abläufe und möchten einen Wettbewerb starten, der akademische und industrielle Solver-Entwickler für das Problem gewinnt.

Fragen und Antworten

Quellen

1. Lotfi, A., Petris, M., Cuvelier, T., De Backer, B., & Archetti, C. (2024). A novel instance generator for simulating middle-mile logistics networks [Conference presentation]. 33rd European Conference on Operational Research (EURO 2024), Copenhagen, Denmark. HAL: hal-04755189. https://hal.science/hal-04755189v1 (externe Website)
2. Google OR-Tools. (2026). MilleMiglia: Instance generator for middle mile logistics optimization (Version 0.0.1) [Computer software]. GitHub. https://github.com/or-tools/millemiglia (externe Website)
3. Eberhard, O., Cuvelier, T., Valko, M., & De Backer, B. (2023). Middle-mile logistics through the lens of goal-conditioned reinforcement learning. NeurIPS 2023 Workshop on Goal-Conditioned Reinforcement Learning. arXiv:2605.02461. https://arxiv.org/abs/2605.02461 (externe Website)
4. Albert, R., & Barabási, A.-L. (2000). Topology of evolving networks: Local events and universality. Physical Review Letters, 85(24), 5234-5237. https://doi.org/10.1103/PhysRevLett.85.5234 (externe Website)