链上镖师 / Chain Biaoshi
COR|时间窗与取送货路由：Steiner旅行商的图缩减与经典—量子混合优化
将必需节点、可选中间节点、服务时限、取送货关系和车辆容量纳入同一条闭合路线
论文提出带时间窗与取送货的Steiner旅行商问题，并用两类数学模型、AFGR图缩减和经典—量子混合求解框架分析复杂路由任务。
- 01：STSP-TWPD同时考虑必需节点访问、可选Steiner节点、时间窗、取送货优先关系和车辆容量。
- 02：论文构建弧基础模型ABF与节点基础模型NBF，两者具有等价的可行空间和最优解。
- 03：AFGR通过无关弧过滤、最短路筛选、孤立节点清理和重新编号压缩图结构。
- 04：实验覆盖60°与80°角度约束，以及必需节点占比0.2至0.6的多类基准实例。
- 05：Gurobi与D-Wave LeapCQMHybrid均参与求解，缩减图在全部测试实例中得到最优解。
从关键客户节点到可执行闭环路线
论文将经典Steiner旅行商问题扩展为STSP-TWPD。车辆从仓库出发并返回仓库，需要访问全部必需客户节点，允许经过可选Steiner节点，路线目标是最小化总行驶时间。每个客户同时关联服务时间窗、取货或送货需求，以及车辆容量约束，模型因此覆盖城市配送、逆向物流和按需服务中的多重运营条件。
01必需节点：每个客户节点在规划周期内服务一次。
02时间约束：服务开始时间需落在节点时间窗内。
03作业约束：取货与送货关系、服务时间和车辆载荷沿路线连续传递。
STSP-TWPD实例类别与拓扑设置（来源：Table 4）
实例生成把网络稀疏度与配送作业放进同一测试框架
基准图由圆周节点和欧氏距离构成，候选边按长度排序后逐步加入，同时满足不相交和最小夹角条件。研究设置60°与80°两类角度阈值，并改变必需节点占比。时间窗由最短路、最长路估计和随机扰动生成，服务时间取5或10，需求包含取货与送货，车辆容量由总需求和随机偏移共同确定。
11. 生成圆周节点并计算候选边距离
22. 按角度阈值筛选边，保持图结构连通
33. 设置必需节点比例、时间窗与服务时间
44. 生成取货需求、送货需求、车辆容量和Big-M参数
STSP-TWPD实例参数与生成规则（来源：Table 5）
ABF与NBF用两种视角表达同一条可行路线
ABF将决策建立在弧与时间步上，直接记录车辆在每个阶段 traversed 的弧。NBF把路由决策组织到节点对上，并保留时间索引来描述服务顺序、时间窗可行性和载荷传递。两类模型都包含路线连续性、客户单次服务、时间一致性、取送货关系与容量限制，论文通过变量映射、约束对应和目标函数对应证明两者数学等价。
阶段 1 路线选择：弧变量记录车辆在时间步上的移动
阶段 2 服务决策：节点变量标记取货或送货操作
阶段 3 时间传播：服务时间与行驶时间共同更新到达时刻
阶段 4 载荷传播：需求变化沿激活弧传递并受容量Q限制
Big-M与容量参数将条件逻辑线性化，使模型保持MILP形式，并兼容Gurobi及D-Wave混合约束求解环境。
AFGR图缩减把冗余弧挡在求解器之前
AFGR首先保留仓库和必需节点相关的候选弧，随后从每个关键节点运行Dijkstra算法，重构关键节点之间的最短路径并标记路径弧。算法继续删除没有剩余关联弧的Steiner节点，最后对弧重新编号并更新图结构。该流程减少模型输入规模，为后续经典或量子混合求解提供更紧凑的网络。
AFGR弧过滤与图缩减算法流程（来源：Algorithm 1 AFGR）
AFGR属于启发式预处理。它保持必需节点之间的连通结构，论文未给出原问题全局最优解必然保留的形式化保证；全部测试实例中的缩减图均得到最优解。
经典搜索与量子退火在混合框架中异步接力
论文将经典模型交给Gurobi求解，并把两类模型部署到D-Wave LeapCQMHybrid平台。混合求解器由经典模块和量子模块组成：经典模块使用局部搜索、禁忌搜索和模拟退火开展大范围搜索，量子模块通过量子退火对候选子问题进行低能量配置采样，两个模块以异步反馈方式持续交换搜索信息。
D-Wave混合求解器的经典模块—量子模块结构（来源：Fig. 1）
1经典模块：探索解空间并构造适合量子处理的子问题
2量子模块：在D-Wave QPU上执行量子退火采样
3反馈机制：返回低能量配置，更新经典搜索轨迹
4调度逻辑：在搜索停滞或需要多样化时调用量子模块
约束组合与图规模共同推高模型计算负担
实验比较STSP-TWPD、STSP-PD和STSP-TW三类模型，并观察节点规模变化下的目标函数趋势。模型维度分析显示，未应用AFGR时，ABF在节点数由4增加到20的过程中，变量数由145增至41,185，约束数由258增至80,853。研究还指出，较高弧密度和更严格拓扑条件会进一步放大模型规模。
图缩减的价值集中体现在模型进入求解器之前：减少弧和节点关联关系，能够同步压低变量数量、约束数量与搜索空间。
三类STSP模型目标函数值随节点规模的变化（来源：Fig. 2）
A1实例中ABF与NBF模型的AFGR规模削减结果（来源：Table A.6）
附录B实例的求解性能曲线（来源：Fig. B.3）
路线图把抽象约束转成空间连接结果
附录路线图展示了模型决策在空间网络中的具体形态。必需节点负责完成客户服务，可选Steiner节点承担路径连接作用，时间窗、取送货顺序和容量条件共同影响路线走向。量子混合实验表汇总目标值、间隙、可行率和耗时，为比较不同模型与求解配置提供统一的结果维度。
路线结构与节点连接示例（来源：Fig. D.13）
不同配置下的路线结构变化（来源：Fig. D.14）
量子混合求解实验结果汇总（来源：Table E.46）
STSP-PD模型的AFGR实验结果（来源：Table E.47）
STSP-TW模型配置与求解性能对比（来源：Table E.48）
模型适用条件与研究边界
论文的实例建立在有向稀疏图、欧氏距离、单位速度车辆、预设时间窗、固定服务时间和给定需求分布等条件上。车辆容量由需求总量加随机偏移确定，Big-M取值依据时间窗、服务时间和最大弧长估计。研究聚焦单车闭环路线，论文未报告多车协同、动态订单、实时交通、随机行驶时间及真实城市配送数据下的外推表现。
适用范围集中在带关键节点、可选中间节点、时间窗和取送货约束的静态路由规划。AFGR的全局最优保留性质、混合求解器的内部量子调用比例，以及更大规模真实网络中的稳定性，论文未报告形式化保证。
论文：Steiner Traveling Salesman Problem with Time Windows and Pickup–Delivery: Integrating classical and quantum optimization
作者：Alessia Ciacco，Francesca Guerriero，Eneko Osaba
期刊：Computers and Operations Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
