Optimizing the Battery-Swapping Problem in Urban E-Bike Systems with Reinforcement Learning

1 Introduction

E-bikes (EBs) have become the primary mode of transportation for many urban residents due to their affordability and ability to navigate through traffic with ease, significantly impacting service delivery platforms where most couriers rely on EBs. In China, the number of delivery platform-based workers reached 84 million by 2020 [Julie Yujie Chen, Ping Sun2023], with steady growth driven by market expansion. Similarly, in India and South America, the number of couriers exceeds 500,000 [Ezra Fieser2019,Rica Bhattacharyya2022]. Couriers typically earn a base hourly wage supplemented by delivery commissions, making it crucial to optimize EB transportation systems to maximize the number of deliveries within a given time frame. However, underdeveloped EB transportation systems often cause range anxiety [Li et al.2024a], which they cannot travel the desired distance due to limited battery capacity.

To address this, battery-swapping stations have been introduced, enabling couriers to exchange depleted batteries for fully charged ones, reducing downtime and improving operational efficiency. With the rapid expansion of the EB demand, managing the imbalance between supply and demand (SnD) at battery-swapping stations has become increasingly complex. As depicted in Figure 1, SnD imbalances can prevent couriers from accessing fully charged batteries at their initial stations, forcing them to travel to alternative locations at a greater distance. This inefficiency not only delays deliveries but also diminishes overall couriers and other EB rider satisfaction of battery needs. The Battery-Swapping Problem (BSP) has thus become a critical challenge in urban transportation, and finding efficient solutions is vital for ensuring fast, cost-effective, and reliable EB transportation. By providing higher earning potential for couriers, as their productivity and route efficiency improve, the BSP further offers significant societal benefits aligned with the United Nations' Sustainable Development Goal 8: Promote sustained, inclusive, and sustainable economic growth, full and productive employment, and decent work for all [United Nations2015].

In the context of urban transportation, the BSP for EBs presents unique challenges that differentiate it from EVs [Sun et al.2019,Mao et al.2024]. One key issue is the dense distribution of EB battery stations, coupled with the need for rapid, localized battery replacements to support the swift operations of couriers. Additionally, the variation in courier behavior and the operational constraints within the battery station networks introduce a high degree of nonlinearity and unpredictability to the SnD dynamics, , which traditional models struggle to capture. Proximal Policy Optimization (PPO) [Schulman et al.2017], the on-policy state-of-the-art reinforcement learning algorithm, seeks to mitigate these issues by constraining policy updates to prevent destabilizing changes. However, its reliance on the clipped surrogate and Kullback-Leibler (KL) divergence is limited in real-time, location-based environments, failing to fully capture the true nature of policy changes and leading to suboptimal performance. This creates a critical need for more advanced approaches that can better model the dynamics of BSP for EBs.

To tackle these challenges, we formulate the BSP as a Markov Decision Process (MDP) and introduce a new onpolicy RL algorithm enhanced by the Wasserstein distance, noting that the problem exhibits Markovian characteristics, where the information received on a given day is primarily influenced by the immediate previous day and a limited set of today's user behaviors, without being influenced by prior days. This algorithm is specifically designed to optimize the battery-swapping process across stations, aiming to maximize battery utilization, improve rider satisfaction, and increase the overall robustness of the BSP system. Grounded in real-world datasets, the algorithm incorporates a carefully designed RL environment to ensure the robust performance guaranteed in highly dynamic environments. Unlike the traditional PPO methods that minimize divergence between old and updated policies, our Wasserstein-enhanced Proximal Policy Optimization (W-PPO) algorithm calculates the actual differences between policies, leveraging real-world simulations for improved precision. This end-to-end solution integrates Wasserstein-improved penalty calculations, delivering high capability and efficiency. To assess the effectiveness of the algorithm, we introduce two key performance metrics: the Shared Battery Utilization Ratio (SBUR) and the Battery Supply Ratio (BSR). The SBUR quantifies the proportion of riders receiving fully charged batteries relative to the total number of batteries at a station, while the BSR assesses the increase in battery availability and the number of riders the system can serve, reflecting the overall performance of EB transportation.

The main contributions can be summarized as follows:

