系统管理学报

系统管理学报 ›› 2020, Vol. 29 ›› Issue (2): 346-353.DOI: 10.3969/j.issn.1005-2542.2020.02.015

• 运筹学与工业工程 • 上一篇    下一篇

最大覆盖选址问题的一种降阶回溯算法

彭大江，宁爱兵，尚春剑，张惠珍   

  1. 上海理工大学 管理学院，上海 200093
  • 出版日期:2020-03-29 发布日期:2020-07-07
  • 作者简介:彭大江（1995-），男，硕士生。研究方向为算法与系统工程。
  • 基金资助:
    国家自然科学基金资助项目(71401106)；上海市一流学科建设资助项目(S1201YLXK)

A Backtracking Algorithm with Reduction for Maximal Covering Location Problem

PENG Dajiang, NING Aibing, SHANG Chunjian, ZHANG Huizhen   

  1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2020-03-29 Published:2020-07-07

PDF

摘要：

最大覆盖选址问题在实际生活中有广泛的应用，是组合优化中的一个NP-Hard问题。首先提出问题的上下界子算法，接着研究数学性质，其中包括可以批量确定某些设施一定开设或一定不开设的性质。最后，利用上下界子算法和这些数学性质设计出一种可以快速减小问题规模且能求出最优解的降阶回溯算法。通过一个示例阐述该算法的执行过程。

关键词: 最大覆盖选址问题, 精确算法, 上界算法, 下界算法

Abstract:

The maximal covering location problem is widely applied in real life, and it is demonstrated to be an NP-Hard problem in combinatorial optimization. First, the algorithms for the upper and lower bound are proposed. Then, the mathematical properties, including the properties that can determine batches of facilities that must engage or not, are addressed. After that, a backtracking algorithm with reduction that returns a global best solution based on sub-algorithms for the upper and lower bound and these mathematical properties is presented, which is able to quickly reduce the scale of the question. Finally, an instance is illustrated to describe the steps of the algorithm.

Key words: maximal covering location problem, exact algorithm, upper bound algorithm, lower bound algorithm

中图分类号: