巡回セールスマン問題に対する局所探索法

巡回セールスマン問題について

複数箇所の訪問先(以下都市とよびます)をすべて一度だけ訪問するとき、
その訪問の総距離が最短となる巡回路(つまり出発地に戻らなくてはならない)
を求める問題です。

  • 都市はアプレットの右上端にあるプルダウンメニューから問題例を選ぶか、
    画面上をクリックすることで配置することができます。
  • SOLVEボタンで局所探索法による求解の動作を開始します。
  • 動作中にSTOPボタンまたは画面をクリックすると一時停止します。
  • SOLVEボタンで動作を再開します。
  • CLEARボタンで都市を消去します。

    • 局所探索法について

    局所探索は、すでに構成済み(1)の巡回路を改良するために用いられます。
    なお、ここで紹介するアプレットでは巡回路の構成はNearest Neighbour
    〜もっとも近いお隣さんをたどること〜によって実現しています。

    (1)構成済み：すべての都市を訪問する巡回路ができあがっているという意味

    さて、局所探索に話をもどしましょう。局所探索は構成済み巡回路を
    (全都市を一度だけ訪問という条件をくずさないよう)一部変化させて
    総距離を改良していく方法の総称と思ってください。

    総称と呼んだのは、変化のさせ方がいろいろあるためであり、
    ここで紹介するアプレットでは2-opt近傍とOr-opt近傍を併用した変化をさせています。

    2-opt近傍について

    2-opt近傍とは、巡回路のなかから2都市間をむすぶ路を2本選んで、
    入れかえるという操作です。
    図1でみると、赤で描かれた路2本が、青で描かれた路2本に
    入れかえられている様子がわかると思います。

    図1 2-optによる巡回路の変化

    Or-opt近傍について

    Or-opt近傍とは、巡回路のなかから多くとも3都市をつなぐ部分路を、
    他の位置に移動挿入する操作です。

    図2をみてください。

    いまグレーの線で囲まれた部分路を赤点線の位置に移動挿入
    しようとしています。赤実線は部分路を本体と接続している路です。

    つぎにこの赤実線を切断し、青実線のように挿入したい位置に
    接続しなおします。

    後始末として、切断された都市が宙ぶらりんになりますので、
    これを青点線のように接続してやります。

    図2 Or-optによる巡回路の変化