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.
Heuristic Approach to the Traveling Salesman Problem
1987
7 pages
Report
No indication
English
A heuristic approach to the traveling salesman problem
AIAA | 1987
|A heuristic algorithm for traveling salesman problems
Elsevier | 1971
|A New Heuristic for the Traveling Salesman Problem with Time Windows
Online Contents | 2000
|A New Heuristic for the Traveling Salesman Problem with Time Windows
British Library Online Contents | 2000
|