An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: Model formulation and Lagrangian relaxation-based solution approach

In one-way electric vehicle (EV) carsharing systems, a practical issue that needs to be addressed is the imbalance of EVs with respect to the spatial time-dependent user reservations at different carsharing stations. In practice, appropriate EV rebalancing operations can satisfy user reservations with limited resources and effectively save system investments. This paper proposes an integrated framework that can determine the optimal allocation plan of EVs and staff on the strategic level while considering the operational EV relocation and staff relocation decisions, in order to minimize the total cost, including the EV and staff investment, EV rebalancing and staff relocation costs. In this framework, the dispatching routes of EVs and staff are represented by two sets of space-time paths in the planning time horizon by using a space-time network representation, and the considered problem is then formulated into a mixed-integer linear programming model (MILP). This model explicitly considers (1) the satisfaction of time-dependent user reservations through dynamically rebalancing EVs and relocating staff to keep the service quality of carsharing system, and (2) the EV battery capacity with limited traveling distance and the charging process of EVs at parking stations. A Lagrangian relaxation-based solution approach is developed to decompose the primal problem into several sets of computationally efficient subproblems. In order to generate good-quality solutions, we also propose a three-phase implementing algorithm based on dynamic programming according to the values of Lagrangian multipliers. An illustrative numerical example and a real-world case study (based on the operation data of Seattle, WA) are conducted to verify the applicability of the formulated model and effectiveness of the proposed approach.