This paper addresses the problem of efficiently routing vehicles for spring sweeping operations in countries that spread sand and gravel on roads in winter. Given a road network, one sweeping fleet, and several depots, we seek to route the fleet over the network so as to minimize the time needed to sweep all required road segments and reduce the distance covered by deadheading trips. The schedule is subject to service time window constraints for highways, time constraints of the crew, and visits to depots along the route. The little work that has been carried out so far to solve this practical problem treat it as an arc routing problem. Instead, we transform the arc routing problem into an equivalent node routing problem and propose three decomposition-based approaches to solve the latter. Tests are conducted on randomly generated instances as well as on a real-world case in Victoriaville, Québec, Canada.