MilleMiglia: A realistic instance generator for middle-mile logistics

How can a Dutch poffert arrive at your door, 450 miles (700 km) away, the very next day? It’s thanks to careful logistics optimization — especially the middle-mile segment. This part of the journey covers the longest distance, represents a huge portion of the overall costs, and most importantly dictates whether your poffert arrives fresh or stale.

Logistics research has historically focused on the first mile (moving goods from producers to initial consolidation points) and the last mile (delivering to the consumer). Both stages are typically modeled as variants of the vehicle routing problem (VRP). However, the middle mile, which handles the bulk movement of goods between distribution centers at a regional or continental scale, has received significantly less attention in operational research despite representing a sizable portion of total logistics expenditure. Academic progress in middle-mile optimization has been hindered by a lack of public, high-quality data. Indeed, most logistics companies treat their network topologies and demand volumes as highly sensitive proprietary information.

Middle-mile logistics has many applications in the supply chain. These range from moving goods from factories to consumers in e-commerce and retailers in city centers, to carrying the right parts from individual plants and central storage to car manufacturers and shops. It also includes time-sensitive movements, like transporting temperature-controlled pharmaceuticals between storage facilities and hospitals.

To address the lack of standardized data for this domain, in “A Novel Instance Generator for Simulating Middle-Mile Logistics Networks”, we introduce MilleMiglia, a C++ instance generator designed to create realistic benchmarks for middle-mile delivery problems. This work serves as a foundational building block to enable future research results. In this post, we explore the unique constraints of the middle mile and how MilleMiglia successfully captures them to generate realistic, privacy-preserving data. The source code and documentation are available on GitHub.

The distinction between first-, middle- and last-mile logistics lies in the journey of an individual shipment. Throughout this journey, the primary operational goal is to efficiently use a fleet of vehicles to visit multiple locations. Consider the example of a manufacturer that sells goods on a typical online marketplace to reach individual consumers.

In first- and last-mile logistics, a specific shipment remains in a single vehicle from its origin (the factory in the first mile, the distribution center in the last mile) to its destination (the distribution center in the first mile, the customer in the last mile). These VRPs involve optimizing a fleet of several vehicles over a limited time span, usually a single day. The optimization challenge is essentially one of assignment and sequencing: determining which vehicle handles which set of shipments, and in what order.

In our example, the first mile corresponds to the collection of the items that have been sold by the manufacturer (e.g., pofferts) while the last mile covers the final delivery to the consumers (some of them being quite hungry!). In both cases, a single truck transports goods to or from the regional distribution center. However, if the manufacturer and the consumer are in different regions, middle-mile logistics bridge the gap between far-away distribution centers. For instance, goods from a manufacturer in Groningen (Netherlands) would first move to the regional distribution center in Utrecht, travel to another center in Paris (France) before being delivered to a consumer in Versailles.

In contrast to the first and last mile, the middle mile functions as a relay race. A single shipment may be transported by several different vehicles across a continental network before reaching its final destination, maybe a week after departing. At intermediate distribution centers, the shipment may be unloaded, sorted by destination, and consolidated with other freight before being loaded onto the next vehicle. This creates a complex synchronization problem: the shipment must arrive at a distribution center within a specific time window to catch its scheduled outgoing truck. If it misses its scheduled connection, it will have to sit at the distribution center until the next cycle, leading to significant delays.

In our example, once the manufacturer’s goods arrive in the Utrecht regional center, they are loaded onto the first truck for Antwerp (Belgium) to arrive the same day. Because the most immediate truck to Paris is full, and let’s say the customer opted for standard shipping, the goods take the second truck the following day from Antwerp to Paris. The parcel arrives in Paris on the night of the second day, where it enters the last-mile network for the final delivery to the customer the next day.

The mathematical structure of middle-mile delivery differs from the standard VRP in several key ways.

