key: cord-0066793-wcbn9mqm
authors: Qin, Meng; Wang, Jiayu; Chen, Wei-Ming; Wang, Ke
title: Reducing CO(2) emissions from the rebalancing operation of the bike-sharing system in Beijing
date: 2021-08-19
journal: Front
DOI: 10.1007/s42524-021-0168-y
sha: c1a1522f9b873f22cc0bac6539ea737d0214ba00
doc_id: 66793
cord_uid: wcbn9mqm

With the development of the bike-sharing system (BSS) and the introduction of green and low carbon development, the environmental impacts of BSS had received increasing attention in recent years. However, the emissions from the rebalancing of BSS, where fossil-fueled vehicles are commonly used, are usually neglected, which goes against the idea of green travel in a sharing economy. Previous studies on the bike-sharing rebalancing problem (BRP), which is considered NP-hard, have mainly focused on algorithm innovation instead of improving the solution model, thereby hindering the application of many existing models in large-scale BRP. This study then proposes a method for optimizing the CO(2) emissions from BRP and takes the BSS of Beijing as a demonstration. We initially analyze the spatial and temporal characteristics of BSS, especially the flow between districts, and find that each district can be independently rebalanced. Afterward, we develop a rebalancing optimization model based on a partitioning strategy to avoid deciding the number of bikes being loaded or unloaded at each parking node. We then employ the tabu search algorithm to solve the model. Results show that (i) due to over launch and lack of planning in rebalancing, the BSS in Beijing shows great potential for optimization, such as by reducing the number of vehicle routes, CO(2) emissions, and unmet demands; (ii) the CO(2) emissions of BSS in Beijing can be reduced by 57.5% by forming balanced parking nodes at the end of the day and decreasing the repetition of vehicle routes and the loads of vehicles; and (iii) the launch amounts of bikes in specific districts, such as Shijingshan and Mentougou, should be increased.

Since 2006, China has surpassed the US as the largest carbon emitter in the world (Wei et al., 2019) . The carbon emission level of the country even reached 13.92 billion tons in 2019. However, given the impact of the COVID-19 pandemic, the largest carbon-emitting countries in the world have reported reduced emission levels, with China reporting only a 1.7% decrease (Friedlingstein et al., 2020) . Transportation is the way that consumes large amount of energy and emits huge quantities of CO 2 . As a super-large city in China, Beijing has a ring-shaped spatial road distribution, with most outsiders residing within the periphery of Beijing to work in the business centers located at the middle of the city. These trends have resulted in a tidal traffic travel phenomenon with adversarial impacts on the environment (Zheng et al., 2017) . For instance, from 2014 to 2018, the air quality index (AQI) of Beijing only reached a fair level (AQI < 100) in 20 months . To improve the road environment and reduce traffic emissions in Beijing, the city traffic management department has increased its public transport infrastructures every year and formulated policies related to the purchase and use of cars, but the effects of these initiatives are generally insignificant (Yu et al., 2017) .

As a new business model, sharing economy has gained much popularity in recent years. This model has been proven to solve several types of challenges, including social inequality, economic improvement, and environmental problems (Jie et al., 2020) . As a representative product of sharing economy, the bike sharing system (BSS) is booming in the Chinese market. Despite existing for half a century, BSSs have significantly grown in their prevalence and popularity across the world only in the past decade (Fishman et al., 2013; Ricci, 2015) . With over 400 BSSs, China is far ahead in its number of bicycles; three out of four public-use bicycles in the world are in the country (de Maio and Meddin, 2014) . With an aim to address the "last kilometer" travel demand, BSS advocates energy conservation, environmental protection, and green low-carbon travel. Regardless of enabling "last kilometer" short distance travel or connecting people to other modes of public transportation, BSS has an important role in one's everyday life and is expected to become a new green transportation mode after subway trains, buses, and public bicycles. Therefore, the environmental impacts of BSS have received increasing attention in recent years.

The bike-sharing rebalancing problem (BRP), which focuses on balancing the bike supply and demand of parking nodes, remains a key issue to be solved by BSSs. Given its important theoretical and practical application values and attention from the society and academia, BRP is considered a selective pick-up and drop-off NP (nondeterministic polynomial)-hard problem (Ting and Li, 2013) . Unlike the general traveling salesman problem (TSP), given the demand of nodes and the limited rebalancing vehicle capacity (Q), BRP requires one to determine the number of bikes being picked up or dropped off at nodes, thereby increasing its complexity.

To meet the demand of a large number of bike-sharing users in the next morning and to consider the length of routes for the rebalancing, trucks are necessary to achieve rebalancing in a medium BSS (Wang and Szeto, 2018) . However, these trucks usually consume gasoline or diesel and emit pollutants, which contradicts the green travel goals advocated by enterprises operating BSSs. However, only few studies have focused on the environmental impacts of BRP.

Some studies on the environmental benefits of rebalancing have used a small amount of randomly generated data and solved their models via numerical analysis (Shui and Szeto, 2018; Wang and Szeto, 2018) instead of using real BSS order data. As an NP-hard problem, BRP has a solution time that increases exponentially along with its scale, thereby hindering the application of the aforementioned methods in municipal-level BRP (Ting and Li, 2013) . Meanwhile, a trade-off relationship can be observed between the total unmet demand and the total fuel and CO 2 emission cost in rebalancing (Shui and Szeto, 2018) .

Traditional environmental research on rebalancing have used a rebalancing model that requires meeting the target number of bikes at each node. According to theory of diminishing marginal benefits, rebalancing the last few bicycles imposes huge economic and environmental costs, thereby resulting in a limited emission reduction space.

To fill these research gaps, by using large amounts of real BSS order data from Mobike in Beijing, we analyze the temporal and spatial characteristics of BSS and use the clustering algorithm based on order demand to locate bike parking nodes. We also propose a partition strategy based on the supply and demand of rebalancing to reduce the scale of BRP and to avoid deciding the number of bikes being loaded and unloaded in nodes. We then modify an optimization model by balancing the cost of minimizing CO 2 emissions and the loss of unmet demand. The overall aim of this paper is to develop a method for optimizing CO 2 emissions from BRP that can be applied to real BSS scenarios and reduce CO 2 emission in rebalancing.

The findings of this work are expected to provide theoretical and practical contributions. First, these findings can help Beijing set up bike parking nodes and weigh the environmental costs and loss of unmet demand in the rebalancing so as to reduce its operational costs and CO 2 emissions and to ensure the sustainability of BSS as a green travel mode. The proposed methods and model can also be applied to BRP in other cities. Second, the clustering algorithm can be used to locate parking nodes in dockless BSS. Third, the applied partition strategy and improved model can address the difficulties encountered when applying the rebalancing model to actual BSS. Fourth, the influencing factors of CO 2 emissions in rebalancing can provide a basic model for future rebalancing low carbon research.

The rest of this paper is organized as follows. Section 2 summarizes the BRP literature. Section 3 presents the temporal and spatial characteristics of BSS in Beijing. Section 4 evaluates the CO 2 emissions of current rebalancing in Beijing and optimizes rebalancing by proposing a partitioning strategy and improving the existing rebalancing model. Section 5 discusses the environmental impacts of the optimization and compares the proposed method with the current rebalancing approaches. Section 6 concludes the paper.

We initially review previous research on the environmental impacts of BSS (including rebalancing). Afterward, we discuss two types of BRP, namely, static and dynamic BRPs, and describe the existing mathematical models used in studying BRP, including assumption and objective functions in models. We eventually focus on the algorithms used in the literature for solving BRP models.

Previous studies (Shaheen et al., 2010; Zhang and Mi, 2018) have only highlighted the direct environmental impacts of BSS (i.e., direct emission reduction from replacing private car trips with shared bike travels) yet did not consider the more complex and indirect environmental impacts such as negative (e.g., increase in the number of motor vehicles used for bike rebalancing) and unintended effects (e.g., abandoning surplus bikes) (Frenken and Schor, 2017; Taylor, 2018) . Fishman et al. (2014) found that bike sharing reduced motor vehicle use in Melbourne, Australia and in Minneapolis and Washington DC, US, and that the rebalancing of public-use bicycles discouraged additional motor vehicle use in London, UK. However, rebalancing operations may threaten the positive environmental impacts of bike sharing given that these operations are performed by fossil-fuel-based vehicles (Wiersma, 2010) . Except for Shui and Szeto (2018) and Wang and Szeto (2018) , only few studies have focused on the environmental impacts of the rebalancing operations of bike sharing. Shui and Szeto (2018) proposed a new dynamic BRP, used a small amount of generated data, and solved the model based on numerical analysis instead of using real BSS order data. Moreover, the authors merely focused on the change of weight between unmet demand and CO 2 emissions and provided neither a unified objective function nor optimal results. Wang and Szeto (2018) addressed the static rebalancing problem, argued that all broken shared bikes should be moved back to the depot, and minimized the CO 2 emissions from all rebalancing vehicles. However, similar to Shui and Szeto (2018) , they did not use real BSS data. Moreover, the emission reduction space may be very limited for meeting all demands, and Wang and Szeto (2018) seemed unaware that part of the demands can be sacrificed in exchange for further emission reductions.

Rebalancing can be divided into static and dynamic rebalancing. Static rebalancing is usually performed at night to meet the needs of stations for the following day. During the rebalancing, the inventory and demand of stations are fixed (Forma et al., 2015) . By contrast, dynamic rebalancing is usually performed at daytime when the BSS has high usage and while station requirements are changing in real time (Legros, 2019) . Both types of rebalancing have been used by operators in practice. However, previous studies have mostly focused on static rebalancing (Ho and Szeto, 2014) . In addition, compared with dynamic rebalancing, static rebalancing has more flexibility, effectively avoids traffic congestion at night (especially in huge cities such as Beijing), and produces less environmental pollution. To fill this research gap, we consider static BRP as our optimization background.

The rebalancing of BSS is usually performed by fossilfueled vehicles. Previous studies have used different fuel consumption or CO 2 emission models to measure the environmental impact of vehicle routing problems. In most of these models, the measurable factors of fuel consumption or CO 2 emission include vehicle speed, acceleration, gradient, load, and fuel (Scott et al., 2010; Hosseini-Nasab and Lotfalian, 2017) . Given that static rebalancing is usually performed by homogeneous vehicles at night, the usage of BSS and congestion effects can be omitted, and the speed of rebalancing vehicle can be treated as a constant (Wang and Szeto, 2018) . Therefore, we assume that CO 2 emissions are related to both the load and the travel distance of the vehicle carrying the load.

In the existing research, the assumptions of the BRP model mainly include the number of vehicles and whether a station can be visited by one vehicle (Cruz et al., 2017) or multiple vehicles (Szeto et al., 2016) , as well as assuming each station can be visited only once (Ho and Szeto, 2014) or multiple times (Bulhões et al., 2018; Liu et al., 2018) . In addition, the existing models often assume that vehicles depart from and return to a depot (Raviv et al., 2013) , and most studies also assume that a BSS has fixed stations (Chemla et al., 2013) ; these assumptions are not applicable to a real dockless BSS operated by an enterprise (Ai et al., 2019) where users can park their bikes in any prescribed area at will.

The objectives of the BRP model usually depend on the focus of the operator. The government-operated public bike system aims to maximize social benefits and meet the needs of users (Contardo et al., 2012) , whereas the BSS operated by enterprises often aims toward the shortest travel distance (Benchimol et al., 2011) and minimized operating costs (Erdoğan et al., 2014) . While the environmental impacts of BSSs have received increasing attention, only few studies have treated BRP with environmental impacts as their objective. Low carbon research can contribute to the sustainable development of BSS and reduce traffic carbon emissions.

Accurate solving algorithms are almost impossible to be used as a solution for large-scale BRP, and the associated costs are unacceptable for operators. Therefore, some heuristics or approximation algorithms have been proposed to solve BRP, such as the genetic algorithm (Liu and Pan, 2019) , branch-and-cut (Chemla et al., 2013) , and neighborhood search (Rainer-Harbach et al., 2013) . The tabu search algorithm has a fast convergence speed and is considered very effective in solving routing problems. In recent years, some scholars have proposed an improved tabu search algorithm to solve static BRP. Szeto et al. (2016) proposed an iterative tabu search heuristic algorithm to minimize the punishment for unmet needs. Lü et al. (2019) designed a two-layer tabu search algorithm to solve static BRP based on the supply and demand relationship. However, these studies ignored the environmental impacts of BRP, thereby preventing us from using their algorithms in this study.

We use real BSS order data from Mobike, formerly one of the largest bike-sharing service providers in China based in Beijing. Mobike accounted for 56.56% of China's bikesharing market in 2017 and received approximately 20 million orders per day (Sohu Finanial, 2017) . We use the desensitized order data (excluding the private information of users) of Mobike for the dates from May 10 to May 16, 2017, which amounts to more than 1.82 million orders and 435492 bikes. Each order contains elementary trip information, including order ID, user ID, bike ID, bike type (as of May 2017, Mobike had produced two types of bike-sharing modes, namely, type 1, the classic mode, and type 2, the light ride mode), start time, and the longitude and latitude of order start and end positions, respectively. Table 1 presents a few representative data samples consisting of several orders placed within May 10 to 16, 2017.

The transportation map of Beijing has a ring-shaped spatial distribution covering eight existing and planned ring roads and radial expressways extending in all directions. Given that urban roads in Beijing usually start from south to north or from west to east, we use the Manhattan distance to calculate the distance between the start and end positions of each order (Ma, 2020) .

The Manhattan distance between two points (x i , y i ) and (x j , y j ), also known as taxi distance, is computed as the distance in the north-south direction plus the distance in the east-west direction, that is, dði, jÞ ¼ jx ix j j þ jy iy j j. We calculate the Manhattan distance between two points based on their longitude and latitude as follows:

where S i represents the Manhattan distance of order i, O xi and O yi denote the longitude and latitude of the start position of order i, respectively, and D xi and D yi denote the longitude and latitude of the end position of order i, respectively. In line with the Haversine formula (Cho and Baik, 2018) , the LBS function calculates the spherical surface distance based on the longitude and latitude of two spherical points. According to the definition of Manhattan distance, we assume an auxiliary point ðO xi , D yi Þ. In this case, the Manhattan distance between points ðO xi , O yi Þ and ðD xi , D yi Þ is equal to the spherical distance from ðO xi , O yi Þ to ðO xi , D yi Þ plus that from ðO xi , D yi Þ to ðD xi , D yi Þ.

3.2 Descriptive analysis of data Figure 1 shows the temporal distributions of bike trip start time. First, shared bike trips in Beijing achieves peak value during 7-8 AM and 5-6 PM on weekdays, which corresponds to the rush hour in the city. This finding is consistent with the purpose of BSS to solve the "last kilometer" problem during commuting times. Second, a small peak can be observed at 12 PM on weekdays, which can be attributed to the fact that some riders use the bikes to have lunch in a nearby place. Third, the temporal distribution of bike trips in the morning is more concentrated than that in the evening, which may be ascribed to the fact that work in China usually starts at 8-9 AM, whereas the work end time is highly flexible. Fourth, the temporal distribution of trips on weekends obviously differs from that on weekdays. Specifically, no obvious peak is observed on weekends, and the distribution of morning trips is lowest during daytime. However, a small increase can be observed in the evening, which may be related to trips for leisure and entertainment. Figure 2 maps the spatial distribution of the bike orders in Beijing. The heat map clearly shows that some central urban areas have a high density of bike start and end positions, especially the districts of Dongcheng, Xicheng, Shijingshan, Haidian, Chaoyang, and Fengtai. Moreover, the density distribution of shared bike trips is related to the traffic roads in Beijing (Fig. 2 ). In general, while the demand for the start and end positions of bikes is balanced across districts, some differences in performance can be observed. Specifically, most trips take place in central districts, such as Chaoyang, Fengtai, Haidian, Dongcheng, and Xicheng, and most start and end positions of each trip are located in the same district ( Fig. 3) . At the end of the day, only a slight fluctuation can be observed in the number of bicycles in each district, with the total increase or decrease amounting to only 0.5% (Table 2) . Therefore, the BRP in Beijing can be solved within each district without rebalancing between districts to reduce the problem scale. We then solve the BRP of each district in the following sections.

We first evaluate the CO 2 emissions of the current rebalancing scheme and use the clustering algorithm to locate the parking nodes. Second, we propose a partition strategy based on the rebalanced supply and demand relationship of bikes to prevent the number of bicycles in each partition from exceeding the vehicle capacity (Q), to avoid deciding the number of bikes being loaded or unloaded at each node, and to reduce the scale of the NPhard problem simultaneously. Third, we improve the existing rebalancing model. Fourth, we apply this model to each partition to connect these partitions. Fifth, we summarize the algorithm. 4.1 CO 2 emissions in rebalancing before optimization 4.1.1 Acquisition of rebalancing data Given that the BSS rebalancing data cannot be obtained directly (GPS is not used for tracking in the rebalancing), we obtain our rebalancing data by processing order data. If the end position of the previous order for a bike with the same ID differs from the start position of the next order, then a rebalancing is very likely to have occurred. Therefore, we initially categorize each order by bike ID and sort these orders based on trip start time (Table 3 ). The start position of the rebalancing data is treated as the end position of the previous order, whereas the rebalancing end position is treated as the start position of the next order, for the bike with the same ID (Table 4 ). Given that some orders do not have previous order data, they all have missing rebalancing position information (shown as NA in Meng QIN et al. Reducing CO 2 emissions from the rebalancing operation of the bike-sharing system in Beijing Table 4 ) and are therefore excluded from the rebalancing operation. Then, data with the start time within 5/10/2017 and 5/16/2017 are selected for the CO 2 emission assessment of the rebalancing. Furthermore, we assume that those bikes with a rebalancing distance of less than 200 m were moved manually instead of by vehicles. 4.1.2 Obtaining parking nodes and the current rebalancing route and estimating CO 2 emission Given the lack of actual rebalancing data, we cannot obtain rebalancing information (e.g., which bikes are loaded by the same vehicle and the route of the vehicle). However, the closer the start and end positions of rebalancing, the more likely they are to be rebalanced by the same vehicle. Given that dockless BSS has no stations unlike in stationbased BSS, we use the clustering algorithm and take the start position, end position, and direction from our rebalancing data as feature vectors given that the vehicles are fully loaded in the rebalancing. We determine the clustering number n based on rebalancing quantity and vehicle capacity (n = Num/Q) and treat this number as a parameter in the clustering algorithm. Afterward, we calculate the geometric center (X, Y) of each class according to the rebalancing start/end positions to identify the start/end parking node of the rebalancing route.

x ¼

where C is the rebalancing data belonging to a class, lat i and lng i denote the latitude and longitude of parking node i, respectively, and atan2ð⋅Þ is a function that returns the arctangent value by giving x and y coordinate values. We assume that homogenous vehicles are used in all rebalancing in Beijing and that these vehicles have a standard capacity of loading 50 bikes. We calculate the CO 2 emissions of a vehicle as 

where E is the total CO 2 emissions of the current rebalancing, F * and F represent the CO 2 emission factor of a fully loaded vehicle and an unloaded vehicle, respectively, d ij represents the distance between the vehicle loading bikes at parking node i and unloading bikes at parking node j, and d ji# represents the distance between the vehicle unloading bikes at parking node j and loading bikes at the next parking node i # . For the selection from j to i # , we apply the greedy algorithm to select the loading node closest to j.

The rebalancing model of dockless BSS is similar to that of station-based BSS, and the greatest difficulty lies in the number of bikes being picked up and dropped off at parking nodes. We avoid deciding the number of bikes being picked up or dropped off at these nodes and reduce the scale of the NP-hard problem by applying a partitioning strategy based on the supply and demand of the rebalancing. After partitioning, the number of bicycles being picked up or dropped off in each partition does not exceed the capacity of rebalanced vehicles. Therefore, deciding the number of bicycles being picked up or dropped off in each node is unnecessary; instead, we only need to decide whether to visit the node and the order of visiting. Theoretically, the target bike number at each node is achieved via internal rebalancing in each partition without the intervention of the other partitions. We therefore divide a large BRP into several small BRPs that can be completed by a vehicle, thereby greatly reducing the complexity of the problem.

The partitioning strategy steps are as follows.

(i) The number of bicycles at each parking node (p i ) differs from the target demand (q i ). According to the supply and demand relationship, we classify parking nodes into the following ( Fig. 4(a) ):

p i < q i , parking nodes that need to be supplied with shared bikes (S d ); p i > q i , parking nodes that need to remove shared bikes (S p ); p i ¼ q i , parking nodes that do not need to be visited given that their bike supply and demand are balanced (S b ).

(ii) We adjust the parking nodes according to the rebalancing demand. For the node with more than 50 bicycles in demand or supply, we dividing this node into two or more nodes with the same coordinates and different labels, lest it cannot be entirely loaded.

(iii) We determine the start node by using the greedy algorithm, and we generate two chains for the partitioning in step (i). We select the start node successively for all nodes in collections S d and S p . We use the greedy algorithm based on distance to solve the TSP problem, and we select the path solution with the minimum distance as our initial solution. This step generates two chains X d and X p (Fig. 4(b) ).

(iv) To ensure that the number of bicycles to be loaded and unloaded in each partition does not exceed the vehicle capacity (Q), we segment the chain X d (X p ) obtained in step (iii). We start from the first node (S 1 ) of each chain and calculate the sum (T) of the demand (supply) quantity of visiting the nodes in sequence. When visiting a node to find that the demand (supply) quantity exceeds the vehicle capacity (Q), that is, T > Q, we cut off X d (X p ) and

initialize T to 0. Afterward, we continue visiting the next node until X d (X p ) is split into a series of sub-chains X di (X pi ) that are approximately Q in demand (supply) quantity (Figs. 4(c) and 4(d)).

(v) We adjust the number of sub-chains when the numbers of sub-chains in the supply and demand sides are unbalanced. We select the sub-chain with the most supply or demand quantity from the side with less sub-chains, divide this sub-chain into two sub-chains, and repeat the above operation until the numbers of sub-chains in the two sides are the same.

(vi) We identify the location of each sub-chain and calculate the geometry center coordinate X dic (X pic ) for each sub-chain according to Eqs. (2-1)-(2-7).

(vii) We match the supply and demand sub-chains, obtain the partitions, and then determine the location of each partition. We use the geometric center coordinate X dic (X pic ) to represent the position of sub-chain X di (X pi ) (Fig. 4(e) ) and then match the supply and demand partitions one by one. Each X dic selects the nearest X pic for matching, and the obtained geometric coordinates are X dic þ X pjc ¼ X dpic , that is, X di þ X pj ¼ X dpi (Fig. 4(f) ).

In this way, the parking nodes set of each partition generated only needs to be rebalanced by one vehicle, and we do not need to decide the number of bikes being loaded and unloaded. We assume that the vehicle does not carry bikes into a partition and that no bikes are left in the vehicle after the rebalancing of a partition. Therefore, the rest of the bikes on the vehicle will be unloaded at the last node of a partition, which would allow us to use the same rebalancing model for all partitions.

Following Ho and Szeto (2014) , we propose a modified formulation to solve BRP. Ho and Szeto (2014) studied the static rebalancing problem of a station-based BSS with a depot as a selective pick-up and drop-off problem and explicitly defined their pick-up and drop-off stations. Their model assumes that the depot is both a pick-up and dropoff node and has sufficient bikes and capacity and that all stations can only be visited once at most. The objective function is to minimize the sum of difference between the number of bikes after rebalancing and the target number at each station.

We modified the formulation of Ho and Szeto (2014) as follows. First, the model no longer establishes constraints on vehicle capacity. By applying the partitioning strategy in Section 4.2, the quantity of bikes to be loaded or unloaded in each partition does not exceed the capacity of one vehicle. Therefore, the model only needs to decide whether to visit the parking node. If so, the vehicle can load the remaining bicycles. Second, in the model, we do not establish constraints for pick-up and drop-off parking nodes because after partitioning, the problem has been greatly simplified, and we only have few cases where two nodes need to be considered separately. Third, although each node in our model can only be visited once at most, the partition strategy applied in step (ii) divides the parking nodes with an excessive demand or supply into several nodes with the same location, thereby making our model equivalent to a multi-visit model. Fourth, we consider a vehicle and a BSS without a depot. Vehicles are usually private and do not need to start from or return to the depot when the rebalancing is finished, thereby avoiding the calculation of the impact of some ineffective rebalancing from the depot to parking nodes (Luo et al., 2020) . Although we use a single vehicle model to connect all parts, this model can be easily transformed into a multivehicle model, where a vehicle completes only one or several partitions. Fifth, the objective function is to minimize the cost of CO 2 emission and the losses caused by unmet demand. In other words, we achieve a trade-off between the environmental impact of the rebalancing and the satisfaction of user demand. Given that the goal of rebalancing is to "restore something back to its original state", the target number of bikes at each parking node (q i ) is equal to the initial bike quantity at the beginning of the day. The rebalancing demand (i.e., number of bikes that need to be picked up from or dropped off at nodes) is defined as the difference between the number at the end of a day (p i ) and the target number (q i ). Finally, we assume that the CO 2 emissions are related to both the load and the travel distance of the vehicle carrying the load. Table 5 provides the definition of the notations involved in the 

X n j¼1 and j≠i x ji ¼ X n j¼1 and j≠i x ij , 8i 2 N , (4-2) X n j¼1 and j≠i x ij £1, 8i, j 2 N , (4-3)

and j≠i y ij -X n j¼1 and j≠i y ji , 8i, j 2 N , (4-5) X n i¼1 y i ¼ 0, 8i 2 N , (4-6) a j ³a i þ 1 -M ð1x ij Þ, 8i, j 2 N , i≠j, (4-7)

x ij 2 f0, 1g, 8i 2 N , (4-8)

y ij ³0, 8i 2 N , (4-10)

S i ³0, 8i 2 N , (4-11) a i ³0, 8i 2 N : (4-12)

The objective function of mathematical model (4) is to minimize the cost of CO 2 emission and the losses caused by unmet demand. Constraint (4-1) defines the number of bikes owned by each parking node after rebalancing. Constraint (4-2) ensures that vehicles leave after visiting a node. Constraint (4-3) ensures that a location can only be visited once at most in the rebalancing. Constraint (4-4) ensures that the number of bikes loaded at a node is equal to the number of redundant bicycles at the node because after applying the partitioning strategy, the number of bikes supplied in each partition does not exceed the capacity of a vehicle; while the number of unloaded bicycles at the node is equal to the smaller value of the number of bicycles required at the node and the number of bicycles carried by a vehicle. Therefore, the visiting order of the parking nodes will determine how many requirements can be met. Constraint (4-5) states that the number of bikes being picked up from or dropped off at a node is equal to the difference between the number of bikes on the vehicle before and after visiting the node. Constraint (4-6) ensures that all picked up bikes are dropped off. Constraint (4-7) eliminates sub-tours. Constraint (4-8) defines x ij as a binary variable. Constraints (4-9) to (4-11) restrict the quantity of bikes being picked up and dropped off, the number of bikes on a vehicle, and the number of bikes in a station after rebalancing to nonnegative integers. Constraint (4-12) ensures that the auxiliary variable is nonnegative. 

We apply our model to the BRP of each partition and use the tabu search algorithm to solve the problem (Figs. 5(a) to 5(c)). Connecting the tail and head of the partition in turn is treated as a shortest path problem. Given that the number of partitions for a district is not too large, we use a simple and fast greedy algorithm to connect the end parking node S ei and the start parking node S sj between different collections (Fig. 5(d) ).

The improved rebalancing algorithm based on the proposed partitioning strategy involves the following steps:

Step 1: A clustering algorithm is used to obtain the parking nodes;

Step 2: Using the partitioning strategy, the large-scale BRP that needs to determine the quantity of bikes to be loaded or unloaded at each node is transformed into several problems to avoid deciding the quantity of loading and unloading;

Step 3: The rebalancing model in Section 4.3 is established for each partition;

Step 4: The tabu algorithm is used to obtain the optimal solution of the model in Step 3;

Step 5: The greedy algorithm is used to connect the ends and heads of the partitions in turn;

Step 6: The algorithm terminates.

We apply our proposed model on the BSS operating in Beijing. Afterward, we illustrate the optimization effect of the algorithm from three aspects.

5.1 Optimize the number of parking nodes visited by vehicles and the driving routes Table 6 shows the difference in the number of parking nodes visited by vehicles before and after optimization in the rebalancing scheduled on Thursday, May 11, 2017. In the current rebalancing, the order data for the day were not fully utilized to judge whether the nodes had been balanced. Therefore, the vehicle visited all the nodes, including those with balanced supply and demand. On the basis of the number of departures and arrivals at each node as obtained from the order, in the optimized rebalancing, the vehicle skipped the balanced nodes, and the number of nodes involved in the rebalancing problem was reduced. This process is critical in optimizing the results, especially in areas where only few bikes are placed and where the rebalancing route is simple. Figure 6 shows the distribution of parking nodes and the vehicle routes before (left) and after (right) optimization on May 11 (only Haidian, Tongzhou, Mentougou, and Shijingshan are listed here). Some peripheral districts of Beijing have few bicycles and parking nodes with very scattered distribution, thereby making the vehicle route rebalancing relatively simple and limiting the space for optimizing the repeated parts of the route. Moreover, a large number of nodes with balanced supply and demand can be found around these districts, such as in Tongzhou, Daxing, Changping, Fangshan, and Shunyi, probably because these districts are located outside the 5th Ring Road of Beijing, situated far away from the urban area, and are not the residence and work places of the main bikesharing users. Given that a few or fixed number of users can be found in these districts, the number of bicycles at each node returns to the initial quantity at the end of the day. In these districts, one should judge whether the nodes are balanced in advance. Table 7 shows the driving distance of vehicles in each district within one week before and after optimization. The driving distances of vehicles in Chaoyang, Haidian, Shunyi, and Dongcheng have been significantly reduced by more than 48%.

Due to the lack of planning for the current rebalancing, most drivers choose the next parking node based on their experience, thereby resulting in repeated and messy driving routes, especially in districts with a large number of bikes and parking nodes, such as Haidian (Fig. 6) . The sample of orders used in this study consists of 197856 bikes on May 11, among which Chaoyang, Haidian, and Fengtai have 59240, 32853, and 32507 bikes, respectively, accounting for 63.0% of all bikes (Fig. 7) . These districts are located in the center of Beijing with many administrative, commercial, and residential areas, where people tend to use bikes to move around, and where nodes are highly concentrated. Given that the demand of each parking node is extremely unbalanced, at the end of the day, the proportion of nodes with a balanced supply and demand is very small. Therefore, for these districts, optimizing the repeated part of the route is critical. Among them, the distance in Chaoyang and Haidian has been reduced by more than 50% (Table 7) . Fengtai has a lower route optimization rate, but its number of parking nodes is higher than that of Haidian because the former is located south-west of Beijing where only few residential and administrative places are located, where roads are relatively simple, and where traffic congestion is low. Therefore, the current vehicle route in Fengtai during the rebalancing is not as complex as that in Haidian.

We observe a different case in Shijingshan and Mentougou. These two districts have s imilar characteristics with Tongzhou and Changping, such as remote location, few parking nodes, and scattered distribution, but only few of the nodes in these two districts have a balanced supply and demand at the end of the day, thereby significantly reducing the effect of route optimization (41.9% and 35.1% for Shijingshan and Mentougou, respectively). According to Fig. 7 , the bicycle turnover rate of Shijingshan, Mentougou, and Fangshan is higher than that of the other similar districts. Therefore, the reduced optimization effect may be ascribed to the small number of bicycles in these districts, which does not meet the demand at some periods of the day and prevents some remote nodes from achieving balance. These areas also have simple vehicle route and limited optimization space for the repeated part of the route. 5.2 Optimize the CO 2 emissions generated in the rebalancing process Table 8 compares the CO 2 emitted by the vehicles during rebalancing before and after optimization. The CO 2 emissions during rebalancing within a week decreased by 57.5% after optimization. The optimization rate of CO 2 emissions demonstrates a greater decrease compared with that of vehicle driving distance because the current rebalancing loads and unloads bikes according to manual experience. The vehicles are almost fully loaded at each supply parking node, which further increases their CO 2 emissions while driving, especially in Fangshan, Shunyi, and Mentougou.

In terms of time, the CO 2 emissions from rebalancing on weekends (May 13 and 14) were significantly lower than those on weekdays, during which the average emission was 5087.27 kg, with an average emission reduction rate of 56.2%. The lowest emission was 4990.92 kg CO 2 recorded on Saturday (May 13), with an emission reduction rate of 55.2%. The average emission on weekdays was 5827.42 kg, with an average reduction rate of 58.0%. The highest emission and emission reduction rate were 6115.04 kg and 59.1%, respectively, both recorded on Monday (May 15).

In terms of district, the distribution of CO 2 emissions within a week before and after the optimization is generally consistent, but a huge gap in emissions can be observed across districts (Fig. 8) . The districts are then divided into three groups according to their emission quantity during rebalancing. The first group includes the high emission areas of Chaoyang, Haidian, and Fengtai, the second group includes the medium emission areas of Daxing, Tongzhou, Xicheng, Changping, and Dongcheng, and the third group includes the low emission areas of Fangshan, Shunyi, and Mentougou.

The high emission areas are located between the 2nd and 4th Ring Roads of Beijing, covering a wide area with a huge supply and demand of sharing bikes. Among them, Chaoyang and Haidian have large numbers of administrative and residential areas. The average daily CO 2 emission in these districts was 1191.00 kg, and the average daily emission reduction rate is 56.9%. The highest average daily emissions and emission reduction rate were observed in Chaoyang (1915.06 kg and 65.0%, respectively).

The medium emission areas have an average daily CO 2 emission of 325.31 kg and average daily emission reduction rate of 54.1%. Some obvious emission reduction effects can be observed. Changping, Daxing, and Tongzhou are all located outside the 4th Ring Road of Beijing, situated far away from the city center, and are not the main areas for BSS, but due to their large geographical area (Table 9) , the CO 2 emissions in these areas cannot be underestimated. On the contrary, although Xicheng and Dongcheng are located in the heart of Beijing and the BSS is widely utilized, they only have small areas, thereby resulting in lower vehicle emissions.

The low emission areas have an average daily CO 2 emission of 104.10 kg and average daily emission reduction rate of 50.7%. A very small number of parking nodes is clustered in these areas. With a significantly low number of bicycles that need to be rebalanced, these areas have limited space for reducing CO 2 emissions via route optimization. For instance, Mentougou only has 10 parking nodes and does not have a balanced parking node at the end of the day. Therefore, vehicle load (number of bikes carried by a vehicle) has a critical role in reducing CO 2 emissions in these areas.

Tables 10 shows the number of bikes in each district where rebalancing demands are met before and after optimization. After optimization, the effect of the restoration degree of the BSS has been significantly improved, and the met rate of the bike demand in the parking nodes could increase from the current 63.7% to 86.6%. In the current rebalancing, the parking nodes in Shunyi, Fangshan, and Mentougou have higher bike recovery rates. Given a very small number of bicycles that need to be rebalanced, the current rebalancing in these districts allows the bike quantity at each node to return to its initial level nearly. After optimization, the nodes in Fangshan, Shunyi, and Mentougou all reach their target number of bicycles. By contrast, due to an excessive number of nodes and an extremely unbalanced demand, the number of bikes that need to be rebalanced in Chaoyang, Fengtai, and Haidian is much higher than that in the other districts, especially in Chaoyang. At the end of a day on weekdays, the number of bikes that need to be rebalanced in Chaoyang exceeds 4000. These challenges reduce the bike recovery degree at each node after the rebalancing, and the deviation between the number of bikes at a node and the target number of the node is significantly reduced after optimization. Table 11 shows the cost of CO 2 emissions and the losses due to failure to meet the demand for the next day (i.e., the economic cost) within the rebalancing before and after optimization. The optimization reduces 62.6% of the total economic cost. Despite the excessive use of bikes, especially in 2017, the demand for the next day can still be satisfied even if the number of bikes at the parking nodes after rebalancing does not meet the target. However, summing up the economic costs remains reasonable to unify the two goals of reducing CO 2 emissions and limiting the deviation in the number of bikes at each parking node. For an excessive BSS, an economic cost as penalty is incurred if the number of bikes at each node after rebalancing differs from the target. Meanwhile, for an appropriately launched BSS, an economic cost as losses is incurred if the order demand for the next day is not met. Given the huge difference between carbon price and amount charged for riding a shared bike (0.051 yuan/kg and 1 yuan/order as of 2017, respectively), the economic cost for BSS is largely determined by the deviation between the number of bikes in a parking node and the target number of the node. This cost is also affected by the judgment of decision makers regarding the economic and environmental benefits of bike sharing orders. The cost of CO 2 emissions and the economic cost caused by unmet bike demand in parking nodes are assigned the same weight of 1 in this paper, which will not be further discussed.

By analyzing the temporal and spatial characteristics of the Mobike BSS in Beijing, China, this paper formulates a partition strategy based on the supply and demand relationship. To solve existing rebalancing models in which large-scale BRP are difficult to be applied, this strategy avoids the cumbersome task of deciding the number of bikes being loaded or unloaded at parking nodes. We then improved existing rebalancing models, and the objective function is the cost of CO 2 emission and the economic cost caused by unmet bike demand in parking nodes during the rebalancing. Data from the dockless Mobike BSS in Beijing are used to generate findings that can help city managers or decision makers promote the green development of BSS.

First, the efficiency of vehicle in the current rebalancing of BSS in Beijing is low. Part of the reason is that the current vehicles still visit balanced parking nodes, and the other part is related to the high repetitions of the current vehicle's travel routes and the excessive load of vehicles. After optimization, the driving route and CO 2 emissions of vehicles could be reduced by 51.2% and 57.5%, respectively. Meanwhile, the number of bikes being deployed in some districts, such as Shijingshan and Mentougou, is too low. Second, time, geographical location, and regional area are identified as the main factors that affect the total CO 2 emissions in each district. In terms of time, due to the difference between shared bike travel demand on weekdays and weekends, there is a large gap in the number of bikes that need to be rebalanced in parking nodes during the week. In terms of space, geographical location of a district determines whether it is the main place of BSS's deployment and service, which will affect the complexity of vehicle routes during rebalancing. Regional area affects the vehicle driving distance. Third, in addition to driving distance, vehicle load has an important impact on CO 2 emissions, especially in districts with limited space for route optimization. Finally, Beijing has an excessive number of BSSs, hence allowing the city to meet user demand despite a low degree of rebalancing (less than 70%). The optimization increases the met bicycle demand of parking nodes by more than 80%. Enterprises can benefit from the findings of this study in reducing the scale of BSS and in meeting next-day demand through optimized rebalancing. In sum, although BSS can reduce CO 2 emissions, its operations need to be optimized to achieve this benefit. The current rebalancing also shows a large space for optimization. While each decision maker assigns different weights to the environmental costs incurred from CO 2 emissions and the economic costs incurred from unmet bikes demand at parking nodes, this problem is not the focus of this paper and is therefore not discussed in detail. 

A deep learning approach on short-term spatiotemporal distribution forecasting of dockless bike-sharing system

Balancing the stations of a self service "Bike hire" system

The static bike relocation problem with multiple vehicles and visits

Bike sharing systems: Solving the static rebalancing problem

The impact of technologyenvironmental innovation on CO 2 emissions in China's transportation sector. Environmental Science and Pollution Research International

Life cycle carbon dioxide emissions of bike sharing in China: Production, operation, and recycling. Resources, Conservation and Recycling

Geo-spatial analysis of the Seoul subway station areas using the Haversine distance and the azimuth angle formulas

Balancing a dynamic public bike-sharing system

A heuristic algorithm for a single vehicle static bike sharing rebalancing problem

The bike-sharing world -Fourth week of

The static bicycle relocation problem with demand intervals

Bike share: A synthesis of the literature

Bike share's impact on car use: Evidence from the United States, Great Britain, and Australia

A 3-step math heuristic for the static repositioning problem in bike-sharing systems

Putting the sharing economy into perspective

Global carbon budget 2020

Solving a static repositioning problem in bike-sharing systems using iterated tabu search

Green routing for trucking systems with classification of path types

A sustainability-oriented optimal allocation strategy of sharing bicycles: Evidence from ofo usage in Shanghai. Resources, Conservation and Recycling

Dynamic repositioning strategy in a bike-sharing system: How to prioritize and how to rebalance a bike station

A genetic algorithm for solving bike sharing rebalancing problem

A static free-floating bike repositioning problem with multiple heterogeneous vehicles, multiple depots, and multiple visits

Research on bike sharing rebalancing problem based on double-layer tabu search algorithm. Computer Integrated Manufacturing Systems, in press, available at: kns.cnki.net/kcms/detail/11

Optimizing bike sharing systems from the life cycle greenhouse gas emissions perspective

Balancing bicycle sharing systems: A variable neighborhood search approach

Static repositioning in a bikesharing system: Models and solution approaches

Bike sharing: A review of evidence on impacts and processes of implementation and operation

Influence of topology and payload on CO 2 optimised vehicle routing

Bikecsharing in Europe, the Americas, and Asia: Past, present, and future

Dynamic green bike repositioning problem: A hybrid rolling horizon artificial bee colony algorithm approach

The market share of Mobike is approaching 60%

Chemical reaction optimization for solving a static bike repositioning problem

The bike-share oversupply in China: Huge piles of abandoned and broken bicycles

The selective pickup and delivery problem: Formulation and a memetic algorithm

Static green repositioning in bike sharing systems with broken bikes

China's cement demand and CO 2 emissions toward 2030: From the perspective of socioeconomic, technology and population. Environmental Science and Pollution Research International

Bicycle Sharing System: Role, Effects and Application to Plymouth. Dissertation for the Master Degree

Environmental benefits of bike sharing: A big data-based analysis

New Institutional Economics Analysis of Urban Public Bicycle System. Dissertation for the Master Degree