Document Type : Research Article

Authors

• Sina Nemati
• Jafar Fathali
• Abolfazl Poureidi

Faculty of Mathematical Sciences, Shahrood University of Technology, University Blvd., Shahrood, Iran

Abstract

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 L_p 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-IFLP1, IFLP2, and IFLP3-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 IFLP1 achieves the lowest CPU time and smallest unbalancing number, while IFLP3 yields superior performance in termsof total transfer cost and is recommended for practical applications

Highlights

• The inverse balanced two-facility location problem in the Euclidean plane is formally introduced and studied for the first time.
• The weight-modification variant in the plane is proven to be equivalent to its network counterpart, solvable in O(n log n) time under any L_p- norm.
• A coordinate-reduction theorem is established: exploiting the isometric property of Euclidean rotations, the planar problem reduces to an equivalent one-dimensional problem without loss of generality.
• Three greedy algorithms (IFLP1, IFLP2, IFLP3) are proposed for the coordinate-modification case, targeting the unbalancing number, transfer cost, and a hybrid criterion, respectively.
• Under uniform weights and identical modification costs, all three algorithms are proven optimal with O(n²) time complexity.
• Experimental results on standard benchmarks and synthetic datasets confirm that IFLP1 minimizes CPU time and unbalancing number, while IFLP3 achieves the lowest transfer cost and is recommended for practical use.
• A sensitivity analysis reveals that initial facility weight imbalance is the primary driver of computational effort and transfer cost, with no systematic dependence on facility index selection.

Keywords

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

Main Subjects

• Optimization & Operations Research