# Station Location Optimization for the One-Way Carsharing System: Modeling and a Case Study

Authors: Yongjun Chen; Lulin Wang; Jingjing Tian
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Carsharing is regarded as a new mode of transportation that can meet the diversity of travel demands. Carsharing systems have different operating modes, and one-way systems are more widely used since cars can be dropped off at any station. However, their planning involves a series of joint decisions regarding the number, size, and location of stations, as well as the fleet size. This paper develops a data-driven mixed-integer linear programming (MILP) model for planning one-way carsharing systems that consider the spatial distribution of demand and the interacting decisions between stations. The characteristics of existing stations and their spatiotemporal correlations are an important part of the model. To solve the MILP model, the extension of the Benders decomposition algorithm is adopted. The practicality of the proposed approach is demonstrated in a case study in Beijing, China. The results show that the existing planning of carsharing could result in a serious waste of resources. In contrast, the proposed method can obtain effective results in a reasonable time. The location results corresponding to a different rate of satisfied demand show that increasing the parking spots to improve the interaction between stations can effectively reduce the cost of operations. It should be noted that this paper only considers the benefit of operators. Future works will be carried out to optimize the one-way carsharing system by considering the benefits of operators, as well as the benefits of users and society. In addition, the impact of COVID-19 will be taken into account in future modeling and case studies.


---

## Body

## 1. Introduction

Carsharing is a type of car rental service, which can be traced back to the late 1940s. As an alternative public transportation, carsharing attracts customers who rent cars for a short period of time and has been observed to have a positive impact on increasing mobility and reducing congestion.Carsharing systems can be divided into three operation modes: round-way, one-way, and floating [1–3]. A round-way system requires the vehicle to be returned to the original rental station. A one-way system allows users to return the vehicle to any designated stations. Unlike the first two, the floating system allows the vehicle to park in any place where parking is allowed. Due to the nature of carsharing, many businesses are difficult to implement, such as vehicle relocation and personnel assignment. Therefore, the commonly used modes are the first two, which are station-based. The one-way carsharing system is a station-based system that gives users more choice. Due to its flexibility, this is the most popular carsharing system currently in most cities all over the world. Therefore, how to optimize the one-way carsharing system has become an important issue that has attracted much attention. Therefore, this paper focuses on the station location problem of a one-way carsharing system, determining the number, capacities, and locations of stations and the fleet size.The literature about carsharing reveals that existing location methods are not considered real conditions comprehensively. The mathematical programming approaches are mainly for the initial station location and do not consider the interaction between stations of the carsharing system, while the data-driven methods are more focused on the later operations of the system, such as vehicle relocation. However, due to the constraints of the investment cost and the difficulty of moving the station, the initial location based on potential demand is more reasonable considering long-term planning. A reasonable and effective initial station location should be able to meet operating conditions as much as possible to minimize the additional cost caused by later adjustments.To this end, this paper proposes a data-driven optimization location method by taking advantage of both mathematical programming and data-driven methods. The spatiotemporal characteristics and potential demand are mined from the data set. And an MILP model is established with the consideration of the coverage of the demand and the interaction of the car rental between stations. The major motivations and contributions of this paper are summarized as follows: (1) this paper analyzes the distribution and demand characteristics of an existing carsharing system; (2) this paper develops a data-driven optimization model, considering both the spatial coverage characteristics of the demand and the interaction of the car rental between stations; and (3) this paper attempts to solve the proposed model based on the extension of the Benders decomposition algorithm.The rest of the paper is organized as follows. In Section2, the problem is described, and the modeling framework of the data-driven model is developed. In Section 3, the distribution of stations and the characteristics of demand are analyzed based on real data. In Section 4, an MILP model is developed based on the results of data analysis. In Section 5, the Benders decomposition is extended to solve the proposed model. In Section 6, case studies are carried out, and the results are discussed. Finally, conclusions are made in Section 7.


## 2. Literature Review

