WEKO3
-
RootNode
アイテム
巡回セールスマン問題に対するヒューリスティック解法
https://ipsj.ixsq.nii.ac.jp/records/77581
https://ipsj.ixsq.nii.ac.jp/records/77581b922c297-6731-479b-9828-16dfd5f23598
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-ITS11046003.pdf (554.9 kB)
|
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-09-21 | |||||||
| タイトル | ||||||||
| タイトル | 巡回セールスマン問題に対するヒューリスティック解法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Heuristic Methods for Traveling Salesman Problem | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 日本大学 | ||||||||
| 著者所属 | ||||||||
| 日本大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nihon University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nihon University | ||||||||
| 著者名 |
星野, 貴弘
浜松, 芳夫
× 星野, 貴弘 浜松, 芳夫
|
|||||||
| 著者名(英) |
Takahiro, Hoshino
Yoshio, Hamamatsu
× Takahiro, Hoshino Yoshio, Hamamatsu
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11515904 | |||||||
| 書誌情報 |
研究報告 高度交通システム（ITS） 巻 2011-ITS-46, 号 3, p. 1-4, 発行日 2011-09-21 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
