The Electric Car-Sharing Relocation and Recharging Problem Considering Route Balancing

Abstract

One-way station-based electric car-sharing systems frequently develop spatial stock imbalances and charging shortfalls. Although operator staff are the primary corrective mechanism to relocate surplus electric cars (ECs) and ferry low-energy ECs to charger-equipped stations, most planning models optimize only the logistics cost or profit while leaving staff workload largely unregulated. This study addresses the electric car-sharing relocation problem considering route balancing, which jointly minimizes relocation distance cost and aggregate duty time while limiting the spreads between the longest and shortest duties and driven distances, subject to residual range limits, shift caps, and sparse charging coverage. The problem is formulated as a nonlinear multi-criterion mixed-integer programming model and, after replacing the extreme-duty terms with linear equivalents, weighted scalarization yields a single-objective mixed-integer linear programming. A request-oriented adaptive large neighborhood search (ALNS) is developed with specialized removal and insertion operators, including a fairness-aware inserter, adaptive operator weights, and simulated annealing-based acceptance. Computational experiments on 21 instances show that ALNS improves CPLEX incumbents by 5.8–6.1% on large cases in 1.5–1.8 s of CPU time (versus a 3600 s limit), exceeds GA by 1.0% on average under equal 30 s budgets, and that the explicit implementation of route equity weights measurably reshapes staff tours without sacrificing operational feasibility.