文章背景与核心概要

在现代物流与供应链管理中，将道路网络划分为指定数量紧凑且连通的区域（即网络区划问题）是一项基础且极具挑战性的任务。传统的区划模型往往难以在大规模实际路网中兼顾计算效率与连通性约束。为此，本文引入了基于边的连续型 p-中值问题（Edge-based Contiguous p-median, ECpM）这一全新框架，并提出了两种不同的二元规划模型来解决该挑战。

本文的核心技术贡献在于提出了基于最短路径连通性（SPC）的模型。与依赖指数级约束的传统割集模型不同，SPC模型仅需多项式数量的约束，从而能够直接通过标准的枝定界（Branch-and-Bound）求解器进行高效求解。研究表明，SPC方法在计算性能上实现了高达17倍的加速，并成功解决了以往在12小时内无法求解的大规模路网区划实例。该研究不仅为物流区划（EBD）提供了可扩展的强大工具，其发现的“超有效不等式”性质也为求解复杂整数可行解问题开辟了新的理论视角。

基于边的连续型 p-中值问题及其在物流区划中的应用

作者： Zeyad Kassem, Adolfo R. Escobedo
日期： 2026年7月30日
arXiv： 2608.11230 [cs.AI]

摘要

本文引入了基于边的连续型 p-中值（Edge-based Contiguous p-median, ECpM）问题，这是一个旨在将道路网络划分为指定数量的紧凑、连续领地的框架。作者提出了两种不同的二元规划模型来应对这一挑战：

1. 基于割集的模型： 采用指数数量的约束来强制实现连通性，通过割平面（branch-and-cut, B&C）算法求解。
2. 最短路径连通性（SPC）模型： 利用多项式数量的约束，允许通过标准的分支定界求解器进行直接求解。

研究表明，基于SPC的方法显著优于基于割集的方法，实现了高达 17 倍的计算加速。此外，作者证明了 SPC 约束对于标准基于边的 p-中值问题起到了“超有效不等式（supervalid inequalities）”的作用。最后，本文将这些发现应用到基于边的区划（Edge-based Districting, EBD）问题中，表明基于SPC的模型成功求解了先前在 12 小时内无法处理的实例。

This paper introduces the Edge-based Contiguous p-median (ECpM) problem, a framework designed to partition road networks into a specified number of compact, contiguous territories. The authors propose two distinct binary programming models to address this challenge:

1. Cut Set-based Model: Employs an exponential number of constraints to enforce contiguity, solved via a branch-and-cut (B&C) algorithm.
2. Shortest-Path Contiguity (SPC) Model: Utilizes a polynomial number of constraints, allowing for direct solution via standard branch-and-bound solvers.

The study demonstrates that the SPC-based approach significantly outperforms the cut set-based method, achieving computational speedups of up to 17x. Furthermore, the authors show that SPC constraints act as "supervalid inequalities" for the standard edge-based p-median problem. Finally, the paper applies these findings to the Edge-based Districting (EBD) problem, showing that the SPC-based model successfully solves instances that were previously intractable within a 12-hour window.

核心贡献

• 算法效率： SPC 模型为网络分区提供了一种强大且可扩展的传统基于割集方法的替代方案。
• 计算性能： 在大规模道路网络（2,700 多个节点，3,400 多条边）上进行了测试，SPC 模型以极高的效率处理了超过 960 万个二元变量。
• 物流应用： 该研究为基于边的区划（EBD）问题提供了关键见解，特别是在需要严格工作平衡标准的情景下。

• 理论洞察： 将 SPC 约束识别为超有效不等式，为简化复杂的整数可行问题提供了新的视角。

• Algorithmic Efficiency: The SPC-based model provides a robust, scalable alternative to traditional cut set-based approaches for network partitioning.

• Computational Performance: Tested on large-scale road networks (2,700+ nodes, 3,400+ edges), the SPC model handles over 9.6 million binary variables with superior efficiency.
• Logistics Applications: The research provides critical insights into the Edge-based Districting (EBD) problem, particularly in scenarios requiring strict work-balance criteria.
• Theoretical Insights: The identification of SPC constraints as supervalid inequalities offers a new perspective on simplifying complex integer-feasible problems.

访问与元数据

Field	Details
Primary Subject	Artificial Intelligence (cs.AI)
Secondary Subject	Discrete Mathematics (cs.DM)
DOI	10.48550/arXiv.2608.11230
Full-text	View PDF
Source	TeX Source