1.
Introduction
As cities grow and the concept of sustainability strengthens, the sharing economy is receiving increasing attention [1]. Over the past decade, the sharing economy, particularly in the transport sector [2], has received significant focus. A prominent area of study within the sharing economy in the transport sector focuses on vehicle-sharing systems. These systems provide shared vehicle services, such as bicycles and electric scooters, in public areas, including bus stops, metro stations, and other high-traffic locations. Users can utilize these services for commuting or travel and should return vehicles to a designated area upon completion of the rental.
The emergence of sharing systems is having an impact on transport patterns in cities [3,4,5]. This innovative transport mode reduces car usage, promotes the sharing economy, improves the quality of the urban environment [6,7,8], and enhances the health of the population [9]. An in-depth understanding of vehicle-sharing systems can provide meaningful insights for urban planning policymakers and companies providing vehicle-sharing services.
The success of vehicle-sharing systems hinges on both strategic design and effective operational strategies, particularly vehicle rebalancing. While infrastructure lays the groundwork, it is the operational strategies that enhance service efficiency [10,11]. This study investigates the optimization strategies for rebalancing shared electric scooters. Unlike traditional shared bicycles, electric scooters utilize their electric drive systems that enable users to complete short-distance commuting without additional physical exertion and thus have a high degree of acceptance among users. In addition, electric scooters show higher adaptability when dealing with complex urban terrains and traffic environments. In particular, the electric drive system is able to respond quickly in scenarios with frequent starts and stops, improving operational flexibility and commute efficiency. Electric scooters offer distinct advantages in convenience and operational efficiency [12], making them an increasingly vital focus of research in modern shared transportation systems.
The rebalancing problem of the shared electric scooter system is mainly affected by the uncertainty of user demand and the shortage of charging station sites. User demand uncertainty introduces complexity to scheduling and allocation processes. Additionally, the constraints imposed by charging facilities affect the state of electric scooters. In our research, we assume that the uncertain demand for scooters each day follows a probability distribution; and accurate demand prediction and effective demand response strategies are vital for optimizing shared electric scooter systems. Moreover, high transportation and labor costs further complicate the rebalancing process.
To solve this uncertain operational problem, we propose a data-driven optimization model to obtain the operational scheduling scheme. Specifically, this data-driven approach fits stochastic user demand by the empirical demand distribution. Using this approach, we can better adjust the electric scooter configurations between stations to meet uncertain user demand. First, we construct a stochastic optimization model M0 to describe the rebalancing problem of electric scooter-sharing systems with uncertain user demand. Second, we use the mean value of historical user demand to fit the random user demand and construct a baseline mean-value model M1. Moreover, we use the empirical distribution of historical data to approximate the user demand, constituting an improved data-driven optimization model M2. Through different approaches, we approximate a stochastic optimization model M0 by the tractable optimization models M1 and M2, respectively. Finally, the performance of these models is evaluated through numerous computational experiments. The experimental results show that model M2 outperforms the benchmark model M1 in different scenarios, indicating that model M2 is better at dealing with stochastic user demand. Moreover, we conduct sensitivity analyses by altering model parameters to further validate the effectiveness of model M2. Consequently, our work has theoretical and practical significance for the development and enhancement of electric scooter-sharing systems.
The rest of the paper is structured as follows: Section 2 reviews the relevant literature. Section 3 constructs a mathematical model for the uncertain electric scooter scheduling problem. Section 4 presents solution approaches to solving the proposed stochastic model. Section 5 tests and validates the performance of our proposed models. Section 6 concludes the paper.
2.
Related literature
There are lots of studies conducted on the sharing of bikes and cars. Yet, less research has been done about how to properly operate shared electric scooters [13]. Therefore, we review research on bike-sharing systems that are similar to the shared electric scooter systems.
The optimization objectives of some studies focus on the strategic design of bike-sharing systems, such as the arrangement of station locations. García et al. [14] used the geographic information system of Madrid city to design the location-allocation model. Raviv et al. [15] constructed a new inventory routing model to standardize emerging bike-sharing systems. Fricker and Gast [16] evaluated the impact of station capacity on the optimization of the bike-sharing system. Liu and Tian [17] optimized companies' decision making for bike-sharing services by constructing virtual sites to promote bike use based on the k-means method. Chen et al. [18] proposed an improved repositioning model using trajectory data from Shenzhen to optimize the system design solution.
More infrastructure development is not enough to improve the service of bike-sharing systems. How to effectively rebalance bikes between stations from an operational perspective has obtained the attention of many researchers [10,11]. For example, Erdoğan et al. [19] presented the first exact algorithm for the bike rebalancing problem. Kadri et al. [20] used the branch-and-bound algorithm to solve the proposed bike rebalancing problem that optimizes the stations' operational costs. However, existing studies [21,22,23,24] are more biased towards the static sharing scheduling problem; that is, they focus more on situations where user demand is constant or has only minor changes, which restricts the system's flexibility and responsiveness.
To better improve the system's performance, some studies have considered analyzing the uncertain user demand. Hulot et al. [25] constructed a station-level user demand prediction model based on two years of real data from BIXI Montréal (a local bus company in Montréal) for rebalancing problems. VE and Cho [26] predicted user demand by analyzing multi-dimensional data containing information such as weather. However, these models have high requirements for data quality and quantity.
In summary, existing literature has extensively explored strategic design and rebalancing strategies for shared bicycle systems. However, compared to shared bicycles, shared electric scooters have significant advantages in terms of storage space requirements and operational flexibility, which enable them to show higher adaptability in urban environments. The shared electric scooters reduce physical effort for users, making scooters preferable for short commutes. Additionally, they are better suited to complex urban environments, with faster responses in stop-and-go conditions, improving both flexibility and commuting efficiency. Nevertheless, the scheduling and rebalancing problems faced by electric scooters, especially those limited by charging equipment, have not been adequately studied. Therefore, this study aims to investigate how shared electric scooter systems can achieve effective rebalancing in the face of user demand uncertainty under charging facility constraints.
3.
Problem description
Take one bus route in an area that stops at multiple stations as an example for a company that offers shared electric scooter services. In the electric scooter scheduling optimization problem, the initial state of electric scooters is influenced by the placement of charging hubs. In order to ensure that the electric scooter can be properly managed and used with the support of charging facilities, we assume that all the electric scooters will return to their designated stations for recharging at the end of each day's operation. On this basis, our model focuses on adjusting the distribution of electric scooters in the face of stochastic user demand, thereby optimizing the scheduling strategy to meet user demand more efficiently.
The rebalancing decision not only determines the operating costs, but also affects user satisfaction. More importantly, this decision is made in the face of the unknown user demand. Therefore, our research attempts to formulate a model that provides the optimal solution to this scheduling problem considering uncertain user demand. This model is constructed based on the following assumptions: i) Each site has an unconstrained capacity for electric scooters; and ii) The total number of electric scooters owned in the shared electric scooter system is fixed.
Our research primarily focuses on implementing operational rebalancing decisions before users begin using the scooters every day. The research aims to achieve effective rebalancing of the electric scooter system on a daily basis, with the objective of minimizing transportation costs associated with transferring scooters between stations and minimizing the penalties resulting from unsatisfied user demand. To handle uncertain user demand, we assume that historical demand information is available.
To formulate the problem discussed above, we consider a region with a set of transit stations, represented as P, where passengers may choose electric scooters for commuting to work upon arriving at the destination station by transit. The region also comprises a set of electric scooter storage stations, denoted as K, where the number of electric scooters available at the station k is qk, ∀k∈K. Here, the transit station set P is a subset of the storage station set K. Additionally, the number of users utilizing electric scooters from station p to work is represented by the stochastic parameter ˜ξp. Although the underlying distribution of ˜ξp is unknown, we are accessible to M pieces of historical user demand at each station p, p∈P over a historical period, denoted as ζ={ξ1,⋅⋅⋅,ξm,⋅⋅⋅,ξM}; here, ξm=(ξm1,⋅⋅⋅,ξm|P|) denotes the vector of user demand in the mth instance, where ξmp means the user demand in the mth instance for station p, ∀m∈{1,2,⋅⋅⋅,M}, ∀p∈P. To handle uncertain user demand, we assume that the distribution of the stochastic user demand (˜ξ1,⋅⋅⋅,˜ξ|P|) is consistent with the historical data, which can be characterized by P(˜ξp=ξmp)=1/M, where ∀p∈P, ∀m∈{1,⋅⋅⋅,M}.
Now, we denote by decision variable xkp∈Z+ the number of electric scooters transported from site k to site p, k∈K, p∈P. Additionally, the parameter ckp signifies the transport cost per unit of electric scooter from site k to site p. Therefore, we quantify the transportation costs in the whole scheduling process by ∑k∈K∑p∈Pckpxkp. Moreover, the decision variable yp denotes the number of electric scooters at site p after the scheduling process, and it can be calculated through Eq (3.1) as follows:
Similarly, the expected decision loss stemming from the inadequate inventory level yp at site p is expressed as dpE[max{0,~ξp−yp}], where dp characterizes the loss incurred due to the lack of an electric scooter at site p. When the final number of electric scooters yp could meet the users' demand ~ξp at station p, the decision loss at station p is zero; otherwise, it is dp(~ξp−yp). Before we present the mathematical programming model for our research problem, we present all of the notions as follows.
The objective of this study is to optimize the allocation of available electric scooters to meet users' uncertain demand. The uncertain scheduling problem, termed model M0, can be mathematically modeled as follows:
Objective function (3.2a) minimizes the sum of transportation cost and decision losses. Constraints (3.2b) compute the number of electric scooters owned by each site after the scheduling is completed. Constraints (3.2c) ensure that the number of electric scooters transported from station k does not exceed its storage capacity qk. Constraints (3.2d) and (3.2e) ensure the domains of the decision variables.
Proposition 1. The integer constraints (3.2e) can be relaxed to the continuous constraints yp∈R+,∀p∈P, where R+ denotes the set of non-negative real numbers.
Proof. The value of yp is formed through integer additions and subtractions in the calculation displayed in (3.2b). Relaxing the constraints of yp does not affect the consistency of the solution. □
4.
Solution methods
4.1. Mean-value optimization model M1
In model M0, objective function (3.2a) incorporates the random user demand ˜ξp at station p. Solving it requires the knowledge of the uncertain demand distribution. To address this challenge, we initially follow the common approach by using the average values of user demand at transit stations from the historical data {ξm}Mm=1 to approximate the random user demand. Incorporating the average values into model M0, the objective function of model M0 is approximated as follows:
The mean-value method approximates the stochastic objective function (3.2a) in model M0 by a deterministic objective function (4.1). However, the objective function (4.1) contains the max operator, which is a nonlinear term. In order to transform the nonlinear term into a linear term, we introduce the auxiliary decision variable wp to represent the number of unmet electric scooters for the users at station p, ∀p∈P, and it can be calculated as follows:
By using the average values of historical data and auxiliary variables wp, ∀p∈P, we approximate the stochastic model M0 by a deterministic mean-value model M1, shown below:
Objective function (4.3a) aims to minimize the sum of transportation costs and decision losses. Constraints (4.3b) calculate the number of scooters owned by each site after the dispatching has been completed. Constraints (4.3c) calculate the number of users whose demand for scooters is unmet. Constraints (4.3d) guarantee that the number of electric scooters transported from site k does not exceed its original storage capacity qk. Constraints (4.3e)–(4.3g) ensure the domains of the decision variables.
4.2. Data-driven optimization model M2
Simple average values may not adequately reflect the real-world uncertainties, thereby reducing the model's effectiveness. Therefore, we approximate the distribution of the random user demand (~ξ1,⋅⋅⋅,˜ξ|P|) by using the empirical dataset ζ={ξm}Mm=1. Specifically, we assume P(~ξp=ξmp)=1/M, ∀p∈P, ∀m∈{1,⋅⋅⋅,M}. This method approximates the calculation of E[max{0,~ξp−yp}] by (M)−1∑Mm=1max{0,ξmp−yp}. Consequently, the objective function of model M0 is approximated by:
Likewise, this approach approximates the original stochastic objective function (3.2a) by the deterministic objective function (4.4), which is tractable. Since Objective function (4.4) contains the max operation, it is nonlinear. Therefore, we introduce the auxiliary decision variable zmp to represent the number of users whose demand for scooters is unmet at site p in the mth instance. Specifically, zmp=0 denotes the successful fulfillment of user needs when the actual inventory level yp equals or exceeds the user demand ξmp at station p in the mth instance; otherwise, zmp means the shortage, indicating the discrepancy between the actual inventory level yp and the user demand ξmp. zmp is calculated as follows:
By doing so, objective function (4.4) is expressed as follows:
Meanwhile, to simplify the model representation, we introduce the decision variable zp to represent the average number of users whose demand for scooters is unmet at site p, which can be calculated as follows:
By utilizing historical data ζ to approximate the distribution of stochastic user demand (˜ξ1,⋅⋅⋅,˜ξ|P|) and introducing auxiliary decision variables zp, ∀p∈P, the complex stochastic optimization model M0 is approximated by the mixed-integer programming model M2, shown as follows:
Objective function (4.8a) aims to minimize the sum of transportation costs and decision losses. Constraints (4.8b) calculate the number of scooters available at a site after the dispatching process. Constraints (4.8c) determine the number of unsatisfied users in any station of any instance. Constraints (4.8d) calculate the average number of users whose demand for scooters is unmet among all of the instances. Constraints (4.8e) ensure that the number of electric scooters transported from site k does not exceed qk. Constraints (4.8f)–(4.8i) define the domains of the decision variables.
5.
Computational experiments
5.1. Experiment settings
Based on the historical data and the introduced auxiliary variables, we approximate the original optimization model M0 by the mixed-integer programming models M1 and M2. This section conducts computational experiments to validate their performance.
In our computational experiments, we run programs using an M3 Pro chip with an 11-core configuration. Simultaneously, we utilize the CBC solver from Python to solve optimization models, an open-source tool specifically designed for integer and mixed-integer linear programming problems.
5.1.1. Parameter settings
Firstly, we determine the values of the parameters to be adopted. The respective considerations and parameter values are listed below:
1). The number of transit stations |P| is set to 20.
2). The number of electric scooter storage stations |K| is set to 40.
3). The number of instances of historic data M is set to 100.
4). The number of electric scooters qk available at the station k, k∈K, is set to 100.
5). As for the number of users needing electric scooters, ξmp, in the site p of the mth instance, we take an arbitrary integer from a discrete uniform distribution over the interval [0,5qk], ∀k∈K, ∀p∈P, ∀m∈{1,⋅⋅⋅,M}.
6). The transport cost ckp per unit of electric scooter from site k to site p is associated with the distance dkp (km) between site k and site p. We first set ckp=0.5dkp ($). Here, \(d_{kp}\) is a randomly generated positive value less than 100. The distances between sites all satisfy the principle of triangulation which means that dkp′+dp′p>dkp, ∀k∈K, ∀p,p′∈P. This distance design approach intends to simplify the complexity of our models.
7). For the loss, dp, incurred due to the lack of an electric scooter at station p, p∈P, we set dp to be the value of 10 ($).
5.1.2. Experimental design
In this section, we describe our experimental design, as illustrated in Algorithm 1. The goal of this algorithm is to evaluate the models' performances based on available data ζ. We divide the historical user demand data ζ into the training dataset ζtrain and the test dataset ζtest in the ratio of 9:1. Here, the training dataset ζtrain can be seen as the historical dataset, and the test dataset ζtest is used to measure the out-of-sample performances of our proposed models. First, we obtain the initial optimal solution X∗1 for the first instance of the test dataset from the model (model M1 or model M2) using the training dataset ζtrain. In the optimal solution X∗1, the element X∗1[i,j] represents the optimal number of electric scooters transported from station i to station j, ∀i∈K and ∀j∈P. In addition, qk is the initial inventory level of the first instance. And then we update the number of electric scooters q1k at station k based on X∗1 through Eq (5.1), which is the end inventory level of the first instance, shown as follows:
For easier evaluation of the model performance, we assume that users will return electric scooters to their original stations after use. Thus, q1k is also the original inventory level of the second test instance.
Next, we use ζtest to evaluate the performance of the model based on q1k. We define ξi as the ith instance of ζtest, ∀i∈{1,2,⋅⋅⋅,|ζtest|}. Specifically, ξip means the actual user demand in the station p in the ith instance of ζtest and here ξi=(ξi1,⋅⋅⋅,ξi|P|). As for the test instance ξi, we concatenate the known data ζtrain and {ξj}j=i−1j=1 to obtain the optimal solution X∗i and qik, k∈K. Then, we evaluate the performance resi of ξi, ∀i∈{1,2,⋅⋅⋅,|ζtest|} by
The calculation of resi is the sum of transport costs ∑k∈K∑p∈PckpX∗i[k,p] and the penalties caused by insufficient electric scooters ∑p∈Pdpmax{0,ξip−qip}. Finally, res is calculated by summing the individual values resi for all of the instances in the test dataset ζtest. The final value res is used to evaluate the performance of the model, calculated by
5.2. Evaluation of models
5.2.1. Model performance
In the previous sections, we presented various models for solving electric scooter scheduling problems. We used the res calculated through the test dataset ζtest as the evaluation metric for comparing model performances; here, a larger value of res indicates a poorer ability of the model to minimize transport costs and penalties caused by inadequate electric scooters. We use Algorithm 1 for assessing the models' performances.
Table 1 presents the results (res) under varying conditions, particularly differences in the number of transit stations (|P|). An analysis of these results reveals that while the performance gap between the two models fluctuates with changes in |P|, model M2 consistently outperforms the baseline model M1 across all scenarios. Notably, model M2 achieves its greatest efficacy at |P|=15, showing an improvement of approximately 13.12% over model M1. The smallest observed improvement, at |P|=16, is approximately 3.61%. These results underscore the enhanced capability of model M2 in managing the operational challenges of electric scooter rebalancing in response to uncertain user demand, confirming its superior performance overall.
5.2.2. Sensitivity analyses
To analyze the electric scooter scheduling problem on a specific bus route, the parameters P and K are generally assumed to be fixed. In contrast, the parameters dp and qk often fluctuate dynamically. For instance, in colder winter weather, the likelihood of choosing electric scooters decreases, leading to a downward adjustment in qk at the station. Considering the dynamic nature of these parameters in real-world scenarios, it is crucial to perform sensitivity analyses to investigate their impact on the scheduling decisions.
To account for the volatility observed in real-world scenarios, this study conducts sensitivity analyses by considering a range of values for the penalty coefficient dp and the storage quantity qk. Specifically, when conducting sensitivity analyses for dp, we assume that |S|=40, |P|=20, and qk=100, allowing dp to vary with an interval of 1 over the integer range from 0 to 10. Similarly, when performing sensitivity analyses for qk, we assume that |S|=40, |P|=20, and dp=10, allowing qk to vary with an interval of 10 over the integer range from 50 to 150. At the same time, we calculate the improvement Δ between models M1 and M2 using Eq (5.4). Here, Δdp corresponds to parameter dp, and similarly, Δqk is associated with parameter qk. The results of these calculations are presented in Table 2.
Table 2 compares the performance of baseline models M1 and M2 under varying values of dp and qk. The data show that model M2 generally surpasses model M1 in performance. However, exceptions are noted at lower dp values (dp=0,1,2), where the models perform similarly or where M1 may exhibit comparative advantages.
In detail, in terms of the penalty coefficient dp, ∀p∈P, when dp=0, both models yield 0 transport costs, which means that no electric scooter is dispatched between sites when there is no penalty for the shortage of electric scooters at a station. However, model M2 fails to improve performance when dp=1 and dp=2. This lack of enhancement may be attributed to the low penalty values assigned for scooter shortages, which are insufficient to significantly influence operational decisions under user demand uncertainty. Consequently, the advantages of model M2, which are designed to optimize around variability, are not effectively leveraged. Model M2 shows a significant performance improvement compared to model M1 when dp≥3, and the Δdp gradually increases along with the increase of dp, with the highest Δdp at dp=10, which is about 6.95%. This trend underscores model M2's adaptability in scenarios where higher penalties compel more strategic rebalancing efforts to accommodate uncertain demand fluctuations.
As for qk, ∀k∈K, an increase in the initial inventory qk means that each site has more electric scooters at the start of the operation. As a result, the number of electric scooters that need to be dispatched from the storage sites to meet user demand decreases, which directly reduces transport costs. Additionally, it also reduces the number of electric scooters in shortage to meet user demand, reducing the corresponding penalties. Thus, the total cost res, consisting of the sum of transport costs and the penalties value due to the lack of electric scooters, decreases gradually as the initial inventory qk increases.
However, according to Table 2, the variation of qk does not change the superior position of model M2, verifying its significant advantages. These findings underscore the effectiveness of the data-driven model M2 in managing variations in dp and qk, making it more applicable in practical scenarios where these parameters may fluctuate. The overall superior performance of the model M2 suggests its capability to provide more effective solutions to electric scooter scheduling problems.
6.
Conclusions
This study addresses the operational rebalancing challenges in shared electric scooter systems by developing and comparing several optimization models. Initially, we construct a stochastic optimization model (M0) to capture the complexity of unknown user demand. To operationalize this model, we introduce the mean-value optimization model (M1), which estimates demand using historical averages. Further enhancing our approach, we develop a data-driven optimization model (M2) that uses the empirical distribution of user demand for greater accuracy.
Through extensive computational experiments, we demonstrate that model M2 consistently outperforms model M1 in various scenarios. These findings underscore the superiority of the data-driven model M2 in effectively managing the complexities of scooter rebalancing. The performance of M2 across different test conditions confirms its practical applicability and potential to significantly improve operational efficiencies in real-world electric scooter sharing systems.
In our research, we have utilized stochastic optimization to cope with user demand uncertainty, and future research can further explore methods such as robust optimization and distributionally robust optimization. These methods provide alternative strategies to cope with worst-case scenarios and limited distributional information, which can help to enhance the robustness of the model. Therefore, future work can be centered around these methods to extend and enrich the existing research results to provide more comprehensive solutions for practical applications.
Use of AI tools declaration
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
Acknowledgments
This work was supported by the National Natural Science Foundation of China [Grant No. 72361137006] and JPI Urban Europe and Energimyndigheten (P2023-00029, e-MATS).
Conflict of interest
The authors declare there is no conflicts of interest.