基于边的连续p-中位问题及其与物流分区的联系

arXiv cs.AI 论文
optimization logistics p-median contiguity road-networks integer-programming

摘要

本文介绍了基于边的连续p-中位（ECpM）问题，用于将道路网络划分为紧凑的区域，提出了两个带有连续性约束的0-1规划模型，并在大型道路网络上进行了测试。最短路径约束模型相比基于割集的分支切割方法实现了显著的加速，并与物流分区相关。

arXiv:2608.11230v1 公告类型：新 摘要：本文介绍了基于边的连续p-中位（ECpM）问题，用于将网络中的道路划分为给定数量的紧凑且连续的区域。提出了两个0-1规划模型，两者都包含网络距离。第一个模型需要指数数量的基于割集的约束来建模连续性；它配备了一个分离方案，通常只生成少量这些约束，即分支切割（B&C）算法。第二个模型利用多项式数量的最短路径约束来建模连续性，并可使用现成的求解器求解。相应的求解方法在拥有超过2,700个节点和接近3,400条边的道路网络上进行了测试，产生的模型包含超过960万个0-1变量。通过标准分支定界求解基于最短路径连续性（SPC）约束的模型，相对于基于割集的B&C实现，计算时间加速可达17倍。此外，SPC约束被证明是基于边的p-中位（EpM）模型的超有效不等式（即该模型不显式要求连续性），这意味着它们可能切掉整数可行解以及这个更简单问题的一部分（但不是全部）最优解。最后，本文探讨了ECpM与基于边的分区（EBD）问题之间的结构洞见和联系，后者还强制要求额外的工作量平衡准则。现有的使用基于割集的连续性约束的模型在12小时内无法为任何测试实例找到可行解，而基于SPC的EBD模型能够将其中大部分求解到最优。
查看原文
查看缓存全文

缓存时间: 2026/08/13 15:23 

# 基于边的连通p-中位问题及其与物流分区的联系
来源：https://arxiv.org/abs/2608.11230
查看PDF (https://arxiv.org/pdf/2608.11230)

> 摘要：本文介绍了基于边的连通p-中位（ECpM）问题，将网络中的道路划分为给定数量的紧凑且连通的区域。提出了两个0-1规划模型，这两个模型都引入了网络距离。第一个模型需要指数数量的基于割集的约束来建模连通性；它配有一个分离方案，该方案通常只生成少量这些约束，即分支切割（B&C）算法。第二个模型利用多项式数量的最短路径约束来建模连通性，并且可以使用现成的求解器进行求解。相应的求解方法在拥有超过2,700个节点和接近3,400条边的道路网络上进行了测试，产生了具有超过960万个0-1变量的模型。通过标准分支定界求解基于最短路径连通性（SPC）约束的模型，在计算时间上相比基于割集的B&C实现获得了高达17倍的加速。此外，SPC约束被证明是基于边的p-中位（EpM）模型（即不显式要求连通性的模型）的超有效不等式，这意味着它们可能剪除整数可行解以及这个更简单问题的一部分（但不是全部）最优解。最后，本文探讨了ECpM与基于边的分区（EBD）问题之间的结构洞见和联系，EBD问题额外强制了工作量平衡准则。一个利用基于割集的连通性约束的现有模型在12小时内无法为任何测试实例找到可行解，而基于SPC的EBD模型则能够将其中大多数实例求解到最优。

## 提交历史

来自：Zeyad Kassem [查看电子邮件](https://arxiv.org/show-email/1480f1e0/2608.11230) **\[v1\]** 2026年7月30日星期四 03:49:03 UTC（68 KB）

相似文章

通过协同划分优化构建稳健可行的路径

arXiv cs.AI

本文介绍了协同路径构建器（CoRC），这是一个框架，允许独立求解的子问题在优化过程中交换客户和车辆，从而提升大规模容量限制车辆路径问题的可行性和可扩展性。

面向组合几何极值问题的几何感知MCTS

arXiv cs.AI

本文提出了一种几何感知的蒙特卡洛树搜索框架，用于在n×n网格上求解极值组合几何问题，在六个测试问题中的五个上取得了新的最佳已知结果，包括对No-Three-in-Line问题的改进。