摘要
在几何通信网络中，只有当主干网络的构建成本较低，并且它足够靠近需要服务的需求点时，该主干网络才具有实用性。本文研究了一种几何通信网络中的主干网络设计问题，该问题明确考虑了连接性和用户覆盖范围之间的权衡。本文考虑了两种经典的组合优化方法：最小生成树（MST），它侧重于实现低成本的连接性；以及支配树（DT），它确保每个节点要么属于主干网络，要么与一个活跃的主干节点相邻。为了在共同的框架内比较这两种方法，本文提出了一个统一的混合整数优化模型，该模型平衡了主干网络构建成本和用户分配成本。本文开发了三类精确的数学建模方法，即MTZ、单流方法和割集方法。特别是，单流方法通过有效的不等式和基于根的连接性切割得到了加强。对于较大的网络实例，精确方法还结合了局部分支启发式算法。最后，本文提供了关于计算复杂性、建模结构以及MST和DT模型之间支配关系的理论结果。计算实验表明，单流方法在可扩展性方面表现最佳。此外，对通信半径和权重参数
