Strategic Placement of Charging Stations for Enhanced Electric Vehicle Adoption in San Diego, California

Kajal Sheth¹, Dhvanil Patel²

¹Department of Energy, New York Tech, Long Island, USA.
²Petroleum Department, Texas A&M University, College Station, USA.

DOI: 10.4236/jtts.2024.141005                

Abstract

California mandated that 100% of vehicles sold must be electric by 2035. As electric vehicles (EVs) reach a higher penetration of the car sector, cities will need to provide publicly accessible charging stations to meet the charging demand of people who do not have access to a private charging spot like a personal garage. We have chosen to limit our scope to San Diego County due to its non-trivial size, well-defined shape, and dependence on personal vehicles; this project models 100% of current vehicles as electric, roughly 2.5 million. By planning for the future, our model becomes more useful as well as more equitable. We anticipate that our model will find locations that can service multiple population centers, while also maximizing distance to other stations. Sensitivity analysis and testing of our algorithms are conducted for Coronado Island, an island with 24,697 residents. Our formulation is then scaled to set the parameters for the whole county.

Keywords

Electric Vehicles, Charging Stations, Energy Policy, Infrastructure Planning, Environmental Sustainability

1. Introduction

California Governor Gavin Newsom has mandated that 100% of cars bought and sold in California must be electric by 2035 [1] . Other states will likely follow California’s bold lead toward electrifying the car market. The current standard model for electric vehicle (EV) charging relies on the driver having access to a permanent parking spot or garage for nightly charging. As EVs reach higher penetration, urban residents will need a way to charge their vehicles, despite reliance on street parking or an inconsistent rotation of available spots. To meet the charging needs of its residents, cities must think critically about placing publicly accessible charging stations such that there is equitable access to all residents. We define equality as guaranteeing a base local supply for all areas; in contrast, we define equity as maintaining consistent local supply across all areas, including excess supply. Equity and equality in this report are in terms of distance to a charging station and number of available chargers. We will be investigating San Diego County because it has well-defined geographical boundaries [2] and its residents rely heavily on personal vehicles for transportation [3] .

Our objective function represents a sum of all charging supplies. Therefore, we are minimizing the capacity of charging needed to meet demand, such that all people have close access to a charger. We assume that charging demand is concentrated at the centroids of the census block groups in the county, which we call population centers. The willingness to drive a certain distance from the center is modeled as a Gaussian function to determine how well a charging station can serve that population center. This population center approach leads to a non-convex objective function, as there are approximately 1796 census block groups in San Diego County. A trivial result of this optimization is that there is a single charging station at every population center, with a number of chargers that are proportional to the demand at that point. This is not an optimal solution, as it would require a minimum of 1796 chargers. The charger supply would be greater than the demand and purchasing that many chargers is also economically infeasible. Hence, we will assign and parameterize a number of charging stations that is lower than the number of population centers.

To test the formulation of our algorithm and parameterize the number of charging stations we have used Coronado Island as a ’toy problem’ or smaller test case for our algorithm. This allows for easier comparison of charging station placement. To meet demand most efficiently, we add the constraints that the demand at each population center is met and that the demand on each charging station does not exceed supply. Once we have optimized to meet demand, we will apply a third constraint that the station is on a road. This will require a second round of optimization to determine the road vertex that is closest to the charging station location. We are using publicly available Geographical Information Systems (GIS) data to get location-based information for variables and parameters such as population density and road locations [3] [4] .

2. Problem Statement and Analysis

For this investigation, we want to determine the minimum amount of geographically weighted supply (i.e. charging spots) that can still satisfy all geographically weighted demand. We did so by modeling the problem as a flow network shown in Figure 1 where the supply from charging stations feeds into the demand from population centers, with the weights determined by distance. Table 1 shows

Figure 1. Charging demand flow model.

Table 1. Model variables and parameters.

different types of model variable and parameters used for the calculation along with their units.

Minimize:

$f\left(x\right)=\frac{{{\displaystyle \sum }}_{i=1}^N{x}_{n,i}}{{{\displaystyle \sum }}_{j=1}^{N_P}{P}_j}$ Station supply scaled by demand

With Respect to:

$x={\left[x_{lat},x_{long},x_n\right]}^{\text{T}}\in {ℝ}^N$ Latitude, longitude & station supply

