We study an electric vehicle routing problem where routing and charging decisions must be coordinated with traffic conditions and electricity grid dynamics. We propose a time-expanded, carbon- and congestion-aware electric vehicle routing problem with station capacity (TE-CC-EVRP) that extends classical EVRP models in several directions. The planning horizon is discretized into time periods and represented by a time-expanded network that captures time-dependent travel times due to congestion, as well as time-varying electricity prices and emission factors. Charging stations have limited resources in each period, modeled through plug availability and aggregate power limits, which may create competition among vehicles for charging. The vehicle fleet is heterogeneous with respect to battery capacity, energy consumption, maximum charging power, and load capacity constraints. The objective is to minimize total operating cost, including travel and charging costs, while satisfying a global carbon budget that limits indirect emissions from electricity use. We formulate the problem as a mixed-integer linear program on a time-expanded network and develop a parallel memetic genetic matheuristic. The algorithm evolves vehicle routes through genetic operators while delegating charging scheduling and feasibility verification to an exact mixed-integer optimization subproblem. Computational experiments on benchmark instances derived from realistic traffic and grid profiles show the impact of congestion and station capacity on routing and charging strategies, highlight cost–emission trade-offs under different carbon budgets, and demonstrate that the proposed matheuristic efficiently produces high-quality solutions for large-scale instances.

Keywords

Electric Vehicle Routing Problem, Time-expanded Network, Carbon-aware Routing, Congestion-aware Routing, Memetic Matheuristic