How to model this problem?

Question

I have recently tasked with a problem in which I have to locate electric vehicle charging points (new) keeping in mind that there continue to exist older charging points. The problem is to model the solution such that the distance between old and new charging points is maximised and the distance between new charging points and potential location is minimised. I was wondering if anyone could assist me with the domain of this problem. Trivially, this problem lies within the Facility Location domain; however, I am not able to correctly how to include the two distances within my model.

Answer 1

If it is desired to keep the new points somewhat close together rather than dispersed from each other, then I do not think the conditional $p$ dispersion problem is applicable. If we assume a discrete set of candidate locations, this might fit into the category of generalized quadratic assignment problem (GQAP), where the quadratic portion of the objective penalizes distances between pairs of new charging stations and a linear term rewards distances between new stations and existing stations. The balance between penalties and rewards (i.e., the relative importance of keeping the new points close together versus keeping them away from existing points) would require weighting the linear term appropriately.

With a discrete set of locations and a goal of keeping the new points away from each other as well as away from the existing points, this might fit the conditional $p$ dispersion problem and might also be modeled as a GQAP (as above, only with both linear and quadratic objective terms rewarding distance).

Addendum: Here is a model (variant of the QAP), assuming a finite grid of possible locations. The sets $N$, $L$ and $F$ index respectively the charging points to be placed, the available (unused) locations and the fixed locations containing existing charging stations. $d_{mn}$ is the distance (in whatever metric you like) between two grid points $m,n \in L\bigcup F.$

We will use binary variable $x_{n\ell}$ to indicate whether a charging station is placed at available location $\ell \in L$ or not. The constraints are very simple: $$\sum_{\ell in L} x_{n\ell} = 1 \quad \forall n\in N$$ (every station gets placed once) and $$\sum_{n\in N} x_{n\ell} \le 1 \quad \forall \ell \in L$$ (no location gets used more than once). For the problem to be feasible, you need to have at least as many available locations as you have charging points that need to be placed ($\vert L \vert \ge \vert N \vert$).

The objective function (to be minimized) is $$\sum_{n \in N} \sum_{n^\prime \in N : n^\prime > n} \sum_{\ell \in L} \sum_{\ell^\prime \in L} d_{\ell \ell^\prime} x_{n\ell} x_{n^\prime \ell^\prime} - \lambda \sum_{n \in N} \sum_{\ell \in L} \sum_{f \in F} d_{\ell f} x_{n\ell},$$where $\lambda > 0$ is a parameter you use to control the tradeoff between minimizing the distance between pairs of new charging points and maximizing the distance between new and existing points.