无容量限制设施选址问题的降阶回溯算法

作     者：何永梅 宁爱兵 彭大江 尚春剑 张惠珍 HE Yong-mei;NING Ai-bing;PENG Da-jiang;SHANG Chun-jian;ZHANG Hui-zhen

作者机构：上海理工大学管理学院上海200093 

基　　金：国家自然科学基金(71401106) 上海市一流学科建设项目资助(S1201YLXK) 高等学校博士学科点专项科研基金联合资助课题(20123120120005) 

出 版 物：《运筹与管理》 (Operations Research and Management Science)

年 卷 期：2018年第27卷第9期

页      码：17-21页

摘      要：无容量限制设施选址问题(uncapacitated facility location problem,UFLP)是经典组合优化中NP-Hard问题之一,在诸多领域具有广泛的应用价值。本文首先研究UFLP的数学性质,并进行了数学证明。运用这些数学性质不仅可以确定某些设施必定开设或者关闭,还可以确定某些连接边是否在服务集中,从而缩小问题的规模,加快求解速度;在此基础上设计出一个新的基于上下界的回溯算法来求解UFLP。最后,通过一个示例进一步阐述该算法的原理,结果表明该算法具有明显的可行性和有效性。

主 题 词：无容量限制设施选址问题 降阶 上界 下界 回溯算法 

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

核心收录：

D　O　I：10.12005/orms.2018.0201

馆 藏 号：203381403...