Subject to:

$h_{1,i}\left(x\right)={\left[\begin{array}{c}{x}_{lat}\\ x_{long}\end{array}\right]}_i-R_i{}_2=0$ ${\forall }_i$ Station is on road.

$g_{1,j}\left(x\right)=\frac{1}{10}\left(o_j-{\displaystyle {\sum }_{i=1}^N{x}_{n,i}{w}_{ij}}\right)\le 0$ ${\forall }_j$ Demand at each population center is met.

$g_{2,i}\left(x\right)={\displaystyle {\sum }_{j=1}^{N_P}{w}_{ij}}-1\le 0$ ${\forall }_j$ Station supply must at least meet demand.

where:

$w_{ij}=\exp \left(-{\left[\begin{array}{c}{x}_{long}\\ x_{lat}\end{array}\right]}_i-P_j{}_2^2\frac{1}{\beta }\right)$ ${\forall }_{i,j}$ Normalized willingness to drive to station.

$32.58\le x_{lat}\le 32.72$ Geographic bounds of Coronado Island

$-117.23\le x_{long}\le -117.12$

$i\in \left\{1,2,\cdots ,N\right\},j\in \left\{1,2,\cdots ,N_P\right\}$

2.1. Assumptions

Several assumptions were made to simplify the problem and arrive at a feasible solution. All the assumptions are valid in the feasible domain. These are listed below.

· Optimized station locations are snapped to the closest road assuming that it still sufficiently satisfies the demand.

· Existing EV charging infrastructure has not been taken into consideration.

· All vehicles are assumed to be EVs compatible with Level 3 charging.

· Vehicle charging demand is assumed to be linearly dependent on the population and the county-wide car/population ratio of 0.73 approximately.

· A household is assumed to be the central unit for the demand analysis where each household consists of 2.73 people and two cars on average [5] . See Appendix A for further details.

· Willingness to travel to a public charger is modeled as a Gaussian distribution centered around the population center and having a variance of 0.00005 (β = 0.0001).

2.2. Natural and Practical Constraints

We have three sets of constraints. First, h₁ contains N practical constraints to ensure that the charging stations are accessible by road and do not lie in geographically infeasible regions. Next, g₁ contains N_p natural constraints to ensure that the demand from every population center is fulfilled by charging supply at all the adjacent charger locations. Finally, g₂ contains N natural constraints to ensure that sufficient charging infrastructure is set up to at least meet the demand.

2.3. Problem Classification

Problem Class: The problem is a constrained nonlinear problem for spatial optimization.

Continuity: The objective function and the constraints are formulated to be continuous functions.

Smoothness: The problem is not smooth even though it is continuous since the objective function and the constraints are summations, therefore their derivatives are not necessarily continuous.

Convexity: The problem is non-convex since the inequality constraints are governed by the Gaussian function, and it is non-convex. However, the objective function and the equality constraints are linear.

Undefined Regions: There are no undefined regions in the problem formulation.

Size: There are 3N variables to solve for, N equality constraints and (N + N_p) inequality constraints.

2.4. Difficulties in Problem Formulation

Initially the problem was formulated to minimize the sum of the distances between population centers and the charging locations. This raised the possibility of landing at trivial solutions or not getting any solution at all due to the highly non-convex nature of the spatial optimization.

A new approach was designed to treat the optimization problem as a network flow setup where the demand is absorbed by the charging stations, by also varying the supply at each station. Therefore, the decision space expanded to include several chargers at each location in addition to the spatial coordinates. The constraints are set up for the demand-supply scenario and willingness to travel to a public charging station is modeled by a Gaussian distribution.

2.5. Scaling Decisions

Constraint g₂, demand at each population center is fully consumed by the charging stations, was scaled down by a factor of 10 so that the constraints are on the same order of magnitude. The objective function was also scaled down by the total demand to keep it on the same order of magnitude as the constraints. Additionally, the fitting parameter β was also adjusted to achieve convergence of the solution.

2.6. Additional Considerations

There are two additional attributes that are not in the model but could be considered in the future. The first is the density of housing types, determined by the American Community Survey [4] . We could assume that areas with high rates of single-family housing will have a lower demand for public charging stations, as a family that has the space for a personal charger will probably opt for that option. Additionally, we can add the locations of existing charging stations to make the analysis more robust [6] . This would reduce the total number of stations that are needed to meet demand, and it would further constrain where the new stations are located.

