An exact method for the bi-objective p-median max-sum diversity problem
研究了一个双目标设施选址问题，目标是最小化用户到所选设施的距离和最大化设施间距离，提出了基于ε约束法的精确算法，在500个地点的大规模实例上有效。
This paper introduces a bi-objective facility location problem with two potentially conflicting objectives. The first objective is to minimize the total distance between p selected facilities and the end users they serve (commonly referred to as the p -median objective). The second objective is to maximize the total distance between the selected facilities (commonly referred to as the max-sum diversity objective). We name this problem the bi-objective p -median max-sum diversity problem. The problem follows the bi-level max-sum framework by including a dispersion constraint that prevents selecting two facilities that are within a certain specified distance of each other. If this distance is too large, then the problem is infeasible. Determining an upper bound for feasibility requires solving a max-min dispersion problem, and we develop an improved bi-section search algorithm for doing this, which is more efficient than current exact methods. Then, for the bi-objective p -median max-sum diversity problem (with a fixed value for the distance cut-off in the dispersion constraint), we develop an exact algorithm based on the ϵ-constraint method for determining all Pareto optimal solutions. This involves repeatedly solving a subproblem with quadratic constraints (arising from the quadratic diversity objective) using tangent cutting planes and Benders decomposition. Computational results using the GKD-d dataset show that our exact method is effective for large instances with up to 500 locations.