Using Travelling Salesman Principle to Evaluate the Minimum Total Cost of the Iraqi Cities
Abstract
The traveling salesman problem (TSP) is a well-known and important combinatorialoptimization problem. The goal is to find the shortest tour that visits each city in a given listexactly once and then returns to the starting city. In this paper we exploit the TSP to evaluatethe minimum total cost (distance or time) for Iraqi cities. So two main methods areinvestigated to solve this problem; these methods are; Dynamic Programming (DP) andBranch and Bound Technique (BABT). For the BABT, more than one lower and upperbounds are be derived to gain the best one. The results of BABT are completely identical toDP, with less time for number of cities (n), 5 ≤ n ≤ 25. These results proof the efficiency ofBABT compared with some good heuristic methods. We are suggesting some additionaltechniques to improve the computation time of BABT for n ≤ 80.
Keywords
Travelling Salesman Problem, Dynamic Programming, Branch and Bound, Greedy method and Minimizing Distance MethodMetrics