The location problem has been extensively studied in many aspects, such as the location of the transportation hub station, the logistics center station, the location of the charging station, and so on. The methods and models for station location are also diverse. At present, the methods can mainly be divided into two categories. One is based on the optimization method of operational research, considering the service radius, spatial constraints, path constraints, and other constraints of the candidate stations. The criteria with the highest coverage, the lowest total cost, and the maximum benefit are defined as the objective function. And the optimal solution is obtained by theoretical methods such as operations research and graph theory. Another method mainly benefits from the development of information technology and computer. Such methods are usually based on actual data (or simulation data) and suitable algorithms and do not involve specific models.At present, the optimization methods have been extensively employed to model the carsharing station location problem, from simple single-objective planning to multi-objective planning and dynamic programming, and a series of hybrid models and algorithms are derived. Jie et al. [4] applied the queuing model to explain congestion charges with the objective of infrastructure investment minimization. Sylvia et al. [5] compared three classic facility location models: the set covering model, the maximal covering location model, and the p-median model. The results show that the p-median model is more effective. Johannes et al. [6] considered the existing charging stations and proposed variants of the maximum coverage location problem, aiming to meet as many charging requirements as possible with a limited number of charging stations. Wei et al. [7] developed a location to maximize the level of electric taxi service on the road network and the level of charging service at the stations under spatial and temporal constraints, such as the ET range, the charging time, and the capacity of charging stations. Lin et al. [8] proposed a non-linear integer programming model based on link formulation, compared it with the p-maximum coverage location model, and developed a link-based implicit enumeration algorithm to solve the problem. He et al. [9] proposed a bi-level programming model for finding the best location for charging station, and the upper layer optimizes the location of the charging station to maximize the path flow using the charging station, while the user balance of the path selection and the mileage of the electric vehicle (EV) are constrained to the lower layer.The second type of method is still in development. Such methods are usually based on relevant statistical data or simulation data such as vehicle trajectory, passenger travel characteristics, and vehicle operating characteristics, to identify the spatiotemporal distribution of demand as the main target and conduct location selection research combined with the corresponding algorithm. Dong and Liu [10] evaluated the feasibility of a battery-powered vehicle for the heterogeneous traveling population in the real world and proposed a new charging station planning model, using genetic algorithms to find the optimal location, and the impact of public charging infrastructure deployment on increased mileage is analyzed. Ge et al. [11] proposed a grid-based method for locating and sizing of charging station, aiming to minimize the users’ loss on the way to the charging station. The optimal position of each partition in GA (genetic algorithm) is selected, taking into account traffic density and charging stations. Through repeated calculations, the coverage of each zone and the location of the charging station are adjusted, and reasonable planning for the electric vehicle charging station in the entire region is finally obtained. Xu et al. [12] attempted to use the real-relevant preference data to study the joint design of electric vehicle charging mode (normal or fast) and location (home/company or public) and proposed a hybrid logit model. The research results provide a new idea for the peak load transfer and operation strategy of the public charging station.Compared with the general location problem, the location of the carsharing system has similarities and differences. For carsharing location problems, additional assumptions are required due to the special nature of carsharing. In general, traditional location methods can be applied to the carsharing system. In this study, we focus on the most prevalent one-way carsharing system, for which imbalance is an obvious feature that is quite different from other systems.The research on station selection of carsharing systems is still in development, and the methods can also be divided into two categories. More studies are conducted based on the approaches of mathematical programming. The focus of such methods is on the improvement and optimization of the model. Boyacı et al. [13] developed a multiobjective mixed-integer linear programming model for location-allocation of one-way carsharing systems, considering different scenarios, vehicle rebalance, charging constraints, and social subsidies. For the convenience of solving, an aggregation model is introduced based on the concept of the virtual hub. This method can achieve a balance between the interests of operators and users. Correia et al. [14] proposed a method for planning a one-way carsharing system based on mixed-integer programming with the goal of maximizing the profit of the carsharing operator. The imbalance of vehicle inventory is solved under three-vehicle allocation schemes, namely, controlled service, full service, and conditional service. Correia et al. [15] extended the previous model, which considers trip selection and station location, and took into account more alternative pickup points and return points. A comparative analysis of different combinations of user flexibility and vehicle inventory information shows that user flexibility combined with vehicle inventory information increases the company’s profits, as people will go directly to stations with available vehicles, making fleet use more efficient. Huang et al. [16] proposed a mixed-integer non-linear programming (MINLP) model to plan stations’ location and their capacity for a one-way system. They were considering vehicle relocation and dynamic demand and introducing the concept of regional attraction to construct a logit model. Wang and Hua [17] proposed an MILP model to solve the location problem with the objective of minimizing the cost of carsharing systems, taking into account vehicle relocation, investment costs, and travel costs of users. Jiao et al. [18] proposed a mixed integer programming (MIP) model to meet the demand caused by limited electric vehicle power, taking into account charging mode and anxiety range. In addition, they solved the location problem by assigning two types of charging piles to meet different types of demand.Alternatively, the data-driven location methods have also been applied to the station location problem of carsharing. These methods mainly determine the location of the sites based on multisource data combined with some algorithms. Such methods generally do not involve mathematical models. Zhu et al. [19] proposed a deep learning method to predict the demand for carsharing, considering the spatiotemporal correlation. The result proves that the distribution of demand meets the power law and uses it as the filtering rule of the station. Willing et al. [20] proposed a spatial decision support system, combining the point of interest (POI) data with the rental data to analyze the user’s behavior. And the system can establish variable itinerary pricing for existing areas and provide decision support for operators in the new city. Liu et al. [21] proposed an optimization method based on the AP (affinity propagation) clustering algorithm to determine the location of the carsharing system. Considering the characteristics of AP clustering, the OD (origin-destination) of the taxi is divided based on the administrative area, and the results are optimized. The results show that the proposed method performs better than the standard K-means algorithm.


## 3. Materials and Methods

### 3.1. Data-Driven Methodology

This paper focuses on how to plan the initial allocation of a one-way carsharing system, including the number, capacities, and locations of stations, as well as fleet size. Carsharing is a complex system involving operators, users, cars, and other related factors. Similar to most existing studies, this paper considers the problem that the operator has the lowest cost when there is only one operator. Furthermore, we assume that all vehicles are electric vehicles since it is very difficult to get license plates of fuel vehicles due to the environmental problem. For the user, only the coverage of demand within grids is considered, and whether each specific requirement is satisfied is not within the scope of this study.This paper discusses the station selection problem of the one-way carsharing system. After a field survey, it is found that the location of the current station is mostly determined based on experience, lacking certain scientific evidence and rationality. As the demand for carsharing increases, the current station is difficult to meet the requirement.To overcome the drawbacks of the existing station location methods, a data-driven approach is developed in this study, as shown in Figure1.Figure 1
Methodology framework.First, based on a real data set, this paper analyzes the characteristics of meted and potential demands, as well as the usage of vehicles, and mines the correlation relationship.Then, based on the data analysis, a data-driven station location model is proposed with the objective of minimizing the total cost of the operator, considering the cost of trip consumption, distance attenuation, and the relationship between fleet size and demand.Finally, the paper attempts to solve the proposed model based on the extension of the Benders extension algorithm and compares the location results with the existing layout.


### 3.2. Data Description and Analysis

The data used in the paper is from a carsharing company in Beijing, including rental data, GPS trajectories, and stations’ information. This paper selects the data of the carsharing company in Beijing for the case studies, which is mainly in terms of two concerns. First, Beijing is one of the cities where carsharing early appeared in China, and there has developed a relatively mature and stable market. Therefore, it can provide stable and reliable data. Second, Beijing’s shared car companies have sufficient amounts of stations and cars, which are widely distributed in the city. Therefore, the carsharing system in Beijing is representative.The data used in this paper were collected from January 1, 2017, to October 16, 2017, for a total of 289 days. The rental data is the trip information generated by the users on the corresponding platform, including the transaction code, pickup time, pickup station, drop-off time, drop-off station, trip distance, rental fee, and so on. There are more than 80,000 effective records with 960 vehicles available.The vehicle trajectories are a series of GPS trajectory points during driving. If a car is driven normally, a GPS signal is captured roughly every 10 s. Otherwise, it is captured every roughly every 1 h. The trajectory data included time-stamped, vehicle number, longitude, latitude, and speed. Vehicle data has approximately 120 million records. In addition, the station data contains the latitude and longitude information of 211 stations.This part mainly analyzes the distribution characteristics of existing demand and explores the effective correlations. The degree of matching between existing stations and potential demand is analyzed, and the irrationality of existing planning distribution.


