地点間の移動時間がわかっているときの巡回セールスマン問題の解き方

Question

地点間の移動時間がわかっているときの巡回セールスマン問題の解き方について
pythonで実装する方法を考えています。

現在総当たり手法を用いて計算していますが、
それではオーダーが階乗であるため地点数が増えれば対応できなくなります。

現在npyファイルに
地点間の移動時間[秒]を
[[定義なし,2.63,6.52,5.34],
[2.63,定義なし,5.87,4.32],
[6.52,5.87,定義なし,7.87],
[5.34,5.87,7.87,定義なし]]
のように格納しているファイルを持っています。
地点数は全部で１５０地点ほどあり、
それぞれ[shop1,shop2,....,shop150]のように
IDとして取り込んでいます。

この150店舗のうち指定したN店舗に関して
巡回セールスマン問題を解く方法を考えています。

入力は
指定する店舗>>>>[shop3,shop5,shop8,...,shop50]
制限時間>>>>7200[秒]
それぞれの店での滞在時間>>>>360[秒]
のようにすると
出力として
[所要時間,行先順路]
が一覧で出てくるようにしたいです。
この候補は条件を指定した店舗の全部を行くパターンまたは一部を行くパターンでその最短経路を出力できているようにします。

この巡回セールスマン問題を素早く方法として
遺伝的アルゴリズムを提案されましたが、
自分の実装力では実装しきれないのと
いまいち今回のパターンにあてはまるソースコードを見つけられず苦戦しています。
参考URL
http://blog.livedoor.jp/komq/archives/1012592617.html

ご協力いただけると幸いです。

Answer 1

そもそも巡回セールスマン問題は NP困難であって、はなから時間のかかるシロモノです。
それだけに高速化の為の手法は多く考案されており、遺伝的アルゴリズムに頼らずとも（数学的手法で）いくつもあります。
また、必ずしも厳密な最適解にこだわらないのであれば、多項式時間で近似できるアルゴリズムも研究されています。

ただ、一つ問題があって、たいていの高速なアルゴリズムでは前提条件として「いかなる2点であっても、直接結んだ場合は第3点を経由するより早く到達できる」が成立している必要があります。が、これ現実に考えるとそうとも言えないのですね。
※道北から道南へ移動する場合とか、道内を列車移動するより羽田経由の飛行機移動×2の方が早い場合があるとか…

ここなんか python でデモしてますからよいかもですね。いろいろなアルゴリズムで試されています。
http://www.geocities.jp/m_hiroi/light/pyalgo62.html