Approximate expressions for evaluating a priori solutions to the probabilistic traveling salesperson problem (PTSP) are introduced. The approximate expressions are incorporated in heuristic improvement procedures for PTSP to provide high-quality solutions with significantly reduced computational complexity compared with that for identical improvement procedures with exact solution evaluation. The link between this approximation evaluation scheme and a metaheuristic is discussed. Additionally, a progressive approximation extension is provided. Numerical experiments were conducted to assess the effectiveness of a proposed approximate evaluation expression and the progressive approximation scheme. Experimental results indicate that improvement procedures incorporated with the approximate evaluation expressions can produce solutions comparable to those of improvement procedures with exact solution evaluation with significantly reduced computational complexity. The results also show that the progressive approximation scheme is able to provide consistently improved solutions with a considerably reduced computational effort compared with that required for a similar approach that uses exact calculation of expected length.