#### 3.2.1. Analysis of Existing Demand

Combined with the functional area division of Beijing, the existing station is visualized on the map, as shown in Figure2. There are a total of 211 stations, including 78 stations within the 4th Ring Road, 63 stations between the 4th Ring Road and the 5th Ring road, and 62 stations between the 5th Ring Road and 6th Ring Road. And more than 95% of the stations are located within the 6th Ring Road.Figure 2
Spatial distribution of the existing stations.Figure3 shows the cumulative distribution of the actual distance between any two stations. About 75% of the stations have a distance between 10 km and 40 km, which is suitable for the short-distance trip of most users.Figure 3
Cumulative distribution curve of the distance between stations.According to the rental data, after renting a vehicle at a station, the user can return the car at any other station. The number of rental records was counted between any two stations. It shows that 95% of the rental records between two stations are less than 20, and many stations are not fully utilized. Figure4 shows the distribution of rental records. The blue dot indicates the stations, and the red line between the stations indicates that there is a rental record between the two stations. As can be seen from the figure, there are many rental records between some stations and others are several, and some stations only have a rental record with one station. Among the 211 stations, only 56 stations have a rental record with other stations.Figure 4
Rental records between any two stations.Figure5 reflects the diversity of attractive demand of the station.Figure 5
The proportion of stations leaving and arriving at a station.
(a)(b)Based on the rental data, the actual travel time between any two stations is counted. Among the stations where there is demand, about 90% of the rental data are within 24 hours, and 97% of the actual mileage of the order is less than 200 km.A notable feature of a one-way carsharing system is that it can cause station imbalances. In addition to the imbalance between the stations shown in Figure4, there is also an imbalance in the amount of car rentals and returns on a single station.Figure6 shows the distribution of the borrowed and returned vehicles after the min-max normalization process, and the red and green lines, respectively, indicate the number of borrowed and returned vehicles at each station. Since the difference between the borrowed and returned is much smaller in value than the two, it is difficult to distinguish on the graph, so the difference between the two is also normalized. A value greater than 0.6 indicates that the number of orders for renting cars from the station is greater than the number of returning cars at the station. When the value is less than 0.6, the result is reversed. The absolute value of the difference is used to indicate the unbalance of the stations. It is found that the station with the most demand has a large imbalance, which indicates that the greater the demand, the greater the imbalance caused by the demand difference.Figure 6
Distribution of imbalance.Figure7 shows the spatial distribution of the unbalanced stations. The red triangle indicates that the number of borrowed vehicles is greater than the returned (22 in total), and the distribution is mainly within the 5th Ring Road. The blue triangle is opposite (29 in total) and near the north of the 4th Ring Road and the east of the 5th Ring Road.Figure 7
Spatial distribution of unbalance stations.Due to the lack of initial vehicle inventory information, this paper counts the number of vehicles per day at each station based on the rental data, using the maximum number of vehicles per day as the initial vehicle inventory for the station.Figure8 shows the distribution of demand and initial vehicles per station. Similarly, in order to eliminate the difference between the two types of data, min-max normalization is used to preprocess, and it can be seen that some stations had more demand but fewer vehicles. For stations with less demand, the number of vehicles is more, indicating that there is a certain irrationality in the current stations and vehicle distribution.Figure 8
Rental record and initial vehicle distribution.From the perspective of the vehicle, the rental data contains 960 vehicles available, counting the frequency of use of each vehicle and sorting them from large to small. The daily average usage trend is shown in Figure9. Combined with the statistics, it is found that the usage rate of only 5 vehicles can reach 1 time/day, only about 11% of the vehicles can reach 0.5 times/day, and the usage rate of 64% can reach 0.2 times/day, and most vehicles are not fully utilized. Since the vehicle types are consistent, the difference in vehicle utilization is caused not by the vehicle itself but by other factors such as demand, station, and so on.Figure 9
Cumulative curve of usage rate.The number of available vehiclesV and the demand U are calculated each day. It is found that the two have an obvious linear relationship, and the linear fitting function is (1)V=0.657⋅U+11.8.The goodness of fitR1=0.98 (R1⟶1, the better the fitness). This fitting function can be used as a constraint of the carsharing system. The constraint can be extended to be expressed as follows:(2)V≥0.657⋅U+11.891.According to the statistics and the above analysis, it can be found that the demand satisfied by the existing stations only accounts for about 40% of the potential demand, and 99% of vehicles have an average daily usage rate of less than 1 time/day. Therefore, the carsharing system requires further planning adjustments.


#### 3.2.2. Potential Demand Analysis

The rental data reflects the carsharing demand that has been met so far, but there are actually many unfulfilled demands and potential demands. To optimize the station locations, this paper extracts the potential carsharing demand based on vehicle trajectory data and analyzes the demand coverage characteristics of existing stations based on this.When the vehicle is in the state of stay, the GPS trajectory data also records the data, but the instantaneous speed is 0 or close to 0. When the continuous stay time exceeds a certain value (Tthresh), it is defined as an activity point. The setting criterion of the stationary point is that the speed is clearly slower than the walking speed (Vw). The speed threshold of the stationary point is set to 0.51 m/s, and Vw = 1.34 m/s refers to the parameters in Du [22]. To avoid contingency, this paper assumes that when the average speed of two consecutive data points is less than 0.51 m/s, the previous data point is a stationary point.Based on the determination of the stationary point, each trajectory is divided into several motion segments and stationary segments. Calculate the duration of the stationary segment (T) and the distance of the motion segment (D). When T≤Tthresh120s [23], the stationary segment can be regarded as a short stay during driving. The state of the stationary segment is converted into a motion segment. When D≤dthresh200m, the motion segment is converted into a stationary segment, and finally, the segments adjacent to the same state are merged. Extract all motion segment information to get all the potential demand OD, including the origin time, destination time, latitude, longitude, and distance. And based on the previous data analysis, OD information is filtered.For convenience, this paper sets the research area within the 4th Ring Road (applying to the case study in Section6) and is divided into 400 square cells with the size of 1 km × 1 km. The daily dwell events of each grid are counted, and the results indicate that 66% of the valid cells have less than 0.4 daily dwell events. Therefore, a popular cell with at least 0.4 daily dwell events can be considered as a candidate station, and 136 candidate stations are selected.


## 3.1. Data-Driven Methodology

This paper focuses on how to plan the initial allocation of a one-way carsharing system, including the number, capacities, and locations of stations, as well as fleet size. Carsharing is a complex system involving operators, users, cars, and other related factors. Similar to most existing studies, this paper considers the problem that the operator has the lowest cost when there is only one operator. Furthermore, we assume that all vehicles are electric vehicles since it is very difficult to get license plates of fuel vehicles due to the environmental problem. For the user, only the coverage of demand within grids is considered, and whether each specific requirement is satisfied is not within the scope of this study.This paper discusses the station selection problem of the one-way carsharing system. After a field survey, it is found that the location of the current station is mostly determined based on experience, lacking certain scientific evidence and rationality. As the demand for carsharing increases, the current station is difficult to meet the requirement.To overcome the drawbacks of the existing station location methods, a data-driven approach is developed in this study, as shown in Figure1.Figure 1
Methodology framework.First, based on a real data set, this paper analyzes the characteristics of meted and potential demands, as well as the usage of vehicles, and mines the correlation relationship.Then, based on the data analysis, a data-driven station location model is proposed with the objective of minimizing the total cost of the operator, considering the cost of trip consumption, distance attenuation, and the relationship between fleet size and demand.Finally, the paper attempts to solve the proposed model based on the extension of the Benders extension algorithm and compares the location results with the existing layout.


## 3.2. Data Description and Analysis

The data used in the paper is from a carsharing company in Beijing, including rental data, GPS trajectories, and stations’ information. This paper selects the data of the carsharing company in Beijing for the case studies, which is mainly in terms of two concerns. First, Beijing is one of the cities where carsharing early appeared in China, and there has developed a relatively mature and stable market. Therefore, it can provide stable and reliable data. Second, Beijing’s shared car companies have sufficient amounts of stations and cars, which are widely distributed in the city. Therefore, the carsharing system in Beijing is representative.The data used in this paper were collected from January 1, 2017, to October 16, 2017, for a total of 289 days. The rental data is the trip information generated by the users on the corresponding platform, including the transaction code, pickup time, pickup station, drop-off time, drop-off station, trip distance, rental fee, and so on. There are more than 80,000 effective records with 960 vehicles available.The vehicle trajectories are a series of GPS trajectory points during driving. If a car is driven normally, a GPS signal is captured roughly every 10 s. Otherwise, it is captured every roughly every 1 h. The trajectory data included time-stamped, vehicle number, longitude, latitude, and speed. Vehicle data has approximately 120 million records. In addition, the station data contains the latitude and longitude information of 211 stations.This part mainly analyzes the distribution characteristics of existing demand and explores the effective correlations. The degree of matching between existing stations and potential demand is analyzed, and the irrationality of existing planning distribution.


### 3.2.1. Analysis of Existing Demand

Combined with the functional area division of Beijing, the existing station is visualized on the map, as shown in Figure2. There are a total of 211 stations, including 78 stations within the 4th Ring Road, 63 stations between the 4th Ring Road and the 5th Ring road, and 62 stations between the 5th Ring Road and 6th Ring Road. And more than 95% of the stations are located within the 6th Ring Road.Figure 2
Spatial distribution of the existing stations.Figure3 shows the cumulative distribution of the actual distance between any two stations. About 75% of the stations have a distance between 10 km and 40 km, which is suitable for the short-distance trip of most users.Figure 3
Cumulative distribution curve of the distance between stations.According to the rental data, after renting a vehicle at a station, the user can return the car at any other station. The number of rental records was counted between any two stations. It shows that 95% of the rental records between two stations are less than 20, and many stations are not fully utilized. Figure4 shows the distribution of rental records. The blue dot indicates the stations, and the red line between the stations indicates that there is a rental record between the two stations. As can be seen from the figure, there are many rental records between some stations and others are several, and some stations only have a rental record with one station. Among the 211 stations, only 56 stations have a rental record with other stations.Figure 4
Rental records between any two stations.Figure5 reflects the diversity of attractive demand of the station.Figure 5
The proportion of stations leaving and arriving at a station.
(a)(b)Based on the rental data, the actual travel time between any two stations is counted. Among the stations where there is demand, about 90% of the rental data are within 24 hours, and 97% of the actual mileage of the order is less than 200 km.A notable feature of a one-way carsharing system is that it can cause station imbalances. In addition to the imbalance between the stations shown in Figure4, there is also an imbalance in the amount of car rentals and returns on a single station.Figure6 shows the distribution of the borrowed and returned vehicles after the min-max normalization process, and the red and green lines, respectively, indicate the number of borrowed and returned vehicles at each station. Since the difference between the borrowed and returned is much smaller in value than the two, it is difficult to distinguish on the graph, so the difference between the two is also normalized. A value greater than 0.6 indicates that the number of orders for renting cars from the station is greater than the number of returning cars at the station. When the value is less than 0.6, the result is reversed. The absolute value of the difference is used to indicate the unbalance of the stations. It is found that the station with the most demand has a large imbalance, which indicates that the greater the demand, the greater the imbalance caused by the demand difference.Figure 6
Distribution of imbalance.Figure7 shows the spatial distribution of the unbalanced stations. The red triangle indicates that the number of borrowed vehicles is greater than the returned (22 in total), and the distribution is mainly within the 5th Ring Road. The blue triangle is opposite (29 in total) and near the north of the 4th Ring Road and the east of the 5th Ring Road.Figure 7
Spatial distribution of unbalance stations.Due to the lack of initial vehicle inventory information, this paper counts the number of vehicles per day at each station based on the rental data, using the maximum number of vehicles per day as the initial vehicle inventory for the station.Figure8 shows the distribution of demand and initial vehicles per station. Similarly, in order to eliminate the difference between the two types of data, min-max normalization is used to preprocess, and it can be seen that some stations had more demand but fewer vehicles. For stations with less demand, the number of vehicles is more, indicating that there is a certain irrationality in the current stations and vehicle distribution.Figure 8
Rental record and initial vehicle distribution.From the perspective of the vehicle, the rental data contains 960 vehicles available, counting the frequency of use of each vehicle and sorting them from large to small. The daily average usage trend is shown in Figure9. Combined with the statistics, it is found that the usage rate of only 5 vehicles can reach 1 time/day, only about 11% of the vehicles can reach 0.5 times/day, and the usage rate of 64% can reach 0.2 times/day, and most vehicles are not fully utilized. Since the vehicle types are consistent, the difference in vehicle utilization is caused not by the vehicle itself but by other factors such as demand, station, and so on.Figure 9
Cumulative curve of usage rate.The number of available vehiclesV and the demand U are calculated each day. It is found that the two have an obvious linear relationship, and the linear fitting function is (1)V=0.657⋅U+11.8.The goodness of fitR1=0.98 (R1⟶1, the better the fitness). This fitting function can be used as a constraint of the carsharing system. The constraint can be extended to be expressed as follows:(2)V≥0.657⋅U+11.891.According to the statistics and the above analysis, it can be found that the demand satisfied by the existing stations only accounts for about 40% of the potential demand, and 99% of vehicles have an average daily usage rate of less than 1 time/day. Therefore, the carsharing system requires further planning adjustments.


