Smart balancing of E-scooter sharing systems via deep reinforcement learning: a preliminary study

2.1 Works motivating our study

The raising interest in the adoption of vehicle sharing systems is witnessed, besides by documents and reports by national and international agencies like those mentioned in the Introduction, by many recent scientific papers.

In 2020 Aguilera-Garcí a et al. [1] collected data from Spanish cities through an online survey in order to identify the drivers for adoption and frequency of use of moped scooter-sharing services in urban areas. Among their conclusions, we mention that age in the range 26-34 and university level education play a key role in determining a positive attitude towards this mobility approach.

The analysis by Eccarius and Lu [10] is instead targeted towards university students: survey responses from 471 university students in Taiwan were collected, and their analysis showed that lack of perceived compatibility with personal values, mobility needs and life-style particularly drives students with low usage intention, while awareness-knowledge about the sharing system and environmental values influence the formation of usage intention in indirect ways.

Comparisons of the performance of bike and scooter sharing have been carried out on data from the Tri-City metropolitan area in northern Poland [3] and from Singapore [27]. The first study concluded that e-scooters are more often used for leisure rides, while e-bicycles are mainly used as first and last mile transport and to commute directly to various places of interest; respondents that adopted shared micromobility are generally young, and e-scooter users are on average younger than e-bike users. The second study confirms the high maintenance cost for rebalancing and charging e-scooter fleets, which is the motivation for our work.

2.2 Works on rebalancing strategies

The recent work by Wen et al. [26] provides a comprehensive overview of the rebalancing strategies used to alleviate the imbalance problem in bike sharing systems. Such strategies have been classified according to two main categories: truck-based rebalancing and customer-oriented rebalancing. Truck-based rebalancing refers to the relocation operations mentioned in Section 1. A specialized group of workers is in charge of moving vehicles from one zone to another by means of trucks. On the other hand, customer-oriented rebalancing is the process of encouraging users to adopt efficient behaviours by providing incentives. The latter category is the main topic of our investigation.

Most past works on rebalancing strategies are not targeted towards “free floating” systems. Regue and Recker [23] addressed the dynamic bike sharing repositioning problem with demand prediction; although their proposal is consistent with an agent-oriented view, being proactive as demands are anticipated, and being self-adaptive as more precise predictions can be made as new data are available, repositioning takes place in existing stations, and hence the problem they address is different from ours. Junming et al. [18] developed a Meteorology Similarity Weighted K-Nearest-Neighbor regressor to predict the station pick-up demand based on large-scale historic trip records and proposed an inter-station bike transition model to predict the station drop-off demand. Incentive proposals mechanisms are also taken under consideration in papers investigating the role of stations in customer-oriented rebalancing [11, 26].

In our work, both truck-based and customer-oriented strategies have been taken into account: truck-based rebalancing is implemented through the simulator, whereas customer-oriented rebalancing is implemented through the Reinforcement Learning system. Few other works employ deep RL to investigate user incentives in bike sharing systems, including those by Duan and Wu [9] and by Pan et al. [21]. However, their objective is to determine an optimal pricing mechanism, whereas the objective of our work is to determine convenient pick-up/drop-off zones for each booking request.

In particular, Duan and Wu [9] consider rebalancing the dockless bike sharing system by providing users with monetary incentives with the long-term goal of maximizing the number of satisfied users who successfully complete their rides over a period of time. The locations of sources and destinations are extracted from a selected dataset named Mobike containing more than 100k trip records of Shanghai, and the experiment results are promising. W.r.t. our work, Duan and Wu’s simulator is driven by less parameters and the model of the domain is less precise: neither battery swap costs (in terms of needed workers and employed time), neither relocation cost (again, in terms of workers and time needed to relocate vehicles) seem to be taken into account. The same Mobike dataset was used by Pan et al. [21] for developing their Hierarchical Reinforcement Pricing, building upon the Deep Deterministic Policy Gradient algorithm. Their pricing algorithm captures both spatial and temporal dependencies using a divide-and-conquer and outperforms state-of-the-art methods in both service level and bike distribution.

The motivation behind the use of deep Reinforcement Learning for our task is mainly related to the possibility of combining many interesting aspects at once. The deep RL system can indeed incorporate demand forecasting models as a baseline to drive agents’ behaviours and, at the same time, can learn efficient suggestions based on past experience and adapt to real-time demand and availability of the system. In this way, the decision process behind the offered suggestions can capture complex information about the dynamics of the mobility system. Furthermore, by formulating the problem as a game, several constraints may be introduced to enforce specific objectives in the mobility system (e.g., a target service availability).