• Formulating the Battery-Swapping Problem (BSP) to address the imbalance between SnD across battery stations within a EB rider transportation network, and modeling the BSP as a discrete-time Markov Decision Process (MDP).
• Introducing a Wasserstein-enhanced Proximal Policy Optimization (W-PPO) reinforcement learning algorithm as a comprehensive solution to the BSP, designed to improve the robustness against SnD dynamic. This algorithm integrates the Wasserstein distance with onpolicy reinforcement learning. W-PPO does not minimizing the divergence between probabilities, as allowing policy changes better reflects the dynamics of the real-
• world simulation. By leveraging the strengths W-PPO, our approach effectively addresses the challenges posed by SnD imbalances in BSP.
• Developing a well-structured algorithm and conducting theoretical evaluations, leading to significant structural insights into the complex BSP transportation network, which demonstrates superior capability and flexibility compared to traditional deep learning methods. The SBUR increased for the average of 30.59% (7 stations per route) and the BSR increased for 16.09%. These two metrics demonstrate our work's improvement of the urban EB transportation system.

2 Battery-Swapping Problem

This section introduces the formal problem statement and its corresponding mathematical models.

From the previous section, we know that customer will swap batteries when the current one they are using is on low battery mode. Depends on the distance they need per day, customers will swap batteries for different number of times. They can return the battery at the station they swapped or at another nearby station, so the number of batteries in each station can be different from one night to the next.

The scenario involving Sharing EB Battery with shared batteries presents a complex landscape that necessitates a detailed representation of the dynamic interactions between riders and EB batteries within a reinforcement learning framework. Delivery companies assign their riders to operate within a designated region, ensuring that battery replacements occur within a confined area. Consequently, the BSP we address is inherently location-based. When users replace batteries, the same battery can appear at multiple exchange stations based on their convenience, allowing it to be reused by a succession of different users. This leads to unbalanced battery resources. To balance the resource, we design the model to learn and match the supply and demand of surplus and shortage battery stations.

We define the problem by building a battery-swapping network: G = (C, R), to be more specific:

• Each station Ci ∈ C allows customers to swap battery and generate corresponding SnD. The number of boxes that can contain battery for each Ci is denoted as Xi. The number of EB battery users for each Ci is denoted as Y t i as the amount is increasing in a timely manner.
• The initial number of batteries in the station at Ci as B0 i , and we use Bt i , Dt i , and Lti , ∀t ∈ (t = 1, 2, ..., T) to represent the number of batteries, battery demand, and battery returned loaded at different time, respectively.
• The battery demand Dt i for each station Ci is the total order number each day.
• The battery returned at each station is denoted as the normal distribution of Li : N(Li, σ2 ). The distribution follows a normal pattern because the location dynamics remain stable, with consistent daily patterns observed. However, notable variations arise between weekdays and weekends. The formulation of Li is Bt+1 i -Bt i +Dt i - xti .

• Under the problem formulation, each route Ri ∈ R is a cycle in the battery-swapping network, consisting of a sequence of consecutive stations Ci1 ,Ci2 , ...,Ci|Ri| , where |Ri| is the number of stops on Ri, and the next destination of Ci|Ri| is Ci1 , which generates a looped path for the vehicle. Each route cannot intersect with others in the network to ensure transportation efficiency. On each route Ri, there is one vehicle cycling around the route, a capacity Captj (the maximum number of batteries it can convey). When a vehicle arrives at a station, it can load batteries or discharge its batteries to the station.

The objective of the battery-swapping network is to maximize the Sharing Battery Used Rate to optimize utility for individual EB riders. At a specific time t, the station can only use the batteries in the last date, i.e., Bt-1 i , to fulfill the current demand Dt i . Once the battery number is not balanced among stations on one route, customer cannot pick up a fully charged battery, which leads to decreased amount of distance they can travel and delivery order they can finish. Accordingly, re-balancing the surplus and shortage stations can increase the amount of fully charged orders and increase the Shared Battery Used Rate (SBUR).

Definition 1. Given the total number of batteries in each station, Bt i , and the fully charged and swapped order number, Dt i , we define the Shared Battery Used Rate (SBUR) in the Battery-Swapping Problem:

After the current demand is processed, returning battery loaded and those discharged from the vehicle will be added to the station battery number. Thus, we can compute the new battery number as Bt i =max(Bt-1 i -Dt i , 0)+Lti +xtj , where xtj ∈ N denotes the number of batteries to delivery or pickup at station Ci by vehicle Vj at time t. xtj can be negative to denote the discharged amount of resources from the vehicle.

Upon the completion of the battery relocation process, the number of batteries available for swapping increases. This increase in availability can be quantified through the calculation of the Battery Supply Ratio (BSR), based on the variables Xi and Y t i . Consequently, the increase in the BSR facilitates the determination of the additional number of EB riders that the system can now accommodate, thereby enhancing the overall efficiency of the EB transportation network.

Definition 2. Given Shared Battery Utilization Rate SBURt i , battery capacity Xi, and the number of EB riders utilizing the shared battery at each cabinet Y t i , we define Battery Supply Rate (BSR) within the context of the BSP as:

3 Designs of W-PPO

Traditional method of matching the demand and supply has limitation as of failures in front of uncertainty of SnD, complex business constraints, and high complexity of transportation networks. To address these issues, we implement the reinforcement learning problem.

3.1 Discrete-time Markov Decision Process

In this section, we will formally define the BSP as a discretetime Markov Decision Process (MDP) (S,A, P, r, γ, T) where S is the state space, A is the action space, P(·|s, a) is the transition probability distribution function, r is the reward function, γ is the discount factor, and T is the total number of days to training in one episode.

State Space S We validated the inclusion of states in successive steps and evaluated the impact of the choices based on rewards. The states transitions are looping in the order of Night (N), Morning (M), and Next Night (N+1).

From SN to SM, each agent will take action to match the demand and the supply. The next night will be the morning state adding the daily usage. It is also important to note that batteries in the stations without transporting will be fully charged throughout the night.

Action Space Each agent, route Ri defined in the previous section, can choose to pick up n ∈ [0, 1, 2, .., k], k ∈ Z battery and can drop off n battery as well. n is the capacity of each route Ri. Two constraints are set in the action space. First, the sum of action space on one route is defined to be zero: ∑ Ai = 0∀i ∈ R. Second, the number of battery picked up or dropped off at each station needs to exceed 0: at ≥ 0 ∀a ∈ Ai.

Transition probability function P defined as a mapping S × A × S → [0, 1], which can be specified by the definition of S, A, and R and the distribution behind SnD within particular battery-swapping networks.

Reward Function We define the reward as maximizing the SBUR until it reaches 1:

The state-value function, the discounted expected reward stating from state s under policy π, is defined as [Sutton and Barto2018]:

To reduce computational overhead, we use the temporal difference (TD) error approximation as advantage function [Schulman et al.2017]:

We use the policy of maximizing the reward to take action. Since the battery number of a new day only depends on the amount of the previous day, the Markov property is satisfied.

A policy π is a function from state to a distribution over actions. The goal of the BSP model is to find policies that maximize episodic return, which is maximizing the SBUR. Running a policy π in the MDP generates a state-action trajectory (s1, a1, r1, s2, a2, r2, ..., rT ) =: τ . θk denotes the parameter for the udated policy πθk (a|s).

Algorithm 1 Wasserstein Enhanced PPO

Input: initialize policy and penalty parameters θ, β

Parameter: Optional list of parameters

Output: Your algorithm's output

• 1: for iteration=1, 2, . . . do
• 2: Compute the SBUR (reward in the BSP) for each route and day under θ
• 3: for route=1, 2, . . . , R do
• 4: Run policy πθ in environment for T time steps
• 5: if W > Wthreshold then
• 6: βk+1 = 2βk
• 7: else if W < Wthreshold then
• 8: βk+1 = βk/2
• 9: end if
• 10: Compute advantage estimates ˆ A1, . . . , ˆ AT using equation 5
• 11: Calculate the loss for each route

• 12: end for
• 13: Compute average loss for all routes under the old policy
• 14: Update the the old policy θ ← θk
• 15: Updated policy θk based on the average loss
• 16: end for

3.2 Wasserstein-Enhanced PPO

