The dust suppression of hauling roads in open-pit mines is done by periodically spraying water from a water truck. The objective of this article is to present a method for locating water depots in the road network so that penalty costs for the lack of humidity in roads and routing costs are minimized. Because the demands are located on the arcs of the network and the arcs require service more than once in a time horizon, this is a periodic capacitated arc routing problem. We compare three methods for finding the initial depot location using an L-A-R (location, allocation, and routing) approach combined with an adaptive large-neighborhood search to improve the solution. This method is the first for depot location in periodic arc routing problems.