当前位置：首页 > news >正文

2026年IEEE TEVC，面向城市电缆布线优化的双层多精度搜索框架

news 2026/5/23 2:33:18

1.摘要

针对城市电缆布线中的双层组合优化难题，本文提出双层多精度搜索框架（BL-MFS），该框架上层采用自适应多邻域搜索探索解空间，下层通过动态多精度筛选机制逐级评估候选方案。实验表明，该方法能有效突破大规模搜索空间的计算瓶颈，显著降低布线成本，性能全面优于现有算法。

2.问题建模

城市电缆布线属典型双层组合优化问题：上层决策变电站连接拓扑，下层沿城市路网规划电缆路径。由于沟槽开挖成本远高于电缆单价，多线共沟敷设可显著降本，导致上下层强耦合。开挖与电缆两项成本的双层优化目标模型：
min ⁡ x u ∈ X U F ( x u , x l ∗ ( x u ) ) \min_{x_u \in X_U} F(x_u, x_l^*(x_u))xu∈XUminF(xu,xl∗(xu))
x l ∗ ( x u ) ← arg ⁡ min ⁡ x l ∈ X L ( x u ) F ( x l ∣ x u ) x_l^*(x_u) \leftarrow \arg \min_{x_l \in X_L(x_u)} F(x_l | x_u)xl∗(xu)←argxl∈XL(xu)minF(xl∣xu)
F ( x u , x l ) = ∑ e ∈ E ( c t r l e y e + c c a l e z e ) F(x_u, x_l) = \sum_{e \in E} (c_{tr} l_e y_e + c_{ca} l_e z_e)F(xu,xl)=e∈E∑(ctrleye+ccaleze)

上层拓扑寻优等效于多车场容量受限车辆路径问题，需满足服务覆盖、容量、流量平衡与子回路消除约束；下层受限于路网连通与共沟一致性约束。

3.方法

辅助优化：初始解生成

为给BL-MFS提供高质量初始解，构建仅针对上层拓扑辅助优化任务，转化为MD-CVRP，目标为最小化总曼哈顿距离：

min ⁡ x u ∈ X u f ~ u ( x u ) = ∑ ( i , j ) ∈ E ( x u ) d i j m a n \min_{x_u\in X_u}\tilde{f}_u(x_u)=\sum_{(i,j)\in E(x_u)}d_{ij}^{man}xu∈Xuminf~u(xu)=(i,j)∈E(xu)∑dijman

采用混合遗传搜索(HGS)算法求解该问题，所得结果作为BL-MFS的初始上层解，从而有效降低主优化阶段探索压力。

上层搜索：自适应多邻域搜索

上层采用自适应多领域搜索算法（AMNS），通过动态权重机制平衡7种搜索算子。算法交替进行探索与开发。算子权重w i w_iwi初始为1，每次迭代后根据表现进行更新：
w i ← { w i × 1.1 , if improved w i × 0.98 , otherwise w_i \leftarrow \begin{cases} w_i \times 1.1, & \text{if improved} \\ w_i \times 0.98, & \text{otherwise} \end{cases}wi←{wi×1.1,wi×0.98,if improvedotherwise
为防止过度收敛并维持基本探索概率，每20次迭代按如下公式对权重进行重置平滑：
w i ← w i ∑ j w j × 7 + 0.1 w_i \leftarrow \frac{w_i}{\sum_j w_j} \times 7 + 0.1wi←∑jwjwi×7+0.1
为避免陷入局部最优，邻域候选解生成规模N NN将根据搜索停滞情况自适应调整，上限设为初始规模N init N_{\text{init}}Ninit的两倍：
N ← { min ⁡ ( 1.1 × N , 2 × N init ) , if stagnated for 10 iterations N , otherwise N \leftarrow \begin{cases} \min(1.1 \times N,\, 2 \times N_{\text{init}}), & \text{if stagnated for 10 iterations} \\ N, & \text{otherwise} \end{cases}N←{min(1.1×N,2×Ninit),N,if stagnated for 10 iterationsotherwise

下层约束

下层模型基于给定上层拓扑x u x_uxu在城市路网中进行电缆路径规划，通过标准流量守恒约束确保各连接需求k kk在源节点与汇节点间形成有效连通路径：
∑ n ∣ ( m , n ) ∈ A w m n k − ∑ n ∣ ( n , m ) ∈ A w n m k = { 1 , m = π ( i k ) − 1 , m = π ( j k ) 0 , otherwise \sum_{n|(m,n)\in A} w_{mn}^k - \sum_{n|(n,m)\in A} w_{nm}^k = \begin{cases} 1, & m = \pi(i_k) \\ -1, & m = \pi(j_k) \\ 0, & \text{otherwise} \end{cases}n∣(m,n)∈A∑wmnk−n∣(n,m)∈A∑wnmk=⎩⎨⎧1,−1,0,m=π(ik)m=π(jk)otherwise
限制电缆仅能敷设于已开挖路段，并聚合计算各路段的电缆总数及开挖决策，从而保证布线与开挖状态的一致性：
w m n k + w n m k ≤ 2 y e w_{mn}^k + w_{nm}^k \leq 2y_ewmnk+wnmk≤2ye
z e = ∑ k ∈ K ( x u ) ( w m n k + w n m k ) z_e = \sum_{k\in K(x_u)} (w_{mn}^k + w_{nm}^k)ze=k∈K(xu)∑(wmnk+wnmk)
y e = min ⁡ ( z e , 1 ) y_e = \min(z_e, 1)ye=min(ze,1)

其中，各决策变量取值域为：y e , w m n k ∈ { 0 , 1 } y_e, w_{mn}^k \in \{0,1\}ye,wmnk∈{0,1}，z e ∈ { 0 , 1 , … , C m a x } z_e \in \{0,1,\dots,C_{max}\}ze∈{0,1,…,Cmax}