基于伪布尔模型和启发式算法求解无容量设施选址问题

中国机械工程

基于伪布尔模型和启发式算法求解无容量设施选址问题

凌海峰

1.合肥工业大学管理学院，合肥，230009
2.过程优化与智能决策教育部重点实验室，合肥，230009

出版日期:2018-12-25 发布日期:2018-12-24
基金资助:
国家自然科学基金资助重大项目（71490725）；
国家自然科学基金资助重点项目（71531008）；
国家自然科学基金资助项目（71371062，71271073）
Major Program of the National Natural Science Foundation of China（No. 71490725）
State Key Program of National Natural Science of China （No. 71531008）
National Natural Science Foundation of China （No. 71371062，71271073）

Solving Uncapacitated Facility Location Problems Using Pseudo-Boolean Model and Heuristic Algorithms

LING Haifeng

1.School of Management, Hefei University of Technology, Hefei，230009
2.Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei，230009

Online:2018-12-25 Published:2018-12-24
Supported by:
Major Program of the National Natural Science Foundation of China（No. 71490725）
State Key Program of National Natural Science of China （No. 71531008）
National Natural Science Foundation of China （No. 71371062，71271073）

摘要/Abstract

摘要： 采用伪布尔模型和启发式算法来求解无容量设施选址问题。首先给出了问题的伪布尔(pseudo-Boolean)表示，然后基于Khumawala规则对问题进行预处理，最后提出两种启发式分支准则来求解问题。实验结果表明所提算法简单有效。

关键词: 无容量设施选址问题(UFLP), 伪布尔表示, Khumawala规则, 启发式分支准则

Abstract: The UFLPs were solved based on pseudo-Boolean model and heuristic algorithm herein. Firstly, the pseudo-Boolean representation of UFLPs was given, and the Khumawala rules were used to preprocess the input instances. Finally, two heuristic branching criterions were presented to solve the problems. Experimental results show that the new method is simple and efficient.

Key words: uncapacitated facility location problem (UFLP), pseudo-Boolean representation, Khumawala rule, heuristic branching criteria

中图分类号:

TH18

凌海峰. 基于伪布尔模型和启发式算法求解无容量设施选址问题[J]. 中国机械工程.

LING Haifeng. Solving Uncapacitated Facility Location Problems Using Pseudo-Boolean Model and Heuristic Algorithms[J]. China Mechanical Engineering.

参考文献

[1]AHMADI-JAVID A, SEYEDI P, SYAM S S. A Survey of Healthcare Facility Location[J]. Computers & Operations Research, 2017, 79:223-263.
[2]BATTA R, LEJEUNE M, PRASAD S. Public Facility Location Using Dispersion, Population and Equity Criteria[J]. European Journal of Operational Research, 2014, 234: 819-829.
[3]CHEN L, OLHAGER J, TANG O. Manufacturing Facility Location and Sustainability: Literature Review and Research Agenda[J]. International Journal of Production Economics, 2014, 149:154-163
[4]CHAN K Y, AYDIN M E, FOGARTY T C. Main Effect Fine-tuning of the Mutation Operator and the Neighbourhood Function for Uncapacitated Facility Location Problems[J]. Soft Computation, 2006, 10:1075-1090.
[5]TOHYAMA H, IDA K, MATSUEDA J. A Genetic Algorithm for the Uncapacitated Facility Location Problem[J]. Electronics and Communications in Japan, 2011, 94(5):47-54.
[6]YIGIT V, AYDIN M E, TURKBEY O. Solving Large-scale Uncapacitated Facility Location Problems with Evolutionary Simulated Annealing[J]. International Journal of Production Research, 2006, 44(22): 4773-4791.
[7]GUNER A R, SEVKLI M. A Discrete Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem[J]. Journal of Artificial Evolution and Applications, 2008, 2008:1-9.
[8]李倩，张惠珍，BELTRAN-ROYO C. 求解无容量设施选址问题的混合蚁群算法[J]. 上海理工大学学报, 2016, 38(4):367-372.
LI Qian, ZHANG Huizhen, BELTRAN-ROYO C. Hybrid Ant Colony Algorithm for the Uncapacitated Facility Location Problem[J]. Journal of University of Shanghai for Science and Technology, 2016, 38(4):367-372.
[9]KOLE A, CHAKRABARTI P, BHATTACHARYYA S. An Ant Colony Optimization Algorithm for Uncapacitated Facility Location Problem [J]. Artificial Intelligence and Applications, 2014, 1(1): 55-61.
[10]李翼，赵茂先，李岳佳. 无容量限制设施选址问题的分支定界法[J]. 山东理工大学学报（自然科学版）,2012, 26(1):70-73.
LI Yi, ZHAO Maoxian, LI Yuejia. Branch and Bound Algorithm for Uncapacitated Facility Location Problem [J]. Journal of Shandong University of Technology: Science and Technology, 2012, 26(1):70-73.
[11]KLOSE A. A Branch and Bound Algorithm for an UFLP with a Side Constrain[J]. International Transactions in Operational Research, 1998, 5(2):155-168.
[12]BELTRAN-ROYO C, VIAL J, ALONSO-AYUSO A. Semi-lagrangian Relaxation Applied to the Uncapacitated Facility Location Problem[J]. Computer Optimization & Applications, 2012, 51(1): 387-409.

