Traveling salesperson problem-TSP problem is an optimization problem to find the optimal way for the traveling salesman who wants to visit several cities, and returned to the original departure city. TSP is a difficult problem when viewed from the point of computing. Several methods have been used to solve these problems but until now not been found mangkus algorithms to solve them. The easiest way to solve TSP is to try all possible routes and find the optimal route. However, at the time of the very practical now required to complete an algorithm that quickly so that the TSP solution obtained near optimal solutions. shortest distance in shipping company package delivery from shipping company is very important due to; hard terrain, traffic, etc. Therefore, the use of TSP to determine the shortest distance is very crucial. Heuristic algorithm is an algorithm that produce the best solution to the problems part or intersect with an the issue is more complex. on completion TSP, the algorithm is looking for the minimum spanning tree of all the nodes. Then, this algorithm forming Eulerian circuit for approximating the solution ago Terlalui node handles more than once which is expected to provide solutions optimal in solving problems TSP. Keywords: delivery, graph algorithm, heuristics, traveling salesperson problem.