Compared to previous works, the innovative contribution of our paper is thus twofold. On one side, few works address the imbalance problem inside “free-floating” e-scooter mobility systems. Most rebalancing strategies proposed so far in the literature have been adapted from station-based sharing systems. On the other side, a deep RL multi-agent system in charge of suggesting pick-up/drop-off zones constitutes an original solution which does not build on any existing work. The work that mainly influenced our proposal is the one by Ciociola et al. [7], in which the ODySSEUS simulator has been introduced (Section 4) — an essential component of the ESB-DQN system.

Ciociola et al. created a flexible, data-driven demand model by using modulated Poisson processes for temporal estimation, and Kernel Density Estimation for spatial estimation. The demand model was used in conjunction with a configurable e-scooter sharing simulator to compare performance of different electric scooter sharing design options, such as the impact of the number of scooters and the cost of managing their charging. Experiments were carried out on open data about e-scooter sharing rides in Minneapolis and Louisville.

Table 1 summarizes the main features of both the systems discussed in this subsection and ESB-DQN.

Other works that are related with ours albeit focusing on different issues, include the study by Carrese et al. [5] who observe that leaving electric vehicles in the wrong position not only interferes with pedestrians and other vehicles, but also reduces urban decorum. They suggest introducing “beautificators”, namely employees that fix inappropriate and disordered parking made by users, by moving vehicles close to the place where they had been left, but in safer, and more acceptable from the urban decorum point of view, place. The repositioning that they propose is different by traditional relocation made to rebalance fleets; their approach could be merged with ours, by recognizing more incentives to users who park their vehicles in the right zone, and also in the right way.

In a paper published in 2021, He and Shin [13] analyze e-scooter distribution features and flow dynamics for the data-driven designs, and propose a novel spatio-temporal graph capsule neural network to predict future dockless e-scooter flows given the reconfigured regions. They the data from the Louisville database of trips that we also employed (see Section 3), plus data from other cities in the US. Although by predicting e-scooter distribution one might also devise strategies for rebalancing, He and Shin do not address rebalancing as their main goal. Also, by exploiting neural networks, they use a different learning approach.

A visionary development of fleet rebalancing involves self-repositioning shared personal mobility devices [17], namely small electric vehicles that can move autonomously at slow speed to reposition themselves, but require to be driven by their user during trips. While the adoption of such self-repositioning devices would boost the efficiency of fleet operations, there are many obstacles to their application ranging from engineering challenges such as self-stabilization of two-wheels vehicles [12] to infrastructural requirements, to regulatory issues involving self-driving electric vehicles.

5.1 Environment

The environment wraps the modified simulator described in Section 4 to make it compliant with DeepMind’s DQN Zoo library for Reinforcement Learning [8]. The major change we have made to the ODySSEUS simulator is conceptual: rather than simulating the whole cascade of trip requests between two time intervals of start and finish, t₀ and t _N , collecting a certain number of statistics about the run afterwards, as the original in [7] does, our simulator moves step by step across the states of the Louisville environment. The state, X _t , is observed as soon as an environment-changing event fires, i.e., a trip request is scheduled; such observation is available to P and D, which will consequently pick an action, a _t . The simulator will then move forward of one step into the state X_t+1 by applying such action. Formally, it is a fully observable environment which produces a n × 3 state vector X _t at every trip request i at time t: X t n × 3 = [ A ( n × 1 ) B ( n × 1 ) C ( n × 1 ) ] = [ a 1 b 1 0 a 2 b 2 0 ⋮ ⋮ ⋮ a p b p 1 ⋮ ⋮ ⋮ a d b d 1 ⋮ ⋮ ⋮ a n b n 0 ](1) with n = | Z | the total number of zones, A the n × 1 column vector with the number of available vehicles per zone z at time t, B the n × 1 column vector with the deficit Δ (t, z) per zone z with respect to the expected optimal baseline at time t, introduced in Section 4, and C is a binary n × 1 column vector with 1s in correspondence of p (i) and d (i) only, indicating if a certain zone is the start or the end zone of the trip (the position corresponding to some zone z contains 1 in vector C if z = = p (i) or z = = d (i)).

