基于高效分支定界法的设备位置耦合优化算法OA
对于飞机等复杂装备,设备安装位置的选择决定互连线缆的物理走向与长度,进而影响线缆总重。因此,线缆的轻量化本质上属于复杂设备的位置耦合分配问题。由于任一设备位置的变动波及全局,影响连接代价,导致问题难以解耦并易引发组合爆炸。为此,提出一种基于高效分支定界法的优化算法。设计了3项定制化策略,采用随机化贪心策略估计紧致上界,采用最短连接松弛策略估计乐观下界,通过实时动态比对上、下界,精准识别并提前剪除无法产生更优解的搜索分支。同时,引入基于连接度驱动的分支策略,优先决策网络拓扑中的关键枢纽设备,进一步提高搜索效率,加快收敛速度。经实验验证,在基准算法可求解的规模(设备数)区间,该算法可稳定获得与穷举法和整数线性规划(ILP)算法一致的最优解,并将可精确求解的问题规模拓展至40个设备数级别。消融实验验证了各定制化策略具有独立贡献和协同效应。最后,在具备不同连接代价分布特征的场景中进行测试,算法均展现出优异的剪枝效率与鲁棒性。该算法已在实际工程中完成部署,证明了其应对典型工程规模难题的有效性,具有实用价值。
孙现龙;张奥楠;赵伟;罗月童
合肥工业大学计算机与信息学院,安徽合肥230601合肥工业大学计算机与信息学院,安徽合肥230601合肥工业大学计算机与信息学院,安徽合肥230601合肥工业大学计算机与信息学院,安徽合肥230601
信息技术与安全科学
耦合优化分支定界边界估计剪枝设备布局成本优化
《浙江大学学报(理学版)》 2026 (5)
P.552-558,613,8
国家自然科学基金项目(62272142,62472139).
评论