The Electric Time-Dependent Capacitated Arc Routing Problem

With rising energy and environmental concerns, electric vehicles (EVs) are becoming crucial for logistics. Traffic congestion significantly affects travel times, especially in urban areas, causing EV speeds to vary across routes. Due to their limited range, models account for energy consumption based on speed and aerodynamics but are often oversimplified. Traditional models use average speeds or linear approximations, which do not accurately reflect real conditions, especially in Arc Routing Problems. We address these issues by defining the Electric Capacitated Arc Routing Problem with Time-dependent Travel Times and Speed-dependent Energy Consumption Rate. Each arc has a stepwise speed function, allowing speed changes while traveling. The goal is to serve arcs using a fleet of EVs with limited load and battery capacity, minimizing total travel time. We propose an exact energy consumption preprocessing algorithm and integrate it into an Iterated Local Search metaheuristic, comparing routes for EVs and conventional vehicles.