Vectors A and B are standardized via z-normalization to achieve a mean of 0 and a standard deviation of 1. C plays the role of a de-facto attention mechanism within the state X _t itself. Indeed, it signals which zones of the operative area may be subject to alterations in the near future leading towards the state transition X _t to X_t+1, which may reflect in how knowledgeable the alternative proposals are.

In our initial design of the system, we planned the ESB-DQN environment to emit a fourth column vector, D, with the number of dead vehicles per zone z at time t. Indeed, we believed that D could enhance the agents’ understanding of the need of re-balancing of z, whereas A and B alone would already take care of the trend of usage of z. Eventually, since this information is highly negatively correlated with A, we opted to leave it out.

Despite a detailed action space definition follows in the next paragraph, it is important to note that the ESB-DQN environment belongs to the family of constrained environments, i.e., the setting of our problem falls within constrained deep Reinforcement Learning [25], namely the integration of constraint models and RL techniques, such that the RL agent, also the learner, is guided by an encapsulating constraint model that describes safety constraints for the agent’s task. There are a number of ways to approach constraint-guided interactions to lead RL agents towards safe behaviour in their exploration. For example, an exploration pattern often persevered is to pretend those unsafe actions do not exist altogether, by strictly avoiding them from the range of actions the agents can pick. Or again, a terminal state may be invoked each time an invalid action is taken, and a new episode started over hoping for better fortune. Here instead, we focus on the third popular paradigm of constrained RL, that is, to let the invalid action pass through, but awarding the agent committing it a strongly penalized reward. Indeed, Spieker [25] shows that this approach is actually the most beneficial under most constrained RL settings to augment the interaction capabilities of the agents with the surrounding environment, while not altering nor interrupting too abruptly their perception of it. The only limitation of this approach is that the harshly penalized reward should be ensured to be at least an order of magnitude smaller than the lowest possible reward achievable as a result of a valid action. Our approach is similar to the one by Spieker, as we define a fall-back action, or NOP, that the agents can fall back to whenever they pick an invalid action, getting severely penalized as a result, to prompt the continuity of the simulation. In our setting, invalid actions for the agents include proposing zones that are not valid in the operational area, proposing a drop-off zone that is identical to the pick-up one or vice-versa, suggesting a pick-up zone where no suitable vehicles are available. In Section 5.4 we further explore this continuity while training the ESB-DQN system, by introducing the concept of lives, borrowed from Atari games [20].

The agents are Deep-Q-Networks (DQN) implementing an ɛ-greedy policy with experience replay [20] belonging to the family of Q-learning. It is an off-policy approach towards deep RL wherein the agent estimates the expected reward for future actions from a given state without following an actual greedy policy, but instead relying on a behaviour policy enriched from direct experience with the environment to update the online policy, by satisfying Bellman’s optimality equation. Such an approach is better suited for large state spaces, S , against rather limited action spaces, A , which we will see to be our case. In fact, they are Rainbow agents [14], a state-of-the-art DQN agents, which we have found beneficial for the three following main features: double Q-learning helps in preventing overestimation of the action values which may lead to very unpleasant proposals; distributional Q-learning helps in investigating the importance of the value distribution, which we find necessary to achieve long-term balance of the ESB-DQN system; prioritized experience replay helps in selecting the subset of previously experienced observations that are the most relevant, which we find necessary to characterize the complexity of the dynamics behind a free-floating sharing system.

Both the pick-up agent P and the drop-off agent D comprise a funnel-like three-layer fully connected network with ReLU activation functions, whose role is to flatten the input and extract a latent representation as a single vector of 256 units. The input of the network is the last observed environment state, X _t , whereas the output feeds the standard Rainbow network that produces a distribution of logits, whose maximum value identifies the action picked by each agent, a_P,t and a_D,t, respectively. The action space is limited to 9 different choices, corresponding to the 8 cardinal directions mapping the 8 adjacent zones (i.e., 1-hop neighbourhood) plus the calling zone, p (i) or d (i) respectively, which function as the NOP actions.

Following this formulation of the action space, and recalling Fig. 2, it becomes clear why the ESB-DQN environment is constrained by a large set of invalid actions. In fact, in the early stages of the RL agents life-cycle, the expectation of picking an invalid action from any given zone z at any given time t far exceeds its complementary (for example, many zones that the agent may select are not inside the e-scooter operational boundaries in the Louisville city, a pick-up zone may be identical to the drop-off one), which is further evidence of the need for outer aid for the RL agents to well characterize the dynamics of the system.

