Electric Heterogeneous Fleet Vehicle Routing Optimization for Campus Commuter Services: A Two-Stage Heuristic Approach

The Multi-Destination Vehicle Routing Problem (MD-VRP) with a heterogeneous electric fleet is a critical challenge in optimizing commuter services for large-scale institutions and logistics operations. To address the complexities of electric fleet composition uncertainty and multi-center routing in “micro-city” campus environments, this paper establishes a robust multi-objective programming model. The model aims to simultaneously minimize three conflicting objectives, the total number of vehicles, total driving distance, and total electric energy consumption (kWh), under constraints of flow conservation and vehicle availability. Considering the nondeterministic polynomial-time hard (NP-hard) nature of the problem, a novel two-stage hybrid heuristic algorithm is proposed. In the first stage, a Modified Kruskal’s algorithm is employed to aggregate scattered stops into optimized clusters to reduce dimensionality. In the second stage, a State-Compressed Dynamic Programming (SC-DP) algorithm is applied to determine the optimal routing and electric vehicle type selection for each cluster. The methodology is validated using a case study of a large-scale campus network with 100 nodes. The optimization results identify an optimal fleet configuration of 41 campus electric commuter vehicles across three specific types (capacities of 45, 55, and 60), resulting in an annual total energy consumption of 5893.98 kWh. Compared with a global Ant Colony Optimization (ACO) baseline in this case study, the proposed framework reduces the required fleet size by 22.6% and annual energy consumption by 9.2%; however, this comparison should be interpreted as a preliminary case-study benchmark because the proposed method adopts a decomposition-based “Cluster-First, Route-Second” strategy. The results indicate that the approach achieves higher solution efficiency, offering an economically and environmentally friendly scheme for electric vehicle fleet operations.