# Decision System Based on Markov Chains for Sizing the Rebalancing Fleet of Bike Sharing Stations
## 3 Methodology  
### Problem Description  
A BSS consists of bike stations equipped with docks where bikes are stored. Clients take bikes for their travel and then return them to another bike station at a dock. To ensure bike availability, trucks are used to rebalance the stations by moving bikes between them. The modeling which encompasses these activities is illustrated in Figure 1:  
State \(\text{BS}_{i}\) signifies that the bike is inside a bike station, and that it is only connected to itself, to state \(\text{Ri}_{i}\) or to state \(\text{Re}_{i}\) (black solid connections). State \(\text{Ri}_{i}\) indicates that the bike is involved in a ride performed by the client, and that it is connected to itself and to every single state BS (red dashed connections). State \(\text{Re}_{i}\) represents that the bike is transported by a vehicle that performs rebalancing, and that it is connected to itself and to every single state BS (green dashed connections), except the corresponding state \(\text{BS}_{i}\). This exception is due to the uselessness of rebalancing, in which the bike is taken from a bike station only to be reintroduced into the same bike station. Every client docks/undocks a bike required for travel from a set of bike stations \(A=\{B_{1},B_{2},\ldots,B_{M}\}\) from the BSS. A load value, defined as the ratio between the number of bikes available (\(k\)) and its capacity (\(C\)--number of parking lots), is assigned to each bike station \(B\), expressed as follows:  
\[\text{load}=L(B)=\frac{k}{C} \tag{1}\]  
Obviously, \(0\leq k\leq C\implies 0<L(B)<1\). A bike station state \(\xi(B)\) is considered \"critical\" when its load is close to either 0 or 1, and it is considered \"highly dynamic\" when \"critical\" state is reached with a frequency much higher than the average. These two properties are formulated in Equations (2) and (3), respectively:  
\[\xi(B)\text{ is CRITICAL }\iff L(B)\to 0\text{ }\text{ OR }L(B)\to 1, \tag{2}\]  
\[B\text{ is HIGHLY DYNAMIC }\iff f(B)\gg\overline{f}, \tag{3}\]  
where \(f(B)\) is the frequency of \(B\) reaching critical state and \(\overline{f}\) is the average frequency of reaching critical state throughout the bike stations set \(A\). Highly dynamic bike stations are those that most require the rebalancing operation and, thus, they are the main contributors to the rebalancing strategy (e.g., designing of the rebalancing fleet). So, they can be isolated from the set, in the form of subset \(\hat{A}\), presented below:  
\[\hat{A}\subset A;A=\{B\in A|B\text{ is HIGHLY DYNAMIC}\} \tag{4}\]  
In the case of BSSs characterized by high dimensions (like Citi Bike, in our case), a rebalancing strategy optimization for the whole BSS is impractical and cluster-based strategies are preferred instead [49; 50; 51; 52]. According to [49], it has been shown that the geographic location is not sufficient, the usage pattern being also required, in order to obtain an effective clustering method. If we select a cluster \(\tilde{A}\subset\tilde{A}\), which is a BSS subsystem (referred to as \"subsystem\" from now on), the proposed problem to be resolved is the developing of a model, in order to predict the behavior of \(\tilde{A}\). The data used for identification and validation purposes were collected from the Citi Bike system consisting of several months' time intervals. An abstract grid of bike stations comprising the whole system and the clustering is shown in Figure 2, where black squares correspond to highly dynamic bike stations, and the others are illustrated by gray squares. As can be seen in Figure 2, four entities are specified:  
* Bike stations--the elements for each of the sets below;
* BSS (\(A\))--the set that contains all bike stations;
* Special subset (\(\hat{A}\))-- the set that contains only the highly dynamic bike stations;
* Subsystem (\(\tilde{A}\))--a region of the special subset, manageable for the rebalancing operations. Figure 1: Graph modeling the bike transfer of a BSS.