{"updated":"2025-01-21T20:51:32.221375+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00077581","sets":["1164:3980:6333:6535"]},"path":["6535"],"owner":"10","recid":"77581","title":["巡回セールスマン問題に対するヒューリスティック解法"],"pubdate":{"attribute_name":"公開日","attribute_value":"2011-09-21"},"_buckets":{"deposit":"5615905d-7d9b-4c55-99df-f9cc9abb757d"},"_deposit":{"id":"77581","pid":{"type":"depid","value":"77581","revision_id":0},"owners":[10],"status":"published","created_by":10},"item_title":"巡回セールスマン問題に対するヒューリスティック解法","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"巡回セールスマン問題に対するヒューリスティック解法"},{"subitem_title":"Heuristic Methods for Traveling Salesman Problem","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2011-09-21","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"日本大学"},{"subitem_text_value":"日本大学"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Nihon University","subitem_text_language":"en"},{"subitem_text_value":"Nihon University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/77581/files/IPSJ-ITS11046003.pdf"},"date":[{"dateType":"Available","dateValue":"2013-09-21"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-ITS11046003.pdf","filesize":[{"value":"554.9 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"37"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"cbcb116d-dfcd-4a45-be61-2002daae14cc","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2011 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"星野, 貴弘"},{"creatorName":"浜松, 芳夫"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takahiro, Hoshino","creatorNameLang":"en"},{"creatorName":"Yoshio, Hamamatsu","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11515904","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"4","bibliographic_titles":[{"bibliographic_title":"研究報告 高度交通システム（ITS）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2011-09-21","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"2011-ITS-46"}]},"relation_version_is_last":true,"weko_creator_id":"10"},"created":"2025-01-18T23:33:08.047822+00:00","id":77581,"links":{}}