Comments
Description
Transcript
サービス科学：理論と実践 サービスの最適設計 最適化法
サービス科学：理論と実践 サービスの最適設計 最適化法 筑波大学システム情報工学研究科 吉瀬章子 サービス科学における最適化モデル スケジューリングを例として １ スポーツスケジューリングとは？ 現状の問題点： 数理的手法の必要性 数理的手法を実際に用いた例 1993年Ｊリーグのスケジュール 最適化問題とは？整数計画問題とは？ 2 サービス科学における最適化モデル スケジューリングを例として ２ アスベスト除去工事日程作成 最適化モデルを作成しよう SCM，ロジスティクス工学 3 スポーツスケジューリングとは？ スポーツ競技での「品質のよい」スケジュールを作成 する． 「品質のよい」スケジュールとは？ スポーツにおいて,勝敗と収益はスケジュールに負う ところが大 昨年のプロ野球日本シリーズ サッカーにおけるサポーター動員数 消化試合の観客動員数,視聴率 4 品質のよいスケジュールとは？ 試合の可能性 無理のない日時，競技 場の割り当て チーム間の公平性 本拠地試合、遠征試合 回数 移動コスト テレビ放送枠 経費の削減 移動コスト 競技場の割り当て 集客力の向上 人気カードと曜日 チーム間の力 消化試合数の低減 5 手作業スケジューリングは可能？ 10チームリーグ戦6日目までスケジュールを作成 7日目にA-Ｈ戦,Ｂ－Ｅ戦を組みたい １ ２ ３ ４ ５ ６ ７ Ａ：Ｊ Ｉ Ｅ Ｆ Ｇ Ｂ Ｂ：Ｉ Ｊ Ｇ Ｈ Ｃ Ａ Ｃ：Ｈ Ｆ Ｉ Ｊ Ｂ Ｄ Ｄ：Ｇ Ｅ Ｊ Ｉ Ｈ Ｃ Ｅ：Ｆ Ｄ Ａ Ｇ Ｉ Ｈ Ｆ：Ｅ Ｃ Ｈ Ａ Ｊ Ｇ Ｇ：Ｄ Ｈ Ｂ Ｅ Ａ Ｆ Ｈ：Ｃ Ｇ Ｆ Ｂ Ｄ Ｅ Ｉ：Ｂ Ａ Ｃ Ｄ Ｅ Ｊ Ｊ：Ａ Ｂ Ｄ Ｃ Ｆ Ｉ ８ ９ 残り対戦相手 ＣＤＨ ＤＥＦ ＡＥＧ ＡＢＦ ＢＣＪ ＢＤＩ ＣＩＪ ＡＩＪ ＦＧＨ ＥＧＨ 6 手作業スケジューリングは可能？ 10チームリーグ戦6日目までスケジュールを作成 7日目にA-Ｈ戦,Ｂ－Ｅ戦を組みたい １ Ａ：Ｊ Ｂ：Ｉ Ｃ：Ｈ Ｄ：Ｇ Ｅ：Ｆ Ｆ：Ｅ Ｇ：Ｄ Ｈ：Ｃ Ｉ：Ｂ Ｊ：Ａ ２ Ｉ Ｊ Ｆ Ｅ Ｄ Ｃ Ｈ Ｇ Ａ Ｂ ３ Ｅ Ｇ Ｉ Ｊ Ａ Ｈ Ｂ Ｆ Ｃ Ｄ ４ Ｆ Ｈ Ｊ Ｉ Ｇ Ａ Ｅ Ｂ Ｄ Ｃ ５ Ｇ Ｃ Ｂ Ｈ Ｉ Ｊ Ａ Ｄ Ｅ Ｆ ６ ７ ８ Ｂ Ｈ Ａ Ｄ Ｃ Ｈ Ｇ Ｆ Ｅ Ａ Ｊ Ｉ ９ 残り対戦相手 ＣＤＨ ＤＥＦ ＡＥＧ ＡＢＦ ＢＣＪ ＢＤＩ ＣＩＪ ＡＩＪ ＦＧＨ ＥＧＨ 7 手作業スケジューリングは可能？ 10チームリーグ戦6日目までスケジュールを作成 7日目にA-Ｈ戦,Ｂ－Ｅ戦を組みたい １ Ａ：Ｊ Ｂ：Ｉ Ｃ：Ｈ Ｄ：Ｇ Ｅ：Ｆ Ｆ：Ｅ Ｇ：Ｄ Ｈ：Ｃ Ｉ：Ｂ Ｊ：Ａ ２ Ｉ Ｊ Ｆ Ｅ Ｄ Ｃ Ｈ Ｇ Ａ Ｂ ３ Ｅ Ｇ Ｉ Ｊ Ａ Ｈ Ｂ Ｆ Ｃ Ｄ ４ Ｆ Ｈ Ｊ Ｉ Ｇ Ａ Ｅ Ｂ Ｄ Ｃ ５ Ｇ Ｃ Ｂ Ｈ Ｉ Ｊ Ａ Ｄ Ｅ Ｆ ６ ７ ８ Ｂ Ｈ Ａ Ｅ Ｄ Ｃ Ｈ Ｂ Ｇ Ｆ Ｅ Ａ Ｊ Ｉ ９ 残り対戦相手 ＣＤＨ ＤＥＦ ＡＥＧ ＡＢＦ ＢＣＪ ＢＤＩ ＣＩＪ ＡＩＪ ＦＧＨ ＥＧＨ 8 手作業スケジューリングは可能？ 10チームリーグ戦6日目までスケジュールを作成 7日目にA-Ｈ戦,Ｂ－Ｅ戦を組みたい １ Ａ：Ｊ Ｂ：Ｉ Ｃ：Ｈ Ｄ：Ｇ Ｅ：Ｆ Ｆ：Ｅ Ｇ：Ｄ Ｈ：Ｃ Ｉ：Ｂ Ｊ：Ａ ２ Ｉ Ｊ Ｆ Ｅ Ｄ Ｃ Ｈ Ｇ Ａ Ｂ ３ Ｅ Ｇ Ｉ Ｊ Ａ Ｈ Ｂ Ｆ Ｃ Ｄ ４ Ｆ Ｈ Ｊ Ｉ Ｇ Ａ Ｅ Ｂ Ｄ Ｃ ５ Ｇ Ｃ Ｂ Ｈ Ｉ Ｊ Ａ Ｄ Ｅ Ｆ ６ Ｂ Ａ Ｄ Ｃ Ｈ Ｇ Ｆ Ｅ Ｊ Ｉ ７ ８ Ｈ Ｅ Ｇ Ｂ Ｃ Ａ ９ 残り対戦相手 ＣＤＨ ＤＥＦ ＡＥＧ ＡＢＦ ＢＣＪ ＢＤＩ ＣＩＪ ＡＩＪ ＦＧＨ ＥＧＨ 9 手作業スケジューリングは可能？ 10チームリーグ戦6日目までスケジュールを作成 7日目にA-Ｈ戦,Ｂ－Ｅ戦を組みたい １ Ａ：Ｊ Ｂ：Ｉ Ｃ：Ｈ Ｄ：Ｇ Ｅ：Ｆ Ｆ：Ｅ Ｇ：Ｄ Ｈ：Ｃ Ｉ：Ｂ Ｊ：Ａ ２ Ｉ Ｊ Ｆ Ｅ Ｄ Ｃ Ｈ Ｇ Ａ Ｂ ３ Ｅ Ｇ Ｉ Ｊ Ａ Ｈ Ｂ Ｆ Ｃ Ｄ ４ Ｆ Ｈ Ｊ Ｉ Ｇ Ａ Ｅ Ｂ Ｄ Ｃ ５ Ｇ Ｃ Ｂ Ｈ Ｉ Ｊ Ａ Ｄ Ｅ Ｆ ６ Ｂ Ａ Ｄ Ｃ Ｈ Ｇ Ｆ Ｅ Ｊ Ｉ ７ ８ Ｈ Ｅ Ｇ Ｆ Ｂ Ｄ Ｃ Ａ ９ 残り対戦相手 ＣＤＨ ＤＥＦ ＡＥＧ ＡＢＦ ＢＣＪ ＢＤＩ ＣＩＪ ＡＩＪ ＦＧＨ ＥＧＨ 10 手作業スケジューリングは可能？ 10チームリーグ戦6日目までスケジュールを作成 7日目にA-Ｈ戦,Ｂ－Ｅ戦を組みたい １ Ａ：Ｊ Ｂ：Ｉ Ｃ：Ｈ Ｄ：Ｇ Ｅ：Ｆ Ｆ：Ｅ Ｇ：Ｄ Ｈ：Ｃ Ｉ：Ｂ Ｊ：Ａ ２ Ｉ Ｊ Ｆ Ｅ Ｄ Ｃ Ｈ Ｇ Ａ Ｂ ３ Ｅ Ｇ Ｉ Ｊ Ａ Ｈ Ｂ Ｆ Ｃ Ｄ ４ Ｆ Ｈ Ｊ Ｉ Ｇ Ａ Ｅ Ｂ Ｄ Ｃ ５ Ｇ Ｃ Ｂ Ｈ Ｉ Ｊ Ａ Ｄ Ｅ Ｆ ６ Ｂ Ａ Ｄ Ｃ Ｈ Ｇ Ｆ Ｅ Ｊ Ｉ ７ ８ Ｈ Ｅ Ｇ Ｆ Ｂ Ｄ Ｃ Ａ 対戦不能 対戦不能 ９ 残り対戦相手 ＣＤＨ ＤＥＦ ＡＥＧ ＡＢＦ ＢＣＪ ＢＤＩ ＣＩＪ ＡＩＪ ＦＧＨ ＥＧＨ 11 現状の問題点 多くの場合手作業で作成 全てのスケジュールは考慮できない 公平性、最適性についても不明 作成に膨大な時間（Jリーグで半年程度） 急な変更に対処できない 数理的な手法を用いたアプローチの必要性 12 数理的手法を用いたアプローチの必要性 数理的な手法を用いることにより 制約を満たすスケジュールを短時間で 作成できる 公平性，最適性も考慮できる 最適化問題としてモデル化することにより， 条件の変化にも容易に対応できる 13 数理的手法を実際に用いた例（米国ＭＬＢ） 26週間の間に30球団による2430試合を 開催 公募採用の外部業者が受託 1982–2004 ：マサチューセッツ在住の 夫婦に依頼． 2005：はカーネギーメロン大学のTrick 教授のグループが作成． (2004年にスケジュール作成会社を起 業) 参考：読売新聞夕刊(2004年11月9日付) 朝日新聞夕刊(2005年4月12日付) 14 数理的手法を実際に用いた例（Ｊリーグ） 1993 年に開幕10 チームから拡大 2008年はJ1 18 チーム 参考： 宮代隆平, 松井知己, 「1993年Jリーグの再スケジューリング」 オペレーションズ・リサーチ 45 (2000) 81－83 15 1993年Jリーグのスケジュール 18期10チーム 影は遠征試合を示す http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/POWER-POINT/sports-miya/10 参照 ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ 16 土曜日に着目 http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/POWER-POINT/sports-miya/10 参照 ① Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ ③ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ ⑤ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ ⑦ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ ⑨ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ ⑪ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ ⑬ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ ⑮ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ ⑰ Ｓ ← チームＫの場合， Ｇ 本拠地での土曜の試合は， Ｆ ⑤の次は⑮． Ｒ ⑤は 5 月 29 日で， Ｎ ⑮は 7 月 3 日． Ｋ 一ヶ月以上も間が開く Ｍ 水曜日だけ見ても同様． Ｖ Ｊ Ｅ 17 1993年Jリーグのスケジューリング における問題点（松井,宮代2000） 特定のチームのみ、3連続遠征試合がある 特定のチームのみ、土曜日の本拠地での試合間隔 が１ヶ月以上ある 本拠地を共有するチームに対する無配慮 etc. 18 計算機を用いて,条件にあう全てのスケジュー ルを列挙できないか？ 10チームの二重総当り戦に対して スケジュール数は 18！（≒6400兆） 以上 1秒間に1億個のスケジュールが生成できる （仮想的な）計算機で 2年 計算機は万能ではない 数理的手法（整数計画法）で効率よく計算 19 最適化問題とは？ いくつかの制約のもとで 目的関数を最小化（あるいは最大化）する問題 線形計画問題，整数計画問題，… 最小化 f ( x) 制約 g i ( x) ≤ 0 (i = 1,2,..., m) x∈ X 20 整数計画問題とは？ 最適化問題のひとつ 変数は「整数」に限定される 難しい問題 n 最小化 ∑cjxj j =1 n 制約 ∑a j =1 ij x j = bi (i = 1,2,..., m) x j ( j = 1,2,..., n) は整数 21 スポーツスケジューリングにおける整数計画問題１ 変数について 以下の変数を用意すれば,スケジューリング問題を整 数計画問題として記述できる t 期に ⎧1 チーム iとチーム j が ⎪ xijtp = ⎨ 場所pで試合をする ⎪0 それ以外 ⎩ ただし、対戦(i,j)において, iの本拠地で試合を行う場合p=1, jの本拠地で試合を行う場合p=2 とする 22 スポーツスケジューリングにおける整数計画問題２ もっとも単純な一重総当り戦を生成するための 制約と目的関数 総当り戦の制約 すべての対戦組み合わ せ(i,j)(i>j)について, ある期tに,ある場所pで 必ず１回試合する すべての期tにおいて, 各チームkは必ず１回試 合する n −1 ∑ ∑x p =1, 2 t =1 ijtp ∑ ∑x p =1, 2 ( k , j ) k> j kjtp =1 + ∑ ∑x p =1, 2 ( i , k ) i >k iktp =1 目的関数は予測観客 動員数，移動距離など 23 スポーツスケジューリングにおける整数計画問題３ A,B,C,Dの4チームの総当り戦を生成する整数計画問題 最小化 0 制約 x x x x x x AB11 + x AB12 + x AB 21 + x AB 22 + x AB 31 + x AB 32 = 1, AC11 + x AC12 + x AC 21 + x AC 22 + x AC 31 + x AC 32 = 1, AD11 + x AD12 + x AD 21 + x AD 22 + x AD 31 + x AD 32 = 1, BC11 + x BC12 + x BC 21 + x BC 22 + x BC 31 + x BC 32 = 1, BD11 + x BD12 + x BD 21 + x BD 22 + x BD 31 + x BD 32 = 1, CD11 + xCD12 + xCD 21 + xCD 22 + xCD 31 + xCD 32 = 1, 変数はすべて0 - 1整数, x x x x x x x x x x x x AB11 + x AB12 + x AC11 + x AC12 + x AD11 + x AD12 = 1, AB 21 + x AB 22 + x AC 21 + x AC 22 + x AD 21 + x AD 22 = 1, AB 31 + x AB 32 + x AC 31 + x AC 32 + x AD 31 + x AD 32 = 1, AB11 + x AB12 + x BC11 + x BC12 + x BD11 + x BD12 = 1, AB 21 + x AB 22 + x BC 21 + x BC 22 + x BD 21 + x BD 22 = 1, AB 31 + x AB 32 + x BC 31 + x BC 32 + x BD 31 + x BD 32 = 1, AC11 + x AC12 + x BC11 + x BC12 + xCD11 + xCD12 = 1, AC 21 + x AC 22 + x BC 21 + x BC 22 + xCD 21 + xCD 22 = 1, AC 31 + x AC 32 + x BC 31 + x BC 32 + xCD 31 + xCD 32 = 1, AD11 + x AD12 + x BD11 + x BD12 + xCD11 + xCD12 = 1, AD 21 + x AD 22 + x BD 21 + x BD 22 + xCD 21 + xCD 22 = 1, AD 31 + x AD 32 + x BD 31 + x BD 32 + xCD 31 + xCD 32 = 1. 24 整数計画法の解の求め方 各種ソフトウェアの活用 ただしソフトウェアも万能ではない 数学的構造を利用して 計算機の負担を軽くする 問題をサイズの小さな子問題に分割, 無駄な計算の除去, etc… 25 提案されたスケジュール（松井,宮代２０００） http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/POWER-POINT/sports-miya/10 参照 ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ Ｒ Ｇ Ｓ Ｊ Ｅ Ｍ Ｎ Ｖ Ｆ Ｋ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ Ｓ Ｊ Ｅ Ｍ Ｖ Ｋ Ｇ Ｆ Ｒ Ｎ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ Ｆ Ｒ Ｊ Ｓ Ｍ Ｅ Ｋ Ｎ Ｇ Ｖ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ Ｊ Ｎ Ｆ Ｇ Ｋ Ｒ Ｍ Ｅ Ｖ Ｓ Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ Ｒ Ｇ Ｓ Ｊ Ｅ Ｍ Ｎ Ｖ Ｆ Ｋ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ Ｓ Ｊ Ｅ Ｍ Ｖ Ｋ Ｇ Ｆ Ｒ Ｎ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ Ｆ Ｒ Ｊ Ｓ Ｍ Ｅ Ｋ Ｎ Ｇ Ｖ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ Ｊ Ｎ Ｆ Ｇ Ｋ Ｒ Ｍ Ｅ Ｖ Ｓ Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ 26 提案されたスケジュール（土曜日のみ） http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/POWER-POINT/sports-miya/10 参照 ① Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ ③ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ ⑤ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ ⑦ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ ⑨ Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ ⑪ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ ⑬ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ ⑮ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ ⑰ Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ 土曜日だけ見たときでも， 遠征試合の連続を 最大２回までに抑えている． 27 日本経済新聞2001.3.4【32面】 自動作成ソフト 隠れたＭＶＰに 1 両ステージとも優勝決定が最終節までもつれた昨年のＪ リーグに、隠れたＭＶＰがいた。 正式名称「Ｊリーグ・スケジュール・オプティマイザー」。 関係者は親しみを込めて「日程くん」の通称で呼ぶ。 Ｊリーグは昨年、Ｊ１の日程を作成するコンピューターソフ トを業者と共同した。生み出されたのが日程くんだ。 日本リーグ時代から手作業で作ってきた組み合わせが、 わずか15分で10通りがはじき出されるようになった。 28 日本経済新聞2001.3.4【32面】 自動作成ソフト 隠れたＭＶＰに 2 日程作りは、様々な条件に縛られる。 ホームでの試合が続かないようにしたり、 客足の鈍いホーム試合の平日開催を均等に分けたり。 日程くんに課せられているのは、観客を増やす日程作り。 どのチームはどういう条件の時に観客が多いか のデータを取り込み、最適の日程を探す。 29 日本経済新聞2001.3.4【32面】 自動作成ソフト 隠れたＭＶＰに 3 昨季、日程くんが作ったスケジュールが リーグを盛り上げた。 第２ステージ優勝の鹿島は 第14節に２位Ｇ大阪、 最終節にも２位柏と直接対決。 第１ステージ第14節には、 優勝を争った横浜ＭとＣ大阪が対戦。 日程くんが陰のＭＶＰと呼ばれるのも納得がいく。 30 デイリースポーツ2006.11.29 カズ 来季Ｊ１開幕は横浜ダービー!? 1 http://daily.jp/soccer/2006/11/29/000017929 1.shtml Ｊリーグの対戦日程はコンピューターソフトの「Ｊリー グマッチスケジューラー」 （愛称・日程クン）に、各ク ラブの要望（スタジアム使用の可否）や同一地域での 試合が重複しないなど、さまざまな条件をインプットし、 対戦カードが決定される。 今季のＪ１は１２月２日で全日程が終了。そこから入 れ替え戦でどちらが勝ってもいいように、２パターンの 日程を作る。 31 デイリースポーツ2006.11.29 カズ 来季Ｊ１開幕は横浜ダービー!? 2 条件が複雑すぎると“日程クン”は約９０時間もの稼働 の末に「答えはありません」の無情な回答を出すこと もあるという。 ０４年から約２０００万円をかけて導入された“日程ク ン”は、昨季は優勝を争う５チームの直接対決がない ドラマを生み、今季は浦和対Ｇ大阪の最後の大一番 を演出した。 そんな優秀な“日程クン”だが、開幕カードなど人為的 に“条件”を入力することも可能で、「ダービーなら盛り 上がる」（関係者）という声も上がっている。 32 サービス科学における最適化モデル スケジューリングを例として ２ アスベスト除去工事日程作成 最適化モデルを作成しよう SCM，ロジスティクス工学 33 様々な「サービス」に見る最適化モデル: アスベスト工事における研究室移動距離最小スケジュール ８月 工区 10 13 14 55 56 57 49 50 51 19 19 20 32 33 60 ９月 室番号 E209 E210 E310 F416 F1115 F1004 F1011 F1031 F1109 F1134 F1208 F1216 F1230 室名 移転用空室 移転用空室 物品保管室 移転用空室 移転用空室 移転用空室 移転用空室 移転用空室 移転用空室 移転用空室 移転用空室 移転用空室 移転用空室 面積２５日着工 5 1 0 1 5 2 120 58 58 56 56 19 19 19 19 19 19 19 19 F1116 F1117 F1015 F1016 F1017 3C306 3C305 3C307 F716 F717 F1135 研究室 共同端末利用室 研究室 研究室 研究室 研究室 研究室 研究室 研究室 研究室 研究室 56 55 56 56 55 122 29 61 56 55 56 １０月 2 5 1 15 2 １１月 25 5 1 1 2 １２月 2 5 1 1 2 2 34 様々な「サービス」に見る最適化モデル: アスベスト工事における研究室移動距離最小スケジュール 工事の前提条件 すでに各室の工事日程は決まっている． 研究室を工事する場合は移動用空室に物品を 移動させて工事を行う． なるべく移動距離は小さくしたい． 特にエレベータによる移動は短時間で済ませたい 各研究室をどの空室に割り当てるべきか？ 35 様々な「サービス」に見る最適化モデル: アスベスト工事における研究室移動距離最小スケジュール モデル化の際に考えるべきポイント 各室とも移動は一回のみで終えたい （工事途中で再度移動するようなことは避けたい） 各研究室の広さに応じて十分な広さの空室を割り当て たい 大きな空室は数が限られているので，小さな空室を組 合わせて利用したい 最適化モデルを作成してみよう 36 研究室割当てスケジュールの最適化モデル 使用できるデータ NLab = 1..32 NRoom = 1..12 NTerm = 1..29 工事予定の実験室の数 工事で利用できる空部屋の 工事期間 From: array(NLab) of integer To: array(NLab) of integer 各研究室の工事開始期 各研究室の工事終了期 LabArea: array(NLab) of real 各実験室の面積 RoomArea: array(NRoom) of real 各空部屋の面積 Dist: array(NRoom,NLab) of real 各空部屋と各実験室の距離 37 研究室割当てスケジュールの最適化モデル 決定変数 （決定変数） x: array(NTerm,NRoom,NLab) of mpvar t期に空室iを研究室jが使用する x(t,i,j)=1 使用しない x(t,i,j)=0 （補助変数） MovD: array(NLab) of mpvar 各実験室の移動距離（工期開始時） 38 研究室割当てスケジュールの最適化モデル 制約1 変数 x(t,i,j) に対する0-1整数制約 forall(t in NTerm, i in NRoom, j in NLab) x(t,i,j) is_binary 各実験室について工事期間中は同じ空部屋が割り当てられる forall(j in NLab) do forall(t in NTerm, i in NRoom | (t >= From(j)) and (t <= To(j)-1)) x(t,i,j) = x(t+1,i,j) end-do 各期，各空部屋について，割り当てられる実験室は１つのみ forall(t in NTerm, i in NRoom) sum(j in NLab) x(t,i,j) <= 1 39 研究室割当てスケジュールの最適化モデル 制約2 各実験室の工事開始期に，実験室の面積の34％以上の 面積の空室（複数可)が割り当てられる forall(j in NLab) sum(i in NRoom) (RoomArea(i) * x(From(j),i,j)) >= 0.34 * LabArea(j) 40 研究室割当てスケジュールの最適化モデル 目的関数 目的関数=総移動距離 各実験室の移動距離 MovD(j)は、 工事開始期に割り当てられた空部屋との距離 総移動距離はMovD(j)の総和 forall(j in NLab) MovD(j) = sum(i in NRoom) Dist(i,j) * x(From(j),i,j) MovDSum := sum(j in NLab) MovD(j) 目的関数を最小化 minimize(MovDSum) 結果の出力 41 様々な「サービス」に見る最適化モデル： サプライ・チェイン・マネジメント（SCM） SCM： NP-困難性と不確実性を伴うため， 様々な最適化手法の導入が必要となる． SCMに対する最適化システムのエキスパート 東京海洋大学 久保幹雄 助教授 適用可能な最適化モデルの階層 ネットワーク最適化（次の授業で） 整数計画法（数理計画実習後半で） Lagrange緩和，Dantzig分解原理（多少専門的） メタヒューリスティック（技術に加え経験も重要） 42 平成２０年１月２３日 平成１９年度第３学期 筑波大学大学院経営・政策科学専攻 サービス科学：理論と実践 小テスト 学籍番号： 氏名： アスベスト工事にあたり，各研究室をどの空室に割り当てるべきか？ 以下の 6 つの条件を考慮した最適化モデルを作成するアイディアを述べよ． 1. すでに各室の工事日程は決まっている． 2. 研究室を工事する場合は移動用空室に物品を移動させて工事を行う． 3. なるべく移動距離は小さくしたい． 4. 各室とも移動は一回のみで終えたい． 5. 各研究室に応じて十分な広さの空室に割り当てたい． 6. 大きな空室は数が限られているので，小さな空室を組合せて各研究室の広さをカバーでき るように利用したい． January 23, 2008 Academic Year 2007 Third Term, MBA/MPP Program, U. of Tsukuba Service Science: Theory and Practice Quiz Student ID: Name: How can we assign each office to vacancies to continue the works? Describe your idea to build an optimization model considering the following 6 constraints. 1. The schedule of the works has been fixed. 2. All equipments in the office have to be moved to vacancies during the work. 3. Minimize the total traveling distance. 4. Each office will be moved just once. 5. Each office will be assigned to sufficiently extensive vacancies. 6. The number of large vacancies is limited. We have to combine several small rooms to cover whole space of an office.