@techreport{oai:ipsj.ixsq.nii.ac.jp:00077581,
 author = {星野, 貴弘 and 浜松, 芳夫 and Takahiro, Hoshino and Yoshio, Hamamatsu},
 issue = {3},
 month = {Sep},
 note = {In this study, we propose an algorithm based on convex hull insertion (CHI) method for the traveling salesman problem (TSP). CHI method and proposed algorithm construct solutions by inserting city to a partial tour. Proposed algorithm is an improvement of insertion procedure in CHI method. This algorithm sets a threshold of the angle between the route from the inserted city to next city and the route from the inserted city to previous city. The city of the maximum angle is inserted, if there are angles being greater than a threshold. Insertion procedure is changed, if there is no angle being greater than a threshold. In order to evaluate the accuracy of solutions obtained using the algorithm, the proposed algorithm and CHI method are applied to 19 benchmark problems: 51-783 city problem in TSPLIB 95. As a result, proposed algorithm  nds shorter tours than CHI in 16 problems., In this study, we propose an algorithm based on convex hull insertion (CHI) method for the traveling salesman problem (TSP). CHI method and proposed algorithm construct solutions by inserting city to a partial tour. Proposed algorithm is an improvement of insertion procedure in CHI method. This algorithm sets a threshold of the angle between the route from the inserted city to next city and the route from the inserted city to previous city. The city of the maximum angle is inserted, if there are angles being greater than a threshold. Insertion procedure is changed, if there is no angle being greater than a threshold. In order to evaluate the accuracy of solutions obtained using the algorithm, the proposed algorithm and CHI method are applied to 19 benchmark problems: 51-783 city problem in TSPLIB 95. As a result, proposed algorithm  nds shorter tours than CHI in 16 problems.},
 title = {巡回セールスマン問題に対するヒューリスティック解法},
 year = {2011}
}