基于分支割平面的一类无容量限制设施选址问题求解算法

作     者：安邦 程朋 AN Bang;CHENG Peng

作者机构：清华大学自动化系北京100084 

基　　金：国家自然科学基金(No.61179052) 

出 版 物：《运筹学学报》 (Operations Research Transactions)

年 卷 期：2015年第19卷第4期

页      码：1-13页

摘      要：无容量限制设施选址问题是经典的组合优化问题,具有广泛的应用价值,然而该问题已被证明是NP难问题,并且传统的分支定界方法求解速度较慢.研究以最大化总收益费用与总投建费用之差为目标的无容量限制设施选址问题,将其转化为节点包装问题,并根据模型的图形特点提出了新的合法不等式族一轴不等式族,经过严格的数学证明后得出轴不等式要强于原有的奇洞不等式.同时,设计出切割不等式快速搜索算法嵌入到分支割平面方法中.最后,通过实验验证了轴不等式族的强有效性,以及分支割平面方法比分支定界方法求解速度快、节点数量少的优点.

主 题 词：无容量限制设施选址问题 分支割平面 轴不等式 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.15960/j.cnki.issn.1007-6093.2015.04.001

馆 藏 号：203139718...