Building upon the state-of-the-art deep reinforcement learning method, PPO [Schulman et al.2017], our analysis reveals that the traditional use of Kullback-Leibler (KL) divergence in PPO fails to ensure robust penalty convergence in the context of BSP. While KL divergence is designed to minimize the divergence between policies, ensuring the new policy θk remains closely aligned with the old one θ, this approach falls short of capturing the actual difference between the two policies-a factor that is critical for BSP applications. In the context of BSP, our objective is to evaluate the SBUR, which is derived from a state and action space modeled on real-world data. Therefore, accurately measuring the true difference between policies (how action selections change the battery status in real-world) is essential, as it provides deeper insights into policy performance and adaptability, rather than merely restricting divergence. To address this limitation, we incorporate the Wasserstein distance, derived from optimal transport theory, into the policy optimization algorithm. This modification results in a new distance-regularized policy optimization approach that better evaluates and enforces meaningful distinctions between policies. We use θk representing the updated policy and θ representing the old policy.

The Wasserstein distance, a metric for comparing two discrete probability distributions P and Q, is rooted in optimal transport theory. Intuitively, it quantifies the minimum "cost" required to transform one distribution into the other, where the cost is determined by the amount of mass transported and the distance it is moved. For computational efficiency and theoretical analysis, we focus on the dual formulation of the Wasserstein distance, which provides an equivalent but often more tractable representation of the original primal problem. The dual form leverages the properties of duality in optimization, facilitating its application in machine learning and reinforcement learning contexts [Kolouri et al.2017,Villani2003]:

The parameter p specifies the order of the Wasserstein distance, governing how the transport cost is aggregated across the probability distributions. To accurately quantify the difference between two policies in our study of the BSP, we focus on the case p = 1, commonly referred to as the 1Wasserstein distance or Earth Mover's Distance (EMD). This metric represents the minimum cost needed to transform one probability distribution into another, with the cost being directly proportional to the quantity of mass moved and the distance over which it is transported. This interpretation aligns closely with practical scenarios, making it particularly suitable for applications that demand an intuitive and meaningful measure of distributional dissimilarity. The equation for 1Wasserstein distance:

where F denotes all maps from Rd to R such that |f(y) - f(x)| ≤ ||x - y||∀x, y. Since the difference between the old policy θ and the updated policy θk exists in a one-dimensional flat space, we let d = 1, so the functions f in the set F are 1-Lipschitz, meaning they do not increase faster than the distance between points by the non-expansiveness property of 1-Lipschitz function [Lang1993,Gulrajani et al.2017]:

F and G are the cumulative distribution function of P and Q. We further expand the d = 1 and p = 1 Wasserstein distance with the form of probability distribution functions

With the formulation of the p = 1, d = 1 Wasserstein distance, it promises a optimal distance between two policies θ and θk. The stochastic policy of reinforcement learning can be written as the probability density function:

The cumulative distribution function of the policy is:

With the cdf of π, we obtain the Wasserstein distance W of θ and θk:

With the definition of the Wasserstein distance for policy, we are ready to propose the Wasserstein enhanced PPO:

Definition 3. Given a MDP M = (S, A, P, r, γ, T ), the loss function of the Wasserstein-enhanced PPO algorithm is defined with a W-penalty:

where

4 Experiment Results

In this section, we report the experiment results of our algorithm and multiple baselines based on historical data.

4.1 Experiment Settings

The extensive database provided by [Anonymous Company] is crucial for developing and evaluating our models, encompassing detailed information on over 500,000 batteries and 30,000 battery stations distributed across more than 80 cities. The dataset is divided into two key components: timelocation data, capturing temporal and spatial relationships, and battery status data, detailing operational metrics such as inventory, capacity, and usage. As most riders tend to swap battery in a certain area, we apply the K-Nearest Neighbor (KNN) algorithm to cluster stations into routes, ensuring the optimization process accounts for the spatial distribution of stations and aligns resource allocation with both operational and geographic constraints. Additionally, the database updates operational data for each station daily, typically by 00:00. In our experiment, we conduct research using the data of one month (31 days).

Based on our dataset, we first configure the environment according to the BSP formulation. To ensure a fair comparison across all approaches, we allocate the same test set for evaluating performance. Initially, we conduct baseline experiments using PPO: without penalty, PPO clipped, and PPO KL penalty [Schulman et al.2017]. We further experimented the off-policy state-of-the-art model: Soft ActorCritic (SAC) [Haarnoja et al.2018] to compare the results between on-policy and off-policy models. Given the unique objective in BSP to maximize the SBUR across all routes, the losses and rewards are computed individually for each route. Subsequently, the average loss and reward across all routes are calculated to provide a comprehensive evaluation metric.

