{'fraction_non_alphanumeric': 0.0258972554539057, 'fraction_numerical': 0.005629838142153413, 'mean_word_length': 4.911397670549085, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improved Set Covering Location Model for Charging Facility Deployments

While electric vehicles (EVs) can assist in resolving environmental pollution and resource scarcity problems, they require specific infrastructure developments. Destination chargers, which are based on current charging technologies and EV characteristics, have been the main charging facilities employed. Using an Improved Set Covering Location Model (ISCLM), the primary objective of this paper is to determine how destination chargers could be deployed in urban areas. As the model basis, the purpose, time, and parking conditions of urban car-use behaviors are first analyzed, based on which the ISCLM is constructed. As the basic Set Covering Location Model (SCLM) is an NP-hard problem, improvements in the assumptions and solution algorithms are made so that the ISCLM treats all demand points as equivalent regardless of the internal sizes. As it is also assumed that the service range for all charging stations is circular and have the same radius, the ISCLM is a polynomial problem; therefore, the Minimum Covering Circle algorithm and the Voronoi Graph are used to derive the destination charger deployment solution. To verify the effectiveness of the ISCLM, the model is used to analyze a specific area in Beijing. In this case study, the simulated demand points were selected based on the location of actual parking lots in residential communities and office buildings. The results validated the enhancement in the ISCLM network architecture.


Introduction
As electric vehicles (EVs) use clean energy, they can reduce greenhouse gas emissions, alleviate urban pollution, and assist in resolving environmental problems. However, to encourage people to switch gasoline and diesel cars to EVs, there needs to be a commensurate rise in the construction and deployment of charging facilities. Currently, there are two types of charging facilities available to EV users; destination chargers and superchargers. What markets are currently assessing is the minimum investment needed to meet the EV charging requirements in a specific area and the charging facility construction that can cover as large an area as possible.
Research has therefore been ongoing on the development of site selection algorithms [1][2][3], for which two mainstream models have been developed; point-based demand models and path-based demand models [4]. Point-based demand models assume that the demand is generated at certain nodes in the road network, and therefore the minimum distance between the demand points and the charging stations has been the optimization goal. Major models currently available are the P-Center Model [5], the P-Median Model [6] and the Covering Location Model [7][8]. Of these models, the Covering Location Model has been found to have the best ability to improve network architecture [9]. For path-based demand models, the energy demand is not limited to the nodes but is based on road section traffic volumes, with the optimization goal being to achieve the maximum traffic volume that can be served by each charging station [10]; therefore, adjacent road sections with high traffic have been found to be the preferred charging station sites.
Existing research has tended to focus on the rapid charging and refueling typical of the supercharging mode, for which road section traffic volume and path-based demand model implementation and improvements have been the main focus [11][12][13]. Therefore, road conditions, dynamic vehicle driving area changes, and market-oriented services are the focus of this model. However, the current EV charging technologies have long-term charging characteristics, which is the main difference between conventional fuel vehicles and EVs. Therefore, it has become more important to first meet the basic requirements necessary for long-term EV charging, which means that the infrastructure should be aimed at fixed demand points. Therefore, in this paper, we focus on point-based demand models, or destination charging, rather than path-based demand models.
Based on above research, network layout optimization and the associated algorithms for deploying destination chargers within a certain boundary can still be improved; therefore, an Improved Set Covering Location Model is proposed to improve the efficiency and accuracy of the existing models.

Preparation of the Model
Charging facility deployments are a technical economics optimization problem. As the optimization model should be constructed and evaluated based on real world situations, the following background settings are proposed before the establishment of the models.

Charging Facilities
Existing EV charging technologies take about 6-10 hours to fully charge a battery, after which the EV can travel from 300-500 kilometers [14]. Depending on the environment and the charging requirements, Tesla, the leading corporation in this field, offers two types of charging facilities; destination chargers and superchargers.
As destination chargers are designed to fully charge the battery, they have a relatively low charging rate and require several hours to reach a full charge. Because of these characteristics, destination chargers are usually installed in mall parking lots, hotels, residential communities or other public places where people can park and charge their cars.
Superchargers, however, can charge the battery in a relatively short period of time, and are designed to meet urgent charging needs; therefore, these charging facilities are generally installed on city streets in the same way as gas stations.

Car-use Behavior in Urban Areas
As the premise for the later analysis, car use patterns and rules are briefly discussed in the following sub-section.

Purpose.
City traffic can be divided into commuting and non-commuting depending on the purpose and the destination [15][16][17].Commuting refers to people moving between their homes and work places, and non-commuting traffic is when people travel to other destinations. Commuting traffic has relatively fixed routes and travel times, and non-commuting traffic has random routes and travel times. Both car use trends tend to be the most important for people in urban areas. a.m. and 10 p.m [18]. As these car use data can give some indication as to the possible EV charging demand during the day, they provide guidance for the installation of effective charging networks.

Parking Conditions.
Generally, the best time to charge an EV is when it is parked and idle. Most people, therefore, would choose to charge their cars at night from 10 p.m. to 6 a.m. As most people park in their own neighborhood or in other public parking lots, installing charging stations in these places would be the most effective plan.

Strategies for the Deployment of Charging Stations
Based on the above analysis, the typical car-use patterns for urban residents are as follows: 1. Relatively fixed routes and travel times. 2. Car-use distribution time is centralized and has a short time span. 3. People tend to park in places that can accommodate many cars. 4. Travel distances are relatively short. Because of the short time-span, EVs owners have plenty of time to use destination chargers. Therefore, when deciding where to deploy charging networks, destination rather than superchargers should a priority to satisfy the daily charging demands of EV owners, which is a key difference between gasoline and diesel cars and EVs.
Further, all mass parking environments such as residential communities, malls, public parking lots, and work places should be fully considered when demand points are selected. To minimize the number of charging stations within a certain degree of need, an Improved Set Covering Location Model (ISCLM) is proposed, which has the following assumptions: 1. There is a strong correlation between the charging station site distribution and the number of EVs in the area. However, site configuration is an infrastructure construction problem and requires forward-looking approaches. Therefore, this model assumes that the EV ownership in a certain area is linearly related to the local population density or the working place areas, and that this ownership is uniformly distributed in a spatial dimension. 2. Sufficient charging equipment is installed at each charging station to fully meet the requirements of all EVs within the service coverage area. Fig. 1 below is an abstract graph of a city map (without roads), in which the smaller black dots are the actual locations with a certain EV charging demand, and the red dots are the charging stations. However, as can be seen, as the charging stations are randomly distributed, they are unable to service all demand points; therefore, in the following, we discuss how these stations can be distributed.

Improved Set Covering Location Model
Church and Revell proposed a Maximum Covering Location Model (MCLM) for a sites selection problem [19], which was mainly applied to deploy a certain number of facilities to cover the maximum demand. While the Set Covering Location Model (SCLM) is a better choice for determining the minimum number of sites in a certain district.
However, the basic SCLM is an NP-hard problem [20], which makes it difficult to solve. So, an Improved Set Covering Location Model (ISCLM) is proposed, the goal of which is to minimize the number of charging stations to cover certain demand.
The term cover is used here to describe a demand point that is within the service range of at least one charging station.
The ISCLM model is formulated as follows: Given a set of elements For every subset j S , the following variable is introduced: Based on these notations, the SCLM is constructed: s.t Here, the model makes two important assumptions based on the basic SCLM; the service range of all charging stations is a circle with the same radius, and every charging station can provide unlimited service and can satisfy all demand point requirements once it is within the station's service range. It also means that the model treats all demand points in the same way, ignores the number of facilities inside the charging station, focuses only on the network topology.
To conduct research on how a charging station can cover the surrounding demand points, the Minimum Covering Circle algorithm is introduced.

Minimum Covering Circle
In a location planning problem such as this, the main effect of the Minimum Covering Circle theory is to assist in determining the least cost for a charging station to serve the furthest demand point in its coverage.
The model can be abstracted into the following problem: There are n points in 2 ; therefore, the goal is to determine the circle O s.t that contains all n points and has a minimum radius. Given this definition, the Minimum Covering Circle Model is constructed as: The solution to this model is indicated in Fig.2 which shows the flow chart for the Minimum Covering Circle algorithm.

Voronoi Graph
Obviously, as users select the nearest charging station, it is necessary to determine the corresponding relationships between n demand points and the m charging stations to be implemented. For this purpose, the Voronoi Graph algorithm is introduced [21]; Let , 1, 2,..., be the V-polygon of i x . The boundary of i V and D determined the Voronoi graph for these n points.
The Voronoi Graph for the following five red points is constructed in Fig.3.

Solution
To effectively deploy the destination chargers, the ISCLM is applied and the Minimum Covering Circle algorithm and the Voronoi Graph are employed to solve the model.
Step Step 3: If the radius of all x O is smaller than r , the B is what is desired; then, use 1 N  to replace N , and repeat Step 1.
Here, the N in Step 1 for the first time is determined from the area of  and r ; if the distance between the two points is close enough, they are considered one point.
In this way, the elements in B are the locations at which to establish the charging stations. Fig.4 shows the flow chart for the Improved Set Covering Location Model algorithm.

Case Study
To verify the effectiveness of the ISCLM, a simulation was conducted based on geographical information from Beijing, the capital of China. Fig. 5 shows the Beijing city map with the simulated demand points extracted from Google Maps. As discussed in 2.2, an area in the city center was first selected, after which the demand points were chosen based on the people's parking behaviors. In this case, these selections were mainly centralized at parking places, such as communities, office buildings and public parking lots.  Table 2. Coordinates for the charging stations No.
x y No.
x y No.

Conclusion
Based on current charging technologies and EV behavioral characteristics, destination chargers are currently being used at charging facilities. In this paper, an Improvement Set Covering Location Model (ISCLM) was presented to solve the destination charger deployment problem in urban areas. Two extra assumptions were appended to the ISCLM and the model improved to become a polynomial problem. The Minimum Covering Circle algorithm and the Voronoi Graph were then employed to find the solution to the ISCLM. The ISCLM was then demonstrated in a practical example for the deployment of destination charging stations in a specific Beijing district of 142.34 square kilometers, with the assumptions that the service range for each charging station was 3.2 kilometers and the charging time was 8 hours. Based on the calculation results, the optimal solution was found to be 12 charging stations. If a uniform distribution model were used, 18 charging stations would be needed; therefore, the ISCLM was proven to give a more effective solution than uniform distribution models. Further research, however, is still necessary. First, while the ISCLM assumes that all demand points are the same, in practice, different places have charging different needs. Therefore, another demand point weight variable is needed to account for these differences. Second, this paper only considered one of the two types of charging facilities; therefore, it is necessary to develop models that also consider supercharger deployments.