5.3 Reward

The rationale behind our reward function is the following, with Δ being the expected deficit of e-scooters in the zone and time under consideration:

Pick-up case with Δ < 0. If the agent confirms the pick-up when there is an expected surplus of vehicles, then the reward is positive. As delta decreases the reward increases because the surplus condition of the zone is improved. Similarly, if the number of available vehicles is high, then the rebalancing for that area is encouraged. As the demand increases, the reward decreases because this may negatively affect the long-term balance of the zone.

The following functions are defined to compute the reward:

(2)     ω (z, t) = Δ ( z , t ) exp [ - ( 1 d ( z , t ) + N A ( z , t ) + ) sign ( Δ ( z , t ) ) ]

(3)      ψ (z, t) = N D ( z , t ) exp ( - 1 d ( z , t ) + N A ( z , t ) )

where:

Δ (z, t): expected deficit of e-scooters at zone z at time t;

Drop-off agent. Let d ˆ ( i ) be the chosen alternative drop-off zone for trip i at time t, N d ˆ ( i ) be the set of valid neighbours around d ˆ ( i ) . If the state of charge of the vehicle s at the end of the trip is greater than the battery swap threshold, i.e. b (s) - e _i  ≥ αC, then the reward corresponding to each of the alternative zones z ∈ N d ˆ ( i ) is:

