In e-commerce warehouses, replenishment operations involve the transportation of ordered items from reserve areas to forward picking areas. This subsection examines the optimal storage of newly arrived items in open locations within forward picking areas before the picking process begins, aiming to minimize the total travel distance for fulfilling picking orders. The locations occupied by items previously stored in the forward area are not available. The problem is formulated as an integer program and proved to be NP-hard. A two-stage decomposition algorithm is proposed, demonstrating its ability to provide high-quality solutions efficiently. In comparison to methods found in the literature and those currently used in practice, this approach significantly reduces travel distance. Additionally, numerical analysis indicates that accounting for the constraint of previously stored items—an aspect often overlooked in prior research—can improve picking performance by more than 5%. The algorithm is applied to real-world data from a Chinese third-party logistics (3PL) retailer, where it substantially outperforms the company’s existing storage policy.