Four methods to calculate the Vertical Protection Level (VPL) can be used in Advanced Receiver Autonomous Integrity Monitoring (A-RAIM), among which the ideal method is the strictest one. To obtain the ideal VPL satisfying the exact required integrity risk, the worst case bias with the maximum integrity risk is searched for. This investigation has found that the correct worst case highly depends on the choice of the input VPL. To gain the correct result, the computation becomes complex and the accuracy of the result is compromised. Therefore, a new procedure is designed with a new search: the maximum VPL is searched to encompass all possible bias sizes. Since VPL is calculated with a given integrity risk for each bias size, the uncertainty of the arbitrary VPL input in the ideal method is avoided. Also, an optimisation algorithm is adopted to improve computational efficiency. It is shown that the new method is more reliable and efficient than the current best method. Simulation results worldwide also show that the new approach has improved A-RAIM availability from 32%–38% to 74% with GPS and from 44%–43% to 85% with Galileo.