# American Institute of Mathematical Sciences

May  2021, 17(3): 1315-1341. doi: 10.3934/jimo.2020023

## Optimal Placement of wireless charging lanes in road networks

 1 School of Computing, Clemson University, Clemson, SC 29634, USA 2 Department of Civil Engineering, Clemson University, Clemson, SC 29634, USA

* Corresponding authors: Hayato Ushijima-Mwesigwa

Received  August 2018 Revised  September 2019 Published  May 2021 Early access  February 2020

The emergence of electric vehicle wireless charging technology, where a whole lane can be turned into a charging infrastructure, leads to new challenges in the design and analysis of road networks. From a network perspective, a major challenge is determining the most important nodes with respect to the placement of the wireless charging lanes. In other words, given a limited budget, cities could face the decision problem of where to place these wireless charging lanes. With a heavy price tag, a placement without a careful study can lead to inefficient use of limited resources. In this work, the placement of wireless charging lanes is modeled as an integer programming problem. The basic formulation is used as a building block for different realistic scenarios. We carry out experiments using real geospatial data and compare our results to different network-based heuristics.

Reproducibility: all datasets, algorithm implementations and mathematical programming formulation presented in this work are available at https://github.com/hmwesigwa/smartcities.git

Citation: Hayato Ushijima-Mwesigwa, MD Zadid Khan, Mashrur A. Chowdhury, Ilya Safro. Optimal Placement of wireless charging lanes in road networks. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1315-1341. doi: 10.3934/jimo.2020023
##### References:

show all references

##### References:
Example of $\mathcal{G}_r$ with $r = (u_1, u_2, u_3)$ and $nLayers = 4$. $u_4$ is an artificial road segment added to capture the final $\textsf{SOC}$ from $u_3$. The nodes in the set $\mathcal{B}_r = \{\mu_{i, j} | i = 4 \text{ or } j = 4\}$ are referred to as the boundary nodes. The out going edges of each node $\mu_{i, j}$ are determined by an $\textsf{SOC}$ function. Each node represents a discretized $\textsf{SOC}$ value
Optimal solution with a four unit installation budget. The thick ends of the edges are used to indicate the direction of the edge. Taking $\alpha = 0$ without any installation, there are 70 number of infeasible routes. An optimal installation of 5 WCLs would ensure zero infeasible routes. With an optimal installation of 4 WCLs, the nodes colored in red, there would have 12 infeasible routes
Directed toy graphs of 26 and 110 vertices used for problems 1 and 2, respectively. The bold end points on the edges of (a) represent edge directions. The graphs are subgraphs of the California road network taken from the dataset SNAP in [47]
Comparison of the different methods. The minimum number of WCL installation needed to eliminate all infeasible routes is $B$. The nodes colored red indicate location of WCL installation. In (a), we demonstrate the result given by our model requiring a budget of 12 WCL'sin order to have zero infeasible routes. In (b) and (c), we demonstrate solutions from the betweenness and eigenvector heuristics that give budgets of 20 and 23 WCL's, respectively
Figures (a) to (f) are plots showing the number of routes ending with final $\textsf{SOC}$ below a given value via the different models. Legend "model: random routes" represents the solution from the proposed model when 100 routes were chosen uniformly at random with $\alpha = 0$ and different budget scenarios. The solution is compared to the solutions from the different centrality measures, a random installation and one with no WCL installation. The $y$-intercept of the different lines shows the number of infeasible routes for the different methods. Our model gives a smaller number in all cases. The plots go further and show how a specific solution affects the $\textsf{SOC}$ of all routes. As the budget approaches 50%, we demonstrate that our model gives a significant reduction to the number of infeasible routes while also improving the $\textsf{SOC}$ in general of the feasible routes
Road segment graphs from real geospatial data: a node, drawn in blue, represents a road segment. Two road segments $u$ and $v$ are connected by a directed edge $(u, v)$ if and only if the end point of $u$ is that start point of $v$
Histograms showing the number of infeasible routes for different values of $\alpha$ and $\beta$ for the Manhattan neighborhood graph. The vertical line indicates the value of $\alpha$. In (a) with a budget of 10%, our model gives a solution with at least 50% less infeasible routes compared to the betweenness heuristic. In (b), we demonstrate how the effects of a 20% budget on the $\textsf{SOC}$ distribution within the network. In (c), our model gives a solution with at least 25% less infeasible routes
The number of routes ending with final $\textsf{SOC}$ below a given value in the lower Manhattan graph. The solution was obtained with $\alpha = 0.7$ and $\beta = 0.1$. The blue curve shows the $\textsf{SOC}$ distribution when no WCL are installed. Green and red curves show the $\textsf{SOC}$ distribution after an installation using the proposed model and the betweenness heuristic, respectively. Plot (b) a gives closer look into (a) for the $\textsf{SOC}$ values below 0.7
Each boxplot depicts the average final $\textsf{SOC}$ for 30 infeasible routes under 50 randomly generated velocity modification scenarios for each $\epsilon_{\nu}$
Using Betweenness Centrality Heuristic to find an Initial Solution
Road category with corresponding speed in Miles/Hr
 Category Road Type Urban Speed Rural Speed 1 Motorway 60 70 2 Trunk 45 55 3 Primary 30 50 4 Secondary 20 45 5 Tertiary 15 35 6 Residential/Unclassified 8 25 7 Service 5 10 8 Living street 5 10
 Category Road Type Urban Speed Rural Speed 1 Motorway 60 70 2 Trunk 45 55 3 Primary 30 50 4 Secondary 20 45 5 Tertiary 15 35 6 Residential/Unclassified 8 25 7 Service 5 10 8 Living street 5 10
Average number of Infeasible Routes for the different methods while varying the global parameter $\alpha$
 $\alpha$ Model $BTN$ $EIG$ $CLN$ $RND$ 0 3180.4 4445.4 6761 6392.4 6637.2 0.2 7159.2 8157.4 9236.6 8845.6 9572.6 0.5 9388.2 9412.6 25411.6 9388.8 10273.8
 $\alpha$ Model $BTN$ $EIG$ $CLN$ $RND$ 0 3180.4 4445.4 6761 6392.4 6637.2 0.2 7159.2 8157.4 9236.6 8845.6 9572.6 0.5 9388.2 9412.6 25411.6 9388.8 10273.8

2021 Impact Factor: 1.411