• MINIMIZATION OF TIME AND COST FOR TRANSPORTATION AND CONSTRUCTION MANAGEMENT OF ROADS IN AFAR REGIONAL STATE BY TRAVELLING SALESMAN PROBLEM

Abstract

At first glance, this problem is extremely similar to the Chinese postman problem. However, in contrast with the Chinese postman problem, no efficient algorithm for solving the travelling salesman problem is known as far. We will here describe a new algorithm to solving the travelling salesman problem in both cases of complete graphs and incomplete connected graphs, following a comprehensive treatment of Hungarian Method. Transport management, Construction management, Tourists, Sales representatives, Postman and visitors are wide application in order to save time and cost. However, the TSP is closely related to several of the problem areas, like 2-matching, spanning tree, and cutting planes, which areas actually were stimulated by questions prompted by the TSP, and often provide subroutines in solving the TSP. Being NP-complete, the TSP has served as prototype for the development and improvement of advanced computational methods, to a large extent utilizing polyhedral techniques.  This paper gives an introduction to the Traveling Salesman Problem that includes current research. Additionally, the algorithms are used to find the shortest route traveling through zones of Afar Regional State in Ethiopia.