### 3.2.2. Potential Demand Analysis

The rental data reflects the carsharing demand that has been met so far, but there are actually many unfulfilled demands and potential demands. To optimize the station locations, this paper extracts the potential carsharing demand based on vehicle trajectory data and analyzes the demand coverage characteristics of existing stations based on this.When the vehicle is in the state of stay, the GPS trajectory data also records the data, but the instantaneous speed is 0 or close to 0. When the continuous stay time exceeds a certain value (Tthresh), it is defined as an activity point. The setting criterion of the stationary point is that the speed is clearly slower than the walking speed (Vw). The speed threshold of the stationary point is set to 0.51 m/s, and Vw = 1.34 m/s refers to the parameters in Du [22]. To avoid contingency, this paper assumes that when the average speed of two consecutive data points is less than 0.51 m/s, the previous data point is a stationary point.Based on the determination of the stationary point, each trajectory is divided into several motion segments and stationary segments. Calculate the duration of the stationary segment (T) and the distance of the motion segment (D). When T≤Tthresh120s [23], the stationary segment can be regarded as a short stay during driving. The state of the stationary segment is converted into a motion segment. When D≤dthresh200m, the motion segment is converted into a stationary segment, and finally, the segments adjacent to the same state are merged. Extract all motion segment information to get all the potential demand OD, including the origin time, destination time, latitude, longitude, and distance. And based on the previous data analysis, OD information is filtered.For convenience, this paper sets the research area within the 4th Ring Road (applying to the case study in Section6) and is divided into 400 square cells with the size of 1 km × 1 km. The daily dwell events of each grid are counted, and the results indicate that 66% of the valid cells have less than 0.4 daily dwell events. Therefore, a popular cell with at least 0.4 daily dwell events can be considered as a candidate station, and 136 candidate stations are selected.


## 3.2.1. Analysis of Existing Demand