In a traditional VRP, such as those solved by open-source tools like OR-Tools or specialized APIs like Google Maps Platform Route Optimization (GMPRO), the goal is typically to optimize tours for a fleet. The focus is on vehicle routing and sequencing of stops to meet tight customer deadlines. Unlike last-mile delivery, middle-mile logistics has the added flexibility of moving between trucks. We model this added dimension as a multi-commodity flow problem on a space-time graph. In these models:

• Nodes: Represent a specific distribution center at a specific time interval.
• Arcs: Represent vehicle movements over time, or a shipment being held at a distribution center (storage/sorting by destination).

While many academic VRPs are defined with few constraints, middle-mile operational constraints are difficult to relax without distorting the structure of the operational problem at hand:

1. Fixed schedules: Vehicles typically operate on fixed timetables that must be respected.
2. Distribution center throughput: Distribution centers have physical limits on how much volume can be sorted or cross-docked within a given hour.
3. Synchronization: The arrival of one vehicle is the prerequisite for the departure of shipments on a different vehicle.

Because of these dependencies, existing VRP solvers cannot apply to the middle mile. The problem requires a sequence of intermediate distribution centers and assignments across multiple vehicles, often over a multi-day time horizon.

MilleMiglia uses a variety of statistical distributions to ensure that the synthetic networks look like actual distribution networks without revealing any private information:

• Spatial distribution: Distribution centers are placed using gravity models or spatial clustering to reflect real-world population and industrial density.
• Demand: Shipments are generated with origin-destination pairs, following realistic volume and weight distributions.
• Rotations: The generator creates structured vehicle schedules rather than arbitrary connections between nodes, linking either two major distribution centers or a major distribution center and its neighboring, smaller-scale distribution centers.

The distributions interpolate between publicly available information from industrial actors and privately disclosed data.

MilleMiglia is written in C++. It uses Protocol Buffers for data serialization, so that the data in its diversity can be stored in a single file for each instance. Thus, the generated instances are compact and can be easily consumed by solvers written in different programming languages.

Unlike VRP instances, with many variants such as the CVRP (with capacities), VRPTW (with time windows), or PDPTW (pickup and delivery with time windows) to capture diverse operational requirements, the structure of our middle-mile data format embeds all interesting constraints in the same file format: fixed vehicle schedules, distribution-center throughput limits, and complex synchronization prerequisites are all fundamental elements of the problem structure.

The intent is to provide the community with a range of instances:

• Small instances: Equivalent to academic "toy" problems for testing exact algorithms.
• Industrial instances: Large-scale, continent-wide problems. These problems require advanced heuristics or metaheuristics to find good solutions.
• Any size in-between, with instances of medium size and/or hardness.

The generator also enables learning scenarios, as it can create huge data sets to train ML algorithms.

MilleMiglia is the first step toward a standardized benchmarking suite for middle-mile logistics, similar to what CVRPLIB (Capacitated Vehicle Routing Problem Library) provides for the VRP community.

This project comes from an ongoing collaboration between Google and academic partners at UniBrescia and ENPC Paris. Beyond instance generation, we are currently working on a specialized solver and API designed specifically for middle-mile operational problems. This solver aims to leverage the unique structure of middle-mile flows.

By open-sourcing our instance generator, we hope to encourage the broader research community to focus on the operational challenges of the middle mile, leading to more robust and efficient global supply chains. We hope to start a challenge on middle-mile problems to increase the interest from academics and industrial solver developers in this underlooked-but-in-need-of-optimization venue. Anyone interested in the field can start by looking at a sample instance hosted in the GitHub repo.

This research was primarily conducted by Aymane Lotfi during his Student Researcher tenure at Google and by Matteo Petris (now at ENPC Paris), as part of an ongoing collaboration. Thanks to Thibaut Cuvelier and Bruno De Backer for their contributions to this work. Special thanks to Claudia Archetti (now at UniBrescia) for her leadership and support.