设备定位问题局部搜索算法的实验

doi:10.3778/j.issn.1002-8331.2010.02.011

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (2): 34-36.DOI: 10.3778/j.issn.1002-8331.2010.02.011

设备定位问题局部搜索算法的实验

肖进杰，谢青松，牛翠霞

山东工商学院计算机科学与技术学院，山东烟台　264005

收稿日期:2008-07-31 修回日期:2008-10-20 出版日期:2010-01-11 发布日期:2010-01-11
通讯作者: 肖进杰

Test of local search algorithms for uncapacitated facility location problems

XIAO Jin-jie，XIE Qing-song，NIU Cui-xia

Department of Computer Science and Technology，Shandong Institute of Business and Technology，Yantai，Shandong 264005，China

Received:2008-07-31 Revised:2008-10-20 Online:2010-01-11 Published:2010-01-11
Contact: XIAO Jin-jie

摘要/Abstract

摘要： 讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法，设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解；贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法，但两者求解质量相当；设备价值和服务价值数值范围越大，局部搜索算法越容易求得最优解。

关键词: 设备定位问题, 局部搜索, 贪心算法

Abstract: This paper discusses approximation local search algorithms for Uncapacitated Facility Location Problems（UFLP） and its new property in actual computation.This paper mainly discusses different generation methods of the initial solution，the influence of facility cost and service cost and the improvement of local search algorithm.The testing data shows：There are about 99% instances for which local search algorithm can be used to directly compute their optimal solutions；the running time of the algorithm using initial solutions of greedy algorithm is shorter than that of algorithm using initial solutions of randomized algorithm，but the quality of solutions is almost the same；the bigger the facility cost and the service cost are，the easier local search algorithm gets the optimal solutions.

Key words: uncapacitated facility location problems, local search algorithm, greedy algorithm

中图分类号:

TP301.6

肖进杰，谢青松，牛翠霞. 设备定位问题局部搜索算法的实验[J]. 计算机工程与应用, 2010, 46(2): 34-36.

XIAO Jin-jie，XIE Qing-song，NIU Cui-xia. Test of local search algorithms for uncapacitated facility location problems[J]. Computer Engineering and Applications, 2010, 46(2): 34-36.

[1]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[2]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[3]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[4]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[5]	董小帅1，2，3，毛政元1，2，3. 基于改进遗传算法的动态路径规划研究[J]. 计算机工程与应用, 2018, 54(19): 49-55.
[6]	肖红德. 最少钱币数量的计算与钱币面额的确定[J]. 计算机工程与应用, 2018, 54(16): 266-270.
[7]	吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1. 改进的差分演化算法求解多维背包问题[J]. 计算机工程与应用, 2018, 54(11): 153-160.
[8]	胡炜1，2，曾斌1，姚路1. 事件驱动下的重点海域监测站部署算法研究[J]. 计算机工程与应用, 2017, 53(7): 136-140.
[9]	宋强. 改进迭代局部搜索算法在MMTVRP中的应用[J]. 计算机工程与应用, 2017, 53(7): 248-255.
[10]	张娜娜，赵作鹏，李晓波. 采用半贪心优化的节点非均匀分布路由协议[J]. 计算机工程与应用, 2017, 53(23): 60-66.
[11]	洪剑珂1，张峥华2，许贵平2. 基于加强概率控制策略的SAT局部搜索算法[J]. 计算机工程与应用, 2017, 53(14): 56-60.
[12]	王蒙，樊坤，翟亚飞，李心宁. 网络并行计算中多处理机任务调度问题研究[J]. 计算机工程与应用, 2017, 53(10): 264-270.
[13]	伍艳莲1，2，姜海燕1，2，庄嘉祥1，郭小清1，许一骅1. 精英策略个体优势遗传算法研究[J]. 计算机工程与应用, 2016, 52(7): 143-149.
[14]	林耿1，徐梅琴2. 图的最大二等分问题的一种离散填充函数算法[J]. 计算机工程与应用, 2016, 52(5): 27-32.
[15]	朱旭，牛存良，白晓丽. 改进的ZigBee树路由算法[J]. 计算机工程与应用, 2016, 52(5): 114-118.

设备定位问题局部搜索算法的实验

Test of local search algorithms for uncapacitated facility location problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics