# Smart Recommendations for Renting Bikes in Bike-Sharing Systems
## 4 User-Centred Station Recommendation
### Expected Cost
#### 4.3.2 Probability Calculation  
Using queueing theory, a station for renting bikes can be modelled as an M/M/1/K queue (see, e.g., [21; 31; 35]. We consider that bikes arrive at a station and request the \"service\" to be rented. The arrival process (e.g., the return of bikes through users) and the \"service\" process (e.g., the rental of bikes by users) follow a Poisson distribution. The number of service channels is 1 and the maximum number of bikes waiting to be rented is K (the capacity of the station). The M/M/1/K queue is a special case of a birth-death process and of continuous-time Markov chains with K+1 states. Let \(\lambda\) be the average bike arrival rate and \(\mu\) the average bike rental rate; given a station \(s_{i}\), let \(\pi^{i}(\text{t})\) denote the (transient) state probability distribution and \(\pi^{i}_{j}(t)\) the probability that the system is in state \(j\) at time \(t\)--that is, \(\pi^{i}_{j}(t)\) represents the probability that there are \(j\) available bikes at station \(s_{i}\) at time \(t\). The time-dependent behaviour of the probability distribution can be determined by the system of differential equations (known as the forward Kolmogorov equations):  
\[\frac{d\pi^{i}_{0}(t)}{dt}=-\lambda\ \pi^{i}_{0}(t)\ +\ \mu\ \pi^{i}_{1}(t) \tag{13}\]  
\[\frac{d\pi^{i}_{j}(t)}{dt}=\lambda\ \pi^{i}_{j-1}(t)\ +\ \mu\ \pi^{i}_{j+1}(t)\ -\ ( \lambda+\mu)\pi^{i}_{j}(t),\text{for}\ 0<j<K \tag{14}\]  
\[\frac{d\pi^{i}_{K}(t)}{dt}=\lambda\ \pi^{i}_{K-1}(t)\ -\ \mu\ \pi^{i}_{K}(t) \tag{15}\]  
Given an initial distribution \(\pi^{i}(0)\) with \(\sum\limits_{j=0}^{K}\pi^{i}_{j}(\,0)=1\), the system can be solved, obtaining the distribution \(\pi^{i}(t)\) at time \(t\). Solving Equation (1) is mathematically complex, but an acceptable approximation can be found. In particular, in our experimental implementation, we use the fourth-order Runge-Kutta method for iteratively approximating solutions of differential equations (given an initial problem defined by \(\frac{dy}{dt}=f(t,y)\), and \(y(t_{0})\ =y_{0}\), solutions for \(y(t_{0}+\Delta t)\) are approximated by iteratively calculating \(y(t_{i}+h)\) based on \(y(t_{i})\) and \(t_{i}\). Taking small steps \(h<\Delta t\), this process is repeated for \(i\) steps, until \(t_{i}+h\) is approximately \(t_{0}+\Delta t\). In this case, \(y(t_{i}+h)\) approximates \(y(t_{0}+\Delta t)\)). Let \(rent_{k}=(l_{k},t,md)\) be a user rental request, \(s_{i}\) a potential station, and \(t_{exp}=t+wtime(l_{k},l(s_{i}))\) the expected arrival time of user \(u_{k}\) at station \(s_{i}\). Then, Equations (13)-(15) can be used to calculate the probability that \(u_{k}\) would find an available bike (or slot) at station \(s_{i}\) when they arrive at time \(t_{exp}\). These probabilities are denoted as \(bikeProb(s_{i},\ rent_{k})\) and \(slotProb(s_{i},\ return_{k})\), respectively. We define \(\pi^{i}(0)\), the current probability distribution of (available) bikes locked at station \(s_{i}\) and the current time \(t\), by:  
\[\pi^{i}_{j}(0)\ =\ \left\{ \begin{array}{c}1,\ if\ j=bikes(s_{i},t)\ +\ changes\big{(}s_{i},t,t_{exp}\big{)}\\ 0,\ otherwise\end{array} \right. \tag{16}\]  
Note that, similarly to the _DistanceExpectedResources_ strategy defined before, we include changes in the number of available bikes at the station that are expected to take placebetween \(t\) and \(t_{exp}\). In particular, we approach such changes as if they had already been \"blocked\" at the moment of the user request (\(t\)).