Individual differences are prevalent in the process of product performance degradation. However, in the current optimal design based on the degradation model, the individual differences are almost not considered. Therefore, an optimal design method of the step-stress accelerated degradation test with random effect Wiener process is proposed. Based on the cumulative failure model, a multi-step-stress accelerated degradation model with individual variations is established. Under the given measurement interval, and subject to the constrain of the total testing time and the accelerated stress, the setting of the test stress level and the measurement times at different stress levels are optimized by minimizing the asymptotic variance of the estimated p-quantile of product lifetime distribution under the normal stress condition. The proposed method has been verified by a double-step-stress accelerated degradation test of LED lamps. The parameter sensitivity of the optimized test is investigated and the optimal test plan is found to have good robustness when the parameters changed in a small range.