Using Travelling Salesman Principle to Evaluate the Minimum Total Cost of the Iraqi Cities

Main Article Content

Sajjad Majeed Jasim Faez Hassan Ali

Abstract

The traveling salesman problem (TSP) is a well-known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. In this paper we exploit the TSP to evaluate the minimum total cost (distance or time) for Iraqi cities. So two main methods are investigated to solve this problem; these methods are; Dynamic Programming (DP) and Branch and Bound Technique (BABT). For the BABT, more than one lower and upper bounds are be derived to gain the best one. The results of BABT are completely identical to DP, with less time for number of cities (n), 5 ≤ n ≤ 25. These results proof the efficiency of BABT compared with some good heuristic methods. We are suggesting some additional techniques to improve the computation time of BABT for n ≤ 80.

Article Details

How to Cite
JASIM, Sajjad Majeed; ALI, Faez Hassan. Using Travelling Salesman Principle to Evaluate the Minimum Total Cost of the Iraqi Cities. Ibn AL- Haitham Journal For Pure and Applied Science, [S.l.], v. 32, n. 3, p. 95-108, sep. 2019. ISSN 2521-3407. Available at: <http://jih.uobaghdad.edu.iq/index.php/j/article/view/2286>. Date accessed: 13 oct. 2019. doi: http://dx.doi.org/10.30526/32.3.2286.
Section
mathematics