A Heuristic for Battery-Constrained Charging and Rebalancing of Micromobility Devices

Abstract

This study presents a heuristic approach to optimize the charging and rebalancing of automatic micromobility devices with battery constraints. The methodology integrates a vehicle routing problem to reposition and charge automatic micromobility devices and a facility location problem to ensure efficient deployment of charging locations. We first define density-based homogeneous regions through a clustering technique and then employ a continuous approximation technique to estimate the average distance between the nodes in each cluster, which is then used to assess the routing objective value. By estimating total travel distance and cost, the heuristic accommodates both known and potential repositioning needs. Using real-world data from Chicago, IL, our findings indicate that the heuristic achieves near-optimal solutions with substantial reductions in computational time, highlighting its practical applicability in real-world scenarios compared with traditional methods. Additionally, sensitivity analyses reveal the impact of battery levels and facility costs on overall performance, providing valuable insights for decision makers. The proposed approach offers a robust framework for enhancing the efficiency of micromobility systems, with promising applications in improving system resilience in disaster-affected areas and improving equitable access to underserved communities.