| P-中心选址问题的一种降阶回溯算法 |
| |
| 引用本文： | 尚春剑,宁爱兵,彭大江,张惠珍. P-中心选址问题的一种降阶回溯算法[J]. 计算机应用研究, 2021, 38(3): 734-737,769. DOI: 10.19734/j.issn.1001-3695.2020.04.0057 |
| |
| 作者姓名： | 尚春剑 宁爱兵 彭大江 张惠珍 |
| |
| 作者单位： | 上海理工大学 管理学院,上海200093;上海理工大学 管理学院,上海200093;上海理工大学 管理学院,上海200093;上海理工大学 管理学院,上海200093 |
| |
| 基金项目： | 上海市一流学科建设资助项目;国家自然科学基金资助项目;上海市教委管理科学与工程高原学科建设项目(2018-2021);高等学校博士学科点专项科研基金联合资助项目 |
| |
| 摘 要： | 运筹学研究领域中的应急服务设施选址问题有许多求解模型,选取了P-中心模型进行研究,首先研究了该问题的数学性质,并给出了证明,利用这些数学性质能对问题进行降阶从而缩小问题的规模;然后在此基础上设计一个基于上界和下界的回溯算法来求解该问题;最后通过一个示例分析进一步阐述了该算法的原理,并证明了该算法能在较短时间内求得问题的最优解。
|
| 关 键 词： | 设施选址问题 P-中心模型 降阶算法 上界 下界 回溯算法 |
| 收稿时间： | 2020-04-10 |
| 修稿时间： | 2021-02-07 |
Backtracking algorithm with reduction for P-center location problem |
| |
| chunjian shang,aibing ning,dajiang peng and huizhen zhang. Backtracking algorithm with reduction for P-center location problem[J]. Application Research of Computers, 2021, 38(3): 734-737,769. DOI: 10.19734/j.issn.1001-3695.2020.04.0057 |
| |
| Authors: | chunjian shang aibing ning dajiang peng huizhen zhang |
| |
| Affiliation: | (Business School,University of Shanghai for Science&Technology,Shanghai 200093,China) |
| |
| Abstract: | There were various solution models for the emergency service facility location problem and this paper studied the P-center model.This paper proposed a backtracking algorithm with upper and lower bound,and added a reduction algorithm by studying the mathematical properties.The algorithm could decrease the scale and the degree of complexity of the P-center location problem,so as to accelerate the execution speed.At the end,this paper illustrated an instance to elaborate this algorithm further. |
| |
| Keywords: | facility location problem P-center model reduction algorithm upper bound lower bound backtracking algorithm |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
|
