An approach for solving the traveling salesman problem as formulated in the AIAA Artificial Intelligence Design Challenge is presented. The approach is based on heuristic measures involving intecity fares, city values, and value to fare ratios. Other heuristic factors take into account the avilable budget, the expected trip cost, and the likelihood of low cost hub cities. Monte Carlo simulations show that this heuristic method produces optimal solutions over 90 percent of time for problems dominated by fare, and at least 55 percent of the time for problems dominated by value to fare ratio. The average measure of optimality for the heuristic solutions exceeds 0.95 in both cases.


    Access

    Access via TIB

    Check availability in my library


    Export, share and cite



    Title :

    Heuristic Approach to the Traveling Salesman Problem


    Contributors:
    C. Y. Huang (author) / S. H. Lane (author)

    Publication date :

    1987


    Size :

    7 pages


    Type of media :

    Report


    Type of material :

    No indication


    Language :

    English




    A heuristic approach to the traveling salesman problem

    HUANG, CHIEN / LANE, STEPHEN | AIAA | 1987



    A heuristic algorithm for traveling salesman problems

    Ashour, Said / Vega, J.F. / Parker, R.G. | Elsevier | 1971


    A New Heuristic for the Traveling Salesman Problem with Time Windows

    Calvo, Roberto Wolfler | Online Contents | 2000


    A New Heuristic for the Traveling Salesman Problem with Time Windows

    CALVO, R. W. | British Library Online Contents | 2000