巡回セールスマン問題の最先端
組合せ最適化の代表的な問題の一つである巡回セールスマン問題の最先端について調べたものをまとめました．
巡回セールスマン問題の歴史から最先端まで分かりやすく解説した動画です．
巡回セールスマン問題（ traveling salesman problem，TSP）は，都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき，全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める組合せ最適化問題です．（Wikipediaより）
巡回セールスマン問題は，非常に効率の良いアルゴリズムがあるため，規模の大きい問題例でも厳密解が得られることが多く，厳密解でなくても非常に精度の良い近似解が短時間で得られるようになっています．
The Traveling Salesman Problem （公式ページリンク）という巡回セールスマン問題，歴史，応用，最新研究が分かるページがあるので，いくつか面白いのをピックアップして紹介します．（The Traveling Salesman Problemはとても有名な最適化の研究者が運営するページです．）
-
ipadで巡回セールスマン問題を解く
ipadのconcorde TSPアプリのExact Solverで巡回セールスマン問題を解いてみました．
最適化計算はネット経由ではなく，全てipad内で計算しています．
厳密解の計算時間
| 問題例（点の数） | 計算時間 | |
| TSPLIB pr2392（2392点） | 40秒 | |
| TSPLIB usa532（532点） | 1分23秒 | |
| TSPLIB pr1000（1000点） | 22秒 | |
| ランダム（500点） | 9秒 | |
＊ランダム問題は点の配置によって計算時間が大きく異なる可能性があります．
アプリはAppストアでconcorde TSPと検索してインストールしました．他に，iPhone版（Appストアでダウンロード可能）とwindows版（公式ページでダウンロード可能）があります．
-
名画の巡回セールスマン問題
Robert Bosch さんが作った名画TSPです．これらの問題の厳密解はまだ見つかっておりません．詳細は公式ページをご覧ください．
| 名画 | 点の数 | |
| da Vinci’s Mona Lisa | 100,000 | |
| van Gogh’s Self Portrait 1889 | 120,000 | |
| Botticelli’s The Birth of Venus | 140,000 | |
| Velazquez’s Juan de Pareja | 160,000 | |
| Courbet’s The Desperate Man | 180,000 | |
| Vermeer’s Girl with a Pearl Earring | 200,000 | |
モナリザ問題例（100,000点）は，2009年永田祐一さんによって計算された解が最良解で，その解（Tour）とBound（現段階でのこれ以上短いツアーがないという値）との誤差は0.0019%のようです．
モナリザTSP結果：Tour: 5,757,191 Bound: 5,757,084 Gap: 107 (0.0019%)
-
世界ツアー巡回セールスマン問題
世界各地にある1,904,711点を回る問題例です．既存最良解は，2021年2月15日にKeld Helsgaunさんによって計算されており，既知のBoundとの誤差は0.0471% のようです．公式ページリンク
-
星の巡回セールスマン問題
欧州宇宙機関(ESA)との研究で，銀河系の星の３次元巡回セールスマン問題を解いているようです．公式ページリンク
Text content
公式ページの実験結果によると，星の数119,614の場合は厳密解，星の数13億の場合も既知のBoundとの誤差は0.0038のようです．
3D Star TSPs 実験結果
巡回セールスマン問題を高速に解くための手法（メタヒューリスティクス）が，弊社の最適化ソルバーでも使われています．
弊社で取り扱っている商品：
配送最適化ソルバー，配送最適化システム：各種制約付きの配送最適化問題を高速に求解可能
制約最適化ソルバーSCOP：大規模組合せ最適化問題を高速に求解可能
eg.人員配置最適化，生産スケジューリングなど
eg. 生産スケジューリング，プロジェクトスケジューリングなど