This article focuses on smart logistics route optimization in MathorCup Problem A. The core idea is to unify TSP, TSP with Time Windows, and multi-vehicle capacity-constrained VRPTW into QUBO formulations, then solve them with the Kaiwu SDK and a coherent Ising machine. It addresses three major challenges: complex multi-constraint modeling, limited qubit capacity, and poor scalability in large routing problems. Keywords: QUBO, coherent Ising machine, VRPTW.
Technical Specifications at a Glance
| Parameter | Details |
|---|---|
| Language | Python |
| Optimization Paradigm | QUBO / Ising |
| Solver Platform | Kaiwu SDK + 550-qubit coherent Ising machine |
| Problem Types | TSP, TSPTW, VRPTW |
| Input Data | Travel time matrix, time windows, demand, service duration |
| Core Dependencies | kaiwu, numpy, pandas, matplotlib |
| Scale Characteristics | Direct solving for 15 customers, block-based solving for 50 customers |
| Stars | Not provided in the source material |
This Method Unifies Logistics Routing Problems into a Quantum-Solvable Model
The original problem spans four levels: single-vehicle TSP, TSP with Time Windows, large-scale 50-customer route planning, and multi-vehicle VRPTW with capacity constraints. At their core, all of them are combinatorial optimization problems, but their constraint structures differ.
The value of QUBO is that it expresses the objective function and constraints within one quadratic energy function. This makes it possible to embed unique visitation, time-window penalties, and vehicle capacity limits into a single framework that quantum hardware or quantum-inspired solvers can process directly.
The minimal core form of QUBO modeling is shown below
# x[i, t] indicates whether customer i is visited at step t
# Objective: minimize route cost + constraint penalties
E = path_cost + penalty_visit + penalty_step
# Each customer can be visited only once
penalty_visit = P * sum((1 - sum(x[i, t] for t in range(N))) ** 2 for i in range(N))
# Each step can visit only one customer
penalty_step = P * sum((1 - sum(x[i, t] for i in range(N))) ** 2 for t in range(N))This code illustrates the basic TSP-QUBO skeleton: the objective drives better solutions, while penalty terms enforce feasibility.
Time Window and Capacity Constraints Are Absorbed into the Energy Function Through Penalty Terms
For time-window-constrained problems, the main difficulty is not the route itself but matching service times to valid time intervals. The original approach applies quadratic penalties to both early and late arrivals, so any route that violates a time window becomes significantly worse in energy.
Capacity constraints are modeled through vehicle assignment variables (y_{k,i}). Each customer must be assigned to exactly one vehicle, and the total demand carried by each vehicle must not exceed its rated capacity. This extends the model from single-route optimization to joint optimization over assignment and sequencing.
The encoding of time-window and load constraints is shown below
# Time-window penalty: both early and late arrivals increase the cost
for i in range(N):
t_arr = sum((t + 1) * 8 * x[i, t] for t in range(N)) # Discretely estimated arrival time
early_penalty = M1 * max(0, a[i + 1] - t_arr) ** 2 # Early-arrival penalty
late_penalty = M2 * max(0, t_arr - b[i + 1]) ** 2 # Late-arrival penalty
# Capacity constraint: apply a squared penalty when overloaded
for k in range(VEHICLE_NUM):
load = sum(q[i + 1] * y[k, i] for i in range(N)) # Compute the total load of vehicle k
overload_penalty = PENALTY * max(0, load - VEHICLE_CAPACITY) ** 2This code shows that the key to QUBO is not enumerating rules explicitly, but folding those rules into computable energy differences.
The Large-Scale 50-Customer Scenario Requires a Block-Based Quantum-Classical Hybrid Strategy
A direct formulation for 50 customers requires roughly 2,500 binary variables, which exceeds the 550-qubit hardware limit. As a result, the problem cannot be sent directly to the machine. The original solution uses a hybrid workflow based on block-wise quantum optimization, classical stitching, and local quantum refinement. This is the most engineering-relevant part of the entire approach.
The strategy first partitions customers into multiple subsets, solves each block independently for a local optimal tour, stitches those sub-routes into a global path with a classical greedy method, and finally performs local re-optimization. Instead of chasing a theoretically closed-form global optimum, it prioritizes hardware feasibility and practical deployability.
The block-based solving process can be summarized as follows
blocks = split_customers(customers, block_size=10) # Split 50 customers into multiple sub-blocks
sub_routes = []
for block in blocks:
route = solve_qubo_with_cim(block) # Call the coherent Ising machine for a local optimum on each block
sub_routes.append(route)
global_route = greedy_merge(sub_routes) # Stitch sub-routes with a classical method
final_route = local_quantum_refine(global_route) # Apply local quantum refinementThis code turns a problem that exceeds hardware capacity into multiple hardware-manageable subproblems, then lets classical algorithms complete the global integration.
Experimental Results Show That the Quantum Approach Remains Feasible Across Multiple Routing Problems
In the 15-customer single-vehicle scenario, the model finds a feasible closed-loop route with a total travel time of 386, with no repeated or missed visits. After adding time-window constraints, the total objective value rises to 472, indicating that the model deliberately accepts a longer route to reduce time-window violations.
In the 50-customer scenario, the block-based strategy produces a complete feasible solution with a total cost of 2,159, proving that the method still works under limited qubit capacity. In the multi-vehicle capacity-constrained setting, the total objective cost is 391 with 8 vehicles, and no overload occurs.
The results are summarized below
| Scenario | Key Result | Notes |
|---|---|---|
| Single-Vehicle TSP | Total time: 386 | Complete route, 100% constraint satisfaction |
| TSP with Time Windows | Total objective: 472 | Reasonable detours introduced to satisfy windows |
| Large-Scale 50-Customer Scenario | Total cost: 2159 | Block strategy breaks the qubit-capacity barrier |
| Multi-Vehicle VRPTW | Cost with 8 vehicles: 391 | Balanced loads, no obvious redundancy |
This set of results shows that the unified QUBO framework offers both expressive power and engineering flexibility.
Sensitivity Analysis Shows That 6 to 10 Vehicles Is the Best Cost-Efficiency Range
As the number of vehicles increases from 4 to 12, the total cost keeps decreasing, but the rate of improvement slows significantly after 10 vehicles. In other words, adding more vehicles can still reduce cost, but the marginal benefit becomes very weak.
A more practical conclusion is therefore not that more vehicles are always better, but that 6 to 10 vehicles delivers a better overall operational balance. This insight is more useful for both competition modeling and real-world logistics scheduling.
The Implementation Uses the Kaiwu SDK to Complete the Full Modeling-to-Solving Loop
The original code reads node attributes and the travel time matrix from Excel, then defines route variables (x) and vehicle assignment variables (y), builds travel cost, time-window penalties, unique-visit penalties, and load penalties, and finally uses simulated annealing as a prior check to validate the model.
This step matters: even if the final target is a coherent Ising machine, validating the energy function with a classical solver first can significantly reduce tuning cost and modeling errors.
A simplified solver entry point is shown below
solver = kw.solver.SimulatedAnnealingSolver(
num_reads=200,
num_sweeps=200000,
temperature=15.0
)
result = solver.solve(qubo) # Validate the QUBO model with classical annealing first
best_sample = result.best_sample # Extract the best binary solution
best_energy = result.best_energy # Read the best objective valueThis code provides a baseline solve for the QUBO model and a verifiable reference for later deployment on quantum hardware.
The Strength of This Approach Lies in Its Unified Formulation, While Its Limits Come from Penalty Tuning and Dynamic Scenarios
This approach has three clear strengths. First, TSP, TSPTW, and VRPTW can share one QUBO modeling language. Second, quantum and classical methods can be combined seamlessly. Third, the block mechanism makes the approach scalable to larger customer sets.
Its limitations are equally clear. Large-scale problems still depend on classical stitching. Penalty coefficients require manual tuning. The model does not yet incorporate dynamic orders, real-time traffic, multiple depots, or heterogeneous fleets.
FAQ
Q1: Why is VRPTW well suited for conversion into QUBO?
A: Because route order, unique visitation, time windows, and vehicle load can all be written as quadratic penalty terms and unified into one energy function, which makes them suitable for quantum optimization.
Q2: Why can the 50-customer problem not be sent directly to the coherent Ising machine?
A: A direct formulation requires about 2,500 variables, which exceeds the capacity of 550-qubit hardware. The problem must therefore be partitioned into customer blocks first, and the resulting sub-routes must then be stitched together classically.
Q3: What is the most valuable engineering takeaway from this method?
A: It is not a single quantum solver, but the hybrid architecture of QUBO modeling, block partitioning, classical stitching, and local quantum refinement. That design is much closer to real deployment constraints.
Core Summary: This article reconstructs the original MathorCup Problem A materials and systematically explains how to map TSP, TSPTW, and capacity-constrained VRPTW into a unified QUBO formulation, then solve them with the Kaiwu SDK and a 550-qubit coherent Ising machine through a quantum-classical hybrid workflow covering modeling, block strategies, result analysis, and implementation.