FedEx Quantum Optimization for Last-Mile Package Delivery Routing

The Problem

FedEx Ground processes millions of package deliveries daily across a network of hub-and-spoke facilities. At each hub, packages must be assigned to drivers and sequenced into delivery routes that respect time window commitments (business deliveries before close of business, residential windows specified by customers), vehicle weight and volume limits, and driver shift lengths. This is a vehicle routing problem with time windows (VRPTW), one of the most intensively studied problems in operations research and one that remains NP-hard.

FedEx’s existing routing system uses Google OR-Tools with a combination of local search heuristics and constraint propagation. It produces good routes but is run once each morning with limited ability to re-optimize during the day as conditions change (failed deliveries, traffic, additional pickups). The question FedEx brought to D-Wave was whether quantum-hybrid optimization could find shorter total routes on the morning planning problem, and do so fast enough to support mid-day re-routing.

CQM Formulation

D-Wave’s Constrained Quadratic Model (CQM) is a more expressive problem format than the binary QUBO used in earlier D-Wave systems. CQM supports integer variables natively, which makes vehicle routing formulation more natural: route assignments can be integer-valued rather than requiring one-hot binary expansions, reducing the problem size significantly.

The FedEx CQM encoded three variable types: binary stop-assignment variables indicating whether driver D visits stop S, integer sequence variables ordering stops within each driver’s route, and continuous slack variables absorbing time window flexibility. Constraints included total mileage per driver (shift time limit), vehicle weight capacity, and time window feasibility for each stop.

import dimod
from dwave.system import LeapHybridCQMSampler

cqm = dimod.ConstrainedQuadraticModel()

# Binary: x[d][s] = 1 if driver d is assigned stop s
x = {}
for d in drivers:
    for s in stops:
        x[d, s] = dimod.Binary(f"x_{d}_{s}")
        cqm.add_variable(dimod.BINARY, f"x_{d}_{s}")

# Integer: sequence position of stop s in driver d's route (0 = unassigned)
seq = {}
for d in drivers:
    for s in stops:
        seq[d, s] = dimod.Integer(f"seq_{d}_{s}", lower_bound=0, upper_bound=len(stops))
        cqm.add_variable(dimod.INTEGER, f"seq_{d}_{s}", lower_bound=0, upper_bound=len(stops))

# Objective: minimize total route mileage
objective = dimod.QuadraticModel()
for d in drivers:
    for s1 in stops:
        for s2 in stops:
            if s1 != s2:
                dist = distance_matrix[s1][s2]
                # Add distance cost when s1 and s2 are consecutive in driver d's route
                # (approximated via sequence variable difference penalty)
                objective.add_quadratic(f"x_{d}_{s1}", f"x_{d}_{s2}", dist * 0.01)
cqm.set_objective(objective)

# Constraint: each stop assigned to exactly one driver
for s in stops:
    cqm.add_constraint(
        sum(x[d, s] for d in drivers) == 1,
        label=f"assign_{s}"
    )

# Constraint: driver shift mileage limit
for d in drivers:
    cqm.add_constraint(
        sum(x[d, s] * stop_service_time[s] for s in stops) <= shift_duration[d],
        label=f"shift_{d}"
    )

sampler = LeapHybridCQMSampler()
result = sampler.sample_cqm(cqm, time_limit=60)
feasible = result.filter(lambda s: s.is_feasible)
best = feasible.first.sample

Rolling Horizon Decomposition

The full Memphis hub problem involves 500 drivers and 15,000 stops, far larger than any quantum or quantum-hybrid solver can handle as a monolithic problem. The team used a rolling horizon decomposition: the network was partitioned into geographic clusters of roughly 30 stops each using classical k-means clustering, and the CQM solver optimized driver assignments and sequencing within each cluster independently. A classical recombination step then resolved boundary conflicts where drivers cross cluster boundaries.

This decomposition is not quantum-specific: classical solvers use similar strategies. The advantage of the CQM approach is that within each cluster, the solver explores the integer-and-binary mixed solution space more effectively than OR-Tools’ local search, particularly for clusters with dense time window constraints that create many infeasible moves for local search.

Results and Comparison to OR-Tools

On the Memphis hub test network, the CQM-based approach reduced total route mileage by 6% compared to FedEx’s existing OR-Tools solution run with a 10-minute time limit. Both solvers used the same 60-minute total compute budget for the full network. The CQM solver spent that budget running 30 parallel cluster subproblems via the LeapHybridCQMSampler cloud API, while OR-Tools ran sequentially across clusters.

A 6% mileage reduction across FedEx Ground’s full network would translate to meaningful reductions in fuel costs and driver hours. FedEx is extending the pilot to additional hubs and testing mid-day re-routing scenarios where the CQM solver re-optimizes clusters affected by failed delivery attempts, a use case where its speed advantage over re-running a full OR-Tools solve is most pronounced.