链上镖师 / Chain Biaoshi
CIE|服务半径一加，枢纽选址就变难了
CIE 2026：用精确模型和两阶段 matheuristic 处理连续空间单分配枢纽网络
这篇论文把最大服务半径加入连续空间单分配枢纽选址，给出首个求解器可直接处理的 MISOCP 精确模型，并用 DICR2 在更大算例上取得高质量可行解。
- 01：研究对象是无容量、单分配、平面枢纽选址：枢纽可以放在连续二维空间，每个需求点只分配给一个枢纽。
- 02：服务水平用最大 spoke-hub 距离 R 表示，任一被选中的需求点到枢纽分配都必须满足半径限制。
- 03：方法组合包括 MISOCP 精确模型、两种 DICR matheuristic，以及改造后的 PHLGA-SL 遗传算法基线。
研究背景
枢纽辐射式网络常见于运输、物流和通信系统。通过少量枢纽汇聚流量，网络可以减少密集的点到点连接，并利用枢纽间转运的规模经济。经典枢纽选址多把候选枢纽限制在有限站点集合内，实际选址场景中的空间灵活性会被压缩。
本文研究的 PHLP 允许枢纽位于欧氏平面上的任意位置，连续坐标带来非线性距离项和位置分配耦合。作者进一步加入服务水平要求：每个需求点分配到的枢纽必须位于给定半径 R 内，用距离约束表达可达性和服务质量。
论文的切入点很明确：在连续空间枢纽选址中同时处理单分配、无容量和服务半径约束，并给出可作为小规模最优性基准的精确模型。
核心问题
模型中有 n 个需求点、p 个待布局枢纽。每个需求点必须分配给且只分配给一个枢纽，枢纽之间完全连通，所有需求点之间的流量都经由枢纽路径运输。成本由 collection、distribution 和 transfer 三部分构成，转运成本系数低于两端接驳成本。
服务水平约束把可行性和空间布局绑定起来。若需求点 i 被分配给枢纽 k，则对应距离 d_ik 不能超过 R；若没有分配给该枢纽，大 M 项放松该约束。R 越紧，能够覆盖所有需求点的枢纽布局越受限。
精确模型时间上限
2小时
AP 对比实验中 MISOCP 按固定时间上限运行
离散初始化时间上限
1小时
DICR2 的离散求解瓶颈单独设限
来源：Fig. 1，DICR离散初始化与连续精炼流程。
方法框架
精确模型被写成 MISOCP：二阶锥约束描述需求点到枢纽、枢纽到枢纽的欧氏距离，McCormick 改造线性化距离与分配变量的乘积。作者用需求点边界框给出 U1 和 U2，尽量收紧大 M 取值，降低松弛模型的数值负担。
来源：Fig. 2，DICR1与DICR2候选枢纽集合示意。
两种 DICR 的区别在初始化候选集。DICR1 只把需求点作为候选枢纽；DICR2 先围绕需求点画服务半径圆，收集圆交点，再通过集合覆盖模型挑选交点并加入候选集。这个设计提高了连续精炼前初始解的空间质量。
来源：Fig. 3，连续精炼阶段的迭代流程。
1先解离散候选枢纽模型，得到初始枢纽位置与需求点分配。
2固定分配后解 SOCP 位置子问题，更新连续空间枢纽坐标。
3固定坐标后解 MILP 分配子问题，在服务半径内重新分配需求点。
4重复位置更新和分配更新，直到目标值收敛。
案例或实验设置
实验使用 AP 基准数据和一个土耳其城际运输真实数据集。AP 原始数据含 200 个节点，论文构造 n=10、20、25、50 的实例，并测试不同枢纽数 p 和服务半径 R。成本参数沿用文献设置：αc=3、αd=2、αt=0.75。
来源：Fig. 4，n=20、p=4、R=14037实例中两种DICR方案的精炼效果。
图4给出一个直观案例：在 n=20、p=4、R=14037 的实例中，DICR1 经连续精炼后目标改善 8.4%；DICR2 的离散初始化已经更优，精炼后继续改善 3.4%，最终解比 DICR1 好 10.0%。
来源：Table 2，AP小规模实例上DICR1与DICR2结果对比。
结果分析
来源：Table 3，MISOCP、DICR2与PHLGA-SL在AP数据集上的比较。
表3显示，小规模实例中 MISOCP 可以在多组参数下证明最优；随着 n、p 和 R 放宽，精确模型在 2 小时时限内会留下较大 gap。DICR2 经常在更短时间内给出与 MISOCP 相同或更好的可行解，负偏差代表它找到了优于限时 MISOCP incumbent 的解。
来源：Fig. 5，服务半径R对DICR2可行率和平均偏差的影响。
服务半径越严格，可行实例比例越低，尤其在较大 n 和较小 p 的组合中更明显。随着 R 增加，可行分配集合扩大，MISOCP 的 LP 松弛变弱，限时最优性 gap 更容易扩大，DICR2 的负偏差也更常出现。
来源：Table 5，土耳其81城市数据集上的MISOCP与DICR2结果。
管理启示
这篇论文给运营规划的核心提示是，服务半径不是附加展示指标，它会直接改变枢纽位置、节点分配和网络成本。企业在设定承诺时效、服务半径或接驳上限时，需要同步评估枢纽数和空间位置的可行性。
来源：Fig. 8，服务水平约束对枢纽位置和节点分配的影响。
当服务水平要求更紧时，枢纽会被迫靠近远端需求点，布局更分散；当 R 放宽时，模型可以更多利用枢纽间低转运成本来平衡总成本。这个结果适合用于解释物流网络中服务承诺和干线集约化之间的取舍。
来源：Fig. 10，土耳其数据集中p=4时的DICR2枢纽布局。
对真实网络设计而言，MISOCP 适合作为小规模基准和质量标尺，DICR2 更适合作为可扩展的规划工具：它保留连续空间选址能力，又能在服务半径约束下稳定产生高质量方案。
论文：Exact and Heuristic Methods for the Uncapacitated Single Allocation Planar Hub Location Problem with Service-level Considerations
期刊：Computers & Industrial Engineering
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