As outlined in Algorithm 1, the average loss for all routes within a single episode is used to update the policy. The primary distinction between these models lies in how the loss is calculated and how feedback is incorporated to update policies. This comparative approach ensures insights into the performance impact of different optimization strategies in the BSP context.

In the experiment, the threshold for divergence/distance is determined as the average divergence/distance observed during training. By adopting this average as the threshold, the policy is afforded the flexibility to either update or remain unchanged, depending on the divergence behavior. To ensure reliable evaluation and prevent overfitting, we analyze the loss patterns and select a configuration of running ten episodes for each model. This approach is chosen based on the observation that the loss stabilizes near zero without exhibiting signs of overfitting, which ensures robust performance across the tested models.

Figure 4 illustrates the detailed technical workflow of the W-PPO model. The process begins with the initialization of the policy, where selected actions are applied to the environment for each specified date and route. The environment then generates experience tuples, which are stored in the trajectory memory. Sample routes are drawn from this memory and processed within the W-PPO model, where they are evaluated using several metrics: the SBUR as the reward, the Wasserstein distance as a penalty, and the ratio between the old and new policies. These evaluation variables are utilized to compute the advantage and the loss function, incorporating the Wasserstein penalty to ensure robust policy learning. Finally, the policy is updated based on these computations, iteratively refining its performance to address the BSP effectively.

4.2 SBURResults Analysis

Table 1 provides a detailed breakdown of the experimental outcomes. A key performance metric, the percentage improvement in the SBUR, is calculated for each policy update episode to evaluate and compare the models. To benchmark the performance of our proposed Wasserstein-Enhanced PPO (W-PPO) model against baseline models, we compute both the average SBUR improvement across all episodes and the maximum SBUR improvement observed during the experiments. The table reveals that W-PPO demonstrates superior

performance for routing scenarios involving 5 and 7 stations per rout, outperforming the baseline models in both average and maximum SBUR metrics. However, for routes with 3 stations, W-PPO underperforms compared to the baseline models, with the PPO without penalty variant achieving the best results in this scenario. This trend is more pronounced in environments with a smaller action space (e.g., [-2, 2]). The observed instability for smaller route sizes can be attributed to the reduced amount of training data available when fewer stations are included, limiting the model's ability to effectively learn optimal policies. The table also reveals that the off-policy model, SAC, performs less favorably compared to all on-policy methods. From a mathematical perspective, the battery patterns exhibit minimal variation within a given time frame and location cluster. As a result, entropy does not fluctuate significantly between updates, which hinders the SAC's ability to effectively train under the BSP framework.

To further investigate the relationship between route size and performance, we systematically vary the number of stations per route C, conducting experiments with 3, 5, 7, 9, and 11 stations. The baseline configuration assumes 5 stations per route. Figure 4 visualizes the average SBUR improvement for each configuration, highlighting a clear peak at 7 stations per route. Beyond this point, performance begins to decline.

This decline for larger routes can be explained by practical limitations: as the number of stations increases, the geographical area covered by a route expands. This often exceeds an efficient delivery range, leading to greater variability in battery usage patterns and reduced optimization efficiency. On the other hand, routes with too few stations fail to fully exploit the available resources, resulting in suboptimal performance.

We tested various action spaces, ranging from [-2, 2] to [-11, 11], to account for the differing storage capacities of battery stations. Most stations have a storage capacity between 10 and 20 batteries, while some have as few as 7 storage spaces. Experiments were conducted using the topperforming set of stations per route, specifically routes with 7 and 8 stations. As shown in Figure 5, the action space [-11, 11] did not result in any SBUR improvement, as removing too many batteries from a station depleted its reserves, leading to premature experiment termination. Similarly, for routes with 9 stations, the SBUR remained unchanged for an action space of [-9, 9], as the higher variability in battery distribution across stations caused some stations to run out of batteries when taking 9 or more, also terminating the experiment. From the plot, we observe that the average SBUR reaches its peak at an action space of [-7, 7] for routes with 7 stations, achieving an impressive average SBUR increase of 61.14%. The average SBUR improvement for 7 stations per route is 30.59% for each route on a daily evaluation. Therefore, we conclude that in this experiment, the action space of [-7, 7] for 7 stations per route represents the optimal configuration. Building upon the training results from the WPPO model for EB battery rebalancing, we further assess the BSR. As presented in Table 2, we observe that under the optimal configuration, the BSR increases by 16.09%. To further investigate the impact of BSR, we evaluate the additional number of EB riders that can be served by this transportation system design. Using the current data from Shanghai, we find that with a BSR increase of 16.09%, the number of EB riders served grows by 45.55%, assuming a constant battery supply. Additionally, to examine the environmental and efficiency benefits, we calculate the number of batteries saved, which, based on the current constant EB rider count in the BSP system, amounts to 3,972. The exploration of the BSR demonstrates the overall BSP robustness.

