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.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Approximate Procedures for Probabilistic Traveling Salesperson Problem


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:


    Publication date :

    2004-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    A new approach for the traveling salesperson problem with hotel selection

    Augusto Pizano Vieira Beltrão / Luiz Satoru Ochi / José André de Moura Brito et al. | DOAJ | 2021

    Free access

    Probabilistic Traveling Salesman Problem with Deadlines

    Campbell, Ann M. | Online Contents | 2008


    Probabilistic Traveling Salesman Problem with Deadlines

    Campbell, A.M. / Thomas, B.W. | British Library Online Contents | 2008


    A Control Theoretic Approach to the Dubins Travelling Salesperson Problem

    Isaiah, P. / Shima, T. / Tekhniyon, Makhon tekhnologi le-Yisra'el | British Library Conference Proceedings | 2014