Hybrid Quantum-Classical Optimization Workflows for the Shipment Selection Problem

Hybrid Quantum-Classical Optimization for Shipment Selection in Electric Freight Logistics

Introduction

The paper "Hybrid Quantum-Classical Optimization Workflows for the Shipment Selection Problem" (2604.11758) presents a novel framework targeting the Shipment Selection Problem (SSP) in the context of large-scale electric vehicle freight operations. SSP arises when unforeseen disruptions, predominantly shipment cancellations, create idle intervals ("gaps") in pre-optimized fleet schedules. Such gaps diminish vehicle utilization and revenue, especially under the restrictive operational constraints of electric fleets. Optimal remediation of these gaps requires solving a combinatorial assignment problem characterized by intricate quadratic dependencies between insertions across gaps—a challenge not explicitly addressed by traditional local-insertion heuristics or large neighborhood search methods.

Figure 1: The classical gap-filling scenario: idle gaps (black blocks) are filled from unassigned shipments using a hybrid workflow integrating quantum optimization within existing vehicle routing solvers.

In this context, the authors introduce a hybrid quantum-classical workflow combining the strengths of commercial Electric Vehicle Routing Problem (E-VRP) solvers with quantum optimization techniques, leveraging recent advances in quantum gate-model algorithms. The goal is to surpass the performance of state-of-the-art classical re-optimization—particularly in capturing the joint effects of assignments across multiple vehicle gaps—while remaining deployable within real logistics pipelines.

Problem Formulation

Mixed-Integer Quadratic Programming (MIQP) Structure

SSP is cast as a Mixed-Integer Quadratic Program where each gap $g \in G$ is assigned from a set of feasible shipment sequences $Q_g$. Decision variables $x_{gq}$ indicate selection, and the objective is to maximize: $$\sum_{g \in G} \sum_{q \in Q_g} v_{gq} x_{gq} + \sum_{(q_1,q_2)} w_{q_1q_2} x_{g_1q_1} x_{g_2q_2}$$ where linear terms capture marginal benefit per sequence and quadratic terms $w_{q_1q_2}$ encode pairwise cost interactions—e.g., temporal/geographical overlaps that influence operational risk or downstream efficiency.

The model enforces real-world constraints: per-gap sequence capacity, exclusivity (no shipment used more than once), and at-most-one-sequence-per-gap. This structure generalizes classical QAP and routing formulations, but uniquely incorporates compatibility between insertions as a first-class objective, motivated by the limitations of standard VRP-based dynamic repair protocols.

Mapping to Quantum Optimization

To utilize quantum optimization, the MIQP is converted to a QUBO encoding, and subsequently mapped to an Ising cost Hamiltonian $H_C$. The relevant constraints are embedded via quadratic penalty terms. Pairwise interactions are derived from a product of flow matrices (sequence overlaps) and distance matrices (gap proximities), scaled by hyperparameters to control their operational influence.

Iterative-QAOA: Quantum Solution Methodology

The optimization task is addressed via Iterative-QAOA, an extension of the Quantum Approximate Optimization Algorithm. Unlike standard QAOA, Iterative-QAOA eschews outer-loop parameter minimization in favor of a fixed, linear ramp parameter schedule, further augmented with a measurement-driven, biasing warm start updated at each iteration. This approach is computationally efficient and robust across varying instance sizes, reducing reliance on costly classical parameter optimization.

Key distinguishing features:

• Non-variational Warm Start: Biases the initial circuit state towards low-energy solutions found thus far.
• Depth Scaling: The quantum circuit depth $p$ adapts slightly based on problem size but avoids exponential expansion.
• Scalable Encoding: Capacity and assignment constraints are handled efficiently with penalties and post-measurement feasibility checks.

Simulation strategy includes both statevector (for $n \leq 32)$ and MPS-based (for $n>32$) quantum hardware emulators, with custom pruning of Hamiltonian terms for tractability on large instances.

Industrial Workflow Integration

The quantum routine is embedded within Einride's live logistics optimization workflow as follows:

