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