{'fraction_non_alphanumeric': 0.024394966118102615, 'fraction_numerical': 0.005098418844788641, 'mean_word_length': 4.805919820157363, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, '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}}
A new site location approach based on Filtering and Clustering for car sharing system

Car sharing service provides people with a new environmentally friendly way to travel. In car sharing system, one of the major challenges is how to determine the location of the car sharing sites. However, the existing method does not take into account people’s demand in reality to select the car sharing sites position. In this paper, we focus on selecting the car sharing sites location by using real taxi GPS trajectories and propose a new method based on filtering and clustering for the location problem. Large-scale real-world experiments shows that the method we proposed in selecting car sharing sites has a better performance than other approaches. Introduction In order to reduce traffic pressure and effectively utilize idle vehicles, car sharing system, which allows people to rental vehicle for short distance journey, gradually shows its importance. As an alternative public transportation, car sharing system has been proved to have a positive effect on urban mobility[1], the mobile and flexible characteristic of car sharing system in the city's transportation system, particularly in the short distance journey has manifested the superiority which other transportation means do not have. With the development of the electric vehicles, car sharing system will have further significant benefits even have the potential to replace traditional private vehicles. Electric vehicles have been observed as the best candidate for shared vehicle systems because of the zero emission[2]. One of the major challenges encountered by the car sharing system providers is selecting the appropriate locations for car sharing sites. Regarding to the service which a car sharing site provide, it is crucial that the site which can serve more people who can reach in short time. In scientific literature on transportation networks, this problem is known as the depot location. The selection of car sharing site location should take quality of service, efficiency of service and the cost of service into consideration. Therefore, a future study of appropriate location for car sharing would be necessary. To select the location of car sharing system sites, we should build a travel requirement module in the service area precisely. The requirement for car sharing usually refers to how much of vehicles is desired, hence we use the taxi trajectory data to present this requirement. In this paper, we propose to locate the car sharing sites based on filtering and clustering. To evaluate this module, we use the real data source of taxi GPS trajectories which generated by over 12,000 taxis in Beijing. The contribution of this paper includes: (1) We proposed a method to aggregate demand points to facilitate clustering based on Grid-distance. (2) We consider the size of each aggregation point as a parameter for the clustering algorithm. And we proposed that Affinity Propagation clustering algorithm is more proper in selecting location of car sharing sites. (3) Extensive experimental results on real data source of taxi GPS tracks collected from over 12,000 taxi in Beijing demonstrate that our location selection mechanism outperforms other compared mechanisms. The remainder of this paper is organized as follows. In section II we review related work about car sharing system and Affinity Propagation. In Section III, firstly we formally define the problem and give an overview of our proposed method. Then, we discuss about the detailed model to locate the car 4th International Conference on Machinery, Materials and Information Technology Applications (ICMMITA 2016) Copyright © 2017, the Authors. Published by Atlantis Press. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/). Advances in Computer Science Research, volume 71


Introduction
In order to reduce traffic pressure and effectively utilize idle vehicles, car sharing system, which allows people to rental vehicle for short distance journey, gradually shows its importance. As an alternative public transportation, car sharing system has been proved to have a positive effect on urban mobility [1], the mobile and flexible characteristic of car sharing system in the city's transportation system, particularly in the short distance journey has manifested the superiority which other transportation means do not have. With the development of the electric vehicles, car sharing system will have further significant benefits even have the potential to replace traditional private vehicles. Electric vehicles have been observed as the best candidate for shared vehicle systems because of the zero emission [2]. One of the major challenges encountered by the car sharing system providers is selecting the appropriate locations for car sharing sites. Regarding to the service which a car sharing site provide, it is crucial that the site which can serve more people who can reach in short time. In scientific literature on transportation networks, this problem is known as the depot location. The selection of car sharing site location should take quality of service, efficiency of service and the cost of service into consideration. Therefore, a future study of appropriate location for car sharing would be necessary. To select the location of car sharing system sites, we should build a travel requirement module in the service area precisely. The requirement for car sharing usually refers to how much of vehicles is desired, hence we use the taxi trajectory data to present this requirement. In this paper, we propose to locate the car sharing sites based on filtering and clustering. To evaluate this module, we use the real data source of taxi GPS trajectories which generated by over 12,000 taxis in Beijing. The contribution of this paper includes: (1) We proposed a method to aggregate demand points to facilitate clustering based on Grid-distance. (2) We consider the size of each aggregation point as a parameter for the clustering algorithm. And we proposed that Affinity Propagation clustering algorithm is more proper in selecting location of car sharing sites. (3) Extensive experimental results on real data source of taxi GPS tracks collected from over 12,000 taxi in Beijing demonstrate that our location selection mechanism outperforms other compared mechanisms. The remainder of this paper is organized as follows. In section II we review related work about car sharing system and Affinity Propagation. In Section III, firstly we formally define the problem and give an overview of our proposed method. Then, we discuss about the detailed model to locate the car sharing sites. In section IV, we give the experimental result of our method and the results of the experiment. Finally, we conclude our work and discuss the future work.

Related works
To locate the car sharing site, Correia [3] proposed an optimization method to depot location in one-way car sharing system where the vehicle stock imbalance issues are addressed under three trip selection schemes. Martinez [4] optimizes the position of shard biking stations and measuring the bicycle relocation activities required in a regular operation day. Jorge [5] presents a simulation model that considers demand variability and one vehicle relocation policy and use MIP model to test the solution. Frey and Dueck proposed a novel clustering method, named Affinity Propagation [6]. Affinity propagation is an exemplar-based clustering algorithm that finds a set of data-points that best exemplify the data, and associates each data-point with one exemplar. AP has been successfully applied to broad areas of computer science research because it has much better clustering performance than traditional clustering methods such as k-means. However，AP does not scale for large data sets because it requires quadratic CPU time in the number of data points to compute the results. Givoni [7] derived an inference algorithm that operates by propagating information up and down the hierarchy, and is efficient despite the high-order potentials required for the graphical model formulation.

Methodology definitions
We now define some notations that will be used throughout the paper. Definition 1 (Vehicle Track): Vehicle Track is composed of sequence of GPS points represented as <latitude, longitude>, which corresponding to an occupied vehicle. For example, 1 where k s is a GPS point of a site consisting of a geospatial coordinate set and a timestamp.
Respectively, 1 s and N s are the origin and destination of the trajectory. Definition 2 (Extraction Point): From vehicle tracks network, we can extract the GPS points which represent the pickup points and the drop points. An extracted GPS point S as a pickup or drop point can be represented as: S= (l.id, l.lat, l.lon). where, l.id is the identifier of a trip, l.lat and l.lon represent coordinates of latitude and longitude of a pickup or drop point.

Grid-distance based filtering for extraction points
After the extraction for the point in the vehicle tracks network, the points can represent the demand of vehicle to travel in selecting the sites of car sharing system. When creating maps with hundreds or thousands of points, it can be difficult to further select the locations of car sites. Hence, the information displayed on the map needs to be evenly distributed and clear. In addition, we should make a decision based on user's desire for car sharing sites when they search nearby places. To solve above mentioned issues, in our method, we use grid-distance based filtering to aggregate the large numbers of extraction points in the map. The basic idea of grid-distance based filtering is to divide the map into a lot of regular grids and obtain the aggregation results for all extraction points fall in the grid. One aggregation result Ag_r i contains the final aggregation point Ag i and the extraction points set { S_set i } in the corresponding grid scope G i , which can be represented as Ag_r i = (Ag i , S_set i , G i ). At first, there is no any known aggregation point in the map. As for each extraction point in the map, we identity the specific grid it belongs to by iterative computation. Then the aggregation point for each grid can be obtained by dividing and merging on extraction points. The detailed filtering process is illustrated in Algorithm 1.

Affinity Propagation clustering for selecting the sites
After filter the extraction points, we get Ag_r as the result. Ag_r= {Ag_r 1 , Ag_r 2 ,…, Ag_r M }, in which Ag_r i contains Ag i ， S_seti and G i . In car sharing system, Ag i represents the location which customers want to take a car and size of S_set i represents the demand degree of customers. In reality, limited by capital investment and geographical location, we cannot establish a site at each demand point. In order to reduce the number of sites, and to serve more customers, we need to use clustering algorithm.
To locate the sites of car sharing system using the result above and perform clustering accurately, we use AP (Affinity Propagation) algorithm proposed by Frey and Dueck at 2007 and it performs better than traditional clustering methods such as k-means. AP algorithm does not need to define the number of clusters K in advance and in the process of iteration, it searches for suitable clustering centers automatically, and identifies the position and number of cluster centers from the data points so that all data points are similar to the nearest clustering centers. The algorithm has been applied to many fields, such as facilities location [7], image recognition [8], image segmentation [9], image retrieval and text mining [10], and achieved good result. The collection of similarities, s(i, j), is the input for AP algorithm, whose similarities reflects how well the aggregation point Ag j is suited to be the exemplar for Ag i . The purpose of Affinity Propagation is to maximize the sum of similarities between the aggregation point Ag i and its cluster center Ag j . Each aggregation point Ag i has a self-similarity, s(i, i), which called preference P . And it will influence the number of cluster centers. The points which are initialized with a bigger P are more suitable to be the cluster centers. Usually, we choose the median of the pairwise similarities to be the initialized value for each point. In this way, each point has the same possibility to become the cluster center. However, in this paper, each aggregation result Ag_r i contains not only Ag i but also a set of extraction points S_set i . The size of S_set i will influence the possibility that Ag i becomes the cluster center. Therefore we initialized s(i, i) with the negative number of linear normalization of each size of S_set i . We defined function size(S_set i ) to represent the size number of S_set i . The formulas for performance P are stated below: Meanwhile, we initialized s(i, j) with the negative number of the square of Euclidean distance between each Ag using below formula: In Affinity Propagation, there are two crucial parameters of information message. The responsibility, r(i, j), represents how well suited Ag j is to become a cluster center for Ag i . The Availability, a(i, j), represents how appropriate it will be for Ag i to select Ag j as its cluster center.

Algorithm 2 Affinity Propagation Clustering
Step4: Another crucial parameter λ, called damping factor, in Affinity Propagation influences the iteration process. a(i, j) and r(i, j) are updated by weighting the current iteration value and previous iteration value for each loop using the formula below:

Experiments
To show the feasibility, effectiveness and benefits of the method we proposed in this paper, we completed our experiments with the data set of real taxi GPS trajectories. The data set is obtained from Beijing taxi GPS trajectories from July 17 to July 23 July, 2014. In order to quantitative analyze the performance of our method, we introduced two concepts coverage rate(CR) and average distance(AD). CR represents the proportion of users within the server radius of the selected sites. In reality, site density enables consumers to reach a site within 30 minutes through walking. So it is reasonable to set service radius to 3 km. . And N is the total number of all extraction point. AD represents the average distance between each point and its car sharing site it belongs, that is the cluster center.   1 shows the output of the comparison among the model above with the data set in seven days. We got a larger coverage rate than the others, which means that in the same condition the car sharing sites selected by our method will get more customers. Fig. 2 shows the comparison of average distance based on the method above. Obviously, we got a smaller average distance than the other model. The shorter the average distance is, the better its performance is. Customers will spend a shorter time to reach a car sharing site. Through the above experiments, the method based on filtering and clustering in car sharing sites selection has a good performance.

Conclusion
In this paper, we proposed a new location approach based on Filtering and Clustering for car sharing system. We take the real travel demand into consideration. The comprehensive experimental analysis shows the efficiency and feasibility of our method. As a future work, we will analyze the relationship of traffic volume between car sharing sites.