3. Optimization Study

3.1. Optimization Approach

As mentioned above, we performed our analysis on a “toy problem” of Coronado Island. The island has sixteen population centers located at the centroids of the census block groups. This allowed us to understand the algorithm and perform a thorough analysis on a much less computationally expensive problem.

For our algorithm, we took a multi-step approach. The first step is to run a genetic algorithm using MATLAB’s “ga” function. We then use the output of the genetic algorithm as starting point for MATLAB’s “fmincon” function. We chose to use a genetic algorithm to create starting points because we anticipated that our objective function would have many local minima and we needed to introduce randomness to find a global minimum. We tested different solvers within the “fmincon” function, such as SQP and interior point. After running six trials with each, we found that SQP was not able to find the global minimum and opted for interior point for the rest of our analysis.

For the two steps above, we kept the constraint that a station is on a road relaxed. We then took the coordinates that were output from MATLAB and input them to ArcGIS, which has a built-in function that can identify the nearest road vertex. This technically leads to a sub-optimal final solution, but we decided that the computation cost of applying the equality constraint along with the others far exceeded the benefit.

3.2. Base Case Results

A few initial runs of our solver showed that N = 6 stations was a reasonable value to use as our base case. Because our optimization is partially stochastic, we ran 100 trials to determine the global minimum. The optimum we found was 1499.94. The optimizers are summarized in Table 2. See Appendix C (Table 8) for more detailed results of this initial study.

Note that we converted the values of x_n to the number of required chargers based on the scaling factors described in Appendix A. To better visualize the results, we plotted the coordinates in Figure 2 below. The darker colored diamonds indicate stations with a higher number of chargers.

Table 2. Base case global optimizers.

Figure 2. Solution of charging stations’ location with and without snapping to road.

3.3 Analysis of Results

For a thorough analysis of this base case solution, see Table 3 below.

Further, Table 4 below summarizes the constraint activity for the global minimum. Note that all of the twenty-two inequality constraints were active to some extent.

As shown above, our Coronado Island solution for charging station locations and sizes is intuitive. The locations of the stations are spread in a way where the four larger stations surround the most densely populated part of the island, and the remaining stations have smaller supply and are located closer to the more sparsely populated parts of the island. Our model assumed that demand would behave similarly to a population centered Gaussian function. Since the stations in our solution are not of infinite or uniform size, are not co-located, and are not randomly located, we demonstrate that this assumption holds for this solution. This is best demonstrated by how our solutions spread out. In the case where our g₁ constraint is the only active case, the stations would tend to cluster in the middle of the population centers. This case would cause the island’s demand to be perfectly supplied, but it would lead to some population centers having more supply than others.

Table 3. Analysis of solution.

Table 4. Constraint summary.

When the g₂ constraint is added each population center cannot be oversupplied, which causes the stations to spread out. In this case, the island would be oversupplied, but each population center would have a fairly equal supply (see Appendix D). When one looks at Table 4 the Lagrange multipliers for constraint g₂ are larger than g₁’s indicating that this constraint is more active. This is desirable because of the equity objective for our problem (equality is guaranteed by constraint g₁). When our model is run just for the Coronado vs when it is run for the entire county (see Figure 3) our Coronado station locations change partially due to these effects. In the county-wide case the non-Coronado population centers change how spread out the stations can become, since if they were to spread out more the stations would be leading to oversupply of some population centers.

4. Sensitivity Analysis

4.1. Constraint Sensitivity

According to Table 4, none of the constraints were truly inactive (i.e. a value of zero), but the level of activity did vary. In general, the value of the Lagrange multipliers for constraint g₁ were much lower than g₂. This indicates that the result is much more sensitive to the second constraint than the first.

4.2. Parameterization of Number of Stations

To understand how sensitive our solution is to the number of charging stations (N), we conducted a parametric study. We performed 100 runs for each N = 1 through N = 15, and Table 5 shows a summary of the results.

Figure 3. Full county preliminary results, snapped to roads (Plotted on GIS).

Table 5. Parameterized Station Count (N)

