Bilevel Multi-Fidelity Search Framework for Urban Cable Routing Optimization
针对城市地下电缆布线中上层变电站拓扑与下层路由耦合的难题，提出双层多保真搜索框架，通过自适应邻域搜索与协同多保真筛选机制，在12个基准实例和3个实际案例中比六种对比方法节省成本3.21%至81.08%。
Urban underground cable construction is crucial for improving the reliability of power distribution grids. It inherently constitutes a bilevel combinatorial optimization problem that couples upper-level substation topology decisions with lower-level cable routing optimization subject to street network constraints. Due to the rigid upper-lower hierarchical coupling and the huge combinatorial search space, conventional methods struggle to obtain high-quality solutions within limited computational budgets. To address this challenge, this study proposes a bilevel multi-fidelity search (BL-MFS) framework that integrates an adaptive multiple neighborhood search (AMNS) algorithm for the upper level with a collaborative multi-fidelity screening mechanism for the lower level. Facing only the upper-level subproblem, the hybrid genetic search (HGS) algorithm is first used for solution initialization. The AMNS, featuring seven problem-specific operators, is then utilized for upper-level solution exploration. In every exploration iteration, three hierarchical lower-level optimizers with increasing fidelity levels are employed sequentially to evaluate the upper-level candidates. The number of solutions filtered by the low-fidelity lower-level optimizer is dynamically adjusted based on ranking consistency across consecutive fidelity levels, thereby ensuring the effectiveness of the screening mechanism. Computational experiments on twelve benchmark instances at four problem scales and three real-world cases reveal that BL-MFS outperforms six competitive baselines, achieving solution cost reductions ranging from 3.21% to 81.08%. Comprehensive ablation studies, hyperparameter sensitivity analyses, and ranking consistency analyses comprehensively validate the effectiveness and robustness of the proposed framework.