Dynamic electric vehicle fleets management problem for multi-service platforms with integrated ride-hailing, on-time delivery, and vehicle-to-grid services

Abstract

The rapid adoption of electric vehicles (EVs) and the surge in mobility service demand necessitate efficient management of EV fleets. In practice, these vehicles often remain idle for extended periods due to fluctuating demand, leading to underutilized resources and lost revenue. In response, this paper investigates a dynamic multi-service platform that concurrently coordinates ride-hailing, on-time delivery, and vehicle-to-grid (V2G) energy services. By leveraging synergies across these services, the proposed coordination strategy improves resource utilization, reduces operational costs, and increases profitability. Upon accessing the platform, users submit various service requests that specify the origin, destination, time windows, and either the number of riders or the weight of goods. To meet these heterogeneous, real-time demands, we propose a dynamic multi-service electric vehicle fleet management (MEFM) problem to optimize the allocation, routing, and scheduling of EV fleets to maximize platform profits over each time period. We formulate the proposed MEFM problem as an arc-based mixed-integer linear programming (MILP) model and develop a customized branch-and-price-and-cut (B&P&C) algorithm for its efficient solution. Our algorithm integrates Dantzig–Wolfe decomposition, improved with subset row cuts, and a novel labeling sub-algorithm that effectively captures multi-service coordination, fleet capacity, and battery-level constraints under partial recharging flexibility. Extensive numerical experiments based on a case study in the context of Shenzhen, China, demonstrate that the customized B&P&C algorithm achieves computation speeds on average 150.99 times faster than the state-of-the-art commercial solver (Gurobi), with speed-ups ranging from 3.33 to 477.42 times, while consistently obtaining optimal solutions for large-scale instances where Gurobi fails. Moreover, our results highlight the benefits of integrating on-time delivery and V2G energy services, e.g., despite a modest increase in operational costs, the substantial rise in profits validates the economic potential of the multi-service platforms. We also identify that partial recharging flexibility for EVs further reduces delay costs by up to 70.27% and boosts overall profits by up to 40.90%.