1. ナースプラクティショナーの人員配置
original case (English)
問題の背景
最近、ウィスコンシン大学（UW）ヘルスは、患者の病院再入院を減らすための取り組みを進めています。広範なデータ分析の結果、高齢者層は再入院の可能性が高いと結論付けられました。データによると、高齢患者の再入院の大部分は、病院を退院してから最初の1週間以内に発生しています。この層の再入院を減らす試みとして、UWヘルスは、専門看護施設（skilled nursing facilities）の患者を訪問し、必要に応じて適切なフォローアップケアを提供するためにナースプラクティショナー（NP）を雇用するという独自のプログラムに投資しました。
専門看護施設に退院したすべての患者を訪問することが極めて重要であるため、UWヘルスは最適な人数のナースプラクティショナーを確実に雇用する必要があります。この移行期ケアプログラムの下では、デーン郡地域にナースプラクティショナーが配置される9つの施設があり、合計で815床あります。各施設は民間によって運営されており、それぞれ固有のベッド数を持っています。下の図は施設の位置を示しています。各施設間の車での移動距離は表に記載されています。
| Capitol Lakes |
0 |
5.2 |
6.4 |
8.8 |
5.6 |
10.9 |
8.9 |
7 |
5 |
| Karmenta |
5.2 |
0 |
15.8 |
5.5 |
11.9 |
17.2 |
15.2 |
2.6 |
0.5 |
| Oakwood West |
6.4 |
15.8 |
0 |
20.9 |
3.4 |
3.4 |
5.4 |
15.5 |
14.6 |
| Oakwood East |
8.8 |
5.5 |
20.9 |
0 |
17.4 |
22.7 |
20.7 |
7 |
5.5 |
| Sunny Hill |
5.6 |
11.9 |
3.4 |
17.4 |
0 |
6 |
3.9 |
13 |
12.1 |
| Attic Angels |
10.9 |
17.2 |
3.4 |
22.7 |
6 |
0 |
6.3 |
17.9 |
17 |
| St. Mary’s |
8.9 |
15.2 |
5.4 |
20.7 |
3.9 |
6.3 |
0 |
15.9 |
15 |
| Oak Park |
7 |
2.6 |
15.5 |
7 |
13 |
17.9 |
15.9 |
0 |
2.9 |
| Belmont |
5 |
0.5 |
14.6 |
5.5 |
12.1 |
17 |
15 |
2.9 |
0 |
download csv file
このプログラムでは、ナースプラクティショナーは特定の施設に配置されます。私たちの最適化問題は、配置されたナースプラクティショナーがいる施設から半径3マイル以内に入る患者数を最大化するために必要なナースプラクティショナーの最小数を決定することと定義します。
この問題をモデル化するために、いくつかの仮定を置きます。
- 各ナースプラクティショナーは同じペースで働き、同じ数の患者を訪問できる。
- 移動時間ではなく、施設間の距離のみを考慮する。
2. シフト最適化
original case(English)
大学のキャンパスに新しい食品店がオープンしました。この店は年中無休、24時間営業となります。 毎日、3つの8時間シフトがあります。 朝番は6:00から14:00、夕番は14:00から22:00、夜勤は22:00から翌日の6:00までです。 夜間（夜勤）は従業員1名のみですが、日中（朝番と夕番）は2名です。ただし、日曜日は各シフトとも1名のみとなります。 各従業員の週労働時間は最大40時間を超えず、シフト間には12時間の休息を取らなければなりません。 週休日に関しては、ある日曜日に休む従業員は、その週の土曜日も同様に休むことが望ましいです。 原則として、利用可能な従業員は10名いますが、これは明らかに過剰人員です。 必要とされる従業員が少なければ少ないほど、他の店舗のためのリソースが多くなります。 １週間の最適なシフトを作成してください。
3. 中規模食品卸売業者の店舗配送ルート最適化
1. 背景と課題
「フレッシュデリバリー株式会社」は、地域のレストランや小規模小売店へ生鮮食品や加工品を卸している中規模の卸売業者です。自社の物流センター（デポ）から、保有する複数の保冷トラック（能力が異なる）を使って毎日配送を行っています。
現状の課題:
- 配送コストの増大: 燃料費の高騰に加え、ベテラン担当者の経験に頼った非効率なルート設定により、人件費（残業代含む）や車両維持費がかさんでいる。
- 時間指定の厳守: 顧客（店舗）からはランチやディナーの仕込みに間に合わせるため、厳しい納品時間帯（タイムウィンドウ）が指定されていることが多いが、遅延が発生することもある。
- 車両積載率のばらつき: 荷量の少ないルートに大型トラックを割り当ててしまうなど、車両の能力を有効活用できていない場合がある。
これらの課題を解決するため、数理最適化を用いて、総配送コスト（車両固定費＋変動費）を最小化し、かつ全ての顧客の時間指定を守る配送計画を作成することを目指します。
2. データ
3. 最適化モデルの目標と制約
- 目的関数:
- 最小化: Σ (使用するトラックの固定費) + Σ (各トラックの総走行距離 × 変動費)
- 主な制約条件:
- 車両割り当て: 各顧客は、いずれか1台のトラックによって、ちょうど1回訪問される。
- デポ発着: 使用される各トラックは、デポを出発し、全ての担当顧客を訪問後、デポに戻る。
- 積載容量: 各トラックに積み込まれる荷物の総量は、そのトラックの積載容量を超えない。
- 時間窓: 各顧客へのトラック到着時刻は、指定された納品時間窓内であること。
到着時刻 >= 時間窓開始時刻到着時刻 <= 時間窓終了時刻- 早く着きすぎた場合は、時間窓開始時刻まで待機する。
- 時間連続性: ある地点への到着時刻、荷降ろし時間、次の地点への移動時間を考慮し、次の地点への到着時刻を計算する。
次の地点への到着時刻 = max(現地点到着時刻, 時間窓開始時刻) + 荷降ろし時間 + 移動時間
- トラック稼働時間: (オプション) ドライバーの最大労働時間などを考慮することも可能。
4. 期待されるアウトプット (最適化ソルバーによる結果)
- 使用トラック: 最適なコストを実現するために使用するトラック (V1, V2, V3 のうちどれか、または全部)。
- 各トラックの担当顧客と訪問順序 (ルート):
- 例:
- トラックV1: デポ → C → A → デポ
- トラックV2: デポ → D → F → B → デポ
- トラックV3: デポ → E → デポ
- 各地点への到着・出発予定時刻:
- 例: トラックV1 - C店到着 10:15, C店出発 10:30, A店到着 11:12 (時間窓違反!), … のような詳細スケジュール。
- 総配送コスト: 最小化された総コスト (円)。
- 各トラックの走行距離と積載率:
5. ケーススタディの意義と実務への応用
このケーススタディは、複数の制約（時間、容量、コスト）が絡み合う複雑な配送計画問題を、数理最適化によってどのように解決できるかを示しています。
- コスト削減: 燃料費、人件費、車両固定費を最適化し、具体的な削減額を提示できる。
- サービス品質向上: 時間指定遵守により、顧客満足度を高める。
- 業務効率化: 配車計画作成にかかる時間を大幅に短縮し、属人化を解消できる。
- 資源の有効活用: トラックの積載率を向上させ、遊休車両を減らす。
- 意思決定支援: 新規顧客獲得時や車両増減時の影響をシミュレーションし、戦略的な意思決定を支援する。
4. 部品メーカーにおける月次生産計画最適化
1. 背景と課題
「テクノパーツ工業」は、自動車産業向けに2種類の精密部品（部品X、部品Y）を製造・販売している中小企業です。部品Xと部品Yは、それぞれ異なる原材料を使用し、工場内の2つの主要な工程（切断工程、組立工程）を経て完成します。
現状の課題:
- 利益最大化の難しさ: 部品XとYでは利益率が異なり、また各工程での加工時間も異なります。どの製品をどれだけ生産すれば、限られた資源（機械稼働時間、原材料在庫）の中で月間の総利益を最大化できるか、経験と勘に頼っており最適化されていない。
- ボトルネック工程の存在: 特定の工程（特に組立工程の機械）の稼働率が高く、生産全体の制約となっている可能性があるが、定量的に把握できていない。
- 原材料の過不足: 需要予測に基づいて原材料を発注しているが、生産計画の変動により、月末に特定の原材料が不足したり、逆に過剰在庫になったりすることがある。
これらの課題に対し、数理最適化を用いて、月間総利益を最大化する最適な部品Xと部品Yの生産量を決定することを目指します。
2. データ (月間)
製品情報:
| 部品X |
5,000 |
800 |
| 部品Y |
6,500 |
600 |
原材料情報:
| 材料P |
300 |
3,000 |
2.0 |
1.0 |
| 材料Q |
500 |
4,000 |
1.5 |
3.0 |
工程・機械情報:
| 切断 |
機械A |
400 |
0.15 (9分) |
0.20 (12分) |
2,000 |
| 組立 |
機械B |
350 |
0.25 (15分) |
0.30 (18分) |
3,000 |
その他:
- 生産量に関わらず発生する固定費は考慮しない（利益最大化の判断には影響しないため）。
3. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化が工場運営において以下の価値を提供することを示しています。
- 収益性の向上: 利益貢献度と資源消費を考慮した最適な製品ミックスを決定し、工場全体の収益性を最大化する。
- 資源の有効活用: ボトルネックとなっている資源（機械、原材料など）を特定し、その利用率を最大化する計画を立てる。また、余剰がある資源も可視化される。
- データに基づいた意思決定: 経験や勘ではなく、定量的なデータ分析に基づいて生産計画を立案できる。これにより、計画の客観性と再現性が向上する。
- 感度分析による柔軟な対応: 原材料価格の変動、機械の故障、需要の変化などが起きた場合に、最適化モデルを再実行することで、変化に対応した新しい最適計画を迅速に作成できる（What-if分析）。
5. 部品メーカーにおける3ヶ月生産・在庫最適化計画
1. 背景と課題の進化
「テクノパーツ工業」では、単月での生産計画最適化により一定の成果を上げましたが、新たな課題が浮上しました。
- 需要の季節変動: 部品Xは春先に、部品Yは初夏に需要が高まる傾向があり、単月計画では需要ピーク時に生産能力が追いつかず機会損失が発生したり、逆に需要閑散期に過剰生産してしまうリスクがあります。
- 原材料調達の変動: 主要な原材料Pのサプライヤーが、特定の月（例: 2月）にメンテナンスのため供給量を減らすと通知してきました。
- 在庫コスト: 製品在庫や原材料在庫を持つことには、倉庫スペースや管理のためのコストが発生します。
これらの課題に対応するため、今後3ヶ月間を見通した生産計画と在庫計画を同時に最適化し、3ヶ月間の総利益（売上 - 原材料費 - 加工費 - 在庫保管費）を最大化することを目指します。
2. データ (3ヶ月計画: 1月、2月、3月)
製品情報:
| 部品X |
5,000 |
700 |
600 |
900 |
50 |
| 部品Y |
6,500 |
500 |
700 |
650 |
60 |
- 初期在庫 (1月初め): 部品X: 50個, 部品Y: 30個
- 目標期末在庫 (3月末): 部品X: 80個, 部品Y: 50個 (安全在庫として)
原材料情報:
| 材料P |
300 |
3,000 |
2,000 |
3,000 |
10 |
2.0 |
1.0 |
| 材料Q |
500 |
4,000 |
4,000 |
4,000 |
15 |
1.5 |
3.0 |
- 初期在庫 (1月初め): 材料P: 200kg, 材料Q: 300kg
工程・機械情報 (各月共通):
| 切断 |
機械A |
400 |
0.15 |
0.20 |
2,000 |
| 組立 |
機械B |
350 |
0.25 |
0.30 |
3,000 |
3. ケーススタディの意義と実務への応用
この多期間モデルは、単期間モデルよりも現実に近い状況を扱えます。
- 需要変動への戦略的対応: 先行生産や在庫調整により、需要の波に柔軟に対応し、機会損失を最小化する。
- サプライチェーンリスクへの備え: 原材料供給の変動などを事前に計画に織り込むことで、生産停止リスクを低減する。
- 在庫コストの最適化: 過剰な在庫や欠品を防ぎ、製品・原材料の両方で最適な在庫レベルを維持する。
- キャッシュフローの改善: 生産、販売、在庫のバランスを取ることで、資金繰りを安定させる計画を立てられる。
- 中期的な視点での資源配分: 複数期間にわたる機械稼働や原材料調達を最適化し、工場全体の生産性を高める。
このような中期的な生産・在庫最適化計画は、企業の収益性向上と安定的な操業に不可欠であり、多くの製造業でSCM (サプライチェーンマネジメント) の一環として導入されています。
6. 新製品発売における広告キャンペーン最適化
1. 背景と課題
ある消費財メーカーのマーケティング部門は、新製品「スマートクリーンX」の発売にあたり、大規模な広告キャンペーンを計画しています。キャンペーンの総予算は1,000万円と限られており、この予算内で製品の認知度と初期売上を最大化するために、どの広告媒体にどれだけの予算を配分するかが重要な課題となっています。
担当者は、テレビCM、ラジオCM、新聞広告、Web広告（リスティング広告とSNS広告）、屋外広告など、複数の広告媒体を検討していますが、各媒体は費用、期待できる効果（ターゲット層へのリーチ数）、そして利用上の制約（最低出稿量や最大枠）が異なります。勘や経験だけに頼るのではなく、データに基づいて最適な予算配分を決定し、キャンペーン効果を最大化したいと考えています。
2. 目標
- 与えられた総予算1,000万円の範囲内で、広告キャンペーンによる総リーチ数（想定される接触人数）を最大化する。
3. 利用可能な広告媒体とデータ
マーケティング部門は、過去のデータや媒体社からの情報に基づき、以下のデータを収集しました。
| テレビCM |
TV |
1回 (15秒スポット) |
500,000 |
80,000 |
最大10回まで |
| ラジオCM |
Radio |
1回 (20秒スポット) |
100,000 |
15,000 |
最低5回以上出稿 |
| 新聞広告 |
Newspaper |
1回 (全国紙半5段) |
200,000 |
25,000 |
最大5回まで |
| Web広告(リスティング) |
Web_Lis |
10,000円予算あたり |
10,000 |
1,000 |
予算上限 200万円 |
| Web広告(SNS) |
Web_SNS |
15,000円予算あたり |
15,000 |
800 |
予算上限 250万円 |
| 屋外広告(主要駅) |
OOH |
1箇所/月 |
1,000,000 |
50,000 |
最大2箇所まで |
追加の制約:
- Web広告比率: Web広告（リスティングとSNSの合計）への予算配分は、総予算の少なくとも30%（300万円）以上とする。
4. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化が広告キャンペーン計画において以下の価値を提供することを示しています。
- データに基づいた意思決定: 経験や勘だけでなく、費用対効果や各種制約を定量的に評価し、最適な予算配分を導き出す。
- ROI (投資対効果) の最大化: 限られた予算内で、キャンペーン目標（ここではリーチ数）を最大化する具体的な計画を立案できる。
- 複雑な制約の考慮: 予算上限、媒体ごとの出稿制限、媒体ミックスの比率など、複数の制約条件を同時に満たす解を見つけ出す。
- What-if 分析: もし予算が変わったら？特定の媒体の効果が予測より高かったら/低かったら？といったシナリオ分析を容易に行い、計画の柔軟性を高める。
- コミュニケーションツール: 最適化結果とその根拠を明確に示すことで、関係部署（経営層、営業部門など）との合意形成を円滑にする。
7. 地域プロバスケットボールリーグの試合スケジュール最適化
1. 背景と課題
地域プロバスケットボールリーグ「リージョナル・フープス」の運営事務局は、来シーズンの試合スケジュール作成に取り組んでいます。リーグには4つのチーム（チームA, チームB, チームC, チームD）が所属しており、ファンやチームからの要望に応え、公平で魅力的なスケジュールを作成する必要があります。
課題:
- 公平性の確保: 各チームのホーム/アウェイ試合数のバランスを取り、特定のチームに有利/不利が生じないようにしたい。
- 複雑な制約: チームの都合（アリーナが他のイベントで使用されるなど）、会場の共有、選手のコンディションを考慮した連戦の回避など、多くの制約を満たす必要がある。
- 手作業の限界: これらの条件を手作業で調整して最適なスケジュールを見つけるのは非常に時間がかかり、ミスも発生しやすい。また、本当に「最適」あるいは「公平」なスケジュールになっているか客観的な評価が難しい。
そこで、数理最適化を用いて、全ての制約を満たし、かつ公平性を考慮した試合スケジュールを自動生成することを目指します。
2. 目標
- リーグ戦（ホーム＆アウェイ総当たり）の全試合を、与えられた期間内（6週間）で実施する。
- 全ての運用上の制約（チーム可用性、会場制約、連戦制限）を遵守する。
- 各チームのホーム試合数とアウェイ試合数を均等（各3試合にする。
3. リーグ設定とデータ
- リーグ構成: 4チーム (T1, T2, T3, T4)
- 期間: 6週間 (W1, W2, W3, W4, W5, W6)
- 試合形式: ホーム＆アウェイ方式による総当たり戦。
- 各チームは他の全チームとホームで1回、アウェイで1回、合計2回対戦する。
- 総試合数 = 4チーム * 3対戦相手 * 2 (H&A) / 2 = 12試合。
- 各チームの総試合数 = 6試合。
- 期間が6週間なので、各チームは毎週1試合を行う。
- 制約条件:
- チーム可用性: チームT1は、Week 3にホームアリーナが使用できないため、ホームゲームを開催できない。
- 会場共有: チームT3とチームT4は同じアリーナを共有しているため、同じ週に両チームがホームゲームを行うことはできない。
- 連戦制限: 選手の負担を考慮し、どのチームも3週連続でホームゲーム、または3週連続でアウェイゲームにならないようにする。
4. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化がスポーツスケジューリングにおいて以下の価値を提供することを示しています。
- 公平性の保証: ホーム/アウェイ数などの公平性に関する基準を明確な制約や目的関数として組み込み、それを満たすスケジュールを作成できる。
- 複雑な制約の処理: チーム、会場、連戦など、多岐にわたる複雑なルールや制約を矛盾なく考慮したスケジュールを生成できる。
- 効率化と客観性: スケジュール作成にかかる時間と労力を大幅に削減し、属人的な判断ではなくデータとルールに基づいた客観的な結果を得られる。
- 多様なシナリオ検討: 新チームの加入、期間の変更、制約の追加・緩和などが発生した場合でも、モデルを修正して迅速に新しいスケジュール案を作成できる。
- 関係者への説明責任: 最適化プロセスとその結果は、なぜそのスケジュールになったのかを論理的に説明する根拠となり、チームやファンへの説明責任を果たしやすくなる。
8. 日次電力供給計画のコスト最小化
1. 背景と課題
地域電力供給会社「エリアパワー株式会社」は、管轄エリア内の家庭や企業への安定的な電力供給を使命としています。同社は複数の発電プラント（火力、水力、太陽光）を保有・運用しており、日々の電力需要は時間帯によって大きく変動します。
課題:
- コスト効率: 各発電プラントは発電コスト（燃料費など）や運用特性（出力調整のしやすさ、最低稼働レベルなど）が異なります。コストを抑えつつ電力を供給する必要があります。
- 需要変動への対応: 刻々と変わる電力需要を正確に予測し、それに対して過不足なく発電量を調整しなければ、供給不安や電力余剰による損失が発生します。
- 再生可能エネルギーの活用: 環境負荷低減のため太陽光発電を導入していますが、その出力は天候や時間帯に左右されるため、他の電源との最適な組み合わせ（ミックス）が求められます。
- プラント制約: 各プラントには最大出力容量があり、火力発電所などでは安定運用のための最低出力レベルも考慮する必要があります。
これらの複雑な要因を考慮し、翌日の各時間帯における最適な発電計画（どのプラントでどれだけ発電するか）を策定し、総発電コストを最小化しつつ、電力需要を確実に満たすことが喫緊の課題となっています。
2. 目標
- 翌日（24時間）の電力需要予測に基づき、全ての時間帯で需要を満たす。
- 各発電プラントの運用制約（容量、最低出力、太陽光の出力変動）を守る。
- 上記を満たした上で、1日の総発電コスト（主に燃料費）を最小化する。
3. 発電プラントとデータ
エリアパワー社が運用する発電プラントと、翌日の計画に必要なデータは以下の通りです。 (簡単のため、1日を3つの時間帯：深夜早朝(T1: 0-8時)、日中(T2: 8-16時)、夕夜間(T3: 16-24時)に分割します)
| PL1 |
火力(LNG) |
500 |
100 |
8,000 |
比較的起動・停止・出力調整が容易 |
| PL2 |
火力(石炭) |
800 |
250 |
5,000 |
起動・停止に時間がかかるがコストは安い |
| PL3 |
水力 |
300 |
0 |
1,000 |
貯水量による制約は今回考慮しない |
| PL4 |
太陽光 |
200 |
0 |
0 |
出力は時間帯・天候依存 (後述) |
時間帯別データ:
| 深夜早朝 |
T1 |
900 |
0 |
| 日中 |
T2 |
1500 |
180 |
| 夕夜間 |
T3 |
1200 |
20 |
4. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化が電力供給計画において以下の価値を提供することを示しています。
- コスト削減: 燃料費や運用コストを考慮し、最も経済的な発電所の組み合わせと出力を決定することで、大幅なコスト削減を実現できる。
- 安定供給の確保: 需要予測とプラントの能力・制約に基づいて計画を立てることで、電力不足のリスクを低減し、安定供給を支援する。
- 再生可能エネルギーの統合: 出力が不安定な再生可能エネルギー源を、他の調整可能な電源と組み合わせて最大限有効活用する計画を立案できる。
- 複雑な運用制約への対応: 最大/最小出力、起動停止時間（より高度なモデルで考慮）、送電網の制約（これも高度なモデルで考慮）など、現実の複雑な制約下での最適運用計画を作成できる。
- 迅速な計画修正: 需要予測やプラントの状態が変化した場合でも、モデルを更新して迅速に最適な計画を再計算できる。
電力系統の運用計画（ユニットコミットメント、経済負荷配分など）は、数理最適化が極めて重要かつ効果的に活用されている分野の一つであり、エネルギーコストの削減と供給信頼性の向上に不可欠なツールとなっています。
9. 農場の季節別作物栽培計画による収益最大化
1. 背景と課題
ある家族経営の農場「グリーンフィールド・ファーム」は、100ヘクタールの耕作可能な土地を所有しています。農場主は、来シーズンに向けてどの作物をどれだけの面積で作付けし、どの程度の資源（水、肥料、労働力）を投入すれば、農場全体の収益を最大化できるか悩んでいます。
課題:
- 作物選択: 栽培可能な作物は複数（例: トマト、小麦、トウモロコシ）あり、それぞれ市場価格、収穫量、必要な資源（土地、水、肥料、労働時間）、栽培期間が異なります。
- 資源制約: 利用可能な土地面積、水利権に基づく月間取水量、購入可能な肥料の量、そして家族や臨時雇いを含めた月間の総労働時間には限りがあります。
- 季節性・天候: 作物ごとに最適な作付け時期と収穫時期があり、また月ごとの天候（主に降水量）が水の必要量に影響します。豊作/不作による収穫量や価格の変動リスクもあります（今回は簡略化のため、平均的な値を使用）。
- 輪作計画（簡略化）: 特定の作物を連作することによる土壌への影響も考慮する必要がありますが、ここでは特定の組み合わせを避ける簡単な制約のみ考えます。
農場主は、これらの要因を総合的に考慮し、データに基づいて収益を最大化する年間（または季節別）の作物栽培計画を立てたいと考えています。
2. 目標
- 限られた土地、水、肥料、労働力の中で、年間を通じて栽培する作物の種類と面積を決定する。
- 各資源の制約と作物の栽培要件を満たす。
- 上記を満たした上で、年間の総粗利益（総売上 - 総変動費）を最大化する。
3. 作物と資源データ
ここでは、簡単のため主要な3つの作物と、春・夏・秋の3つの栽培期間を考えます。
作物データ (1ヘクタールあたり):
| トマト |
TOM |
春夏 |
50 |
30,000 |
春:300, 夏:400 |
100 |
春:50, 夏:80 |
連作不可 (前年考慮) |
| 小麦 |
WHT |
春 |
6 |
200,000 |
春:200 |
150 |
春:30 |
|
| トウモロコシ |
COR |
夏秋 |
10 |
80,000 |
夏:350, 秋:250 |
120 |
夏:40, 秋:60 |
小麦の後作は推奨 |
資源制約:
| 土地 |
ヘクタール |
100 |
100 |
100 |
(作付で消費) |
| 水 |
m³ |
30,000 |
35,000 |
25,000 |
20 円/m³ |
| 肥料 |
kg |
12,000 |
12,000 |
12,000 |
150 円/kg |
| 労働力 |
時間 |
4,000 |
5,000 |
4,500 |
1,500 円/時間 |
その他の制約:
- 連作回避: トマトは、前年にトマトを栽培した区画では栽培できない。（簡単のため、今回は全ての土地で前年はトマト以外だったと仮定）
- 後作推奨: 小麦を春に栽培した土地では、夏にトウモロコシを栽培することを推奨する（が、必須ではない）。
4. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化が農業経営において以下の価値を提供することを示しています。
- 収益性の向上: 市場価格、コスト、収量、資源制約を総合的に考慮し、最も収益性の高い作物ミックスと作付面積を決定できる。
- 資源の効率的利用: 土地、水、肥料、労働力といった限られた資源を最も効果的に配分し、無駄を削減する。ボトルネックとなっている資源を特定し、改善策（例: 節水技術の導入、労働力の確保）の検討に繋げる。
- リスク管理: 天候不順や価格変動のリスクを考慮したシナリオ分析を行い、より頑健な生産計画を立てるための情報を提供する（感度分析）。
- 計画策定の高度化: 経験や勘に頼るだけでなく、データに基づいた客観的で合理的な栽培計画を迅速に作成できる。
- 持続可能性への貢献: 水や肥料などの投入量を最適化することで、環境負荷の低減にも貢献できる可能性がある。
農業生産計画は、天候などの不確実性も伴う複雑な問題ですが、数理最適化を用いることで、より科学的で収益性の高い、持続可能な農業経営を目指すための強力なツールとなります。
10. 国内線航空会社のフリートアサインメントと基本スケジュール最適化
1. 背景と課題
国内線を運航する航空会社「スカイウィング航空」は、競争激化と燃料費高騰の中で、収益性を改善する必要に迫られています。現在、保有する複数のタイプの航空機（異なる座席数、燃費、航続距離）を、様々な国内路線に割り当てていますが、その割り当てと基本的な運航スケジュールは、過去の経験や部分的な調整に基づいており、必ずしもコスト効率や収益性が最大化されているとは言えません。
課題:
- コスト効率の最適化: どの路線にどの機材タイプを投入すれば、燃料費や運航コスト全体を最小化できるか。
- 需要と供給のマッチング: 各路線の時間帯別需要予測に対して、適切なサイズの機材を割り当て、空席を減らしつつ機会損失（需要を取りこぼすこと）も最小限に抑えたい。
- 機材繰りの複雑さ: 機材は空港間を移動するため、ある便の到着機が次の便の出発機となる「機材繰り」を考慮する必要がある。効率的なローテーションを組まなければ、機材の遊休時間が増えたり、必要な場所に必要な機材がないという事態が発生する。
- 空港制約: 主要空港では離着陸可能な便数（スロット）が限られており、特に混雑する時間帯では制約が厳しい。
これらの課題に対し、数理最適化を用いて、総運航コストを最小化しつつ、需要を満たし、各種制約を遵守する実現可能な機材割り当て計画と基本的な運航スケジュールを作成することを目指します。
2. 目標
- 翌日の全ての計画フライト（主要路線）に対して、最適な航空機タイプを割り当てる。
- 各路線の旅客需要予測を可能な限り満たす。
- 機材の連続的な運用（フロー）を保証し、機材不足や矛盾がないようにする。
- 空港の離着陸スロット制約を遵守する。
- 上記を満たした上で、1日の総運航コスト（主に燃料費ベースの変動費）を最小化する。
3. 設定とデータ
- 対象空港 (A): {HND (東京羽田), ITM (大阪伊丹), CTS (札幌千歳), FUK (福岡)}
- 航空機タイプ (P):
- Type A (中型機): 座席数 150席, 運航コスト 50万円/飛行時間
- Type B (大型機): 座席数 250席, 運航コスト 80万円/飛行時間
- 保有 機材数: Type A: 10機, Type B: 5機
- フライト候補 (F): 主要路線における翌日の運航候補便。各フライト
f は (出発空港, 到着空港, 出発時刻, 到着時刻, 飛行時間) を持つ。 (例: f1: HND→ITM 08:00発-09:00着, 飛行時間1h; f2: ITM→FUK 10:00発-11:15着, 飛行時間1.25h …)
- 路線需要 (Demand): 各路線（例: HND-ITM）、時間帯ごとの旅客需要予測。フライト候補
f がカバーすべき需要 Demand[f] として簡略化。 (例: f1(HND-ITM 08:00発)の需要は 180人)
- 空港スロット (Slot): 各空港
a、各時間帯（例: 1時間ごと）t の離着陸可能回数 SlotLimit[a, t]。 (例: HNDの08:00-08:59の離着陸枠は合計 40回)
- 機材の初期配置: 運用開始時点（例: 早朝）での各機材タイプの各空港における待機機数。
4. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化が航空会社の運行計画において以下の価値を提供することを示しています。
- 大幅なコスト削減: 燃料効率の良い機材を適切に割り当て、不要な大型機の投入を避けることで、運航コスト（特に燃料費）を大幅に削減できる。
- 収益機会の最大化: 需要予測に基づいて適切な座席数を供給することで、逸失利益を減らし、収益を最大化する。
- 機材稼働率の向上: 効率的な機材繰りを計画することで、機材の遊休時間を減らし、投資対効果を高める。
- 複雑な制約下での意思決定: 空港スロット、機材数、需要など、多数の制約が絡み合う中で、実行可能で最適な計画を迅速に作成できる。
- 運航の安定性向上: 事前に矛盾のない計画を立てることで、当日のイレギュラー発生リスクを低減する（ただし、実際の不規則運航への対応はさらに別の最適化問題となる）。
- 戦略的意思決定支援: 新しい機材の導入や路線の開設/廃止が、全体のコストや効率にどう影響するかをシミュレーションし、経営判断を支援する。
航空会社のフリートアサインメントとスケジューリングは、オペレーションズ・リサーチの古典的かつ重要な応用分野であり、数理最適化技術によって日々莫大な経済的価値が生み出されています。
11. 小規模航空路線網における乗務ペアリング最適化
1. 背景と課題
地域航空会社「コネクトエア」は、限られた機材と乗務員で効率的な運航を目指しています。翌日に運航予定の主要フライトレグ（区間飛行）が6便確定しました。これらをカバーするために、事前にいくつかの実行可能な「乗務ペアリング」（1人の乗務員が担当する一連のフライトで、拠点空港から出発し拠点空港に戻るもの）候補が作成されています。
課題:
- 全てのフライトレグを、いずれかの乗務ペアリングによって担当させる必要がある。
- 各フライトレグは、重複なくちょうど1つのペアリングによってカバーされなければならない。
- 各ペアリングには、移動費や宿泊費などを反映した推定コストがかかる。
- これらの条件を満たし、かつ総ペアリングコストを最小化するペアリングの組み合わせを選定したい。
2. 目標
- 確定した6便のフライトレグ全てをカバーする。
- 各フライトレグがちょうど1つのペアリングに含まれるようにする。
- 総ペアリングコストを最小化するペアリングの組み合わせを選択する。
3. データ
対象フライトレグ (L): {L1, L2, L3, L4, L5, L6}
- L1: HND (羽田) → ITM (伊丹)
- L2: ITM (伊丹) → FUK (福岡)
- L3: FUK (福岡) → HND (羽田)
- L4: HND (羽田) → CTS (千歳)
- L5: CTS (千歳) → ITM (伊丹)
- L6: ITM (伊丹) → HND (羽田) (簡単のため、出発/到着時刻や具体的な機材はここでは考慮しない)
生成されたペアリング候補 (P) とコスト: (コストは仮の単位)
| P1 |
{L1, L2, L3} |
15 |
| P2 |
{L4, L5, L6} |
12 |
| P3 |
{L1, L6} |
5 |
| P4 |
{L4, L5} |
9 |
| P5 |
{L2, L3} |
8 |
| P6 |
{L1, L2, L5, L6} |
20 |
| P7 |
{L3, L4} |
10 |
カバー情報 (Covers[p, l]): (ペアリングpがレグlを含むなら1)
| P1 |
1 |
1 |
1 |
0 |
0 |
0 |
| P2 |
0 |
0 |
0 |
1 |
1 |
1 |
| P3 |
1 |
0 |
0 |
0 |
0 |
1 |
| P4 |
0 |
0 |
0 |
1 |
1 |
0 |
| P5 |
0 |
1 |
1 |
0 |
0 |
0 |
| P6 |
1 |
1 |
0 |
0 |
1 |
1 |
| P7 |
0 |
0 |
1 |
1 |
0 |
0 |
4. ケーススタディの意義と実務への応用
この簡略化されたケーススタディでも、数理最適化が乗務員スケジューリングにおいて以下の価値を提供することがわかります。
- コスト効率の追求: 複数の選択肢（ペアリング）の中から、コストを最小化する最適な組み合わせを客観的に見つけ出すことができます。この例では、コスト27の案よりコスト22の案が優れていることを示しました。
- 制約遵守の保証: 全てのフライトレグを確実にカバーするという基本的な制約を厳密に満たすスケジュールを作成できます。現実の問題では、これに加えて勤務時間や休息時間などの複雑な制約も組み込まれます。
- 計画の自動化と迅速化: 複雑な組み合わせ問題を自動で解くことにより、計画作成にかかる時間と労力を大幅に削減できます。
- 透明性と客観性: なぜそのペアリングの組み合わせが選ばれたのかが、コストと制約に基づいて明確に示されます。
12. 大学学部の授業教室・時間割割り当て最適化
1. 背景と課題
ある大学の〇〇学部では、来学期の授業スケジュールと教室割り当ての計画を進めています。学部には複数の授業があり、それぞれ担当教員、予想される受講者数、必要な設備（プロジェクターなど）が異なります。一方、利用可能な教室数には限りがあり、各教室の収容人数や設備も様々です。
課題:
- 教室不足とミスマッチ: 特定の時間帯に授業が集中し、必要な大きさや設備の教室が不足することがある。逆に、少人数の授業に大きな教室が割り当てられ、非効率になる場合もある。
- 時間割の衝突: 同じ教員が同時刻に複数の授業を担当したり、学生が必修科目を同時に履修できなくなったりするような時間割の衝突を避けなければならない。
- 制約の複雑さ: 教員の担当可能時間、教室の設備要件、学生の履修パターン（特定の科目は連続で受けたい等、今回は簡略化）など、多くの条件を考慮する必要がある。
- 手作業の限界: これらの複雑な条件を考慮しながら、手作業で最適な（あるいは実行可能な）時間割と教室割り当てを作成するのは非常に困難で時間がかかる。
そこで、数理最適化を用いて、全ての制約を満たし、かつ効率的な授業の時間割と教室割り当てを自動生成することを目指します。
2. 目標
- 全ての授業を、指定された時間割の枠（例: 月曜～金曜の1限～5限）と利用可能な教室に割り当てる。
- 以下の必須制約を全て満たす：
- 同じ教室・同じ時間帯に複数の授業が入らない（教室衝突回避）。
- 同じ教員が同じ時間帯に複数の授業を担当しない（教員衝突回避）。
- 授業の受講者数が、割り当てられた教室の収容人数を超えない（収容人数制約）。
- 授業に必要な設備が、割り当てられた教室に備わっている（設備制約）。
- 教員の担当可能時間外には授業を割り当てない（教員可用性）。
- 上記を満たした上で、総割り当てコスト（ペナルティ）を最小化する。（例：希望時間帯以外への割り当て、必要最低限より大きい教室への割り当て、などにペナルティを設定） (今回はシンプルに、必須制約を満たす実行可能な解を見つけることを主目的とする)
3. 設定とデータ
4. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化が教室割り当てとスケジューリングにおいて以下の価値を提供することを示しています。
- 衝突のないスケジュールの保証: 複雑な条件（教室、教員、設備、収容人数）を考慮し、ルール違反のない実行可能な時間割を確実に作成できます。
- リソース利用の効率化: 教室の収容人数や設備を考慮して授業を割り当てることで、教室の無駄遣いを減らし、利用率を向上させることができます（目的関数に組み込めばより明確に）。
- 計画作成の自動化と迅速化: 面倒で時間のかかる割り当て作業を自動化し、担当者の負担を大幅に軽減します。急な変更（教員の都合、教室の変更など）にも迅速に対応できます。
- 公平性と透明性: 特定の教員への負担集中などを避ける制約を追加したり、割り当て結果の根拠を明確に示したりすることで、公平性を高め、関係者への説明責任を果たしやすくなります。
- What-if 分析: 新しい授業の追加、教室の改修、履修人数の変動などが、時間割全体にどのような影響を与えるかを事前にシミュレーションできます。
大学や学校における時間割・教室割り当ては、多くの関係者の要求と物理的な制約が絡み合う典型的な組合せ最適化問題であり、数理最適化の導入効果が高い分野の一つです。
13. 森林公園における希少動物生息地の監視センサーネットワーク設計
1. 背景と課題
広大な森林公園「ミドリの森国立公園」の管理事務所は、公園内に生息する希少動物（例：特別天然記念物のニホンカモシカ）の生態調査と保護のため、主要な生息候補地や水飲み場を監視するセンサーネットワークの導入を計画しています。しかし、設置できるセンサーの数や性能、設置・運用にかかる予算は限られています。
課題:
- 効果的なカバレッジ: 限られた予算内で、できるだけ多くの重要監視ポイントをカバーしたい。特に、過去の目撃情報が多いポイントや、密猟のリスクがあるポイントは優先的に監視したい。
- センサー選択: 性能（検知範囲）とコスト（設置費、通信費）が異なる複数のセンサータイプから、最適な組み合わせを選ぶ必要がある。
- 設置場所の選定: センサーを設置できる候補地点はいくつかあるが、地形やアクセスの制約がある。どの候補地点にどのセンサーを置くのが最も効率的か。
- コスト管理: 設置費用だけでなく、データ通信にかかるランニングコストも考慮し、予算内に収める必要がある。
管理事務所は、これらの課題を解決するため、数理最適化を用いて、予算内で最も効果的なカバレッジ（重要度を考慮）を達成するセンサーの配置計画を策定したいと考えています。
2. 目標
- 与えられた総予算内で、センサーの設置場所とタイプを決定する。
- 各監視ターゲットポイントの重要度を考慮し、総カバレッジスコア（カバーされたターゲットの重要度の合計）を最大化する。
- 設置場所の制約（各候補地に設置できるセンサーは1つまで）を守る。
3. 設定とデータ
センサー設置候補地点 (L): 公園内の5箇所 {L1, L2, L3, L4, L5}
監視ターゲットポイント (T): 動物の生息・活動が予想される10箇所 {T1, T2, …, T10}
センサータイプ (S):
SensorA (標準型): 設置コスト 5万円, 通信コスト 1万円/年, 検知範囲 1kmSensorB (広範囲型): 設置コスト 12万円, 通信コスト 2万円/年, 検知範囲 2km
ターゲットポイントの重要度 (Importance[j]): (1～5の5段階評価)
設置候補地点からターゲットポイントまでの距離 (km) とカバレッジ: (距離が検知範囲以下ならカバー可能 (1)、超えるなら不可 (0))
SensorA (範囲1km) でのカバー可否 Covers[l, SensorA, j]:
| L1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| L2 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
| L3 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
| L4 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
| L5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
SensorB (範囲2km) でのカバー可否 Covers[l, SensorB, j]:
| L1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
| L2 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
| L3 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
| L4 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| L5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
総予算 (Budget): 40万円 (設置コスト+初年度通信コストの合計)
4. ケーススタディの意義と実務への応用
このケーススタディは、数理最適化がセンサーネットワーク設計において以下の価値を提供することを示しています。
- コスト効率の最大化: 限られた予算内で、カバレッジや性能といった目標を最大化する最適なセンサーの種類と配置を決定できる。
- 客観的な意思決定: どのターゲットを優先的にカバーするか（重要度）、どのセンサータイプがコスト対効果で優れているかなどをデータに基づいて判断できる。
- 複雑なトレードオフの考慮: センサー性能（範囲）、コスト（設置、通信）、カバレッジ要件、予算などの間の複雑なトレードオフを考慮した上で、全体として最適な解を見つけ出す。
- 計画の柔軟性: 予算の増減、新しいセンサー技術の登場、監視対象エリアの変更などがあった場合に、モデルを更新して迅速に再計画できる。
- 多様な分野への応用: 環境モニタリングだけでなく、防犯・防災、スマート農業、工場自動化、交通システム、インフラ監視など、センサーネットワークが利用されるあらゆる分野の設計最適化に応用可能。
センサーネットワーク設計は、モノのインターネット (IoT) の普及に伴い、ますます重要性が高まっている分野であり、数理最適化はその効率性と効果を最大化するための重要なツールとなります。
# -----------------------------------------------
# モデル (sensor_placement.mod)
# -----------------------------------------------
reset; model;
# --- 集合 ---
set LOCATIONS; # センサー設置候補地点
set TARGETS; # 監視ターゲットポイント
set SENSOR_TYPES; # センサータイプ
# --- パラメータ ---
# センサーのコスト
param InstallCost{SENSOR_TYPES} >= 0;
param CommCost{SENSOR_TYPES} >= 0;
# 予算
param Budget >= 0;
# ターゲットの重要度
param Importance{TARGETS} >= 0;
# カバー可能かを示すバイナリパラメータ (疎なデータなのでdefault 0を指定)
param Covers{LOCATIONS, SENSOR_TYPES, TARGETS} binary default 0;
# --- 変数 ---
# Place[l,s]=1 ならば、地点lにセンサーsを設置する
var Place{LOCATIONS, SENSOR_TYPES} binary;
# IsCovered[j]=1 ならば、ターゲットjがカバーされている
var IsCovered{TARGETS} binary;
# --- 目的関数 ---
# カバーされたターゲットの重要度の合計（カバレッジスコア）を最大化
maximize TotalCoverageScore:
sum{j in TARGETS} Importance[j] * IsCovered[j];
# --- 制約条件 ---
# 1. 各設置候補地には最大1つのセンサーしか置けない
subject to OneSensorPerLocation{l in LOCATIONS}:
sum{s in SENSOR_TYPES} Place[l, s] <= 1;
# 2. 総コストは予算内に収める
subject to BudgetConstraint:
sum{l in LOCATIONS, s in SENSOR_TYPES} (InstallCost[s] + CommCost[s]) * Place[l, s] <= Budget;
# 3. ターゲットjがカバーされているか否かを定義
subject to DefineCoverage{j in TARGETS}:
IsCovered[j] <= sum{l in LOCATIONS, s in SENSOR_TYPES: Covers[l,s,j] = 1} Place[l,s];
# -----------------------------------------------
# データ (sensor_placement.dat)
# -----------------------------------------------
data;
set LOCATIONS := L1 L2 L3 L4 L5;
set TARGETS := T1 T2 T3 T4 T5 T6 T7 T8 T9 T10;
set SENSOR_TYPES := SensorA SensorB;
# センサーコスト
param: InstallCost CommCost :=
SensorA 5 1
SensorB 12 2;
# 総予算
param Budget := 40;
# ターゲットの重要度
param Importance :=
T1 5 T2 4 T3 5 T4 3 T5 2
T6 3 T7 4 T8 2 T9 3 T10 5;
# カバー可能か (値が1のものだけを記述)
param Covers :=
# SensorA
L1 SensorA T1 1 L1 SensorA T2 1
L2 SensorA T2 1 L2 SensorA T3 1 L2 SensorA T4 1
L3 SensorA T4 1 L3 SensorA T5 1 L3 SensorA T6 1
L4 SensorA T6 1 L4 SensorA T7 1 L4 SensorA T8 1
L5 SensorA T8 1 L5 SensorA T9 1 L5 SensorA T10 1
# SensorB
L1 SensorB T1 1 L1 SensorB T2 1 L1 SensorB T3 1 L1 SensorB T4 1
L2 SensorB T1 1 L2 SensorB T2 1 L2 SensorB T3 1 L2 SensorB T4 1 L2 SensorB T5 1 L2 SensorB T6 1
L3 SensorB T2 1 L3 SensorB T3 1 L3 SensorB T4 1 L3 SensorB T5 1 L3 SensorB T6 1 L3 SensorB T7 1 L3 SensorB T8 1
L4 SensorB T4 1 L4 SensorB T5 1 L4 SensorB T6 1 L4 SensorB T7 1 L4 SensorB T8 1 L4 SensorB T9 1 L4 SensorB T10 1
L5 SensorB T8 1 L5 SensorB T9 1 L5 SensorB T10 1;
# -----------------------------------------------
# 実行と結果表示
# -----------------------------------------------
option solver highs;
solve;
printf "\n--- 最適なセンサー配置計画 ---\n";
printf "%-12s %-12s %-12s\n", "設置場所", "センサー", "総コスト";
printf "--------------------------------------\n";
for {l in LOCATIONS, s in SENSOR_TYPES: Place[l,s] > 0.5} {
printf "%-12s %-12s %-12.1f 万円\n", l, s, InstallCost[s] + CommCost[s];
}
printf "--------------------------------------\n";
printf "使用総コスト: %.1f 万円 (予算: %.1f 万円)\n", sum{l in LOCATIONS, s in SENSOR_TYPES} (InstallCost[s] + CommCost[s]) * Place[l,s], Budget;
printf "達成カバレッジスコア: %d\n\n", TotalCoverageScore;
printf "--- カバーされたターゲット ---\n";
for {j in TARGETS: IsCovered[j] > 0.5} {
printf "%s (重要度: %d)\n", j, Importance[j];
}
printf "\n";
HiGHS 1.10.0: optimal solution; objective 36
4 simplex iterations
1 branching nodes
--- 最適なセンサー配置計画 ---
設置場所 センサー 総コスト
--------------------------------------
L1 SensorB 14.0 万円
L4 SensorB 14.0 万円
--------------------------------------
使用総コスト: 28.0 万円 (予算: 40.0 万円)
達成カバレッジスコア: 36
--- カバーされたターゲット ---
T1 (重要度: 5)
T2 (重要度: 4)
T3 (重要度: 5)
T4 (重要度: 3)
T5 (重要度: 2)
T6 (重要度: 3)
T7 (重要度: 4)
T8 (重要度: 2)
T9 (重要度: 3)
T10 (重要度: 5)
14. 時間帯ごとに複数の仕事をもつシフトスケジューリング問題
背景: 「ミニマート・サポート」は、小規模なオンラインストアの顧客対応を3名のスタッフで行っています。効率的な運営のため、3日間のシフトを計画する必要があります。
目的: 3名のスタッフを、3日間のシフトに割り当てる。その際、各シフトの必要人数を満たし、特定の勤務ルールを守りつつ、スタッフ間の勤務時間の公平性をできるだけ保つ。
登場要素:
1. 対象期間:
1日目、2日目、3日目の3日間。
2. スタッフ:
3. 勤務時間帯:
- 朝 (Morning)
- 昼 (Day)
- 夜 (Night) (簡単化のため、全日共通の3時間帯とします)
4. 仕事の種類:
- 受付 (Reception)
- 対応 (Support) (簡単化のため、2種類の仕事とします)
5. シフトの定義と必要人数: 「日・時間帯・仕事」の組み合わせを「シフト」とします。
| 1日目 |
朝 |
受付 |
D1MA_Rec |
1人 |
| 1日目 |
朝 |
対応 |
D1MA_Sup |
1人 |
| 1日目 |
昼 |
受付 |
D1MD_Rec |
1人 |
| 1日目 |
昼 |
対応 |
D1MD_Sup |
1人 |
| 1日目 |
夜 |
対応 |
D1MN_Sup |
1人 |
| 2日目 |
朝 |
受付 |
D2MA_Rec |
1人 |
| 2日目 |
朝 |
対応 |
D2MA_Sup |
1人 |
| 2日目 |
昼 |
受付 |
D2MD_Rec |
1人 |
| 2日目 |
昼 |
対応 |
D2MD_Sup |
1人 |
| 2日目 |
夜 |
対応 |
D2MN_Sup |
1人 |
| 3日目 |
朝 |
受付 |
D3MA_Rec |
1人 |
| 3日目 |
朝 |
対応 |
D3MA_Sup |
1人 |
| 3日目 |
昼 |
受付 |
D3MD_Rec |
1人 |
| 3日目 |
昼 |
対応 |
D3MD_Sup |
1人 |
| 3日目 |
夜 |
対応 |
D3MN_Sup |
1人 |
6. スタッフのスキルと割り当て可能性: 各スタッフが担当可能な仕事。
| S1 (山田) |
受付, 対応 |
| S2 (佐藤) |
対応 |
| S3 (田中) |
受付 |
7. シフト割り当てに関する制約・要望: （元の問題から主要なものを抜粋・単純化）
- 必要人数の充足 (厳守): 各シフトには、表5で定められた「必要人数」のスタッフが必ず割り当てられること。
- 夜勤明けの朝勤回避 (厳守): 前日の「夜(Night)」の時間帯に勤務したスタッフは、翌日の「朝(Morning)」の時間帯の勤務はできない。
- 連続夜勤日数制限 (厳守): いかなるスタッフも、「夜(Night)」勤務が2日以上連続しないこと（最大1日まで）。 (元の4日から大幅に短縮)
- 作業量の公平性 (努力目標): 各スタッフの3日間における総勤務シフト数ができるだけ均等になるようにする。
- 具体的には、全スタッフの総勤務シフト数のうち、最大値と最小値の差をできるだけ小さくしたい。
解決したい問題:
「ミニマート・サポート」の管理者は、3名のスタッフ（山田、佐藤、田中）を上記の条件を考慮しながら、3日間の全シフトに割り当てる必要があります。特に、1～3の条件は必ず守り、その上で4の作業量の公平性をできるだけ達成したいと考えています。
期待されるアウトプット: * 3日間の各シフトに、どのスタッフが割り当てられるかの具体的なシフト表。 * 各スタッフの総勤務シフト数、およびその最大と最小の差。
15. 均等化を考慮したチーム割当問題
背景:
「未来技術研究所」は、社内の多様な部門からメンバーを集め、3日間の「イノベーション・ワークショップ」を開催します。参加者は新しいアイデアを創出し、プロトタイプを開発するために複数のチームに分かれて活動します。効果的なワークショップのためには、各チームの能力を最大限に引き出し、かつチーム間の経験やスキルセットのバランスを取ることが重要です。
目的:
ワークショップに参加する社員を複数のチームに割り当て、以下の目標を達成する。
- 各社員をいずれか1つのチームに割り当てる。
- 各社員を特定のチームに割り当てた際に得られる「貢献度（利得）」の全チーム合計を最大化する。
- 各チームの平均年齢と平均スキルポイントが、チーム間でできるだけ均等になるようにする。
- 各チームの平均年齢と平均スキルポイントが、定められた範囲内（下限と上限）に収まるようにする。
- 均等化の度合いは、チーム間の平均値の差の合計（重み付き）を最小化するか、あるいは年齢の均等化を優先し、次にスキルポイントの均等化を優先する（辞書的順序）形で評価する。
登場要素:
1. 参加者 (社員):
ワークショップに参加する社員は5名です。
| E001 |
田中太郎 |
30 |
7 |
| E002 |
佐藤花子 |
45 |
9 |
| E003 |
鈴木一郎 |
25 |
6 |
| E004 |
高橋次郎 |
38 |
8 |
| E005 |
伊藤三郎 |
52 |
5 |
2. チーム:
編成するチームは2チームです。
3. チーム割り当て時の貢献度（利得） (\(p_{ij}\)): 各社員を各チームに割り当てた場合に期待される貢献度（アイデア発想力、専門性などを総合的に評価）。
| E001 |
8 |
7 |
| E002 |
9 |
9 |
| E003 |
6 |
7 |
| E004 |
7 |
8 |
| E005 |
5 |
6 |
4. チームの属性に関する目標範囲: 各チームに割り当てられたメンバーの平均年齢と平均スキルポイントについて、以下の範囲内であることが望ましい。
| チームA |
30 |
45 |
6.0 |
8.0 |
| チームB |
30 |
45 |
6.0 |
8.0 |
5. チーム間の均等化に関する目標:
- 目標1 (貢献度最大化): 上記3の貢献度の合計を最大にする。
- 目標2 (均等化 - 重み和最小化アプローチ): チームAとチームBの「平均年齢の差の絶対値」と「平均スキルポイントの差の絶対値」を計算し、これらの差に適切な重みを掛けて合計した値を最小化する。 (例:
重み年齢 * |平均年齢_A - 平均年齢_B| + 重みスキル * |平均スキル_A - 平均スキル_B| を最小化)
- 年齢差の重み: 1.0
- スキルポイント差の重み: 2.0 (スキル差の方をより重視)
- 目標3 (均等化 - 辞書的順序アプローチ):
- まず、チーム間の「平均年齢の差の絶対値」を最小化する。
- その上で（平均年齢差が最小となる割り当ての中で）、「平均スキルポイントの差の絶対値」を最小化する。
解決したい問題:
「未来技術研究所」のワークショップ運営担当者は、5名の社員を2つのチーム（チームA、チームB）に割り当てる必要があります。以下の条件と目標を考慮して、最適なチーム編成を決定してください。
- 全員割り当て: 各社員は、必ずチームAまたはチームBのいずれか1つのチームに割り当てられる。
- 貢献度の最大化: 全体の貢献度の合計が最も高くなるようにする。
- チーム属性の制約: 各チームの平均年齢と平均スキルポイントが、表4で定められた下限と上限の範囲にできるだけ収まるようにする（努力目標、あるいは厳密な制約）。
- チーム間の均等化: 上記「5. チーム間の均等化に関する目標」で述べた、重み和アプローチまたは辞書的順序アプローチのいずれかに基づいて、チーム間の平均年齢と平均スキルポイントのバランスを取る。
期待されるアウトプット:
- 各社員がどのチームに割り当てられるかのリスト。
- その割り当てによって達成される総貢献度。
- 各チームの平均年齢と平均スキルポイント、およびチーム間のこれらの値の差。
- （均等化目標を達成するための目的関数の値）
16. 献立問題
背景: 「ぷちデリ弁当」は、小規模ながら健康志向の宅配弁当サービスです。コストを抑えつつ、栄養バランスと日々の献立の目新しさを提供することを目指しています。今回は、月曜日から水曜日までの3日間の日替わり弁当（主菜1品、副菜1品）の献立を計画します。
目的: 3日間の各日において、主菜と副菜を1品ずつ選び、以下の目標を達成する献立を作成する。 1. 毎日の弁当が、定められた栄養素（カロリー、塩分）の摂取基準（下限と上限）を満たす。 2. 3日間の弁当の総費用をできるだけ安く抑える。 3. 献立のバラエティを豊かにするため、同じ日の主菜と副菜で、また連続する2日間の献立で、同じ「素材」や「調理法」ができるだけ重ならないようにする（ペナルティとして評価）。
登場要素:
1. 対象期間: 月曜日、火曜日、水曜日の3日間。
2. 食品候補: 弁当に使用できる食品の候補リスト。
食品リストと基本情報:
| M01 |
鶏の照り焼き |
主菜 |
200 |
肉 |
焼き物 |
| M02 |
鮭の塩焼き |
主菜 |
220 |
魚 |
焼き物 |
| M03 |
豚の角煮 |
主菜 |
250 |
肉 |
煮物 |
| S01 |
ほうれん草の胡麻和え |
副菜 |
80 |
野菜 |
和え物 |
| S02 |
きんぴらごぼう |
副菜 |
70 |
野菜 |
炒め物 |
| S03 |
だし巻き卵 |
副菜 |
90 |
卵 |
焼き物 |
食品ごとの栄養素含有量（1食あたり）:
| M01 |
300 |
1.5 |
| M02 |
250 |
1.2 |
| M03 |
400 |
1.8 |
| S01 |
70 |
0.5 |
| S02 |
90 |
0.7 |
| S03 |
120 |
0.6 |
3. 栄養素の摂取基準 (1日あたり):
| カロリー(kcal) |
400 |
600 |
| 塩分(g) |
1.5 |
2.5 |
4. 素材と調理法:
- 素材の分類: 肉、魚、野菜、卵
- 調理法の分類: 焼き物、煮物、和え物、炒め物
5. 重複ペナルティの値 (1回発生するごと):
| 同じ日の主菜と副菜の「素材」が同じ |
30 |
| 同じ日の主菜と副菜の「調理法」が同じ |
20 |
| 連続する2日間の献立で同じ「素材」が使われる |
40 |
| 連続する2日間の献立で同じ「調理法」が使われる |
25 |
解決したい問題:
「ぷちデリ弁当」の献立プランナーとして、月曜日から水曜日までの3日間の弁当献立（各日に主菜1品、副菜1品）を決定する必要があります。以下の全ての条件を満たしつつ、3日間の「総費用（材料費）＋ 重複ペナルティの合計」を最小にする献立プランを見つけてください。
- 主菜・副菜の選択: 各日、表2の食品リストから、指定された主菜/副菜の区分に従い、主菜候補から1品、副菜候補から1品を選択する。
- 栄養基準の遵守: 毎日、選択された主菜と副菜の栄養素（カロリー、塩分）の合計が、表3の「栄養素の摂取基準」の下限と上限の範囲内に収まるようにする。
- 素材・調理法の重複回避の考慮: 表5で定義されたペナルティに基づき、素材や調理法の重複を評価する。
- 総コストの最小化: 3日間の食品費用と、発生した重複ペナルティの合計額が最も少なくなるようにする。
期待されるアウトプット: 月曜日、火曜日、水曜日の各日について、どの食品を主菜とし、どの食品を副菜とするかの具体的な献立リスト。そして、その献立によって達成される総費用（食品費用＋ペナルティ）、および各日の栄養摂取量。
17. エア・フロンティア航空の月間乗務員スケジュール作成
背景: エア・フロンティア航空は、ヨーロッパを拠点とする中規模航空会社です。同社は、乗務員の満足度と効率的な運航を両立させるため、乗務員の個々の事情や実行可能な勤務パターンを考慮した上で、月間の乗務スケジュール（個別月間ブロック）を作成する「乗務員勤務表問題 (Crew Rostering Problem)」に取り組んでいます。事前に、運航計画に基づいて効率的な「ペアリング」（ある出発地点（home base）から出発し， 再び同じ出発地点に戻る乗務員のスケジュール）が複数作成されており、これらのペアリングを各乗務員に適切に割り当てる必要があります。
目的: 全てのペアリングが必要な人数でカバーされ、各乗務員は実行可能な月間スケジュールを1つだけ担当し、会社全体としてスケジューリングのコスト（乗務員の特性や希望を反映）を最も低くすること。
登場要素:
1. 乗務員 今回の対象となるパイロットは3名です。
2. ペアリング と 必要人数 1ヶ月間に実施すべきペアリングと、各ペアリングに必要な乗務員の数は以下の通りです。
3. 乗務員ごとの実行可能な月間スケジュール候補 各パイロットには、実行可能な月間スケジュールの候補がいくつかあります。各スケジュールは、1つ以上のペアリングを含んでいます。
パイロットA のスケジュール候補:
パイロットB のスケジュール候補:
パイロットC のスケジュール候補:
4. 各スケジュールの費用
各パイロットが特定の月間スケジュールを担当する場合の「費用」です。この費用が低いほど、会社や乗務員にとって望ましいとされます。
| パイロットA |
S_A1 |
100 |
| パイロットA |
S_A2 |
120 |
| パイロットB |
S_B1 |
110 |
| パイロットB |
S_B2 |
70 |
| パイロットC |
S_C1 |
150 |
| パイロットC |
S_C2 |
90 |
解決したい問題:
エア・フロンティア航空は、次の2つの条件を必ず満たした上で、全体の費用が最も少なくなるように、各パイロットにどの月間スケジュールを割り当てるか（または割り当てないか）を決めたいと考えています。
ペアリングのカバー: 表に記載された全てのペアリング（P1からP4まで）は、それぞれ定められた「必要な乗務員数」が確保されるように、誰かしらのパイロットに担当されなければなりません。
- 例えば、ペアリングP1は2人の乗務員が必要です。もしパイロットAがS_A1（P1を含む）を担当し、パイロットBがS_B1（P1を含む）を担当した場合、P1は2人の乗務員によってカバーされたことになります。
乗務員へのスケジュール割り当て: 各パイロット（パイロットA、B、C）は、表3で示された自身の実行可能なスケジュール候補の中から、最大で1つだけしか割り当てられません。
期待されるアウトプット: どのパイロットにどの月間スケジュールを割り当てるのが最適か、そしてその時の最も低い総費用。
18. ケーススタディ：首都圏フーズ物流の挑戦「最適化が導く共同配送計画」
登場人物と背景
佐藤さんは、中堅食品卸「首都圏フーズ物流」の物流企画マネージャー。彼の部署は、千葉と神奈川にある基幹倉庫から、需要が集中する渋谷と新宿のエリア配送センター（卸）へ、日々商品を補充する重要な役割を担っています。
近年、燃料費の高騰、ドライバー不足、そして「物流の2024年問題」の余波が、物流コストを圧迫していました。経営陣からは「コストを5%削減しつつ、都心店舗への欠品は絶対に回避せよ」という厳しい指示が出ています。
直面している課題
これまでの首都圏フーズ物流のやり方は、渋谷と新宿の各センターから個別に発注依頼が来たら、その都度、近い方の倉庫からトラックを手配するという、いわば「場当たり的」なものでした。この方法にはいくつかの問題がありました。
- 非効率なトラック稼働: 同じ日の午前中に千葉倉庫から渋谷へトラックが出たのに、午後にはまた千葉倉庫から少量の追加荷物を積んで渋谷へ向かう、といった無駄が発生していました。
- 低い積載率: 緊急の補充依頼に応えるため、トラックの荷台が半分も埋まらないまま輸送することがあり、輸送の固定費が収益を圧迫していました。
- トラック台数の制約: 提携している運送会社との契約上、1日に全社で利用できるトラックの合計台数には上限があり、繁忙期には手配できないリスクがありました。
佐藤さんは、個別の発注に個別に対応するやり方では限界があると感じていました。「渋谷と新宿、千葉と神奈川、製品在庫と輸送タイミング。これら全てを統合的に考え、最も効率的な計画を立てる必要がある」と考えた彼は、数理最適化モデリング言語AMPLを用いて、この複雑な問題を解決することにしました。
AMPLによる問題のモデル化
佐藤さんは、AMPLのエキスパートに相談し、自社の課題を数理モデルに落とし込んでいきました。
最適化の実行と得られた洞察
佐藤さんは、これらの条件をすべて盛り込んだAMPLモデルに、過去の需要データ、輸送費、在庫費などの現実の数値を入力し、ソルバーを実行しました。数秒後、コンピュータは最適な補充計画を提示しました。
その結果を見て、佐藤さんはいくつかの重要な発見をします。
発見1：共同配送による固定費削減 最適化された計画では、これまで別々に輸送していた渋谷向けと新宿向けの荷物の一部が、同じ日に千葉倉庫からまとめて輸送されていました。これにより、トラックの稼働台数が減り、固定費が大幅に削減されていました。
発見2：戦略的な在庫活用 これまでは需要に応じて輸送量を決めていましたが、計画では1日目に少し多めに輸送して在庫として確保し、トラック台数の上限が厳しい2日目の輸送量を抑える、という動きが見られました。在庫費用は少し増えますが、それを上回る輸送費の削減効果があり、トータルコストは最小化されていました。
発見3：非効率な輸送の撲滅 最低積載量のルールが効果を発揮し、少量の荷物を運ぶためだけにトラックを1台走らせる、といった最も非効率な輸送が完全に排除されていました。
結論
AMPLによる最適化アプローチは、佐藤さんに「コスト削減」と「安定供給」という二律背反の課題を両立させるための具体的なアクションプランを示してくれました。彼は、このモデルを毎週実行し、常に全体の状況を把握しながら最適な輸送・在庫計画を立案していくことで、会社の競争力を高められると確信したのでした。
新たな課題：週次計画の最適化
物流企画マネージャーの佐藤さんは、AMPLを用いた2日間の補充計画の最適化に成功し、コスト削減と安定供給の両立に手応えを感じていました。次のステップとして、彼はこのアプローチを1週間単位の計画に拡張することを決意します。
週末を挟むことで需要の変動はさらに大きくなります。例えば、週末前の金曜日には需要が急増し、週明けの月曜日には各センターが在庫を補充するため再び需要が高まります。一方で、土日のトラック稼働台数は平日よりも少なくなる契約です。
これらの変動をすべて見越して、週全体で最も効率的な補充計画を立てるためには、日々の場当たり的な判断では到底不可能です。佐藤さんは、1週間の需要予測データをもとに、再度AMPLで最適計画を立案することにしました。
1週間の計画データ
佐藤さんは、過去の販売実績から、今後1週間の製品別・センター別の需要量を予測しました。製品P1は「プレミアム緑茶」、P2は「ミネラルウォーター」です。
表1：1週間の需要予測データ（単位：ケース）
| 1 |
月曜 |
緑茶 |
400 |
500 |
|
|
水 |
300 |
350 |
| 2 |
火曜 |
緑茶 |
300 |
400 |
|
|
水 |
230 |
280 |
| 3 |
水曜 |
緑茶 |
330 |
450 |
|
|
水 |
200 |
300 |
| 4 |
木曜 |
緑茶 |
310 |
420 |
|
|
水 |
210 |
290 |
| 5 |
金曜 |
緑茶 |
450 |
550 |
|
|
水 |
350 |
400 |
| 6 |
土曜 |
緑茶 |
250 |
300 |
|
|
水 |
280 |
320 |
| 7 |
日曜 |
緑茶 |
150 |
200 |
|
|
水 |
180 |
210 |
また、運送会社との契約により、1日に全社で利用できるトラックの合計台数は、平日（1〜5日目）は4台まで、週末（6, 7日目）は2台までという制約があります。
AMPLモデルと更新されたデータ
この新しい7日間計画のために、佐藤さんはAMPLモデルの定義部分（model;ブロック）を一切変更する必要がありませんでした。モデルはT_maxという期間を指定するパラメータを使って汎用的に作られているため、データ部分を更新するだけで、異なる期間の問題に柔軟に対応できるのです。
7日間計画から得られる新たな洞察
この1週間モデルを実行することで、佐藤さんはさらに高度な計画を立てられるようになります。例えば、トラックの台数が制限される週末に向けて、木曜日や金曜日に少し多めに輸送して在庫を積み増しておく、といった先行補充の判断が可能になります。また、週明けの月曜日の高い需要に応えるため、輸送コストが安いルートを使って日曜日のうちに補充を済ませておくなど、より戦略的でコスト効率の高い物流網の構築が実現できるのです。