AI&数理最適化技術を用いたサプライチェーン最適化 - ログ・オプト -
研究者および技術者のプロフェッショナル集団です.
  • Home
  • Products
    • SCMOPT デモ&トライアル
    • サプライチェーン最適化システムSCMOPT
      • サプライ・チェイン基本分析
      • サプライ・チェインリスク分析
      • 需要予測
      • 需要予測+動的発注方策
      • 安全在庫最適化
      • 配送最適化
      • 幹線輸送ネットワーク最適化
      • ロジスティクス・ネットワーク最適化
      • 生産ロット最適化
      • 生産スケジューリング最適化システム
      • 人員配置(シフト)最適化
      • ダイナミックプライシング/収益最適化
    • 最適化ソルバー
      • 制約最適化ソルバーSCOP
      • スケジューリング最適化ソルバーOptSeq
      • 数理最適化ソルバーGurobi Optimizer
      • 配送最適化ソルバーMETRO
      • 集合被覆最適化ソルバーOptCover
  • Solutions
    • 分野別ソリューション
      • サプライ・チェイン
      • マーケティング
      • その他分野
    • コンサルティング
  • News/Blog
  • Resource
  • About us
    • 会社概要
    • プライバシーポリシー
    • 情報セキュリティポリシー
    • SCMOPTセキュリティー
    • 商品・サービス利用規約
  • Contact Us
    • お問い合わせ
    • 無料書籍申し込みフォーム
研究者および技術者のプロフェッショナル集団です
   

CHINESE ENGLISH

  • ENGLISH
  • CHINESE
巡回セールスマン問題の最先端
2021-02-18

巡回セールスマン問題の最先端

LogOpt その他, 最適化

組合せ最適化の代表的な問題の一つである巡回セールスマン問題の最先端について調べたものをまとめました.

巡回セールスマン問題の歴史から最先端まで分かりやすく解説した動画です.

巡回セールスマン問題( 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版(公式ページでダウンロード可能)があります.

concorde TSP

  

Concorde TSPで巡回セールスマン問題アルゴリズム紹介
巡回セールスマン問題をipadのConcorde TSPアプリで解く様子

  • 厳密解が見つかった問題例

VLSI応用問題:85,900点

スウェーデン巡回問題:24,978 点

ドイツ巡回問題:15,112点

詳細は公式ページをご覧ください.

画像公式ページ:http://www.math.uwaterloo.ca/tsp/optimal/index.html
画像公式ページ:http://www.math.uwaterloo.ca/tsp/optimal/index.html

  • 名画の巡回セールスマン問題 

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
画像公式ページ:http://www.math.uwaterloo.ca/tsp/data/art/index.html
画像公式ページ:http://www.math.uwaterloo.ca/tsp/data/art/index.html

 

モナリザ問題例(100,000点)は,2009年永田祐一さんによって計算された解が最良解で,その解(Tour)とBound(現段階でのこれ以上短いツアーがないという値)との誤差は0.0019%のようです.

モナリザTSP結果:Tour: 5,757,191 Bound: 5,757,084 Gap: 107 (0.0019%)

画像公式ページ:http://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html
画像公式ページ:http://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html

  • 世界ツアー巡回セールスマン問題

世界各地にある1,904,711点を回る問題例です.既存最良解は,2021年2月15日にKeld Helsgaunさんによって計算されており,既知のBoundとの誤差は0.0471% のようです.公式ページリンク

動画公式ページリンク http://www.math.uwaterloo.ca/tsp/world/index.html

  • 星の巡回セールスマン問題

欧州宇宙機関(ESA)との研究で,銀河系の星の3次元巡回セールスマン問題を解いているようです.公式ページリンク

画像公式ページリンク:http://www.math.uwaterloo.ca/tsp/star/index.html
画像公式ページリンク:http://www.math.uwaterloo.ca/tsp/star/index.html

Text content

動画公式ページリンク:http://www.math.uwaterloo.ca/tsp/star/index.html

公式ページの実験結果によると,星の数119,614の場合は厳密解,星の数13億の場合も既知のBoundとの誤差は0.0038のようです.

3D Star TSPs 実験結果

画像公式ページリンク:http://www.math.uwaterloo.ca/tsp/star/about.html
画像公式ページリンク:http://www.math.uwaterloo.ca/tsp/star/about.html

巡回セールスマン問題を高速に解くための手法(メタヒューリスティクス)が,弊社の最適化ソルバーでも使われています.

弊社で取り扱っている商品:

配送最適化ソルバー,配送最適化システム:各種制約付きの配送最適化問題を高速に求解可能

制約最適化ソルバーSCOP:大規模組合せ最適化問題を高速に求解可能

eg.人員配置最適化,生産スケジューリングなど

スケジューリング最適化ソルバーOptSeq:

eg. 生産スケジューリング,プロジェクトスケジューリングなど

PyCaretによる自動機械学習(AutoML) スケジューリング最適化ソルバーOptSeqを用いた事例論文

Related Posts

News, Python, その他, 実務, 最適化

「書籍」Pythonによる実務で役立つ最適化問題100+

News, Python, その他

「書籍」Python言語によるプログラミングイントロダクション 第3版

AI, SCMOPT, サプライ・チェイン, 実務, 最適化

サプライチェーンリスク解析の最先端

カテゴリー

  • AI
  • News
  • Python
  • SCMOPT
  • サプライ・チェイン
  • その他
  • 可視化
  • 実務
  • 最適化
AI&数理最適化技術を用いたサプライチェーン最適化 - ログ・オプト -
Copyright © 2019 Log Opt Co., Ltd.