[1]	刘雪梅；刘涛；郭欢. 基于可用度评价的混联生产线缓冲区配置优化[J]. 中国机械工程, 2020, 31(18): 2220-2230.
[2]	刘雪梅1;王笑1;柳跃雷2. 模糊时间窗约束下的装配线物料配送方案优化[J]. 中国机械工程, 2020, 31(17): 2095-2103.
[3]	廖不凡1;雷琦1;吴文烈2;宋豫川1;郭伟飞1. 基于混合教学优化算法的多车间协作综合调度[J]. 中国机械工程, 2020, 31(16): 1940-1949.
[4]	杨杰, 胡琦, 肖亭, 张文颖, 张超勇. 基于能耗的冷轧连退机组能效建模与工艺参数优化及排序建模优化[J]. 中国机械工程, 2020, 31(14): 1724-1732.
[5]	刘建胜;雷兆发;聂伟豪;涂海宁. 一种鱼骨仓储布局下的拣选路径优化方法[J]. 中国机械工程, 2020, 31(10): 1225-1232.
[6]	张青雷1;张帆2;段建国1. 基于DMPSO算法的大型船舶动力部件生产车间布局优化[J]. 中国机械工程, 2020, 31(03): 344-351.
[7]	贺长征1;宋豫川1;雷琦1;吕向飞1;刘软香1;陈进2. 柔性作业车间多自动导引小车和机器的集成调度[J]. 中国机械工程, 2019, 30(04): 438-447.
[8]	钟祾充, 钱斌, 胡蓉, 王凌. [车间调度]混合布谷鸟算法求解绿色流水车间调度问题[J]. 中国机械工程, 2018, 29(22): 2674-2681.
[9]	任莹晖, 黄向明, 马忠凯, 周志雄. [供应链调度]基于信息熵的物料配送时间节点预测方法[J]. 中国机械工程, 2018, 29(22): 2725-2732.
[10]	杨杰1;宋健1;胡琦1;张超勇2;孟磊磊2. 酸洗连轧生产线机组轧制功率建模及工艺参数优化[J]. 中国机械工程, 2018, 29(19): 2371-2376.
[11]	刘永奎, 王力翚, 王曦, 徐旬. [云制造]云制造再探讨[J]. 中国机械工程, 2018, 29(18): 2226-2237.
[12]	杨宇;黄敏;王震宇;朱启兵. 利用有限制稳定配对策略求解双目标柔性作业车间调度问题[J]. 中国机械工程, 2018, 29(14): 1743-1750.
[13]	肖鹏飞1;张超勇1;罗敏1;林文文2. 基于自适应动态无偏最小二乘支持向量机的刀具磨损预测建模[J]. 中国机械工程, 2018, 29(07): 842-849.
[14]	杨林;李文锋;段莹;罗云;杨文超. 工业物联网环境下隐式人机交互消息传播方法[J]. 中国机械工程, 2018, 29(04): 463-470.
[15]	侯仰强1;王天琪1;李亮玉1;张志臣1;赵娜2. 基于蚁群算法-粒子群算法的白车身侧围点焊机器人路径规划[J]. 中国机械工程, 2017, 28(24): 2990-2994.