Static and Dynamic Models for Rebalancing and Charging Battery-Powered Mobility
Advisor: Professor Yanfeng Ouyang
Abstract:
The number of trips by micromobility modes (such as dockless bikes and e-scooters) in North America, after their initial adoption in 2017, rapidly grew to 147 million by 2019. This trend of growth continued in recent years despite a significant drop in ridership due to the COVID-19 pandemic in 2020, and micromobility usage has since rebounded and continued to grow beyond pre-pandemic levels. The rapid growth of e-scooter sharing services, however, has come with significant operational challenges. Operators must manage tens of thousands of e-scooters in large cities such as Los Angeles, San Francisco, Washington DC, Austin, and Chicago, and the spatiotemporal demand heterogeneity requires that those e-scooters be frequently recharged and repositioned/rebalanced for future users. Proper strategies for e-scooter planning and operations, especially those related to charging and rebalancing, have become a critical challenge for cities and micromobility companies. Lack of such strategies has mandated many cities across the U.S. to impose licensing, parking, and pathway regulations to reduce the clutter caused by excess or uneven supply of e-scooters.
Numerous charging technologies have emerged to enhance the rebalancing and charging operations of shared micromobility systems, including charging hubs, charging stations, and battery swapping. Recent innovations, such as portable batteries and fast-charging capabilities, also enable e-scooters to be charged quickly while being transported during rebalancing trips. These strategies provide new opportunities to improve operational efficiency and, when effectively implemented, may achieve stronger economies of scale. However, integrating these technologies into daily operations is nontrivial. Operators must create a daily charging-and-routing plan for all e-scooters that simultaneously accounts for their state of charge (SoC), required charging durations, energy supply resources, and a pickup/drop-off strategy, while balancing supply and demand across time and space. Furthermore, if rebalancing and charging occur during service operations, the strategy must accommodate temporal demand surges in real time, which increases the complexity of large-scale planning and operations.
As such, this dissertation research focuses on developing new mathematical models and customized solution approaches that can effectively support decision making for static and dynamic e-scooter rebalancing and charging operations in a variety of business scenarios. An on-board charging strategy for overnight operations, modeled as a discrete inventory routing problem, is first presented. E-scooters of different SoC are modeled as different commodities that can transition into each other while being transported by the rebalancing vehicles. To mitigate the complexity of such models, a discrete-continuous hybrid solution approach is developed for large-scale instances. The key idea is to embed a continuous approximation (CA) subroutine (which estimates costs for routing decisions in local areas) into a discrete mixed-integer inventory-routing problem formulation. A series of numerical experiments, including hypothetical problem instances and a full-scale case study for Washington DC, are conducted to demonstrate the applicability and effectiveness of the proposed hybrid approach.
Then, we propose a capacitated charging hub strategy for overnight e-scooter rebalancing and charging. The problem is similarly modeled as a static inventory routing problem with SoC transitions at charging hubs (i.e., as satellite facilities). We propose a different discrete-continuous hybrid model reformulation and solution algorithm, in which the spatial region is partitioned into local zones with embedded CA subroutine. This method is validated through hypothetical experiments and a case study to draw managerial insights.
Finally, a family of dynamic decision support models are developed to evaluate and compare a range of charging strategies (e.g., on-board charging, battery swapping, and charging stations) during daytime operations. Under a unified Markov Decision Process (MDP) framework, we test different battery evolution rules and operation actions in a time-varying environment. A series of stochastic dynamic lookahead approximations is introduced to solve these MPD models. The models are initially tested on hypothetical networks and subsequently validated using real-world cases from Chicago. The emphasis is on comparing their performance under various conditions to derive practical insights and estimate the benefits of each strategy.