TSP解法の実験的解析とそれに基づく2-Optと相性のよいツアー構築法の提案

スポンサーリンク

概要

• 論文の詳細を見る

• 巡回セールスマン問題(TSP)の発見的解法は, 一般的に, ツアー構築法と局所改善法かち構成される。局所改善法の一つであり, 最も広く使用されている2-Opt は, そのツアー長と実行時間が, 初期ツアーを生成する構築法に強く依存することが知られている。そのため, 構築法単体では最もよいトレードオフを持つGT法が, 2-Optを適用する場合には他の構築法に及ばないという現象が起きる。今までにこのような現象は解析されておらず, 2-Optを適用する場合に性能がよい(つまり2-Optと相性がよい), という観点での構築法の提案はなされていなかった。本稿では, 既存の幾つかの構築法と2-Optの性能を実験的に解析し, それに基づいて2-Optと相性のよい構築法RSLを提案する。RSL法に2-Optを適用する解法(RSL+2-Opt)は, これまで最も性能がよいとされていたMF+2-Optよりも, 高速によい解を生成する。

• 一般社団法人情報処理学会の論文
• 1997-09-24

著者

• 味園 真司

  日本アイ・ビー・エム株式会社東京基礎研究所

• 岩野 和生

  日本アイ・ビー・エム株式会社未来価値創造事業担当

• 岡野 裕之

  日本アイ・ビー・エム(株)

• 岩野 和生

  日本アイ・ビー・エム(株)

• 岩野 和生

  日本アイ・ビー・エム株式会社東京基礎研究所

• 岡野 裕之

  日本アイ・ビー・エム 東京基礎研

• 岩野 和生

  日本アイ・ビー・エム

関連論文

• 最小カット問題に対するKargerのランダムアルゴリズムの新しい確率的評価について
• クラウド・コンピューティングの動向とIBMの取組み
• 巡回カメラマン問題とその自動光学的検査への応用
• アクセス管理のための承認者選択最適化(IBMにおけるOR)
• 特集にあたって(企業事例)
• 第9回企業事例交流会ルポ(情報の窓)
• 配送経路最適化の適用 : 銀行における配送を例として (企業事例)
• TSP解法の実験的解析とそれに基づく2-Optと相性のよいツアー構築法の提案
• デジタルマップを用いた最適倉庫配置問題への取り組み(交通・輸送(2))
• RSC : グループウェアのためのオブジェクト共有機構
• 日英機械翻訳システムJETSにおける翻訳エディタ
• 不定期便に対応したパイロット乗務スケジューリング
• 不定期便に対応したパイロット乗務スケジューリング
• 製造業における巡回セールスマン問題の応用
• サーキットボード穴開け問題
• 最大流アルゴリズムの最近の発展とその背景 : II
• 最大流アルゴリズムの最近の発展とその背景 : I
• A New Randomized Approach to the Minimum Cut Problem and Its Variants by Minimum Range Cut Algorithms
• 92-16 多項式時間かつ線形以下計算領域で無向グラフ上のs-t連結性を判定する決定性アルゴリズム
• 良い『メモリ図』の生成
• 新しい社会サービスの実現に向けてその課題と解決策を考える
• 研究室紹介 : 日本アイ・ビー・エム(株)東京基礎研究所
• 日本アイ・ビー・エム株式会社ソフトウェア開発研究所
• 物理的世界とデジタルの世界の融合がもたらすもの Smarter Planet の目指す世界
• マネジメント最前線1 新技術が社会と企業にもたらすもの (特集 グリッド・コンピューティング)
• シミュレーション技術への期待
• 巡回セールスマン問題をめぐる最近の話題
• 理論と実際の邂逅の場としての情報処理学会

もっと見る 閉じる

スポンサーリンク