QPRIMORA · QUANTUM COMPUTING DEMO

车辆路径规划

Vehicle Routing Problem · VRP

一个配送中心有多辆车和多个客户。 每个客户应该分配给哪辆车? 每辆车又应该按照什么顺序访问客户, 才能使所有车辆的总行驶距离最短?

与 TSP 相比,VRP 多出了一层关键决策: 不仅需要决定“访问顺序”, 还必须同时决定“每个客户由哪辆车负责”。
01 · YOUR PROBLEM

设置配送问题

6

方形节点代表配送中心。 所有车辆均从配送中心出发, 完成配送后返回同一配送中心。

配送地图
02 · QPRIMORA TRANSFORMATION

QPRIMORA 如何理解车辆路径问题

REAL-WORLD PROBLEM 完成全部客户配送
↓
CUSTOMER ASSIGNMENT 每个客户由哪辆车负责?
↓
ROUTE ORDER 每辆车应该按照什么顺序访问?
↓
CONSTRAINTS 每个客户必须且只能访问一次
↓
REPRESENTATION QUBO
↓
QPRIMORA PRIMITIVE Multi-Vehicle Combinatorial Optimization
QPRIMORA · INSIDE THE TRANSFORMATION

逐层查看问题转换

A · CUSTOMER ASSIGNMENT

VRP 的第一个问题已经不只是访问顺序。 对于每个客户 i 和车辆 v, 首先需要决定客户属于哪辆车。

yi,v ∈ {0,1}

y(i,v)=1 表示客户 i 被分配给车辆 v。

B · ROUTE VARIABLES

随后需要决定车辆 v 是否从地点 i 直接行驶到地点 j。

xi,j,v ∈ {0,1}
C · CONSTRAINTS
每个客户访问一次
Σv yi,v = 1
路线连续性
incoming = outgoing
从配送中心出发
Depot → Route
返回配送中心
Route → Depot
D · OBJECTIVE

目标是最小化所有车辆行驶距离之和。

min Σv,i,j di,j xi,j,v
E · QUBO

路线距离、客户分配和路线约束 可以统一编码进一个二次二进制优化目标。

E(x,y) = Distance + A·AssignmentPenalty + B·RoutePenalty
VRP → Binary Variables → QUBO
F · QAOA + VIRTUAL QPU
QUBO → Cost Hamiltonian → QAOA → Virtual QPU → Measurement

量子优化路径尝试提高低成本车辆路径状态 在测量结果中出现的概率。

03 · COMPUTE

同时运行两种计算路径

CLASSICAL

普通精确搜索

客户位置 ↓ 车辆分配 ↓ 路线排列组合 ↓ 最小总距离
QUANTUM PATH

Virtual QPU

QUBO ↓ Cost Hamiltonian ↓ QAOA ↓ Virtual QPU ↓ Measurement
04 · WHY VRP IS HARD

为什么 VRP 比 TSP 更复杂?

01 客户分配

首先需要决定每个客户由哪辆车服务。

02 访问顺序

然后还需要优化每辆车内部的客户访问顺序。

03 决策相互耦合

只改变一个客户的车辆归属, 就可能同时改变多条最优路线。

QPRIMORA ARCHITECTURE

从物流需求到 QPU 执行

配送问题 → Representation → Primitive → Algorithm → Compiler → Virtual QPU → Real QPU

用户只需要描述现实中的物流目标, QPRIMORA 负责完成通向量子可执行表示的转换路径。