|
【ネットワーク解析】セールスマン巡回問題解析
GA(遺伝的アルゴリズム)を用いて「セールスマン巡回問題」を解析する機能です。
ポイントデータを巡回点として、単純直線距離での解析や、道路レイヤーを指定する事で、近接する道路ネットワークを介したネットワーク解析が行われます。
なお、"遺伝的アルゴリズム"の性格上、必ずしも最適な結果が得られるという保証はなく、また、同一条件で再実行しても同一結果になるという保証はありません。
※GA(遺伝的アルゴリズム)やTSP(セールスマン巡回問題)そのものに関しては、サポート範囲外となりますので、各種の文献・書籍等を参照下さい。
 |
- セールスマン巡回問題【traveling salesman problem (TSP)】
- 「あるセールスマンが幾つかの都市を一度ずつ訪問して出発点に戻ってくる時に、移動距離が最短になる経路」を求める問題。
都市数が少ないうちは楽な問題だが、都市数が増えるに従って加速度的に難しくなる(都市数を10とすると、(10-1)!=362,880通りの巡回経路となる)。
|
- ■ 操作方法
-
- ポイントデータのあるレイヤーをアクティブにします。
- [ツール]-[ネットワーク解析]-[セールスマン巡回問題解析]を選択すると、[遺伝的アルゴリズムによるセールスマン巡回問題解析]ダイアログボックスが表示されます。
「起点」と「終点」の指定は内部IDを入力しますが、内部IDが分からない場合は、テキストエリアの右の青い三角ボタンをクリックして下さい。
一旦ダイアログが消え、クロスカーソルになりますので、それぞれのポイントをクリックすると、自動的に内部IDが入ります。
- ＜OK＞ボタンをクリックすると、「プレビュー」にポイント位置とその間の経路を順に処理していく様子が表示されます。
処理途中で＜完了＞ボタンを押すと、その段階での最後の世代が表示されます。
- 以下のような結果になります。
- ダイアログボックスの「高度な設定」の黒い三角ボタンをクリックする(2.の青い丸で囲われた部分)と、詳細設定が行えます。
例えば、試行世代数を「50」と「100(標準)」では結果が異なります。
▼ 試行世代数：100
▼ 試行世代数：50
- また、2.でそれぞれのポイントを訪問する際、道路ネットワークでの最短経路を検索する事もできます。
その場合は、道路(アーク)の方向や通行可能/不可の指定や、距離換算も行えます。
▼ 設定は4.と同じだが、経路に道路ネットワークを指定した場合
|