R D ( z , t ) = { ω ( z , t ) if d ˆ ( i ) = z - ω ( z , t ) otherwise

Otherwise:

R D ( z , t ) = { ψ ( z , t ) if d ˆ ( i ) = z - ψ ( z , t ) otherwise

The overall reward for the choice d ˆ ( i ) is:

R ¯ D ( d ˆ ( i ) , t ) = { 1 | N d ˆ ( i ) | ∑ z ∈ N d ˆ ( i ) R D ( z , t ) if drop - off action is valid - γ D max z ∈ N d ˆ ( i ) | R D ( z , t ) | otherwise

with γ _D being a constant which modulates the penalty of an invalid drop-off action.

Pick-up agent. Let p ˆ ( i ) be the chosen alternative pick-up zone for trip i at time t, N p ˆ ( i ) be the set of valid neighbours around p ˆ ( i ) . The reward corresponding to each of the zones z ∈ N p ˆ ( i ) is:

R P ( z , t ) = { - ω ( z , t ) if p ˆ ( i ) = z ω ( z , t ) otherwise

The overall reward for the choice p ˆ ( i ) is: R ¯ P ( p ˆ ( i ) , t ) = { 1 | N p ˆ ( i ) | ∑ z ∈ N p ˆ ( i ) R P ( z , t ) if pick - up action is valid - γ P max z ∈ N p ˆ ( i ) | R P ( z , t ) | otherwise with γ _P being a constant which modulates the penalty of an invalid pick-up action. Figure 3 shows some examples of the reward function R _P for different values of the parameters Δ, d.

OPEN IN VIEWER

Fig. 3

Pick-up action: some examples of the reward function R _P for different values of the parameters Δ, d. (Upper row) Negative reward: the agent suggests to pick-up a vehicle from a zone having an expected deficit of vehicles (Δ > 0). As Δ and d increase, the reward is smaller because the expected deficit condition will be worsened. In both cases, the larger the number of available vehicles the higher the curve, as the deficit condition will be alleviated. (Bottom row) Positive reward: the agent suggests to pick-up a vehicle from a zone having an expected surplus of vehicles (Δ < 0). The larger Δ the larger the reward, reflecting how problematic the surplus being improved. Similarly, when the number of available vehicles is high, the rebalancing effect is considered more valuable. As the demand d increases, the reward decreases because the pick-up may negatively affect the long-term balance of the zone.

As we have anticipated in Section 5, a major role during the training of the ESB-DQN system has been played by the parameter regarding the number of lives, k. The continuity of the simulation is a key factor for the eventual learning of the RL agents, as interrupting the simulation to just start it over too often, as soon as an invalid action happens, would slow down the convergence by a considerable margin, given how full of potential invalid actions ESB-DQN environment is.

To overcome this limitation, we have borrowed the concept of lives from Atari: every time one of the two agents or both commit an invalid action, the whole environment loses a life.

By doing so, an invalid action does not immediately lead to a terminal state, but takes it closer to the ESB-DQN state. On life loss, the discount for the timestep t is zeroed, cancelling any connection between the previous and later events, and the agents are set to perform a NOP.

Let a _t  = (a_t,P, a_t,D) be the generic action for the simulator taken at time t, defined as the resulting combination of the action picked by the pick-up (P) agent, a_P,t, and the action picked by the drop-off (D) agent, a_D,t. The set of invalid actions has been set as follows:

either zone corresponding to a_P,t or a_D,t is invalid: z_P,t ∉ Z ∪ z_D,t ∉ Z, with Z the set of valid zones of the city of Louisville;

As soon as k reaches 0, then the simulation is stopped. Indeed, we would not want our RL agents to learn the dynamics of the environment while committing thousands of errors.

It is important to note that by implying the concept of lives, the training framework of RL agents has turned into a sort of collaborative RL framework, wherein both P and D cannot rely solely on their capabilities to reach the goal, but even on the other’s to reach a common goal: if D was to lose a life, P would lose it as well, and vice-versa.

6.1 Parameters of the simulator

The parameters of the simulator have been set as follows:

the number of available e-scooters is | S | = 400 (almost half of the Louisville fleet, that amounts to 850 vehicles, scaled down having a medium size city like Genova in mind);

The fleet size | S | and the user willingness w immediately stand out from the lot of parameters. The former has been set to half the nominal fleet size granted by the city of Louisville. Indeed, as further experiments on cities with more complex dynamics have not been conducted for the time being, we have decided to restrict Louisville to a worst case scenario, as the satisfied demands would remain strong nonetheless (88%). The latter has been set to 1 for measuring the advantage of an incentives mechanism, as in the training phase we wanted to let both RL agents experience as much of the environment as possible, regardless of whether they would be actually asked to do so. Baseline results have been obtained by setting willingness to 0.

6.2 Parameters of the reinforcement learning system

The parameters of the Reinforcement Learning system have been set as follows:

the optimizer is Adam [16] with a learning rate of 6.25 × 10^-5;

Moreover, concerning the reward function, the future demand is computed in a time interval Δt = 1h, whereas the constants modulating the penalties are γ _D  = γ _P  = 2. Also, every 3 iterations a checkpoint has been stored locally for evaluation purposes.

6.3 Results of the experiments

In the first experiment, the model has been trained from scratch with the number of battery swap workers being n_swap = 12 and the number of relocation workers being n_rel = 6. Other two experiments have been performed, by drastically reducing the number of workers and applying transfer learning from the pre-trained P and D agents. In particular, in the second experiment we have fixed n_swap = 6, n_rel = 3 and in the third experiment n_swap = n_rel = 1.

The final results in validation are shown in Table 4. The evolution of the satisfied demand during the learning procedure is represented in Fig. 4.

OPEN IN VIEWER

Fig. 4

Evaluation of the satisfied demand during the learning procedure for training and validation agents versus a baseline model with no incentive policy (user willingness w = 0). The value of the parameters is shown in the titles. (a) Model trained from scratch, (b), (c) Transfer learning.

Our ratio between validation and training trips is 1 : 2: for example, if a training episode would experience 1000 trips, a validation episode would experience only half of those. A single iteration took over 1 hour on a PC equipped with a GeForce GTX 1650 Ti GPU with 4GB of memory along with an Intel i7-10750H CPU with 32GB of RAM. Both CPU and GPU specs are crucial, as the SimPy processes undergoing the simulation run solely on CPU, whereas the forward and backward pass of the RL agents’ networks happen on GPU.

As shown in Fig. 4(a), the two agents trained from scratch cause a decrease in the satisfied demand during the first iterations, due to their random behaviour with no previous experience. After around 25 iterations their policies have been efficiently updated. The level of satisfied demand has improved with respect to the baseline - referred to a standard mobility service with no user incentives. More interestingly, by reducing the number of workers and applying transfer learning, it is possible to observe again a beneficial effect over the satisfied demand. In particular, Fig. 4(c) shows that in the critical scenario with n_swap = n_rel = 1 the satisfied demand is constantly larger with respect to the baseline. This means that by following the proposal of alternative pick-up and drop-off zones, users are actively participating in the system rebalancing and contributing to a positive increase of the satisfied demands.