1. Disrupted Instance Preparation: Real anonymized schedule data is subjected to stochastic cancellation scenarios, mimicking operational disruptions.
2. Classical Candidate Extraction: All feasible insertions per gap are compiled using the production-grade E-VRP solver.
3. Quantum Optimization: The MIQP/QUBO is solved via Iterative-QAOA.
4. Post-Processing: Solutions are refined with a lightweight classical local search heuristic to ensure strict feasibility/cost improvements.
5. Hybrid Evaluation: Quantum solutions serve either as direct assignments (Q) or as warm starts (QWS) for the classical E-VRP solver for further re-optimization.

   Figure 2: Weekly schedule showing idle (black) bars due to shipment cancellations; quantum refinement is applied to the variable gap window at the end (potential for extension with greater quantum resources).

Evaluation, Results, and Analysis

Benchmarking and Simulation Protocol

Evaluation is performed on eight real-world weekly fleet schedules under realistic (moderate) disruption scenarios. Solution quality is judged by application-level metrics:

• Shipments Delivered (SD): Primary service metric.
• Schedule Compatibility Score (SCS): Encapsulates pairwise operational correlation between insertions.
• Total Drive Distance (TDD) and TDD/SD: Routing efficiency indicators.

Baseline comparisons are made versus (1) the cold-start classical solver EOS, (2) direct quantum assignment (Q), and (3) quantum warm-start refinement (QWS).

Quantum Algorithm Performance

Noiseless Iterative-QAOA simulations on instances up to 130 qubits demonstrate effective concentration of solution sampling in the low-energy regime after a modest number of iterations. Convergence is consistently rapid, with peaked distributions tightly localized around minimum-energy assignments.

Strong empirical results:

• Best-case improvements: QWS yields up to $+12.1\%$ increase in SD, and $Q_g$0 decrease in TDD in individual scenarios, with best-case SCS gains of $Q_g$1.
• Average-case: QWS delivers consistent, though more modest, average improvements ($Q_g$2 in SD, $Q_g$3 in TDD/SD), with operational cost remaining flat.
• Compatibility signature: The direct quantum assignments show robust improvement in SCS, underlining the advantage in capturing quadratic (assignment-assignment) effects that classical greedy heuristics typically miss.

Hybrid deployment is essential: while raw quantum solutions may not always outperform cold-start scheduling in raw delivered shipments, acting as a structured warm start for the classical solver yields the most substantial and consistent operational gains.

Figure 1: The hybrid quantum-classical framework replaces classical gap filling with compatibility-aware insertions optimized via quantum methods.

Figure 2: Dynamic gap windowing in a weekly schedule, illustrating the region accessible under existing qubit limits.

Implications and Future Directions

This work establishes the operational viability of embedding near-term quantum optimization modules in real-world logistics pipelines—specifically for stochastic, combinatorial assignment problems with non-trivial pairwise dependencies. The Iterative-QAOA method demonstrates both robustness (non-variational scheduling, minimal parameter tuning) and scalability (instances up to 130 qubits), with simulation evidence for substantial gains in key logistics KPIs when coupled with classical refinement.

Theoretical implications:

• Demonstrates how quadratic assignment structures in logistics (beyond linear routing optimizations) can be addressed via quantum frameworks.
• Provides empirical evidence supporting linear-ramp fixed-parameter QAOA as a resource-efficient alternative to variational QAOA in practical hybrid workflows.

Practical considerations:

• The classical refinement step is lightweight and effective, bridging quantum output to operational feasibility and augmenting performance.
• The workflow remains effective under current and near-term hardware constraints, with scope for further scale-up as quantum hardware evolves.

Future research avenues:

• Extending interaction modeling to higher-order objective terms, incorporating multi-gap/correlation context beyond pairwise.
• Systematic calibration of quadratic-weight hyperparameters to target complex, multi-tiered operational objectives.
• Direct quantum hardware deployment to assess fidelity-to-simulation transfer and circuit-depth/resource trade-offs.
• Investigating hybrid quantum-classical workflow automation and integration for continuous-disruption repair in large fleets.

Conclusion

The presented hybrid pipeline for the Shipment Selection Problem in electric freight logistics clearly demonstrates that quantum optimization—in the form of non-variational, linear-ramp Iterative-QAOA—can generate actionable, compatibility-aware candidate assignments that materially enhance classical schedule repair workflows. The combination leverages the expressive power of quantum quadratic assignment, makes efficient use of classical heuristics, and aligns with the trajectory of scalable quantum hardware developments. The findings signal a strong case for focused R&D on hybrid quantum-classical architectures for industrial-scale, stochastic, and combinatorial logistics optimization.