Return of products within the warranty coverage induces additional cost and loss of reputation to manufacturers. It is of practical interest to predict the return rate by experimental means before introducing a product to the market. In this paper, we propose to optimize accelerated reliability tests to achieve the goal within limited time. To describe the heterogeneity in the customers’ usage mode, a discrete random variable is employed to model the degradation rate in addition to the continuous stress variable. To further characterize the heterogeneity in the customers’ behavior, two models of product return are investigated: one assumes that customers return products once the degradation level reaches the minimum eligible return threshold and the other assumes that the threshold varies among different customers. Optimal reliability tests are planned under the large-sample assumption with two novel test schemes: global optimal planning and stress constrained planning. Insights regarding the optimal plans are gleaned to ameliorate the test planning procedure and verify the optimality. A real example from the battery industry is then presented along with the simulation study and sensitivity analysis to demonstrate the methods. We find that the randomness in return level results in different test plans. Furthermore, the constrained optimal plans offer more robustness to the compromise plans.