This article presents a matheuristic algorithm for the single-source capacitated facility location problem (SSCFLP) and its variants: SSCFLP with K facilities (SSCKFLP), SSCFLP with contiguous service areas (CFLSAP), and SSCFLP with K facilities and contiguous service areas (CKFLSAP). The algorithm starts from an initial solution, and iteratively improves the solution by exactly solving large neighborhood-based sub-problems. The performance of the algorithm is tested on 5 sets of SSCFLP benchmark instances. Among the 272 instances, 191 optimal solutions are found, and 35 best-known solutions are updated. For the largest set of instances with 300-1000 facilities and 300-1500 customers (Avella and Boccia 2009), the proposed algorithm outperforms existing methods in terms of the solution quality and the computational time. Furthermore, based on two geographic areas, two sets of instances are generated to test the algorithm for solving SSCFLP and its variants. The solutions found by the proposed algorithm approximate optimal solutions or the lower bounds with average gaps of 0.07% for SSCFLP, 0.22% for CFLSAP, 0.04% for SSCKFLP, and 0.13% for CKFLSAP.


翻译:本文为单一源码设施定位问题(SSCFLP)及其变式提供了一个数学算法:SSCFLP与K设施(SSCKFLP)、SSCFLP与毗连服务区(CFLSAP),SSCFLP与K设施和毗连服务区(CKFLSAP),以及SSCFLP与K设施和毗连服务区(CKFLSAP)的最大一组情况(Avella和Boccia,2009年)。这一算法从最初的解决方案开始,通过精确解决大型以邻里为基础的子问题,迭接地改进了解决方案。在SSCFLP及其变式的5个基准实例中测试了算法的性。在272例中,找到了191个最佳解决方案,并更新了35个最著名的解决方案。对于300-1000设施和300-1000个客户(Avilla和Boccia)的最大一组情况,提议的算法在解决方案质量和计算时间方面超越了现有方法。此外,根据两个地理区域,产生了两套实例来测试SSCFLFLP及其变式的算法。在解决SFLFLFLP及其变式中,根据拟议算法找到最佳解决方案或较低框中,最佳解决方案或最低范围为0.0-074%,SFLFLFLFLFLFMCFLFLFP的0.12。

0
下载
关闭预览

相关内容

专知会员服务
84+阅读 · 2020年12月5日
专知会员服务
52+阅读 · 2020年9月7日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
会议交流 | IJCKG: International Joint Conference on Knowledge Graphs
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
国家自然科学基金
5+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年4月18日
Arxiv
0+阅读 · 2022年4月17日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
VIP会员
相关资讯
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
会议交流 | IJCKG: International Joint Conference on Knowledge Graphs
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
相关基金
国家自然科学基金
5+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员