TY - JOUR
ID -
TI - Using Travelling Salesman Principle to Evaluate the Minimum Total Cost of the Iraqi Cities
AU - Sajjad Majeed Jasim
AU - Faez Hassan Ali
PY - 2019
VL - 32
IS - 3
SP - 95
EP - 108
JO - Ibn Al-Haitham Journal For Pure and Applied Sciences مجلة ابن الهيثم للعلوم الصرفة والتطبيقية
SN - 16094042 25213407
AB -
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.
ER -