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.
-
1$\begingroup$ It sounds like a version of the conditional $p$ dispersion problem link.springer.com/article/10.1007/s10898-020-00962-4 $\endgroup$– SuneMay 29, 2022 at 14:28
-
1$\begingroup$ What do you mean by "potential location"? $\endgroup$– prubin ♦May 29, 2022 at 14:56
-
$\begingroup$ Sorry for lack of clarification. Potential location are locations of interest: parking areas, residential areas etc. $\endgroup$– IshaanMay 29, 2022 at 17:07
-
1$\begingroup$ We need more details. (1) Are you locating a fixed number of new charging points, or is the number a decision? (2) Can you locate them only at a finite number of specified points, or can coordinates be chosen anywhere in a given area (rectangle or whatever)? (3) Should the distance between any two new charging points be maximized, or is it bounded below by a constant, or do you not care about it (only care about distance to existing charging points)? $\endgroup$– prubin ♦May 29, 2022 at 21:02
-
$\begingroup$ Yes it is a fixed number of charging points, this rings p-median problem in my head. The points can be located anywhere in a grid(area), however we could consider the centroid of the this grid and make the problem discrete. The distance between the new charging points should be maintained within a bound I guess. But, the distance between existing charging points and new charging points should be maximized. $\endgroup$– IshaanMay 31, 2022 at 14:58
1 Answer
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.
-
$\begingroup$ Thank you, I was wondering if you could provide a reference to the Quadratic Assignment Problem. I am not able to find the correct resources highlighting the reward and penalization indicated. $\endgroup$– IshaanMay 31, 2022 at 20:12
-
2$\begingroup$ I don't have a particular "go to" reference for the QAP, and I am not sure if any references bother to include a linear objective term in addition to the quadratic term. I've added a model to my answer to show how a formulation might look. $\endgroup$– prubin ♦May 31, 2022 at 20:16
-
$\begingroup$ Wow thank you. This helps me understand so much! :)) $\endgroup$– IshaanMay 31, 2022 at 21:07
-
$\begingroup$ Just wanted to ask what do $l'$ and $l$ suggest? $\endgroup$– IshaanJun 1, 2022 at 5:45
-
1$\begingroup$ $\ell$ and $\ell^\prime$ index two distinct potential locations for charging points. (If $\ell = \ell^\prime,$ presumable $d_{\ell \ell^\prime}=d_{\ell \ell}=0$ and the term drops out of the summation.) $\endgroup$– prubin ♦Jun 1, 2022 at 16:15