最適化問題解決に Open なブースター ~ 踏み出せ 予測モデリングの一歩先へ ~ SAS Institute Japan 株式会社ソリューション統括本部 OSSイノベーション推進室葉陽
Who am I スポーツ興行需要予測収入最適化 リテール需要予測製造業自動報告書作成
1. 最適化とは 2. ネットワークの最適化 3. 最適化の事例 4. 近年最適化トレンド
1. 最適化とは 一般論最適化問題手法
一般論限られた条件の中で ある数値関係の最小値または最大値を求めること
シャトルバス収入問題 : 単価 :15 ドル チケット販売数 :1,200 枚 / 日 現在収入 : 15*1,200 = 18,000 ドル R( 収入 ) = Q( 販売数 )*P( 単価 ) Q( 販売数 ) = (P-15)*(-50)+1200 1950-50P R( 収入 ) = P*(1950-50P)
収入 単価 販売数 収入 0 1,950 0 20000 18000 16000 1 1,900 1,900 14000 2 1,850 3,700 12000 3 1,800 5,400 10000 8000 19.50 975 19,012.50 6000 36 150 5,400 4000 2000 37 100 3,700 38 50 1,900 0 1 5 9 13 15 17 21 25 29 33 37 19.50 単価 39 0 0
一般論 条件または制約 ある数値関係の最小値または最大値 Constraints Target 単価と販売数の関係 バスに乗せれる人数 適正価格範囲 等々 収益の最大化
実ビジネスの様々な最適化問題 工場主の意思決定 消費者の購買行為 小売業の価格最適化 等々
最適化の手法 1.LP( 線形計画法 ) 2.ILP( 整数計画法 ) 3.MIP( 混合整数線形計画法 ) 4.NLP( 非線形計画法 ) : シンプレックス法 : 分枝切除法 : 分枝切除法 : ローカルサーチ ニュートン法
2. ネットワークの最適化 デモ1 : コンビニ配置問題 デモ2 : 巡回セールスマン問題
デモ :5 つコンビニ配置問題 Aさん住所 : 東経 139 北緯 35 候補地 2: 東経 139.2 北緯 35.2 候補地 1: 東経 139.1 北緯 35.1 候補地 住居 アクセスルート 矢印 出典 :Google Map
デモ :5 つコンビニ配置問題 緯度 Aさん住所 : 東経 139 北緯 35 候補地 2: 東経 139.2 北緯 35.2 候補地 1: 東経 139.1 北緯 35.1 候補地 住居 アクセスルート 矢印 経度
デモ :5 つコンビニ配置問題 緯度 Aさん住所 : 東経 139 北緯 35 候補地 1: 東経 139.1 北緯 35.1 候補地 住居 アクセスルート 矢印 経度
デモ :5 つコンビニ配置問題 A さん住居 (15, 63) 北緯 139.1234 東経 35.1234
デモ :5 つコンビニ配置問題 2 3 J の可能性 :6 通り 1 j2 i3 j1 i4 4
デモ :5 つコンビニ配置問題 J の可能性 :6 通り j2 i3 j1 i4
デモ :5 つコンビニ配置問題 J の可能性 :6 通り j2 i3 j1 i4
デモ :5 つコンビニ配置問題 J の可能性 :6 通り j1 j2 i3 Ij の可能性 :4 通り i4
デモ :5 つコンビニ配置問題 2 3 X 判定 :j になるか 1 j2 i3 j1 Y 判定 :ij ペアになるか 1 通りの総距離計算 i4 4 24 通りの総距離比較
デモ :5 つコンビニ配置問題 X 判定 Y 判定 ネットワーク総距離の最小値 コンビニ数 :p 住居が必ず唯一の候補地へ繋ぐ
デモ :5 つコンビニ配置問題 物流センターの最適な設置場所 エネルギーパイプラインルート 地域の公共施設場所
デモ : 巡回セールスマン問題 ビジネス問題 : 日本のビジネスマンがアメリカで巡回展示会をすることに決めた 交通費と時間を抑えるために 最短ルートで巡りたいと考えている 最適化目標 : 49 都市を一通り回るための地図上での最短最速の直線ルートを探す
デモ : 巡回セールスマン問題 5 都市 24 通り 10 都市 26 万通り以上 15 都市 870 億通り以上 ルート組み合わせの和 :(n-1)!
都市緯度経度 デモ : 巡回セールスマン問題 city, lat, long "Albany, NY", 42.65255278, -73.75732222 "Annapolis, MD", 38.97861111, -76.49111111 "Atlanta, GA", 33.74927222, -84.38826111 "Augusta, ME", 44.30723611, -69.78167778 "Austin, TX", 30.27472222, -97.74055556 "Baton Rouge, LA", 30.45707222, -91.18740556 Bismarck, ND, 46.82081389, -100.7827417 "Boise, ID", 43.61769722, -116.1996139 "Boston, MA", 42.35770833, -71.06356389 "Carson City, NV", 39.164075, -119.7662917 "Charleston, WV", 38.33638889, -81.61222222 "Cheyenne, WY", 41.14027778, -104.8197222 "Columbia, SC", 34.00043333, -81.03314722 "Columbus, OH", 39.96138889, -82.99888889 "Concord, NH", 43.20674722, -71.53812778 "Denver, CO", 39.73909444, -104.9848972 Albany: Lat: 42.652552784 Long: -73.75732222 Annapolis: Lat: 38.97861111 Long: -76.49111111 リンク : Cities: Annapolis-Albany Distance:291.179205
都市緯度経度 デモ : 巡回セールスマン問題 city, lat, long "Albany, NY", 42.65255278, -73.75732222 "Annapolis, MD", 38.97861111, -76.49111111 "Atlanta, GA", 33.74927222, -84.38826111 "Augusta, ME", 44.30723611, -69.78167778 "Austin, TX", 30.27472222, -97.74055556 "Baton Rouge, LA", 30.45707222, -91.18740556 Bismarck, ND, 46.82081389, -100.7827417 リンクデータ Albany: Lat: 42.652552784 Long: -73.75732222 Annapolis: Lat: 38.97861111 Long: -76.49111111 リンク : Cities: Annapolis-Albany Distance: 291.179205
デモ : 巡回セールスマン問題 ビジネス計画 物流設計 スケジューリング
3. 最適化の事例 Nestlé 様 DBS Bank 様
Nestlé S.A. スイスにおける食品 飲料の大手企業 欧州における最優良企業 世界に 189 か所の事業拠点を持ち ローカル グローバル含め 2000 以上の商品ブランドを持つ Key Challenges チャネル統合 : リテール ディスカウント店 e コマース プロモーション効果の最大化 プロモーションのやり方によって投資回収が難しい時がある 需要予測の精度を高め 企業のキャッシュフローを支える How SAS supported the process Results SAS アナリティクスをサプライチェーンに活用 大規模分析を実現 SAS Viya で分析プラットフォームを先進化 実績ある SAS の機能を各地域の事業に適用し 小売注文管理最適化 財務予測 マーケティングミックス費用対効果最大化など幅広い課題を解決 SAS による予測数値を唯一の根拠とすることにより 月次計画に費やす時間を削減 Powered by SAS Advanced Analytics
DBS Bank シンガポール最大の銀行であり 1,100 の ATM から月 2,500 万回の取引が行われる Key Challenges ATM の現金不足発生による顧客への不便と銀行の現金輸送コスト増加 世界で最も ATM 利用率が高い国であるため ATM のダウンタイムは大変な不便を利用者にかけることになる How SAS supported the process Results SAS を ATM 現金引き出し予測に活用し 現金補充プロセスを最適化 個々の ATM の精確な現金引き出しパターン予測により ATM 網全体の現金補充スケジュール最適化モデルを策定 ATM の現金切れが 80% 削減 ATM 網への現金補充のための移動が 20% 削減 利用者待ち時間が年間 3 万時間以上削減 Powered by SAS Advanced Analytics 革新的なソリューションによって DBS は世界で初めて ATM 利用と顧客の行動データを活用し 非繁忙時間帯に現金を補充する作業計画を作成することができています David Gledhill Managing Director and Head of Group Technology and Operations
4. 近年最適化トレンド
近年の最適化トレンドに関して 従来の最適化手法 : 方程式 実現速度のメリット 厳密数値解法 近年新たな最適化トレンド : 近似ロジック ヒューリスティクス解法 計算速度のメリット 32
近年の最適化トレンドに関して 方程式ベースの厳密解法 強化学習 例 :AlphaGo 20000 20000 18000 18000 16000 16000 14000 14000 12000 12000 10000 10000 8000 8000 6000 4000 A 6000 4000 A 2000 2000 0 1 5 9 13 17 21 25 29 33 37 0 1 5 9 13 17 21 25 29 33 37 現実問題 方程式解 モデリング 限界あり
SAS R&D 近年の最適化トレンドに関して 深層強化学習 サプライチェーン在庫の最適化 全体コストを圧倒的に削減 トレーニングできたモデルをすぐ再学習可能 リアルタイムに利用可能 ダウンロード :https://arxiv.org/abs/1708.05924 今年度 SAS Viya の強化学習機能を公開