Combined with the functional area division of Beijing, the existing station is visualized on the map, as shown in Figure2. There are a total of 211 stations, including 78 stations within the 4th Ring Road, 63 stations between the 4th Ring Road and the 5th Ring road, and 62 stations between the 5th Ring Road and 6th Ring Road. And more than 95% of the stations are located within the 6th Ring Road.Figure 2
Spatial distribution of the existing stations.Figure3 shows the cumulative distribution of the actual distance between any two stations. About 75% of the stations have a distance between 10 km and 40 km, which is suitable for the short-distance trip of most users.Figure 3
Cumulative distribution curve of the distance between stations.According to the rental data, after renting a vehicle at a station, the user can return the car at any other station. The number of rental records was counted between any two stations. It shows that 95% of the rental records between two stations are less than 20, and many stations are not fully utilized. Figure4 shows the distribution of rental records. The blue dot indicates the stations, and the red line between the stations indicates that there is a rental record between the two stations. As can be seen from the figure, there are many rental records between some stations and others are several, and some stations only have a rental record with one station. Among the 211 stations, only 56 stations have a rental record with other stations.Figure 4
Rental records between any two stations.Figure5 reflects the diversity of attractive demand of the station.Figure 5
The proportion of stations leaving and arriving at a station.
(a)(b)Based on the rental data, the actual travel time between any two stations is counted. Among the stations where there is demand, about 90% of the rental data are within 24 hours, and 97% of the actual mileage of the order is less than 200 km.A notable feature of a one-way carsharing system is that it can cause station imbalances. In addition to the imbalance between the stations shown in Figure4, there is also an imbalance in the amount of car rentals and returns on a single station.Figure6 shows the distribution of the borrowed and returned vehicles after the min-max normalization process, and the red and green lines, respectively, indicate the number of borrowed and returned vehicles at each station. Since the difference between the borrowed and returned is much smaller in value than the two, it is difficult to distinguish on the graph, so the difference between the two is also normalized. A value greater than 0.6 indicates that the number of orders for renting cars from the station is greater than the number of returning cars at the station. When the value is less than 0.6, the result is reversed. The absolute value of the difference is used to indicate the unbalance of the stations. It is found that the station with the most demand has a large imbalance, which indicates that the greater the demand, the greater the imbalance caused by the demand difference.Figure 6
Distribution of imbalance.Figure7 shows the spatial distribution of the unbalanced stations. The red triangle indicates that the number of borrowed vehicles is greater than the returned (22 in total), and the distribution is mainly within the 5th Ring Road. The blue triangle is opposite (29 in total) and near the north of the 4th Ring Road and the east of the 5th Ring Road.Figure 7
Spatial distribution of unbalance stations.Due to the lack of initial vehicle inventory information, this paper counts the number of vehicles per day at each station based on the rental data, using the maximum number of vehicles per day as the initial vehicle inventory for the station.Figure8 shows the distribution of demand and initial vehicles per station. Similarly, in order to eliminate the difference between the two types of data, min-max normalization is used to preprocess, and it can be seen that some stations had more demand but fewer vehicles. For stations with less demand, the number of vehicles is more, indicating that there is a certain irrationality in the current stations and vehicle distribution.Figure 8
Rental record and initial vehicle distribution.From the perspective of the vehicle, the rental data contains 960 vehicles available, counting the frequency of use of each vehicle and sorting them from large to small. The daily average usage trend is shown in Figure9. Combined with the statistics, it is found that the usage rate of only 5 vehicles can reach 1 time/day, only about 11% of the vehicles can reach 0.5 times/day, and the usage rate of 64% can reach 0.2 times/day, and most vehicles are not fully utilized. Since the vehicle types are consistent, the difference in vehicle utilization is caused not by the vehicle itself but by other factors such as demand, station, and so on.Figure 9
Cumulative curve of usage rate.The number of available vehiclesV and the demand U are calculated each day. It is found that the two have an obvious linear relationship, and the linear fitting function is (1)V=0.657⋅U+11.8.The goodness of fitR1=0.98 (R1⟶1, the better the fitness). This fitting function can be used as a constraint of the carsharing system. The constraint can be extended to be expressed as follows:(2)V≥0.657⋅U+11.891.According to the statistics and the above analysis, it can be found that the demand satisfied by the existing stations only accounts for about 40% of the potential demand, and 99% of vehicles have an average daily usage rate of less than 1 time/day. Therefore, the carsharing system requires further planning adjustments.


## 3.2.2. Potential Demand Analysis

The rental data reflects the carsharing demand that has been met so far, but there are actually many unfulfilled demands and potential demands. To optimize the station locations, this paper extracts the potential carsharing demand based on vehicle trajectory data and analyzes the demand coverage characteristics of existing stations based on this.When the vehicle is in the state of stay, the GPS trajectory data also records the data, but the instantaneous speed is 0 or close to 0. When the continuous stay time exceeds a certain value (Tthresh), it is defined as an activity point. The setting criterion of the stationary point is that the speed is clearly slower than the walking speed (Vw). The speed threshold of the stationary point is set to 0.51 m/s, and Vw = 1.34 m/s refers to the parameters in Du [22]. To avoid contingency, this paper assumes that when the average speed of two consecutive data points is less than 0.51 m/s, the previous data point is a stationary point.Based on the determination of the stationary point, each trajectory is divided into several motion segments and stationary segments. Calculate the duration of the stationary segment (T) and the distance of the motion segment (D). When T≤Tthresh120s [23], the stationary segment can be regarded as a short stay during driving. The state of the stationary segment is converted into a motion segment. When D≤dthresh200m, the motion segment is converted into a stationary segment, and finally, the segments adjacent to the same state are merged. Extract all motion segment information to get all the potential demand OD, including the origin time, destination time, latitude, longitude, and distance. And based on the previous data analysis, OD information is filtered.For convenience, this paper sets the research area within the 4th Ring Road (applying to the case study in Section6) and is divided into 400 square cells with the size of 1 km × 1 km. The daily dwell events of each grid are counted, and the results indicate that 66% of the valid cells have less than 0.4 daily dwell events. Therefore, a popular cell with at least 0.4 daily dwell events can be considered as a candidate station, and 136 candidate stations are selected.


## 4. Model Formulation

### 4.1. Assumptions

This paper studies the station location problem of the one-way carsharing system. Considering the difference between the problem and other location problems, the following assumptions should be set:(1)
The impact of other types of transportation on the carsharing system is ignored(2)
Other vehicles are not allowed to occupy the parking spaces in carsharing(3)
Not all demands are satisfied(4)
At least one parking space at a station(5)
All vehicles are electric cars


### 4.2. Notation

The notations used in this paper are listed as follows.


### 4.3. Model Formulation

