Overbounding the integrity risk is a significant challenge for Kalman filter (KF)-based advanced receiver autonomous integrity monitoring (ARAIM) when the measurement error has an uncertain time correlation. Thus, this paper presents a method that addresses this challenge by effectively bounding the integrity risk for KF-based ARAIM while considering the uncertainty in the model of the time-correlated error. Firstly, the recursive equation for covariance is derived, establishing a direct mathematical expression that links the integrity risk and the correlation time constant. Subsequently, a min–max optimization model is constructed, utilizing the obtained expression as the objective function, to simultaneously bound the integrity risk and reduce conservatism. To effectively address the current min–max optimization problem, a hybrid evolutionary algorithm is proposed, which conducts global searching followed by local searching. The simulation result demonstrates that it outperforms other algorithms, enabling rapid attainment of the minimum upper bound on the integrity risk.