著者

星野 貴弘 浜松 芳夫

雑誌

研究報告 高度交通システム(ITS)

巻号頁・発行日

vol.2011-ITS-46, no.3, pp.1-4, 2011-09-21

---

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.