Abstract: An integration approach based on heuristic strategies and branchbound algorithm was proposed for solving asymmetric traveling salesman problem. In this method, associated with each node of the branchdecision tree, a parametric solution of the relaxed assignment problem and a feasible solution obtained by patching algorithm are used to tighten the lower and upper bound. A hueristic strategy that conbines the threshold constraint based depthfirstsearch and weighted random breadthsearch is adopted to seek the optimal solution. Therefore, a feasible solution that is very close to the optimal solution can be found in comparatively short time. The computational results on data in the TSPLIB and a hot strip scheduling simulation show the efficiency of the proposed algorithm.