Inverse Balanced Facility Location Problem in the Plane

Classical inverse location models aim to modify problem parameters such that pre-specified facility locations become optimal with respect to a given objective. This paper addresses a fundamentally different variant: the inverse balanced    facility location problem in the Euclidean plane, in which parameters are adjusted so as to achieve an equitable distribution of client demand between two given facilities. Specifically, given a set of n weighted points in the plane and two predetermined facility locations, the objective is to minimally modify either the weights or the coordinates of the client points such that the absolute difference in total demand assigned to each  facility-referred to as the unbalancing number-is minimized. For the weight-modification case, we establish that the planar problem is structurally equivalent to its network counterpart and is therefore solvable in O(n Log n) time under any Lp norm, via an existing linear programming formulation. For the coordinate-modification case under the Euclidean norm, we exploit the isometric property of orthogonal rotations to prove that thetwo-dimensional problem reduces, without loss of generality, to a one-dimensional problem along the perpendicular bisector of the segment joining the two facilities. Leveraging this reduction, we design three novel greedy algorithms-IFLP۱, IFLP۲, and IFLP۳-that prioritize minimization of the unbalancing number, minimization of the total transfer cost, and a hybrid criterion balancing both objectives, respectively. Under uniform weights and identical modification costs, all three algorithms are proven to yield optimal solutions and operate within O(n۲) time  complexity. Extensive computational experiments on standard benchmark datasets and randomly generated instances demonstrate that IFLP۱ achieves the lowest CPU time and smallest unbalancing number, while IFLP۳ yields superior performance in termsof total transfer cost and is recommended for practical applications

کلیدواژه ها:

Facility location ، Inverse facility location ، Balanced allocation ، Greedy algorithm ، Coordinate modification ، Euclidean plane