A decomposition approach for the p-median problem on disconnected graphs
A decomposition approach for the p-median problem on disconnected graphs
复制标题
断开图上p中值问题的分解方法
DOI：
10.1016/j.cor.2017.05.006
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Cristina Requejo
中科院分区：
文献类型：
--
作者：
A. Agra;J. Cerdeira;Cristina Requejo
p-中值问题寻求p个设施在图的顶点（客户）上的位置，以最小化从设施满足客户需求的运输成本之和。在p-中值问题的许多真实的应用中，底层图是不连通的。这是p-中位数问题的情况下，定义在分裂的行政区域或地理上分开的区域（如群岛），以及来自行业的问题，如最佳多样性管理问题的情况。在这种情况下，问题可以分解成更小的p-中位数问题，这些问题在每个分量k中针对不同的可行pk值进行求解，并且通过找到pk中位数的最佳组合来获得全局解。这种方法的优点是，它允许解决更大的实例，因为只有连接组件的大小是重要的，而不是整个图的大小。然而，由于从每个组件中选择的设施的最佳数量是未知的，因此有必要为每个组件上的设施的每个可行数量求解p-中值问题。在本文中，我们给出了一个分解算法，使用一个程序来减少子问题的数量来解决。计算测试的最佳多样性管理问题的真实的实例和模拟实例的报告表明，减少子问题是显着的，并在合理的时间内找到最佳的解决方案。
Thep-median problem seeks for the location ofpfacilities on the vertices (customers) of a graph to minimize the sum of transportation costs for satisfying the demands of the customers from the facilities. In many real applications of thep-median problem the underlying graph is disconnected. That is the case ofp-median problem defined over split administrative regions or regions geographically apart (e.g. archipelagos), and the case of problems coming from industry such as the optimal diversity management problem. In such cases the problem can be decomposed into smallerp-median problems which are solved in each componentkfor different feasible values ofpk, and the global solution is obtained by finding the best combination ofpkmedians. This approach has the advantage that it permits to solve larger instances since only the sizes of the connected components are important and not the size of the whole graph. However, since the optimal number of facilities to select from each component is not known, it is necessary to solvep-median problems for every feasible number of facilities on each component. In this paper we give a decomposition algorithm that uses a procedure to reduce the number of subproblems to solve. Computational tests on real instances of the optimal diversity management problem and on simulated instances are reported showing that the reduction of subproblems is significant, and that optimal solutions were found within reasonable time.