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.