In warehouses, storage replenishment operations involve the transportation of items to capacitated item slots in the forward storage area from reserve storage. These items are later picked from these slots as demand arises. While order picking constitutes the majority of warehouse operating costs, efficient management of replenishment operations is important to ensure the availability of the items for picking and to decrease the operating costs due to replenishment, which might be particularly higher in warehouses with fast-moving items (e.g., e-commerce warehouses or retail distribution centers). In this paper, we define the storage replenishment routing problem in a parallel-aisle warehouse, where replenishment and order picking operations are carried out in successive cycles with time limits. The aim is to determine the item slots that will be replenished and the route of the replenishment worker in each replenishment cycle, so as to minimize the total travel time and ensure the availability of items at the start of the cycle they will be picked. We present complexity results on different variants of the problem and show that the problem is -hard in general. Consequently, we adapt a heuristic approach based on a priori routing and inspired by the literature on the inventory routing problem. We use randomly generated warehouse instances to analyze the effects of different a priori routing methods and demand skewness patterns on replenishment performance, and to compare the proposed approach to benchmarks that mimic practice.