EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

249. The Planar Obnoxious Facilities p-Center Problem

Invited abstract in session TB-61: Nonlinear Location Optimization, stream Locational Analysis.

Tuesday, 10:30-12:00
Room: S10 (building: 101)

Authors (first author is the speaker)

1. Pawel Kalczynski
Information Systems Decision Sciences, California State University, Fullerton
2. Zvi Drezner
California State University, Fullerton

Abstract

The p-center problem is one of the classical location analysis problems. It involves locating one or more facilities (in the plane or on the network) among multiple demand points while minimizing the largest distance between a facility and a demand point. Recent papers present novel solution techniques that allow for solving large-scale planar p-center problems. However, p-center models involving obnoxious facilities have yet to be investigated. Obnoxious facilities emit or inflict nuisance, such as noise or pollution, on the demand points. This nuisance propagates "by air," so it can be reduced by locating the facilities further away from the demand points. However, this new property makes p-center models nonconvex and more challenging to solve.
We formulate the planar obnoxious p-center problem as a general non-linear program and reformulate it as a nonconvex quadratically constrained optimization problem. We present two solution techniques: an optimal (within tolerance) one involving the linearization of non-linear constraints and one involving a multi-start approach with a local solver (without the optimality guarantee). The effectiveness and efficiency of our techniques are demonstrated on both generated and commonly used instances of the p-center problem. In addition, we investigate the impact of the obnoxious property on the planar p-center problem difficulty and solution quality.

Keywords

Status: accepted

Back to the list of papers