Greedy-Based Hybrid Metaheuristics for the Sustainable Electric Vehicle Routing Problem

Abstract

The growing adoption of electric vehicles in urban logistics has increased the need for routing models that jointly address operational efficiency and environmental impact. This paper studies a Sustainable Electric Vehicle Routing Problem with Time Windows, which extends the classical EVRPTW by integrating mixed time windows with penalties and carbon-emission costs, while restricting each charging station to at most one visit per route and prohibiting depot-to-station and station-to-station movements. To solve this NP-hard problem, two greedy-based hybrid metaheuristics are proposed, Greedy Simulated Annealing (GSSA) and Greedy Variable Neighborhood Search (GSVNS). Computational experiments on 76 benchmark instances show that greedy-based hybridization significantly improves the baseline methods. GSSA achieves an average total-cost reduction of 49.48% over SA, while GSVNS improves VNS by 11.49% in total cost, 16.89% in distance, and 19.52% in fleet size. In addition, GSVNS attains the best total cost on 80.26% of the tested instances, confirming its effectiveness, particularly on large-scale instances.