Based on the idea of a general location model, the purpose of this paper is to select the appropriate location and capacity to minimize the total cost of operators. The model can be formulated as follows:(3)min Z=Cs∑iXi+Cp∑iPi+Cv∑iVi+Ce⋅∑i∑kTikuik.Subject to:(4)Pi≤MXi,∀i∈I,Xi≤Pi,∀i∈I,Vi≤αPi,∀i∈I,Pi≤M1,∀i∈I,zji≤Xi,∀i∈I,j∈J,∑izji≤1,∀j∈J,∑iDjzji≤Dj,∀j∈J,∑jDjzji≤Pi,∀i∈I,∑j∑iDjzjisji≥β∑jDj,uik=∑jDjzjisjinik,∀i∈I,k∈I,Vi≥∑kuik,∀i∈I,fV,U≥0,0≤zji≤1,∀i∈I,j∈J,Pi,Vi∈integer+,uik≥0,∀i,k∈I,j∈J.The objective function (3) of this mixed-integer optimization model minimizes the total daily cost of the operator, taking into consideration the investment cost of the station, the parking space cost, the vehicle cost, and the power consumption cost.The model comprises fourteen sets of constraints. Constraint (4) indicates that parking spaces can be built only in selected stations, whereM is a positive integer large enough. Constraint (5) indicates that the selected station has at least one parking space. Constraint (6) ensures that the vehicles do no’t exceed the parking space at a station, where α is an elasticity coefficient. It guarantees that there will be at least 1−αPi parking spots available for parking. Constraint (7) defines the maximum number of parking spots. Constraint (8) indicates that only one effectively built station can meet the demand. Constraints (9) and (10) ensure its proportion of satisfied demand that cannot exceed 1. Constraint (11) ensures that the satisfied demand does not exceed the parking space. Constraint (12) assures that the satisfied demand is above the minimum limit β. Constraint (13) denotes the number of vehicles from station i to station k. Constraint (14) indicates vehicles leaving from station i that do no’t exceed the initial vehicle per station. Constraint (15) represents a functional relationship between vehicle fleet and demand. Constraints (16) and (17) set the domain for the decision variables.The model in this paper is a mixed-integer programming model and is a typical NP-hard problem. Based on the Benders decomposition algorithm, a solution algorithm for the proposed model is designed to improve the efficiency of the solution.The Benders decomposition algorithm was first proposed by Benders [24] and is considered one of the effective algorithms for efficiently solving mixed-integer programming problems. In the problem considered by Benders, the value of the complex variable is fixed first so that the problem is transformed into a general linear programming problem (i.e., the complex variable is used as a parameter. The complex variable means that when these variables are fixed, the remaining optimization is made. The problem (subproblem) becomes relatively easy).


## 4.1. Assumptions

This paper studies the station location problem of the one-way carsharing system. Considering the difference between the problem and other location problems, the following assumptions should be set:(1)
The impact of other types of transportation on the carsharing system is ignored(2)
Other vehicles are not allowed to occupy the parking spaces in carsharing(3)
Not all demands are satisfied(4)
At least one parking space at a station(5)
All vehicles are electric cars


## 4.2. Notation

The notations used in this paper are listed as follows.


## 4.3. Model Formulation

Based on the idea of a general location model, the purpose of this paper is to select the appropriate location and capacity to minimize the total cost of operators. The model can be formulated as follows:(3)min Z=Cs∑iXi+Cp∑iPi+Cv∑iVi+Ce⋅∑i∑kTikuik.Subject to:(4)Pi≤MXi,∀i∈I,Xi≤Pi,∀i∈I,Vi≤αPi,∀i∈I,Pi≤M1,∀i∈I,zji≤Xi,∀i∈I,j∈J,∑izji≤1,∀j∈J,∑iDjzji≤Dj,∀j∈J,∑jDjzji≤Pi,∀i∈I,∑j∑iDjzjisji≥β∑jDj,uik=∑jDjzjisjinik,∀i∈I,k∈I,Vi≥∑kuik,∀i∈I,fV,U≥0,0≤zji≤1,∀i∈I,j∈J,Pi,Vi∈integer+,uik≥0,∀i,k∈I,j∈J.The objective function (3) of this mixed-integer optimization model minimizes the total daily cost of the operator, taking into consideration the investment cost of the station, the parking space cost, the vehicle cost, and the power consumption cost.The model comprises fourteen sets of constraints. Constraint (4) indicates that parking spaces can be built only in selected stations, whereM is a positive integer large enough. Constraint (5) indicates that the selected station has at least one parking space. Constraint (6) ensures that the vehicles do no’t exceed the parking space at a station, where α is an elasticity coefficient. It guarantees that there will be at least 1−αPi parking spots available for parking. Constraint (7) defines the maximum number of parking spots. Constraint (8) indicates that only one effectively built station can meet the demand. Constraints (9) and (10) ensure its proportion of satisfied demand that cannot exceed 1. Constraint (11) ensures that the satisfied demand does not exceed the parking space. Constraint (12) assures that the satisfied demand is above the minimum limit β. Constraint (13) denotes the number of vehicles from station i to station k. Constraint (14) indicates vehicles leaving from station i that do no’t exceed the initial vehicle per station. Constraint (15) represents a functional relationship between vehicle fleet and demand. Constraints (16) and (17) set the domain for the decision variables.The model in this paper is a mixed-integer programming model and is a typical NP-hard problem. Based on the Benders decomposition algorithm, a solution algorithm for the proposed model is designed to improve the efficiency of the solution.The Benders decomposition algorithm was first proposed by Benders [24] and is considered one of the effective algorithms for efficiently solving mixed-integer programming problems. In the problem considered by Benders, the value of the complex variable is fixed first so that the problem is transformed into a general linear programming problem (i.e., the complex variable is used as a parameter. The complex variable means that when these variables are fixed, the remaining optimization is made. The problem (subproblem) becomes relatively easy).


## 5. Solution Algorithm