For N = 1 and N = 2, no minimum was found that satisfied the constraints. This is because the Gaussian w_ij decays in such a way that outlying populations’ demand cannot be met in any station placement configuration. For N = 3 through N = 5, a minimum was found that satisfied the constraints, but it was not the global optimum. For N = 6 through N = 15 a global optimum of 1499.94 was found. For a similar reason as N = 1 and N = 2, the distances to outlying populations w_ij decay such that x_n need to be inflated drastically in order to meet demand. The initial parameterization found an optimum slightly higher for N = 7 through N = 15 (within 0.2). However, when the constraint tolerance was tightened, the higher N values were found to come to the same global optimum, albeit much slower and in more iterations than for N = 6. The same global optimum for various N gave non-unique placements. As N increased, the {x_lat, x_long} minimizers remained the same, with some stations doubling up in placement and occupying the same {x_lat, x_long}. When this occurred, the co-located stations split the x_n value, which indicates that the solver was trying to force a higher N to be equivalent to the global optimum of N = 6.

4.3. Scaling to Full County

We ran the full-county problem once, as shown in Figure 3. We used the optimal N count from the parameterized Coronado Island problem, N = 6, to scale N for the full county. The full county has about 125 times the population, so an N = 750 was used as a scaled N value. However, the ideal N value may not scale linearly. To find the ideal N for the full problem, another parameterization would need to be conducted. We determined that such an analysis is outside the scope of this project.

The full-county problem contains a few quirks not seen in the Coronado Island case. First, with multiple neighborhoods, the algorithm will attempt to make one station serve different areas separated by geographic barriers (mountains, ravines, freeways). Much of San Diego’s residential areas are located atop mesas, which means that some stations were allocated to bridges or mountain roads between such areas; others were snapped to freeways after processing in ArcGIS. Moreover, in the same way that many unsnapped stations in the Coronado Island case were placed in water, one station was placed in Mexico (we wager it’ll make its way to Zihuatanejo in due time).

Another issue is the underservice of sparse areas. As the width β of the Gaussian functions used in our problem was tuned for the urban Coronado Island, the gradients w_ij of for many of the outlying settlements of the county vanish to zero, which prevents any station to move towards fulfilling their demands (or satisfying the constraints in some cases). This can be resolved by tuning β for the appropriate population density or modulating β to change as a function of local population density to accommodate both dense and sparse areas.

5. Conclusions

The problem we address in this investigation is determining the minimum charging supply needed to equitably satisfy the electric vehicle demand of Coronado Island. These stations are weighted by their placement relative to the population (demand) centers for Coronado Island. A parametric study of N, the number of stations, was conducted. For this study, we performed 100 iterations for each N to provide a significant enough sample of our solution space to determine the global solution. The global solution found for Coronado Island was N = 6 stations with a total supply of f = 1499.94. The placement of the stations in this solution is intuitive. The stations form two clusters, one around the more densely populated northern part of Coronado, and the second cluster around the less densely populated lower tail of the island. The size of the stations in these clusters also makes sense as the northern cluster has larger stations than the southern cluster. When the sum of the charging supply is converted to a number of chargers, the solution suggests that roughly twenty-five high-speed chargers would be needed to fulfill the demand for Coronado Island. If we only consider demand and neglect constraints, only seventeen chargers are needed to meet the demand for Coronado Island; however, our constraints are set up in order to enforce equality and equity of access, both important factors in building infrastructure networks. Our model reflects a 35% increase in the number of chargers needed, which indicates that our model is non-trivial, and that location is important.

Our model suggests six optimal locations to place these chargers and therefore has some advantages over a centralized or uniform location scheme. However, like all models, our model makes assumptions that could affect the real number of chargers needed. For example, we assume that the cost at a charger station is linear with the amount of chargers at each station x_n. In reality, there are fixed costs associated with setting up a station. Our model also assumes that the demand comes purely from the residents of the island and neglects people who travel to Coronado during the day and may need to charge. These factors would cause the numbers of chargers at each station, the location of stations, and the overall number of charging stations to change. Furthermore, we assumed equal demand among residents. In reality, factors like type of home and commute distance may impact charging demand greatly between residents in a way that was not factored in for this analysis. While these concerns fell outside the scope of this investigation, they provide a basis for future investigations.