5 Discussion and Conclusion

This work has addressed the key challenges of optimizing SnD imbalances in battery-swapping stations for EB transportation, which impact courier efficiency, income, and overall EB rider satisfaction. By formulating the BSP as a discrete-time MDP, we provide a robust mathematical foundation to manage these imbalances in complex transportation networks. The proposed W-PPO algorithm, combining PPO with Wasserstein distance, effectively handles the uncertainties in SnD forecasting. Our approach demonstrates notable advantages in both theoretical insights and practical outcomes, achieving a 30.59% average improvement in the SBUR and a 16.09% increase in BSR for 7 stations per route, offering a significant enhancement over traditional methods.

Several limitations and future works is considered in this study. Data protection restrictions hinder the evaluation of cost efficiency, and the applicability of our method to other transportation systems like EVs and AGVs requires further adaptation due to differing operational dynamics. Additionally, the method's performance is sensitive to hyperparameters, affecting its generalizability. Future work will focus on developing advanced hyperparameter optimization techniques, adapting the W-PPO algorithm for broader transportation contexts, and extending the W-PPO algorithm to realtime SnD predictions.

6 RelatedWork

Electric transportation management has become a key research area, with significant efforts in optimizing various objectives in different types of electric transportation, like electric vehicles (EVs), automated guided vehicles (AGVs), EScooters [He and Shin2020], and EBs. Most works studied the EVs discussing its state of charge [Baccari et al.2024,Sun et al.2019,Cui et al.2023], system costs [Widrick et al.2016], battery system [Mao et al.2024, Zhang et al.2018], and company profits [Jin et al.2023, Shalaby et al.2023, Liang et al.2023, Zheng et al.2014, Gao et al.2020]. The studies related to AGVs used RL and are implemented in warehouses to increase logistics and operational efficiency. Additionally, AI models like transformers and RL techniques have played a vital role in the studies of the EB transportation system. Previous studies focused on monitoring and detecting battery status and predicting riding range in EBs [Li et al.2024c, Li et al.2024b]. These AI-driven approaches have greatly advanced the efficiency and reliability of electric transportation management systems. Moreover, AI has been extensively applied to optimize logistical systems, such as express delivery networks [Li et al.2020], empty container repositioning [Li et al.2019], and resource-balancing challenges in various domains [Naderializadeh et al.2020,Yi et al.2019], further improving operational decision-making and system efficiency across the electric transportation landscape.

In RL, Proximal Policy Optimization (PPO) has proven effective in diverse applications, including robotics and logistics, due to its stability and efficiency [Schulman et al.2017]. Optimal transportation theory has also been integrated into RL to address resource allocation and distribution challenges. Studies have combined optimal transportation with RL in multi-agent systems [Gulrajani et al.2017, Ali Baheri2024] and curriculum learning [Huang et al.2022], showcasing its potential. Our work extends this by incorporating the Wasserstein distance [Kolouri et al.2017, Villani2003] with PPO to create a more meaningful penalty structure for policy optimization, especially in environments with limited data. This combination enhances the model's ability to make precise and efficient updates, making a significant contribution to RL applications in complex resource-balancing scenarios.

Acknowledgments

This work was supported, in part by China NSF grant No. U2268204, 62322206, 62025204, 62132018, 62272307,

62372296, in part by Alibaba Group through Alibaba Innovative Research Program. The opinions, findings, conclusions, and recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies or the government.

Zhenzhe Zheng is the corresponding author.