Location Routing is a fundamental planning problem in logistics, in which strategic location decisions on the placement of facilities (depots, distribution centers, warehouses etc.) are taken based on accurate estimates of operational routing costs. We present an approximation algorithm, i.e., an algorithm with proven worst-case guarantees both in terms of running time and solution quality, for the general capacitated version of this problem, in which both vehicles and facilities are capacitated. Before, such algorithms were only known for the special case where facilities are uncapacitated or where their capacities can be extended arbitrarily at linear cost. Previously established lower bounds that are known to approximate the optimal solution value well in the uncapacitated case can be off by an arbitrary factor in the general case. We show that this issue can be overcome by a bifactor approximation algorithm that may slightly exceed facility capacities by an adjustable, arbitrarily small margin while approximating the optimal cost by a constant factor. In addition to these proven worst-case guarantees, we also assess the practical performance of our algorithm in a comprehensive computational study, showing that the approach allows efficient computation of near-optimal solutions for instance sizes beyond the reach of current state-of-the-art heuristics.


翻译:在后勤方面,对设施(供应站、分配中心、仓库等)的安置,根据对业务路由成本的准确估计,作出关于设施(供应站、分配中心、仓库等)安置的战略定位决定; 我们提出近似算法,即在运行时间和解决办法质量两方面都得到证明的最坏情况保障的算法,用于这一问题的一般功能化版本,使车辆和设施都具有能力; 在此之前,这种算法只针对设施没有能力或其能力可以任意以线性成本扩展的特殊案例,才知道这种算法; 以前确定的较低界限,已知在无能力情况下最接近最佳解决办法的价值,但一般情况下可以任意排除。 我们表明,可以通过两重的近似近似近似性算法,通过可调整的、任意的小边距略超过设施能力,同时以固定因素抵消最佳成本; 除了这些经证明的最坏情况保证外,我们还在全面计算研究中评估我们算算法的实际表现,表明在目前达到的大小的情况下,可以有效地计算出近优劣性解决办法。

0
下载
关闭预览

相关内容

【CVPR2021】深度学习细粒度视觉分析
专知会员服务
35+阅读 · 2021年6月23日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
【最受欢迎的概率书】《概率论:理论与实例》,490页pdf
专知会员服务
162+阅读 · 2020年11月13日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
已删除
将门创投
3+阅读 · 2020年8月3日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
【CVPR2021】深度学习细粒度视觉分析
专知会员服务
35+阅读 · 2021年6月23日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
【最受欢迎的概率书】《概率论:理论与实例》,490页pdf
专知会员服务
162+阅读 · 2020年11月13日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
相关资讯
已删除
将门创投
3+阅读 · 2020年8月3日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员