Appendix A. Total Charging Station Estimation

The Scope of our investigation is limited to Coronado Island; however, county-wide demand data was scaled down to estimate charging demand per person for the island of Coronado. Since Coronado Island is a part of San Diego County, these county-wide figures were then scaled to Coronado’s population. The population density, based on census block groups was obtained from the 2018 census. San Diego county has a population of 3.34 million [2] , which is unevenly distributed throughout the county. To define the scope of the optimization problem, the objective function should represent the number of electric vehicles on the road as a function of the population density. More specifically, the number of vehicles that would require charging at any given time was estimated based on some aggregate assumptions and generalizations about San Diego County that could then get scaled to the known population of Coronado Island. Table 6 shows average distribution of household types with the availability of home chargers within San Diego region.

First, the housing trends statistics from San Diego’s Regional Planning Agency (SANDAG) shows that the average household size in the region is 2.73 persons per household [5] and each household has 2 cars on average [5] . Therefore, San Diego has approximately 2.45 million on-road vehicles; this is consistent with total estimates of on-road vehicles (2.5 million) [7]

The following assumptions were made to estimate the charging requirements for EVs:

· Average daily usage of each car - 25 miles

· Average maximum range for EVs - 250 miles

· Level 1 chargers - 32 Amp chargers give 25 mi/hr of charging

· Level 2 chargers - 50 Amp chargers give 37 mi/hr of charging

· Level 3 chargers - 300 Amp superchargers give 1000 mi/hr of charging

Optimistically assuming that the charging infrastructure will support level 3 fast charge, the total number of charging stations required in a perfect charging scenario is as follows:

Demand:

$D_{\text{miles}}=N_{\text{cars}}\ast \text{DailyMiles}=61.2\ast {10}^6\text{miles}$

Supply per charger:

$S_{\text{miles}}=1000\text{mi/hr}\ast 24\text{hr/day}=24,000\text{mi/day}$

Now we know the total demand and the amount of demand supplied by each type of charger, so we can determine how many chargers we need assuming no inefficiencies or down-time:

Table 6. Household statistics.

Number of chargers:

$N_{\text{chargers}}=\frac{\text{TotalDemand}}{\text{Supplypercharger}}=2550\text{chargers}$

Based on the regional average distribution of household types, the availability of home chargers was estimated.

Considering only 50% of the household require access to public chargers on a regular basis and 50% require access to public chargers for opportunity charging. We also factor in 60% charger downtime due to inefficiencies and day-time/night-time cycle:

Effective Number of chargers:

$N_{\text{chargers}}=2550\ast 0.5\ast 1.25\ast 1.6\approx 2550\text{chargers}$

This means with the super charger case we would need 2100 chargers to meet the county’s demand for charging. This averages out to approximately 1300 individuals and about 1000 cars using each public EV charger each day.

When calculated for Coronado is land’s population of 24,697 people, the constant demand model here suggests 17 super charges for the island (ignoring distance to chargers and just meeting baseline demand). The 1500.08 supply number from our model when re-scaled, leads to a supply of 30,000. As one can see below this means we would need around 23 super chargers on the island of Coronado. Table 7 shows the number of charges supplied to different charging station and scaled according to the number of chargers at each station.

Coronado population to chargers conversion (no account for equity) uniform model:

${\#}_{\text{chargers}}=21,400\text{people}\ast \frac{1}{300\text{people/charger}}=17\text{chargers}$

Coronado Supply to chargers conversion our model:

$\begin{array}{c}{\#}_{\text{chargers}}=1500.8\text{calculatedsupply}\ast 20\text{un-scalingfactor}\ast \frac{1}{1300\text{people/charger}}\\ =23\text{chargers}\end{array}$

Table 7. Stations’ supplies scaled to number of chargers.

Appendix B. Matlab Code

Optimization Main Function and Constraints & Variable Functions

function [X_end, F, exitflag, output] = optimization_EV(zip, p_lat, p_lng, demand, N, plots)

%%%%%%%%%%%%%%%%%% Globals %%%%%%%%%%%%%%%%%%%%%%%

% N = 5; % Number of charging stations B = 0.0001; %% fitting parameter

P = [p_lat'; p_lng'; demand']; % Populations centers (lat, long) (j)

%%%%%%%%%%%%% objective function %%%%%%%%%%%%%%%%%% avg = sum(demand) / N;

ga_options = optimoptions(@ga,'NonlinearConstraintAlgorithm','penalty');%, 'InitialPopulationMatrix', pop);

lb_ga = [-117.2*ones(1, N), 32.55*ones(1, N), ones(1, N)];

ub_ga = [-117.1*ones(1, N), 32.75*ones(1, N), avg*N*ones(1, N)]; [X_end, ~] = ga(@(X) objective_ga(X), N*3, [], [], [], [], lb_ga',

ub_ga', @(X) constraints_ga(X, P, B), ga_options);

X_ga = [X_end(1,1:N); X_end(1,(N+1):(N*2)); X_end(1,(2*N+1): (N*3))];

lb = [-117.2*ones(1, N); 32.55*ones(1, N); ones(1, N)];

ub = [-117.1*ones(1, N); 32.75*ones(1, N); avg*N*ones(1, N)]; fmincon_options = optimoptions(@fmincon, 'MaxIterations',

inf, 'MaxFunctionEvaluations', inf, 'Algorithm', 'interior-point'); [X_end, ~, ~, ~] = fmincon(@(X) objective(X, P), X_ga, [], [], [],

[], lb, ub, @(X) constraints(X, P, B), fmincon_options); [X_end, ~, exitflag, output] = fmincon(@(X) objective(X,

P), X_end, [], [], [], [], lb, ub, @(X) constraints(X, P, B), fmincon_options);

F = sum(X_end(3,:));

if plots == 1 figure;

mapshow(zip, 'edgecolor', 'k', 'facecolor', 'none') hold on;

scatter(p_lat, p_lng, 'oc'); if size(X_end, 1) == 3

scatter(X_end(1,:), X_end(2,:), 20,

X_end(3, :), '*', 'linewidth', 1.5);

scatter(X_ga(1,:), X_ga(2,:), '.b', 'linewidth', 1.5); disp(sum(X_end(3, :)));

else

scatter(X_end(1,1:N), X_end(1,(N+1):(N*2)), 20, X_end(1,

(2*N+1):(N*3)), '*', 'linewidth', 1.5);

disp(sum(X_end(1,(2*N+1):(N*3))));

end

end

end

function [W, dwdlat, dwdlng] = create_w(X, P, B) % weight function

x_lat = X(1, :);

x_lng = X(2, :);

p_lat = P(1, :);

p_lng = P(2, :);

[x_lat_mesh, p_lat_mesh] = meshgrid(x_lat, p_lat); [x_lng_mesh, p_lng_mesh] = meshgrid(x_lng, p_lng); d_lat = x_lat_mesh - p_lat_mesh;

d_lng = x_lng_mesh - p_lng_mesh; D = d_lat.^2 + d_lng.^2;

W = exp(-D./B);

dwdlat = -2 .* d_lat .* W ./ B;

dwdlng = -2 .* d_lng .* W ./ B;

end

function [g, h] = constraints(X, P, B) % scaled (Fmincon) x_n_i = X(3, :);

p_o_i = P(3, :);

[W] = create_w(X, P, B);

g1 = ((p_o_i') - sum(x_n_i .*W, 2))/10; g2 = -1 + sum(W, 1)';

g = [g1; g2];

h = [];

end

function [f, df] = objective(X, P) % scaled (Fmincon) x_n_i = X(3, :);

p_o_i = P(3, :);

f = sum(x_n_i)/sum(p_o_i);

end

function [g, h] = constraints_ga(X, P, B) %unscaled (GA) Nx = length(X)/3;

X_ga = [X(1, (1):(Nx));X(1, (Nx+1):(Nx*2));X(1, (Nx*2+1):(Nx*3))];

x_n_i = X(1, (Nx*2+1):(Nx*3)); p_o_i = P(3, :);

[W, ~, ~] = create_w(X_ga, P, B);

g1 = (p_o_i' -sum(x_n_i .* W, 2)); g2 = -1 + sum(W, 1)';

g = [g1; g2];

h = [];

end

function [f, df] = objective_ga(X) % unscaled (GA) Nx = size(X, 2)/3;

x_n_i = X(1, (Nx*2+1):(Nx*3)); f = sum(sum(x_n_i));

end

Outer Wrapper Function for Running Parame-Terization

%%%%%%%%%%%%%% Population Data %%%%%%%%%%%%%%%%

%%%% Full County

% raw_data = xlsread('toy_data/san_diego_centers.xlsx', 'san_diego_centers'); % full county

% zips = shaperead('Full_data/USA_Counties.shp'); % full county

%%%% Toy Problem

raw_data = xlsread('toy_data/ san_diego_centers.xlsx', 'coronado'); % toy

zips = shaperead('toy_data/2010_Census_5- digit_ZIP_Code_Tabulation_Areas.shp'); % toy

%%%% Processing

zip = zips(1); % creates a polgon p_lng = raw_data(:, 4);

p_lat = raw_data(:, 5); demand = raw_data(:, 6); stats = zeros(200, 16);

%%%% Function Call for N = 1:15

plots = 0; %binary plot or not (1 if all plots) runs = 100;

xs = zeros(300, N+3); for i = 1:runs

p = (i)*3;

[x, n, exitflag, ~] = optimization_EV(zip, p_lat, p_lng, demand, N, plots);

xs([p-2,p-1, p], 4:(N+3)) = x;

xs(p-2, 1) = i;

xs(p-2, 2) = n;

xs(p-2, 3) = exitflag; disp([N,i]);

end

writematrix(xs,'final_comparison.xls', 'sheet', sprintf('N=

%f', N));

ns = xs(:,2);

ls = ns(ns > 1);

[m] = min(ls);

I = find(ls==m); stat = [N; m; I];

stats(1:size(stat), N-2) = stat;

end

%%%% Summary Tab

writematrix(stats,'final_comparison.xls', 'sheet', 'stats');

Random Multistart Generator for Inside the Is-Land/County Bounds

function [x, y] = toy_multistart(N, zip) stBB = zip.BoundingBox;

st_minlat = min(stBB(:,2)); st_maxlat = max(stBB(:,2)); st_latspan = st_maxlat - st_minlat; st_minlong = min(stBB(:,1)); st_maxlong = max(stBB(:,1));

st_longspan = st_maxlong - st_minlong; stX = zip.X;

stY = zip.Y;

x = zeros(1, length(st_minlong)); y = zeros(1, length(st_minlat)); for i = 1:N

flagIsIn = 0; while ~flagIsIn

x(i) = st_minlong + rand(1) * st_longspan; y(i) = st_minlat + rand(1) * st_latspan; flagIsIn = inpolygon(x(i), y(i), stX, stY);

end

end

end

Appendix C. Base Case Results: Frequency of Minima

Table 8. Breakdown of 100 runs for N = 6 stations.

Appendix D. Constraint Activity and Spreading

See the Figure 4 below for a visualization of how our constraints affect the spreading behavior of the stations. This explains our results for the toy problem, where most stations spread into the ocean before being snapped back onto roads.

Figure 4. Constraint values under various geographical spreads.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Pfeiffer, S. (2020) California Gov. Newsom Calls Transition To Electric Cars An “Economic Imperative”. https://www.npr.org/2020/09/24/916625380/california-governor-on-his-order-to-ban-sale-of-new-gasoline-vehicles-by-2035
[2]	San Diego Association of Governments (SANDAG) (2020) Regional GIS Data Warehouse. https://sdgis-sandag.opendata.arcgis.com/
[3]	U.S. Census Bureau (2020) Mapping Files. https://www.census.gov/geographies/mapping-files.2020.List_1421273848.html#list-tab-List_1421273848
[4]	U.S. Census Bureau (2018) American Community Survey: Selected Housing Characteristics. https://data.census.gov/table/ACSDP1Y2019.DP04?q=housing&hidePreview=false
[5]	Data USA (2019) SAN DIEGO COUNTY, CA. https://datausa.io/profile/geo/san-diego-county-ca
[6]	U.S. Department of Energy (2020) Electric Vehicle Charging Station Locations. https://afdc.energy.gov/fuels/electricity_locations.html#/find/nearest?fuel=ELEC
[7]	(2019) California Department of Motor Vehicles. Estimated Vehicles Registered by County. https://www.dmv.ca.gov/portal/uploads/2020/06/2019-Estimated-Vehicles-Registered-by-County-1.pdf