ブロックシフト操作とカオスニューロダイナミクスを用いた非対称巡回セールスマン問題の解法

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2012/05/01

タイトル(英語): A Method for Solving Asymmetric Traveling Salesman Problems Using Block Shift Operation and Chaotic Neurodynamics

著者名: 橘　俊宏（東京電機大学大学院 先端科学技術研究科），安達　雅春（東京電機大学大学院 先端科学技術研究科）

著者名(英語): Toshihiro Tachibana (Graduate School of Advanced Science and Technology, Tokyo Denki University), Masaharu Adachi (Graduate School of Advanced Science and Technology, Tokyo Denki University)

キーワード: 非対称巡回セールスマン問題，カオスニューラルネットワーク，ブロックシフト操作　　Asymmetric traveling salesman problems，Chaotic neural networks，Block shift operation

要約(英語): An asymmetric traveling salesman problem is one in which the costs for travel between one city and another are not symmetric. In this paper, we propose a method for solving such problems based on chaotic search method. It uses block-city exchange method, block insertion method, and 2-opt exchange as exchanging methods. In the block-city exchange method, we consider several cities as a block, and the whole block is exchanged with other city. In the block insertion method, we consider several cities as a block, and the block is inserted at the specified location. In the proposed method, a switching between two exchange methods is determined by chaotic neurodynamics. In the proposed method, the block-city exchange method uses one of exchange method for any instance. The other exchange method is selected from the 2-opt exchange and block insertion methods according to the standard deviations of the costs city-wise and that of all branches in the instance. The proposed method obtains better or equivalent solutions with the conventional heuristic methods for asymmetric TSPs.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.132 No.5 （2012） 特集：新たな産業応用を可能にする無線通信技術

本誌掲載ページ: 774-781 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/132/5/132_5_774/_article/-char/ja/