A solution algorithm for the proposed model is designed based on the Benders decomposition algorithm. In the model, constraint (14) represents the relationship between the vehicle fleet and demand, combined with formula (1) in Chapter 3, replacing constraint (15) with formula (2). Since X,P,V are integer variables and u is an intermediate variable, we first fix the variables X,P,V,u as known parameters. Thus, the model is transformed into a general linear programming P1 with respect to the continuous variable z. Since the objective function is independent of the variable z, and the variables X,P,V,u are non-negative, the objective function of P1 can be simplified to min0.(5)P1min0.Subject to:(6)zji≤X¯i,∀i∈I,j∈J,∑izji≤1,∀j∈J,∑jDjzji≤P¯i,∀i∈I,∑j∑iDjzjisji≥β∑jDj,nik∑jDjzjisji≤u¯ik∀i∈I,k∈I,0.657∑j∑iDjzjisji+11.89≤∑iV¯i,zji≤1,∀i∈I,j∈J,0≤zji,∀i∈I,j∈J.For the dual problem of P1, the fixed complex variablesX,P,V,u have no effect on the constrained polyhedral sets but only affect the objective function, and the dual problem P2 is expressed as follows:(7)P2max∑i∑jX¯iaji+∑jbj+∑iP¯ici−β∑jDjd+∑i∑ku¯ikeik+∑iV¯i−11.89f+∑i∑jgji.Subject to:(8)aji+bj+Djci−Djsjid+Djsji∑keiknik+0.657Djsjif+gji≤0,aji≤0,bj≤0,ci≤0,d≤0,eik≤0,f≤0,gji≤0.It can be seen that the constraint in problem P2 is independent of the fixed variablesP,V,u, and these variables only affect the objective function. When the constraint set is empty, the problem has no solution, and accordingly, the original problem has no solution. When the convex polyhedral set is non-empty, the constraint set has a pole or pole direction. Question P2 can be further expressed as P3.(9)P3minq.Subject to:(10)∑i∑jXia˙ji+∑jb˙j+∑iPic˙i−β∑jDjd˙+∑i∑kuike˙ik+∑iVi−11.89f˙+∑i∑jg˙ji≤q,∑i∑jXia¨ji+∑jb¨j+∑iPic¨i−β∑jDjd¨+∑i∑kuike¨ik+∑iVi−11.89f¨+∑i∑jg¨ji≤0.where p=a˙,b˙,c˙,d˙,e˙,f˙,g˙ represents the pole of the P2 constraint set and u=a¨,b¨,c¨,d¨,e¨,f¨,g¨ represents the polar line of the convex polyhedral sets. Constraint (23) guarantees that q is the maximum of the feasible solutions for the dual problem P2, and constraint (24) guarantees that P2 has a feasible solution.The master problem of the original question can be expressed as follows:(11)minCs∑iXi+Cp∑iPi+Cv∑iVi+Ce⋅∑i∑kTikuik+q.Subject to:(12)3−6，13,16,22,23,q∈R.The dual problem P2 is a primal problem of the target problem; the primal problem is general linear programming; and the linear programming P2 is solved. The solution has three forms:(1)
.There is no feasible solution; then the target problem also has no feasible solution(2)
.There is an infinite optimal value, get a polar lineu of the polyhedral sets of P2, and add constraint (23) to the master problem(3)
.There is a finite optimal solution, get a polep of the polyhedral sets of P2, and add constraint (24) to the master problem.


## 6. Case Study

Case studies are carried out to validate the proposed model based on the data from a carsharing operator in Beijing, China. Considering the nearest choice, people always expect to pick up at the nearest station to collect the OD demand between the candidate sites. Based on this, the OD between the candidate stations can be counted. For example, if a tripd with the origin O and the destination D, the candidate station i is closest to O, and the candidate station k is closest to D, then trip d is counted in the OD between i and k. The minimum expected travel time between candidate stations is calculated by the formula distance/free-flow speed, where the free speed is 60 km/h.Considering the distance decay between zones and candidate stations, function (13) is used to determine the degree of satisfaction of zones. The function is as follows, and the corresponding relationship curve is shown in Figure 10.(13)sji=−wtji4+w14w14expwtji/403,wtji≤w1,0,wtji≥w1,Figure 10
Distance decay function.Based on the extracted trip information, assuming that the vehicle can be used for 5 years. Refer to the parameter settings in other related literature and set the corresponding parameters as:Cs=1 yuan/day, Cp=12 yuan/(day∗per), and Cv=56 yuan/(day∗per). In addition, considering the current electricity price and the 100 km energy consumption of the car, set Ce=6yuan/hour. Figure 11 shows the spatial distribution of the candidate stations, for a total of 136.Figure 11
Spatial distribution of candidate stations.Figures12–15 show the distribution of selected stations when the demand satisfaction rate is 0.4, 0.5, 0.6, and 0.7, respectively. The results obtained for the four schemes are presented in Table 1. The table contains the values for several indicators for comparison. In the study area of the model application, the number of existing stations, parking spots, and fleet size are 101, 724, and 556, respectively. The analysis of Table 1 reveals that the objective function of different satisfaction rates is smaller than the existing system.Figure 12
Parking spots and vehicle distribution when rate = 0.4.Figure 13
Parking spots and vehicle distribution when rate = 0.5.Figure 14
Parking spots and vehicle distribution when rate = 0.6.Figure 15
Parking spots and vehicle distribution when rate = 0.7.Table 1
Results of the model.
Number of stationsNumber of parking spotsFleet sizeObjective valueCurrent10172455611,357.47Rate = 0.41179634,517.35Rate = 0.51699795,671.05Rate = 0.623236948,165.80Rate = 0.7292811109,613.87As shown in Figure16, it can be seen that as the satisfaction rate increases, the values of the four indicators increase, and the fleet size almost changes linearly because of the linear relationship between the demand and the size of the fleet is considered in the model. The number of spots varies greatly because the operational decision is considered in the static model. The number of parking spots is increased to convert the dynamic operating costs into static costs, thereby improving vehicle utilization.Figure 16
The results of the location model.


## 7. Conclusion

This paper addresses the one-way station-based carsharing network location problem by considering the spatial coverage characteristics and the demand characteristics between stations, which has not been reported in the existing studies according to the literature review. A mixed-integer programming model is established to minimize the total cost of operators. In order to get effective results quickly, the classical Benders decomposition algorithm is extended. The case study results show that at a radius of 1.5 km, the candidate stations can cover about 90% of the demand and then consider the interaction between the stations to meet the demands of about 70%. As the demand for satisfaction increases, the difference between the number of parking spots and vehicles is greater. This is because the model considers both the satisfaction of the requirements and the interaction between the stations. The redundant parking spots are set to improve the utilization of the vehicle. That is to say, the number of parking spots is increased to convert the dynamic operating cost into the static cost. This strategy can reduce the use of vehicles with low utilization, thereby increasing the efficiency of the system. It should be noted that this paper only considers the benefit of operators. Future works will be carried out to optimize the one-way carsharing system by considering the benefits of operators, as well as the benefits of users and society. In addition, the impact of COVID-19 will be taken into account in future modeling and case studies.



---

*Source: 6142950-2022-02-08.xml*