②巡回セールスマン問題：枝に重みを与えたグラフGにおいて, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)のn点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある.
出所：OR事典Wiki https://orsj-ml.org/orwiki/wiki/index.php?title=メインページ
＜簡単な事例＞名古屋市昭和区役所の所員が緑区、守山区、中川区、熱田区、名東区の各区役所を書類を持って移動し、最後に昭和区役所に戻る場合の総移動距離が最短となる移動順序を求める事例。
この場合、総移動距離が最小となる移動順を図に赤矢印で示します。総移動距離は46.68ｋｍとなります。ちなみに、上記記載の順番で移動した場合（図中の青い矢印）は70.81kmとなります。
従いまして、この事例の場合、知らずに移動計画を立てていた場合、24.13km余分に移動していたのかもしれません。
各区役所の位置を示します。
赤い線が最短移動を示す。青い点線が事例記載の順番で移動した場合。
各区役所間の距離（直線）を示します。
コメント