An Ant-based approach to solve the Electric Vehicle Routing Problem with Time Windows and Partial Recharges

Nowadays, emissions from the transportation area are among the most contributors to climate change and global warming. As a consequence, routing problems that consider the usage of alternative energy sources is relevant to tackle. This work proposes ACOLS, a specially designed ant-based approach to solving the Electric Vehicle Routing Problem with Time Windows and Partial Recharges. Our approach has three steps an ant-based construction of feasible solutions (in terms of fuel and capacity constraints), a feasibility local search phase focused on reducing the time windows violations, and a local search improvement phase focused on reducing the number of routes and total distance traveled. We present a comparison with state-of-the-art algorithms and a convergence analysis on large-size problem instances. ACOLS obtains promising results in benchmark instances.