TIM Labs

巡回セールスマン問題、セールスマンが2人だったら。

| コメント(0) | トラックバック(0)

一般的な巡回セールスマン問題は、一人のセールスマンが多数の街を巡回することになっているが、これでは過重労働になり、過労死するかも知れない。

ということで、セールスマンを増員してみよう。

2人のセールスマンは、いずれもセンター(基地、本社、本部、、、、何と呼んでも良いのだが)から出発して、全ての街をいずれかのセールスマンが立ち寄り、二人とも出発点のセンターに戻ってくるとする。

2人の負荷はできるだけ差が少ないことが望ましい。それで、各人の経路長の差を少なくしたい。かつ、各人の経路長も短くしたい。

それで、平均経路長+経路長の差 をできるだけ小さく(短く)することにしてみた。

すると、こんな結果が得られた。

100-2-2-2202-s.png    100-2-2-2120-s.png

左は赤と青の巡路が分かれているが、右は巡路が交叉している。

点の位置は同じになっているのだが、どちらが 平均経路長+経路長の差 が小さくなっている、つまり望ましいプランであろうか?

この場合、交差している方が良い結果になっている。

一般には、良い結果の場合は、だいたい巡回する個所が左のように分離するのが普通だけれど、かならずしもそうなる訳ではない。

さて、2人巡回セールスマン問題は、どういう風にすれば良いのだろうか。

次回に説明しようと思う。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/750

コメントする

このブログ記事について

このページは、fujiが2018年12月 5日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「戻ってこない巡回セールスマン問題」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