クラスタ化と段階的経路精細化による巡回セールスマン問題の発見的解法

スポンサーリンク

概要

論文の詳細を見る
ユークリッド型巡回セールスマン問題の近似解を求める新しい発見的方法を報告する。この方法では最初に、空間内の近接性に基づいて都市の階層的クラスタ化を行う。ついで、上位レベルにある数個の大きなクラスタを対象として、クラスタを単位とした全体の概略的な経路を作成する。その後順次下位レベルのより小さなクラスタを対象として、クラスタ内経路の精細化を行う。本方法では、同時に考慮するクラスタ数を変えることにより、解の精度を調節できる。乱数により生成した16都市の座標を用いて計算機実験を行い、分岐限定法によって得られた最適解との比較をおこなった。その結果、半数以上の場合に最適解と一致し、平均誤差が1%以下となる解を高速に得られることが判明した。本方法で最適解が得られなかった場合の考察を含めて報告する。
一般社団法人情報処理学会の論文
1995-05-12

著者

関連論文

もっと見る

スポンサーリンク