最適化ケーススタディ

実践的なケーススタディによって、自分で最適化モデリングをする力をつける。以下のケースは、特定の実問題に基づくものではない。

AGI4OPT プロジェクト

  • AGI4OPTは、自然言語をamplpyのコードに変換するエージェントスキルとamplpyのコードをWebアプリケーションに変換するエージェントスキルから構成される。
  • AGI4OPTで、以下のケーススタディは解決できる（以下のサイト参照）。
  • 最適化ショーケース : ケーススタディの解答と各種パズルの解答とデモ（Webアプリケーション）

ローカルで amplpyを動かす方法

AMPLをインストールしてampl.exeがある場所をEnvironmentで指定する。

from amplpy import AMPL, Environment, tools
ampl = AMPL(Environment("/Users/mikiokubo/Documents/ampl/"))

Google Colab.で使う場合

ampl_notebook関数で、使うソルバー(modules)とlicense_uuidを設定する（空白でも動く）。

!pip install amplpy
from amplpy import ampl_notebook
ampl = ampl_notebook(
    modules=["highs","gurobi","cbc","scip","coin"],
            #coin includes ipopt, couenne, bonmin
    license_uuid=None)

1. ナースプラクティショナーの人員配置

original case (English)

問題の背景

最近、ウィスコンシン大学（UW）ヘルスは、患者の病院再入院を減らすための取り組みを進めています。広範なデータ分析の結果、高齢者層は再入院の可能性が高いと結論付けられました。データによると、高齢患者の再入院の大部分は、病院を退院してから最初の1週間以内に発生しています。この層の再入院を減らす試みとして、UWヘルスは、専門看護施設（skilled nursing facilities）の患者を訪問し、必要に応じて適切なフォローアップケアを提供するためにナースプラクティショナー（NP）を雇用するという独自のプログラムに投資しました。

専門看護施設に退院したすべての患者を訪問することが極めて重要であるため、UWヘルスは最適な人数のナースプラクティショナーを確実に雇用する必要があります。この移行期ケアプログラムの下では、デーン郡地域にナースプラクティショナーが配置される9つの施設があり、合計で815床あります。各施設は民間によって運営されており、それぞれ固有のベッド数を持っています。下の図は施設の位置を示しています。各施設間の車での移動距離は表に記載されています。

場所 (距離 マイル) Capital Lakes Karmenta Oakwood West Oakwood East Sunny Hill Attic Angels St. Mary’s Oak Park Belmont
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マイル以内に入る患者数を最大化するために必要なナースプラクティショナーの最小数を決定することと定義します。

この問題をモデル化するために、いくつかの仮定を置きます。

  1. 各ナースプラクティショナーは同じペースで働き、同じ数の患者を訪問できる。
  2. 移動時間ではなく、施設間の距離のみを考慮する。

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. データ

  • 物流センター（デポ）:

    • 所在地: (座標 0, 0)
    • 稼働開始可能時刻: 8:00

  • 配送先顧客（店舗）:

    顧客ID 所在地 (X, Y) 需要量 (ケース) 納品時間窓 荷降ろし時間 (分)
    A (15, 25) 30 9:00 - 10:00 15
    B (30, 10) 45 9:30 - 11:00 20
    C (-10, 20) 25 10:00 - 12:00 15
    D (5, -15) 50 9:00 - 11:30 25
    E (-20, -10) 35 10:30 - 12:30 15
    F (20, -5) 40 11:00 - 13:00 20

  • 配送トラック:

    トラックID 積載容量 (ケース) 固定費 (円/日) 変動費 (円/km) 平均速度 (km/h)
    V1 100 6000 120 40
    V2 80 5000 110 45
    V3 80 5000 110 45

  • 地点間距離 (km) と移動時間 (分):

    距離行列 (km)

    デポ A B C D E F
    デポ 0 32 35 25 18 25 23
    A 32 0 30 28 45 55 40
    B 35 30 0 48 30 58 15
    C 25 28 48 0 35 20 45
    D 18 45 30 35 0 30 15
    E 25 55 58 20 30 0 40
    F 23 40 15 45 15 40 0

    移動時間行列 (分) - トラックの平均時速 (40km/h) をもとに計算

3. 最適化モデルの目標と制約

  • 目的関数:
    • 最小化: Σ (使用するトラックの固定費) + Σ (各トラックの総走行距離 × 変動費)
  • 主な制約条件:
    1. 車両割り当て: 各顧客は、いずれか1台のトラックによって、ちょうど1回訪問される。
    2. デポ発着: 使用される各トラックは、デポを出発し、全ての担当顧客を訪問後、デポに戻る。
    3. 積載容量: 各トラックに積み込まれる荷物の総量は、そのトラックの積載容量を超えない。
    4. 時間窓: 各顧客へのトラック到着時刻は、指定された納品時間窓内であること。
      • 到着時刻 >= 時間窓開始時刻
      • 到着時刻 <= 時間窓終了時刻
      • 早く着きすぎた場合は、時間窓開始時刻まで待機する。
    5. 時間連続性: ある地点への到着時刻、荷降ろし時間、次の地点への移動時間を考慮し、次の地点への到着時刻を計算する。
      • 次の地点への到着時刻 = max(現地点到着時刻, 時間窓開始時刻) + 荷降ろし時間 + 移動時間
    6. トラック稼働時間: (オプション) ドライバーの最大労働時間などを考慮することも可能。

4. 期待されるアウトプット (最適化ソルバーによる結果)

  • 使用トラック: 最適なコストを実現するために使用するトラック (V1, V2, V3 のうちどれか、または全部)。
  • 各トラックの担当顧客と訪問順序 (ルート):
    • 例:
      • トラックV1: デポ → C → A → デポ
      • トラックV2: デポ → D → F → B → デポ
      • トラックV3: デポ → E → デポ
  • 各地点への到着・出発予定時刻:
    • 例: トラックV1 - C店到着 10:15, C店出発 10:30, A店到着 11:12 (時間窓違反!), … のような詳細スケジュール。
  • 総配送コスト: 最小化された総コスト (円)。
  • 各トラックの走行距離と積載率:

5. ケーススタディの意義と実務への応用

このケーススタディは、複数の制約（時間、容量、コスト）が絡み合う複雑な配送計画問題を、数理最適化によってどのように解決できるかを示しています。

  • コスト削減: 燃料費、人件費、車両固定費を最適化し、具体的な削減額を提示できる。
  • サービス品質向上: 時間指定遵守により、顧客満足度を高める。
  • 業務効率化: 配車計画作成にかかる時間を大幅に短縮し、属人化を解消できる。
  • 資源の有効活用: トラックの積載率を向上させ、遊休車両を減らす。
  • 意思決定支援: 新規顧客獲得時や車両増減時の影響をシミュレーションし、戦略的な意思決定を支援する。

これは、タイムウィンドウ付き異種車両配送計画問題 (Heterogeneous Fleet Vehicle Routing Problem with Time Windows - HFVRPTW) と呼ばれる典型的な数理最適化問題です。

問題の定義と定式化

この問題を数理モデルとして定式化するために、以下の集合、パラメータ、変数を定義します。

1. 集合 (Sets)

  • \(V\): トラックの集合 (e.g., V1, V2, V3)
  • \(C\): 顧客（店舗）の集合 (e.g., A, B, C, D, E, F)
  • \(N\): デポを含む全地点の集合 (\(N = C \cup \{\text{Depot}\}\))

2. パラメータ (Parameters)

  • \(Q_k\): トラック \(k \in V\) の積載容量
  • \(F_k\): トラック \(k \in V\) の固定費
  • \(C_k^V\): トラック \(k \in V\) の変動費 (距離あたり)
  • \(d_i\): 顧客 \(i \in C\) の需要量
  • \(e_i\): 顧客 \(i \in C\) の納品時間窓の開始時刻
  • \(l_i\): 顧客 \(i \in C\) の納品時間窓の終了時刻
  • \(s_i\): 顧客 \(i \in C\) での荷降ろし時間
  • \(D_{ij}\): 地点 \(i \in N\) から地点 \(j \in N\) への距離
  • \(T_{ijk}\): トラック \(k \in V\) で地点 \(i \in N\) から地点 \(j \in N\) へ移動する時間
  • \(T_{start}\): デポの稼働開始時刻

3. 決定変数 (Decision Variables)

  • \(x_{ijk}\): トラック \(k \in V\) が地点 \(i \in N\) から地点 \(j \in N\) へ直接移動する場合に \(1\)、さもなければ \(0\) となるバイナリ変数。
  • \(y_k\): トラック \(k \in V\) を使用する場合に \(1\)、さもなければ \(0\) となるバイナリ変数。
  • \(t_{ik}\): トラック \(k \in V\) が地点 \(i \in N\) に到着する時刻を表す連続変数。

4. 定式化

目的関数 総配送コスト（全使用トラックの固定費と全トラックの総変動費の合計）を最小化します。 \[\text{Minimize} \quad \sum_{k \in V} F_k \cdot y_k + \sum_{i \in N} \sum_{j \in N} \sum_{k \in V} C_k^V \cdot D_{ij} \cdot x_{ijk}\]

制約条件

  1. 顧客訪問制約: 全ての顧客は、いずれかのトラックによって、ちょうど1回訪問されなければなりません。 \[ \sum_{i \in N, i \neq j} \sum_{k \in V} x_{ijk} = 1 \quad (\forall j \in C) \]
  2. フロー保存則: トラックがある顧客を訪問した場合、必ずその顧客から次の地点へ出発しなければなりません。 \[ \sum_{i \in N, i \neq h} x_{ihk} = \sum_{j \in N, j \neq h} x_{hjk} \quad (\forall h \in C, \forall k \in V) \]
  3. デポ出発・帰着制約: 使用されるトラックは、必ずデポから出発し、1つのルートを担当した後、デポに戻ります。 \[ \sum_{j \in C} x_{\text{Depot}, j, k} = y_k \quad (\forall k \in V) \] \[ \sum_{i \in C} x_{i, \text{Depot}, k} = y_k \quad (\forall k \in V) \]
  4. 積載容量制約: 各トラックが配送する荷物の総需要量は、そのトラックの積載容量を超えてはなりません。 \[ \sum_{i \in C} d_i \left( \sum_{j \in N, j \neq i} x_{ji k} \right) \le Q_k \cdot y_k \quad (\forall k \in V) \]
  5. 時間窓制約: 各顧客への到着時刻は、指定された時間窓内でなければなりません。 \[ e_i \le t_{ik} \le l_i \quad (\text{if customer } i \text{ is visited by truck } k) \]
  6. 時間連続性と部分巡回路除去: ある顧客への到着時刻は、前の顧客でのサービス時間と移動時間を考慮して計算されます。早く到着した場合は待機します。この制約は、同時に非合理な部分巡回路（デポを含まないループ）の発生を防ぎます。 \[ t_{jk} \ge (\max(t_{ik}, e_i) + s_i + T_{ijk}) \cdot x_{ijk} \quad (\forall i \in C, \forall j \in N, i \neq j, \forall k \in V) \] このmaxを含む非線形制約は、線形のBig-M法を用いて以下のように表現されます。\(M\)は十分に大きな定数です。 \[ t_{jk} \ge t_{ik} + s_i + T_{ijk} - M(1-x_{ijk}) \] \[ t_{jk} \ge e_i + s_i + T_{ijk} - M(1-x_{ijk}) \]

4. 部品メーカーにおける月次生産計画最適化

1. 背景と課題

「テクノパーツ工業」は、自動車産業向けに2種類の精密部品（部品X、部品Y）を製造・販売している中小企業です。部品Xと部品Yは、それぞれ異なる原材料を使用し、工場内の2つの主要な工程（切断工程、組立工程）を経て完成します。

現状の課題:

  • 利益最大化の難しさ: 部品XとYでは利益率が異なり、また各工程での加工時間も異なります。どの製品をどれだけ生産すれば、限られた資源（機械稼働時間、原材料在庫）の中で月間の総利益を最大化できるか、経験と勘に頼っており最適化されていない。
  • ボトルネック工程の存在: 特定の工程（特に組立工程の機械）の稼働率が高く、生産全体の制約となっている可能性があるが、定量的に把握できていない。
  • 原材料の過不足: 需要予測に基づいて原材料を発注しているが、生産計画の変動により、月末に特定の原材料が不足したり、逆に過剰在庫になったりすることがある。

これらの課題に対し、数理最適化を用いて、月間総利益を最大化する最適な部品Xと部品Yの生産量を決定することを目指します。

2. データ (月間)

  • 製品情報:

    製品名 販売単価 (円/個) 月間最大需要 (個)
    部品X 5,000 800
    部品Y 6,500 600

  • 原材料情報:

    原材料名 単価 (円/kg) 月間利用可能量 (kg) 部品X必要量 (kg/個) 部品Y必要量 (kg/個)
    材料P 300 3,000 2.0 1.0
    材料Q 500 4,000 1.5 3.0

  • 工程・機械情報:

    工程名 使用機械 利用可能時間 (時間/月) 部品X処理時間 (時間/個) 部品Y処理時間 (時間/個) 加工費 (円/時間)
    切断 機械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月)

  • 製品情報:

    製品名 販売単価 (円/個) 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個 (安全在庫として)

  • 原材料情報:

    原材料名 単価 (円/kg) 1月調達量(kg) 2月調達量(kg) 3月調達量(kg) 在庫保管費 (円/kg/月) 部品X必要量(kg/個) 部品Y必要量(kg/個)
    材料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

  • 工程・機械情報 (各月共通):

    工程名 使用機械 月間利用可能時間(時間) 部品X処理時間(時間/個) 部品Y処理時間(時間/個) 加工費 (円/時間)
    切断 機械A 400 0.15 0.20 2,000
    組立 機械B 350 0.25 0.30 3,000

3. ケーススタディの意義と実務への応用

この多期間モデルは、単期間モデルよりも現実に近い状況を扱えます。

  • 需要変動への戦略的対応: 先行生産や在庫調整により、需要の波に柔軟に対応し、機会損失を最小化する。
  • サプライチェーンリスクへの備え: 原材料供給の変動などを事前に計画に織り込むことで、生産停止リスクを低減する。
  • 在庫コストの最適化: 過剰な在庫や欠品を防ぎ、製品・原材料の両方で最適な在庫レベルを維持する。
  • キャッシュフローの改善: 生産、販売、在庫のバランスを取ることで、資金繰りを安定させる計画を立てられる。
  • 中期的な視点での資源配分: 複数期間にわたる機械稼働や原材料調達を最適化し、工場全体の生産性を高める。

このような中期的な生産・在庫最適化計画は、企業の収益性向上と安定的な操業に不可欠であり、多くの製造業でSCM (サプライチェーンマネジメント) の一環として導入されています。

複数期間にわたる生産・在庫最適化計画

提示された課題は、複数期間（今回は3ヶ月）にわたる需要やコスト、供給の変動を考慮し、全体の利益を最大化する生産計画および在庫計画を同時に策定する問題です。このような問題は、数理最適化の分野で「多期間計画問題」として知られており、線形計画法（Linear Programming）を用いて最適化することが可能です。

1. 問題の定義と定式化

この問題の目的は、3ヶ月間の総利益（総売上 - 総費用）を最大化することです。総費用は、原材料費、加工費、製品在庫保管費、原材料在庫保管費の合計です。これを達成するために、各月にどの製品をどれだけ生産し、どれだけ販売し、どれだけ在庫として保有するかを決定します。

集合とインデックス

  • \(P\): 製品の集合 (\(p \in P\))
  • \(M\): 原材料の集合 (\(m \in M\))
  • \(C\): 工程（機械）の集合 (\(c \in C\))
  • \(T\): 計画期間（月）の集合 (\(t \in T = \{1, 2, 3\}\))
  • \(T_0\): 初期在庫を含む期間の集合 (\(t \in T_0 = \{0, 1, 2, 3\}\))

パラメータ

  • \(SalesPrice_p\): 製品 \(p\) の販売単価
  • \(Demand_{pt}\): 月 \(t\) における製品 \(p\) の需要量
  • \(ProdHoldingCost_p\): 製品 \(p\) の在庫保管費（/個・月）
  • \(InitialProdInv_p\): 製品 \(p\) の初期在庫量（0ヶ月目末）
  • \(TargetProdInv_p\): 製品 \(p\) の目標期末在庫量（最終月）
  • \(MaterialPrice_m\): 原材料 \(m\) の調達単価
  • \(Procurement_{mt}\): 月 \(t\) における原材料 \(m\) の調達量
  • \(MatHoldingCost_m\): 原材料 \(m\) の在庫保管費（/kg・月）
  • \(InitialMatInv_m\): 原材料 \(m\) の初期在庫量（0ヶ月目末）
  • \(MaterialNeed_{mp}\): 製品 \(p\) を1個生産するのに必要な原材料 \(m\) の量
  • \(MachineHours_c\): 機械 \(c\) の月間利用可能時間
  • \(ProcessTime_{cp}\): 製品 \(p\) の生産に機械 \(c\) が要する時間
  • \(ProcessingCost_c\): 機械 \(c\) の加工費（/時間）

決定変数

  • \(Produce_{pt} \ge 0\): 月 \(t\) に製品 \(p\) を生産する量
  • \(Sell_{pt} \ge 0\): 月 \(t\) に製品 \(p\) を販売する量
  • \(ProdInv_{pt_0} \ge 0\): 月 \(t_0\) 末時点での製品 \(p\) の在庫量 (\(t_0 \in T_0\))
  • \(MatInv_{mt_0} \ge 0\): 月 \(t_0\) 末時点での原材料 \(m\) の在庫量 (\(t_0 \in T_0\))

目的関数

総利益 = (総売上) - (原材料費 + 加工費 + 製品在庫費 + 原材料在庫費) を最大化します。

\[\text{maximize} \quad \sum_{p \in P, t \in T} SalesPrice_p \cdot Sell_{pt} - \left( \sum_{m \in M, t \in T} MaterialPrice_m \cdot Procurement_{mt} + \dots \right)\]

制約条件

  1. 製品の在庫バランス: (前月の在庫) + (当月の生産量) - (当月の販売量) = (当月の在庫) \[ProdInv_{p, t-1} + Produce_{pt} - Sell_{pt} = ProdInv_{pt} \quad (\forall p \in P, \forall t \in T)\]
  2. 原材料の在庫バランス: (前月の在庫) + (当月の調達量) - (当月の消費量) = (当月の在庫) \[MatInv_{m, t-1} + Procurement_{mt} - \sum_{p \in P} MaterialNeed_{mp} \cdot Produce_{pt} = MatInv_{mt} \quad (\forall m \in M, \forall t \in T)\]
  3. 販売量の上限: 各月の販売量は、その月の需要量を超えることはできません。 \[Sell_{pt} \le Demand_{pt} \quad (\forall p \in P, \forall t \in T)\]
  4. 機械の稼働時間制約: 各月の各機械の総稼働時間は、利用可能時間以下でなければなりません。 \[\sum_{p \in P} ProcessTime_{cp} \cdot Produce_{pt} \le MachineHours_c \quad (\forall c \in C, \forall t \in T)\]
  5. 初期在庫・期末在庫の制約:
    • \(ProdInv_{p,0} = InitialProdInv_p \quad (\forall p \in P)\)
    • \(MatInv_{m,0} = InitialMatInv_m \quad (\forall m \in M)\)
    • \(ProdInv_{p, |T|} \ge TargetProdInv_p \quad (\forall p \in P)\)

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 分析: もし予算が変わったら？特定の媒体の効果が予測より高かったら/低かったら？といったシナリオ分析を容易に行い、計画の柔軟性を高める。
  • コミュニケーションツール: 最適化結果とその根拠を明確に示すことで、関係部署（経営層、営業部門など）との合意形成を円滑にする。

問題の定義と定式化

1. 問題の定義

ある企業が、新製品の広告キャンペーンのために1,000万円の予算を持っています。複数の広告媒体（テレビ、ラジオ、新聞、Web、屋外広告）を利用可能で、それぞれの媒体は費用、期待できるリーチ数、および出稿量の制約（最小・最大量）が異なります。また、Web広告には総予算の30%以上を割り当てるという追加の制約があります。 この問題の目的は、与えられた制約条件の中で、キャンペーン全体の総リーチ数を最大化する各媒体への最適な予算配分（出稿量）を決定することです。

2. 数理モデルの定式化

この問題を数理最適化問題として定式化します。

集合とインデックス

  • \(M\): 広告媒体の集合 (e.g., TV, Radio, …)
  • \(M_{web} \subset M\): Web広告媒体の集合
  • \(m \in M\): 各広告媒体を指すインデックス

パラメータ

  • \(B\): キャンペーンの総予算 (円)
  • \(B_{web\_min}\): Web広告に割り当てるべき最小予算 (円)
  • \(c_m\): 媒体 \(m\) の単位あたりの費用 (円/単位)
  • \(r_m\): 媒体 \(m\) の単位あたりのリーチ数 (人/単位)
  • \(L_m\): 媒体 \(m\) の最小出稿量 (単位)
  • \(U_m\): 媒体 \(m\) の最大出稿量 (単位)

※「単位」は媒体ごとに異なります。テレビCMなら「回」、Web広告なら「1万円分の予算」など。

決定変数

  • \(X_m\): 媒体 \(m\) の出稿量（単位）。\(L_m \le X_m \le U_m\) の範囲の非負の数値です。

目的関数

総リーチ数を最大化します。 \[\text{Maximize} \quad \sum_{m \in M} r_m X_m\]

制約条件

  1. 総予算制約: キャンペーンの総費用は、与えられた総予算 \(B\) を超えてはなりません。 \[\sum_{m \in M} c_m X_m \le B\]

  2. Web広告予算比率制約: Web広告への支出合計は、指定された最小Web広告予算 \(B_{web\_min}\) 以上でなければなりません。 \[\sum_{m \in M_{web}} c_m X_m \ge B_{web\_min}\]

  3. 出稿量制約（変数の上下限）: 各媒体の出稿量は、それぞれの最小量と最大量の範囲内でなければなりません。これは決定変数の定義に含まれます。 \[L_m \le X_m \le U_m \quad (\forall m \in M)\]

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試合を行う。
  • 制約条件:
    1. チーム可用性: チームT1は、Week 3にホームアリーナが使用できないため、ホームゲームを開催できない。
    2. 会場共有: チームT3とチームT4は同じアリーナを共有しているため、同じ週に両チームがホームゲームを行うことはできない。
    3. 連戦制限: 選手の負担を考慮し、どのチームも3週連続でホームゲーム、または3週連続でアウェイゲームにならないようにする。

4. ケーススタディの意義と実務への応用

このケーススタディは、数理最適化がスポーツスケジューリングにおいて以下の価値を提供することを示しています。

  • 公平性の保証: ホーム/アウェイ数などの公平性に関する基準を明確な制約や目的関数として組み込み、それを満たすスケジュールを作成できる。
  • 複雑な制約の処理: チーム、会場、連戦など、多岐にわたる複雑なルールや制約を矛盾なく考慮したスケジュールを生成できる。
  • 効率化と客観性: スケジュール作成にかかる時間と労力を大幅に削減し、属人的な判断ではなくデータとルールに基づいた客観的な結果を得られる。
  • 多様なシナリオ検討: 新チームの加入、期間の変更、制約の追加・緩和などが発生した場合でも、モデルを修正して迅速に新しいスケジュール案を作成できる。
  • 関係者への説明責任: 最適化プロセスとその結果は、なぜそのスケジュールになったのかを論理的に説明する根拠となり、チームやファンへの説明責任を果たしやすくなる。

8. 日次電力供給計画のコスト最小化

1. 背景と課題

地域電力供給会社「エリアパワー株式会社」は、管轄エリア内の家庭や企業への安定的な電力供給を使命としています。同社は複数の発電プラント（火力、水力、太陽光）を保有・運用しており、日々の電力需要は時間帯によって大きく変動します。

課題:

  • コスト効率: 各発電プラントは発電コスト（燃料費など）や運用特性（出力調整のしやすさ、最低稼働レベルなど）が異なります。コストを抑えつつ電力を供給する必要があります。
  • 需要変動への対応: 刻々と変わる電力需要を正確に予測し、それに対して過不足なく発電量を調整しなければ、供給不安や電力余剰による損失が発生します。
  • 再生可能エネルギーの活用: 環境負荷低減のため太陽光発電を導入していますが、その出力は天候や時間帯に左右されるため、他の電源との最適な組み合わせ（ミックス）が求められます。
  • プラント制約: 各プラントには最大出力容量があり、火力発電所などでは安定運用のための最低出力レベルも考慮する必要があります。

これらの複雑な要因を考慮し、翌日の各時間帯における最適な発電計画（どのプラントでどれだけ発電するか）を策定し、総発電コストを最小化しつつ、電力需要を確実に満たすことが喫緊の課題となっています。

2. 目標

  • 翌日（24時間）の電力需要予測に基づき、全ての時間帯で需要を満たす。
  • 各発電プラントの運用制約（容量、最低出力、太陽光の出力変動）を守る。
  • 上記を満たした上で、1日の総発電コスト（主に燃料費）を最小化する。

3. 発電プラントとデータ

エリアパワー社が運用する発電プラントと、翌日の計画に必要なデータは以下の通りです。 (簡単のため、1日を3つの時間帯：深夜早朝(T1: 0-8時)、日中(T2: 8-16時)、夕夜間(T3: 16-24時)に分割します)

プラントID タイプ 最大容量(MW) 最低出力(MW) 発電コスト(円/MWh) 備考
PL1 火力(LNG) 500 100 8,000 比較的起動・停止・出力調整が容易
PL2 火力(石炭) 800 250 5,000 起動・停止に時間がかかるがコストは安い
PL3 水力 300 0 1,000 貯水量による制約は今回考慮しない
PL4 太陽光 200 0 0 出力は時間帯・天候依存 (後述)

時間帯別データ:

時間帯 ID 電力需要予測(MW) 太陽光(PL4)最大出力(MW)
深夜早朝 T1 900 0
日中 T2 1500 180
夕夜間 T3 1200 20

4. ケーススタディの意義と実務への応用

このケーススタディは、数理最適化が電力供給計画において以下の価値を提供することを示しています。

  • コスト削減: 燃料費や運用コストを考慮し、最も経済的な発電所の組み合わせと出力を決定することで、大幅なコスト削減を実現できる。
  • 安定供給の確保: 需要予測とプラントの能力・制約に基づいて計画を立てることで、電力不足のリスクを低減し、安定供給を支援する。
  • 再生可能エネルギーの統合: 出力が不安定な再生可能エネルギー源を、他の調整可能な電源と組み合わせて最大限有効活用する計画を立案できる。
  • 複雑な運用制約への対応: 最大/最小出力、起動停止時間（より高度なモデルで考慮）、送電網の制約（これも高度なモデルで考慮）など、現実の複雑な制約下での最適運用計画を作成できる。
  • 迅速な計画修正: 需要予測やプラントの状態が変化した場合でも、モデルを更新して迅速に最適な計画を再計算できる。

電力系統の運用計画（ユニットコミットメント、経済負荷配分など）は、数理最適化が極めて重要かつ効果的に活用されている分野の一つであり、エネルギーコストの削減と供給信頼性の向上に不可欠なツールとなっています。

9. 農場の季節別作物栽培計画による収益最大化

1. 背景と課題

ある家族経営の農場「グリーンフィールド・ファーム」は、100ヘクタールの耕作可能な土地を所有しています。農場主は、来シーズンに向けてどの作物をどれだけの面積で作付けし、どの程度の資源（水、肥料、労働力）を投入すれば、農場全体の収益を最大化できるか悩んでいます。

課題:

  • 作物選択: 栽培可能な作物は複数（例: トマト、小麦、トウモロコシ）あり、それぞれ市場価格、収穫量、必要な資源（土地、水、肥料、労働時間）、栽培期間が異なります。
  • 資源制約: 利用可能な土地面積、水利権に基づく月間取水量、購入可能な肥料の量、そして家族や臨時雇いを含めた月間の総労働時間には限りがあります。
  • 季節性・天候: 作物ごとに最適な作付け時期と収穫時期があり、また月ごとの天候（主に降水量）が水の必要量に影響します。豊作/不作による収穫量や価格の変動リスクもあります（今回は簡略化のため、平均的な値を使用）。
  • 輪作計画（簡略化）: 特定の作物を連作することによる土壌への影響も考慮する必要がありますが、ここでは特定の組み合わせを避ける簡単な制約のみ考えます。

農場主は、これらの要因を総合的に考慮し、データに基づいて収益を最大化する年間（または季節別）の作物栽培計画を立てたいと考えています。

2. 目標

  • 限られた土地、水、肥料、労働力の中で、年間を通じて栽培する作物の種類と面積を決定する。
  • 各資源の制約と作物の栽培要件を満たす。
  • 上記を満たした上で、年間の総粗利益（総売上 - 総変動費）を最大化する。

3. 作物と資源データ

ここでは、簡単のため主要な3つの作物と、春・夏・秋の3つの栽培期間を考えます。

作物データ (1ヘクタールあたり):

作物 略称 期間 予想収量(トン) 市場価格(円/トン) 水必要量(m³/月) 肥料必要量(kg) 労働時間(時間/月) 備考
トマト 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. ケーススタディの意義と実務への応用

このケーススタディは、数理最適化が農業経営において以下の価値を提供することを示しています。

  • 収益性の向上: 市場価格、コスト、収量、資源制約を総合的に考慮し、最も収益性の高い作物ミックスと作付面積を決定できる。
  • 資源の効率的利用: 土地、水、肥料、労働力といった限られた資源を最も効果的に配分し、無駄を削減する。ボトルネックとなっている資源を特定し、改善策（例: 節水技術の導入、労働力の確保）の検討に繋げる。
  • リスク管理: 天候不順や価格変動のリスクを考慮したシナリオ分析を行い、より頑健な生産計画を立てるための情報を提供する（感度分析）。
  • 計画策定の高度化: 経験や勘に頼るだけでなく、データに基づいた客観的で合理的な栽培計画を迅速に作成できる。
  • 持続可能性への貢献: 水や肥料などの投入量を最適化することで、環境負荷の低減にも貢献できる可能性がある。

農業生産計画は、天候などの不確実性も伴う複雑な問題ですが、数理最適化を用いることで、より科学的で収益性の高い、持続可能な農業経営を目指すための強力なツールとなります。

1. 問題の定義と定式化

この問題は、限られた資源（土地、水、肥料、労働力）のもとで、年間の総粗利益を最大化する作物の作付面積を決定する線形計画問題として定式化できます。

1.1. 集合とインデックス

  • \(C\): 作物の集合 (e.g., TOM: トマト, WHT: 小麦, COR: トウモロコシ)
  • \(P\): 栽培期間の集合 (e.g., SPR: 春, SUM: 夏, AUT: 秋)
  • \(R\): 資源の集合 (e.g., WATER: 水, FERTILIZER: 肥料, LABOR: 労働力)

1.2. パラメータ

  • \(\text{land\_limit}\): 利用可能な総土地面積 (ヘクタール)
  • \(\text{yield}_c\): 作物 \(c \in C\) の1ヘクタールあたりの収量 (トン)
  • \(\text{price}_c\): 作物 \(c \in C\) の市場価格 (円/トン)
  • \(\text{resource\_cost}_r\): 資源 \(r \in R\) の単位あたりの変動費 (円/m³, 円/kg, 円/時間)
  • \(\text{resource\_limit}_{r,p}\): 期間 \(p \in P\) における資源 \(r \in R\) の利用上限
  • \(\text{resource\_consumption}_{c,r,p}\): 作物 \(c \in C\) を1ヘクタール栽培するのに必要な、期間 \(p \in P\) における資源 \(r \in R\) の量
  • \(\text{occupies}_{c,p}\): 作物 \(c \in C\) が期間 \(p \in P\) に土地を占有する場合 1、そうでなければ 0

1.3. 決定変数

  • \(\text{CultivateArea}_c \ge 0\): 作物 \(c \in C\) の作付面積 (ヘクタール)

1.4. 目的関数

年間の総粗利益（総売上 - 総変動費）を最大化します。 - 総売上: \(\sum_{c \in C} (\text{yield}_c \times \text{price}_c \times \text{CultivateArea}_c)\) - 総変動費: \(\sum_{c \in C} \sum_{r \in R} \sum_{p \in P} (\text{resource\_consumption}_{c,r,p} \times \text{resource\_cost}_r \times \text{CultivateArea}_c)\)

これをまとめると、以下の目的関数となります。 \[ \text{Maximize} \quad \sum_{c \in C} \text{CultivateArea}_c \left( \text{yield}_c \cdot \text{price}_c - \sum_{p \in P} \sum_{r \in R} \text{resource\_consumption}_{c,r,p} \cdot \text{resource\_cost}_r \right) \]

1.5. 制約条件

  1. 土地制約: 各期間において、作付けされている総面積は土地の上限を超えてはなりません。 \[ \forall p \in P, \quad \sum_{c \in C} (\text{occupies}_{c,p} \times \text{CultivateArea}_c) \le \text{land\_limit} \]
  2. 資源制約: 各期間、各資源において、総消費量は利用上限を超えてはなりません。 \[ \forall r \in R, \forall p \in P, \quad \sum_{c \in C} (\text{resource\_consumption}_{c,r,p} \times \text{CultivateArea}_c) \le \text{resource\_limit}_{r,p} \]
  3. 非負制約: 作付面積は0以上でなければなりません。 \[ \forall c \in C, \quad \text{CultivateArea}_c \ge 0 \]

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. ケーススタディの意義と実務への応用

このケーススタディは、数理最適化が航空会社の運行計画において以下の価値を提供することを示しています。

  • 大幅なコスト削減: 燃料効率の良い機材を適切に割り当て、不要な大型機の投入を避けることで、運航コスト（特に燃料費）を大幅に削減できる。
  • 収益機会の最大化: 需要予測に基づいて適切な座席数を供給することで、逸失利益を減らし、収益を最大化する。
  • 機材稼働率の向上: 効率的な機材繰りを計画することで、機材の遊休時間を減らし、投資対効果を高める。
  • 複雑な制約下での意思決定: 空港スロット、機材数、需要など、多数の制約が絡み合う中で、実行可能で最適な計画を迅速に作成できる。
  • 運航の安定性向上: 事前に矛盾のない計画を立てることで、当日のイレギュラー発生リスクを低減する（ただし、実際の不規則運航への対応はさらに別の最適化問題となる）。
  • 戦略的意思決定支援: 新しい機材の導入や路線の開設/廃止が、全体のコストや効率にどう影響するかをシミュレーションし、経営判断を支援する。

航空会社のフリートアサインメントとスケジューリングは、オペレーションズ・リサーチの古典的かつ重要な応用分野であり、数理最適化技術によって日々莫大な経済的価値が生み出されています。

航空会社の機材割り当て最適化問題

1. 問題の定義

国内線を運航する航空会社が、翌日の運航計画において、総運航コストを最小化するための最適な機材割り当てを決定する問題です。この計画では、各フライトの旅客需要を満たし、保有する機材の数や空港の離着陸能力（スロット）といった物理的制約、さらには機材が空港間を連続して運航するためのフロー（機材繰り）の整合性を保つ必要があります。

この問題は、どのフライトにどの機材を割り当てるかという組み合わせ最適化問題であり、特に混合整数計画問題（MIP）として定式化することができます。

2. 定式化

集合とインデックス

  • \(A\): 空港の集合 (\(a \in A\))
  • \(P\): 航空機タイプの集合 (\(p \in P\))
  • \(F\): 運航候補フライトの集合 (\(f \in F\))
  • \(T\): 1日の運用を離散化した時間帯の集合 (\(t \in T\))

パラメータ

  • \(Seat_p\): 機材タイプ \(p\) の座席数
  • \(NumPlanes_p\): 機材タイプ \(p\) の保有数
  • \(HourlyCost_p\): 機材タイプ \(p\) の時間当たり運航コスト
  • \(Demand_f\): フライト \(f\) の予測需要
  • \(Duration_f\): フライト \(f\) の飛行時間
  • \(DepAP_f, ArrAP_f\): フライト \(f\) の出発空港と到着空港
  • \(DepTime_f, ArrTime_f\): フライト \(f\) の出発時刻と到着時刻
  • \(InitPlanes_{ap}\): 空港 \(a\) における機材タイプ \(p\) の初期配置数
  • \(SlotLimit_{at}\): 空港 \(a\)、時間帯 \(t\) での離着陸スロット上限

計算パラメータ

  • \(FlightCost_{fp} = HourlyCost_p \times Duration_f\): フライト \(f\) を機材 \(p\) で運航するコスト

決定変数

  • \(Assign_{fp} \in \{0, 1\}\): フライト \(f\) に機材タイプ \(p\) を割り当てる場合に1、そうでない場合に0をとるバイナリ変数。

目的関数

総運航コストを最小化します。

\[\text{minimize} \quad \sum_{f \in F} \sum_{p \in P} FlightCost_{fp} \cdot Assign_{fp}\]

制約条件

  1. 一便一機材: 各フライトには、必ずいずれか1つの機材タイプが1機だけ割り当てられます。

    \[\sum_{p \in P} Assign_{fp} = 1, \quad \forall f \in F\]

  2. 需要充足: 割り当てられた機材の座席数は、フライトの予測需要以上でなければなりません。

    \[\sum_{p \in P} Seat_p \cdot Assign_{fp} \ge Demand_f, \quad \forall f \in F\]

  3. 機材数上限: 各時刻において、飛行中の各機材タイプの総数は、そのタイプの保有総数を超えてはなりません。

    \[\sum_{f \in F: DepTime_f \le t \text{ and } ArrTime_f > t} Assign_{fp} \le NumPlanes_p, \quad \forall p \in P, \forall t \in T\]

  4. 機材フロー保存: 各空港、各時刻において、その時刻までに到着した機材の累積数（初期配置を含む）は、その時刻までに出発した機材の累積数以上でなければなりません。これにより、存在しない機材が出発することを防ぎます。

    \[\sum_{f \in F: ArrTime_f \le t, ArrAP_f = a} Assign_{fp} + InitPlanes_{ap} \ge \sum_{f \in F: DepTime_f \le t, DepAP_f = a} Assign_{fp}, \quad \forall a \in A, \forall p \in P, \forall t \in T\]

  5. 空港スロット: 各空港、各時間帯において、離陸する便と着陸する便の合計数は、空港の処理能力（スロット）の上限を超えてはなりません。

\[\sum_{f \in F: \lfloor DepTime_f \rfloor = t, DepAP_f = a} \sum_{p \in P} Assign_{fp} + \sum_{f \in F: \lfloor ArrTime_f \rfloor = t, ArrAP_f = a} \sum_{p \in P} Assign_{fp} \le SlotLimit_{at}, \quad \forall a \in A, \forall t \in T\]

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) とコスト: (コストは仮の単位)

    ペアリングID カバーするフライトレグ コスト (Cost[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)

    L1 L2 L3 L4 L5 L6
    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. 設定とデータ

  • 時間割枠 (T): 月曜～金曜の各1限～3限 (簡単のため 5曜日 * 3時限 = 15スロット)

    • t1: 月1限, t2: 月2限, …, t15: 金3限

  • 授業リスト (J):

    授業ID 科目名 教員ID 受講者数 要プロジェクター 備考/制約
    C1 最適化入門 ProfA 40 Yes
    C2 線形代数 ProfB 60 Yes
    C3 プログラミング基礎 ProfC 50 Yes
    C4 データ構造 ProfC 45 Yes
    C5 統計学 ProfB 55 No
    C6 経済学原論 ProfA 70 Yes 月曜午前(t1, t2)は担当不可

  • 教室リスト (R):

    教室ID 収容人数 プロジェクター
    R101 50 Yes
    R102 75 Yes
    R201 60 No
    R202 80 Yes

  • 教員可用性:

    • ProfA: 月曜午前(t1, t2) は担当不可。
    • その他は全時間帯で担当可能と仮定。

4. ケーススタディの意義と実務への応用

このケーススタディは、数理最適化が教室割り当てとスケジューリングにおいて以下の価値を提供することを示しています。

  • 衝突のないスケジュールの保証: 複雑な条件（教室、教員、設備、収容人数）を考慮し、ルール違反のない実行可能な時間割を確実に作成できます。
  • リソース利用の効率化: 教室の収容人数や設備を考慮して授業を割り当てることで、教室の無駄遣いを減らし、利用率を向上させることができます（目的関数に組み込めばより明確に）。
  • 計画作成の自動化と迅速化: 面倒で時間のかかる割り当て作業を自動化し、担当者の負担を大幅に軽減します。急な変更（教員の都合、教室の変更など）にも迅速に対応できます。
  • 公平性と透明性: 特定の教員への負担集中などを避ける制約を追加したり、割り当て結果の根拠を明確に示したりすることで、公平性を高め、関係者への説明責任を果たしやすくなります。
  • What-if 分析: 新しい授業の追加、教室の改修、履修人数の変動などが、時間割全体にどのような影響を与えるかを事前にシミュレーションできます。

大学や学校における時間割・教室割り当ては、多くの関係者の要求と物理的な制約が絡み合う典型的な組合せ最適化問題であり、数理最適化の導入効果が高い分野の一つです。

大学の授業スケジューリングと教室割り当ての最適化

提示された課題は、多くの制約条件を考慮しながら、授業を時間割と教室に効率的に割り当てる最適化問題です。ここでは、数理最適化モデリング言語AMPLを用いてこの問題を解決するアプローチを示します。

1. 問題の定義と定式化

この問題は、どの授業を、どの時間枠に、どの教室で実施するかを決定する「割り当て問題」として定式化できます。目標は、物理的、人的、設備的な制約をすべて満たす実行可能な時間割を作成することです。

集合とインデックス

  • \(J\): 授業の集合 (\(j \in J\))
  • \(T\): 時間割枠（タイムスロット）の集合 (\(t \in T\))
  • \(R\): 教室の集合 (\(r \in R\))
  • \(P\): 教員の集合 (\(p \in P\))
  • \(U \subseteq P \times T\): 教員が担当不可能なスロットの集合 (\((p, t) \in U\))

パラメータ

  • \(Teacher_j\): 授業 \(j\) の担当教員
  • \(Enrollment_j\): 授業 \(j\) の予想受講者数
  • \(ReqProj_j\): 授業 \(j\) がプロジェクターを必要とするか (Yes=1, No=0)
  • \(Capacity_r\): 教室 \(r\) の収容人数
  • \(HasProj_r\): 教室 \(r\) にプロジェクターがあるか (Yes=1, No=0)

決定変数

  • \(Assign_{j,t,r}\): 授業 \(j\) を時間 \(t\) に教室 \(r\) で実施する場合に 1、そうでない場合に 0 をとるバイナリ変数。

目的関数

今回はすべての必須制約を満たす実行可能な解を見つけることが主目的であるため、目的関数はダミーとして定数0の最小化を設定します。 \[\text{minimize} \quad \text{DummyObjective}: 0\]

制約条件

  1. 授業割り当て制約: 全ての授業は、ただ1つの時間と教室の組み合わせに割り当てられなければなりません。 \[\sum_{t \in T} \sum_{r \in R} Assign_{j,t,r} = 1 \quad (\forall j \in J)\]
  2. 教室の衝突回避: 各時間、各教室には、最大で1つの授業しか割り当てられません。 \[\sum_{j \in J} Assign_{j,t,r} \le 1 \quad (\forall t \in T, \forall r \in R)\]
  3. 教員の衝突回避: 各時間、各教員は、最大で1つの授業しか担当できません。 \[\sum_{j \in J : Teacher_j=p} \sum_{r \in R} Assign_{j,t,r} \le 1 \quad (\forall p \in P, \forall t \in T)\]
  4. 収容人数・設備・教員可用性の制約: 割り当ては、収容人数、設備、教員の担当可能時間の条件を満たす組み合わせでのみ可能です。これは、変数を定義するインデックス集合を、予めこれらの条件を満たすものに限定することで効率的に表現します。 \[Assign_{j,t,r} = 0 \quad \text{if} \begin{cases} Enrollment_j > Capacity_r \\ \text{or} \quad (ReqProj_j = 1 \text{ and } HasProj_r = 0) \\ \text{or} \quad (Teacher_j, t) \in U \end{cases}\]

2. AMPLモデルとデータ

上記の定式化に基づき、AMPLのモデルとデータを作成します。ハードな制約（収容人数、設備、教員可用性）を満たさない割り当ては、実行不可能な組み合わせとして予め除外するために POSSIBLE_ASSIGNMENTS という補助的な集合を定義します。これにより、モデルがより効率的になります。

13. 森林公園における希少動物生息地の監視センサーネットワーク設計

1. 背景と課題

広大な森林公園「ミドリの森国立公園」の管理事務所は、公園内に生息する希少動物（例：特別天然記念物のニホンカモシカ）の生態調査と保護のため、主要な生息候補地や水飲み場を監視するセンサーネットワークの導入を計画しています。しかし、設置できるセンサーの数や性能、設置・運用にかかる予算は限られています。

課題:

  • 効果的なカバレッジ: 限られた予算内で、できるだけ多くの重要監視ポイントをカバーしたい。特に、過去の目撃情報が多いポイントや、密猟のリスクがあるポイントは優先的に監視したい。
  • センサー選択: 性能（検知範囲）とコスト（設置費、通信費）が異なる複数のセンサータイプから、最適な組み合わせを選ぶ必要がある。
  • 設置場所の選定: センサーを設置できる候補地点はいくつかあるが、地形やアクセスの制約がある。どの候補地点にどのセンサーを置くのが最も効率的か。
  • コスト管理: 設置費用だけでなく、データ通信にかかるランニングコストも考慮し、予算内に収める必要がある。

管理事務所は、これらの課題を解決するため、数理最適化を用いて、予算内で最も効果的なカバレッジ（重要度を考慮）を達成するセンサーの配置計画を策定したいと考えています。

2. 目標

  • 与えられた総予算内で、センサーの設置場所とタイプを決定する。
  • 各監視ターゲットポイントの重要度を考慮し、総カバレッジスコア（カバーされたターゲットの重要度の合計）を最大化する。
  • 設置場所の制約（各候補地に設置できるセンサーは1つまで）を守る。

3. 設定とデータ

  • センサー設置候補地点 (L): 公園内の5箇所 {L1, L2, L3, L4, L5}

  • 監視ターゲットポイント (T): 動物の生息・活動が予想される10箇所 {T1, T2, …, T10}

  • センサータイプ (S):

    • SensorA (標準型): 設置コスト 5万円, 通信コスト 1万円/年, 検知範囲 1km
    • SensorB (広範囲型): 設置コスト 12万円, 通信コスト 2万円/年, 検知範囲 2km

  • ターゲットポイントの重要度 (Importance[j]): (1～5の5段階評価)

    ターゲット T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
    重要度 5 4 5 3 2 3 4 2 3 5

  • 設置候補地点からターゲットポイントまでの距離 (km) とカバレッジ: (距離が検知範囲以下ならカバー可能 (1)、超えるなら不可 (0))

    SensorA (範囲1km) でのカバー可否 Covers[l, SensorA, j]:

    T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
    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]:

    T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
    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) の普及に伴い、ますます重要性が高まっている分野であり、数理最適化はその効率性と効果を最大化するための重要なツールとなります。

センサーネットワーク配置の最適化問題

問題の定義と定式化

この問題は、限られた予算内でセンサーの設置場所と種類を最適に選択し、監視対象エリアのカバレッジを最大化する、典型的な最大被覆問題（Maximal Covering Location Problem）の一種です。特に、各ターゲットの重要度を考慮に入れるため、重み付きの最大被覆問題として定式化します。

集合とインデックス

  • \(L\): センサー設置候補地点の集合 (\(l \in L\))
  • \(S\): センサータイプの集合 (\(s \in S\))
  • \(J\): 監視ターゲットポイントの集合 (\(j \in J\))

パラメータ

  • \(InstallCost_s\): センサータイプ \(s\) の設置コスト
  • \(CommCost_s\): センサータイプ \(s\) の（初年度）通信コスト
  • \(Budget\): 利用可能な総予算
  • \(Importance_j\): ターゲットポイント \(j\) の重要度
  • \(Covers_{lsj}\): 候補地点 \(l\) にセンサー \(s\) を設置した際に、ターゲット \(j\) がカバーされるか否かを示すバイナリ値（カバーされるなら1、されないなら0）

決定変数

  • \(Place_{ls} \in \{0, 1\}\): 候補地点 \(l\) にセンサータイプ \(s\) を設置する場合に1、そうでない場合に0をとるバイナリ変数。
  • \(IsCovered_j \in \{0, 1\}\): ターゲットポイント \(j\) がいずれかのセンサーによってカバーされる場合に1、そうでない場合に0をとるバイナリ変数。

目的関数

カバーされた各ターゲットの重要度の合計（総カバレッジスコア）を最大化します。 \[\text{maximize} \quad \sum_{j \in J} Importance_j \cdot IsCovered_j\]

制約条件

  1. 設置場所制約: 各設置候補地点には、最大でも1つのセンサーしか設置できません。 \[\sum_{s \in S} Place_{ls} \le 1 \quad (\forall l \in L)\]
  2. 予算制約: 設置する全てのセンサーの総コスト（設置費＋通信費）は、総予算を超えてはなりません。 \[\sum_{l \in L} \sum_{s \in S} (InstallCost_s + CommCost_s) \cdot Place_{ls} \le Budget\]
  3. カバレッジ定義: あるターゲットポイント \(j\) がカバーされる（\(IsCovered_j = 1\) となる）のは、そのターゲットを監視可能なセンサーが少なくとも1つ設置された場合に限ります。この関係は以下の制約で表現できます。 \[IsCovered_j \le \sum_{l \in L} \sum_{s \in S, \text{ s.t. } Covers_{lsj}=1} Place_{ls} \quad (\forall j \in J)\] この制約により、ターゲット \(j\) をカバーするセンサーが一つも設置されない場合（右辺が0）、\(IsCovered_j\) は0にならざるを得ません。目的関数が \(IsCovered_j\) の最大化を目指すため、右辺が1以上になれば \(IsCovered_j\) は1となり、正しくカバレッジを表現できます。

14. 時間帯ごとに複数の仕事をもつシフトスケジューリング問題

背景: 「ミニマート・サポート」は、小規模なオンラインストアの顧客対応を3名のスタッフで行っています。効率的な運営のため、3日間のシフトを計画する必要があります。

目的: 3名のスタッフを、3日間のシフトに割り当てる。その際、各シフトの必要人数を満たし、特定の勤務ルールを守りつつ、スタッフ間の勤務時間の公平性をできるだけ保つ。

登場要素:

1. 対象期間:

1日目、2日目、3日目の3日間。

2. スタッフ:

スタッフID 氏名
S1 山田太郎
S2 佐藤花子
S3 田中一郎

3. 勤務時間帯:

  • 朝 (Morning)
  • 昼 (Day)
  • 夜 (Night) (簡単化のため、全日共通の3時間帯とします)

4. 仕事の種類:

  • 受付 (Reception)
  • 対応 (Support) (簡単化のため、2種類の仕事とします)

5. シフトの定義と必要人数: 「日・時間帯・仕事」の組み合わせを「シフト」とします。

日 時間帯 仕事 シフトID 必要人数
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. スタッフのスキルと割り当て可能性: 各スタッフが担当可能な仕事。

スタッフID 担当可能な仕事
S1 (山田) 受付, 対応
S2 (佐藤) 対応
S3 (田中) 受付

7. シフト割り当てに関する制約・要望: （元の問題から主要なものを抜粋・単純化）

  1. 必要人数の充足 (厳守): 各シフトには、表5で定められた「必要人数」のスタッフが必ず割り当てられること。
  2. 夜勤明けの朝勤回避 (厳守): 前日の「夜(Night)」の時間帯に勤務したスタッフは、翌日の「朝(Morning)」の時間帯の勤務はできない。
  3. 連続夜勤日数制限 (厳守): いかなるスタッフも、「夜(Night)」勤務が2日以上連続しないこと（最大1日まで）。 (元の4日から大幅に短縮)
  4. 作業量の公平性 (努力目標): 各スタッフの3日間における総勤務シフト数ができるだけ均等になるようにする。
    • 具体的には、全スタッフの総勤務シフト数のうち、最大値と最小値の差をできるだけ小さくしたい。

解決したい問題:

「ミニマート・サポート」の管理者は、3名のスタッフ（山田、佐藤、田中）を上記の条件を考慮しながら、3日間の全シフトに割り当てる必要があります。特に、1～3の条件は必ず守り、その上で4の作業量の公平性をできるだけ達成したいと考えています。

期待されるアウトプット: * 3日間の各シフトに、どのスタッフが割り当てられるかの具体的なシフト表。 * 各スタッフの総勤務シフト数、およびその最大と最小の差。

スタッフスケジューリングの最適化問題

提示された課題は、複数の制約を遵守しながら、スタッフの勤務公平性を最大化するようなシフト割り当てを決定する、典型的な数理最適化問題です。AMPLを用いて、この問題を混合整数計画問題としてモデル化し、解決します。

1. 問題の定義と定式化

この問題は、どのスタッフをどのシフト（日・時間帯・仕事の組み合わせ）に割り当てるかを決定する問題です。厳守すべき複数のルール（必要人数、スキル、勤務パターン）を満たした上で、全スタッフの総勤務時間（シフト数）のばらつきを最小化することを目的とします。

集合とインデックス

  • \(S\): スタッフの集合 (\(s \in S\))
  • \(D\): 日の集合 (\(d \in D\))
  • \(T\): 時間帯の集合 (\(t \in T\))
  • \(J\): 仕事の種類の集合 (\(j \in J\))
  • \(K \subseteq D \times T \times J\): 存在するシフトの集合 (\(k=(d,t,j) \in K\))
  • \(Skill_{sj} \subseteq S \times J\): スタッフ \(s\) が仕事 \(j\) を担当可能であることを示すペアの集合

パラメータ

  • \(Req_{k}\): シフト \(k\) に必要なスタッフの人数

決定変数

  • \(Assign_{sk} \in \{0, 1\}\): スタッフ \(s\) をシフト \(k\) に割り当てる場合に1、そうでない場合に0をとるバイナリ変数。
  • \(TotalShifts_s\): スタッフ \(s\) の総勤務シフト数（連続変数）。
  • \(MaxShifts, MinShifts\): 全スタッフの総勤務シフト数の最大値と最小値（連続変数）。

目的関数

スタッフ間の総勤務シフト数の差（最大値と最小値の差）を最小化することで、勤務の公平性を目指します。 \[\text{minimize} \quad \text{FairnessGap}: MaxShifts - MinShifts\]

制約条件

  1. スキル制約: スタッフは、担当可能な仕事のシフトにのみ割り当て可能です。これは、決定変数 \(Assign_{sk}\) を、スキル上可能な組み合わせ \((s,k)\) についてのみ定義することでモデルに組み込みます。
  2. 必要人数充足: 各シフトには、定められた必要人数のスタッフを割り当てなければなりません。 \[\sum_{s \in S} Assign_{sk} = Req_{k} \quad (\forall k \in K)\]
  3. 夜勤明け朝勤の回避: 前日の夜勤を担当したスタッフは、翌日の朝の勤務はできません。 \[\sum_{j \in J, k=(d,'Night',j) \in K} Assign_{sk} + \sum_{j' \in J, k'=(d+1,'Morning',j') \in K} Assign_{sk'} \le 1 \quad (\forall s \in S, \forall d \in D \text{ s.t. } d < |D|)\]
  4. 連続夜勤の制限: 夜勤は連続で最大1日までです（2日連続は不可）。 \[\sum_{j \in J, k=(d,'Night',j) \in K} Assign_{sk} + \sum_{j' \in J, k'=(d+1,'Night',j') \in K} Assign_{sk'} \le 1 \quad (\forall s \in S, \forall d \in D \text{ s.t. } d < |D|)\]
  5. 公平性のための定義: 目的関数で用いる変数を定義します。
    • \(TotalShifts_s = \sum_{k \in K} Assign_{sk} \quad (\forall s \in S)\)
    • \(MaxShifts \ge TotalShifts_s \quad (\forall s \in S)\)
    • \(MinShifts \le TotalShifts_s \quad (\forall s \in S)\)

15. 均等化を考慮したチーム割当問題

背景:

「未来技術研究所」は、社内の多様な部門からメンバーを集め、3日間の「イノベーション・ワークショップ」を開催します。参加者は新しいアイデアを創出し、プロトタイプを開発するために複数のチームに分かれて活動します。効果的なワークショップのためには、各チームの能力を最大限に引き出し、かつチーム間の経験やスキルセットのバランスを取ることが重要です。

目的:

ワークショップに参加する社員を複数のチームに割り当て、以下の目標を達成する。

  1. 各社員をいずれか1つのチームに割り当てる。
  2. 各社員を特定のチームに割り当てた際に得られる「貢献度（利得）」の全チーム合計を最大化する。
  3. 各チームの平均年齢と平均スキルポイントが、チーム間でできるだけ均等になるようにする。
  4. 各チームの平均年齢と平均スキルポイントが、定められた範囲内（下限と上限）に収まるようにする。
  5. 均等化の度合いは、チーム間の平均値の差の合計（重み付き）を最小化するか、あるいは年齢の均等化を優先し、次にスキルポイントの均等化を優先する（辞書的順序）形で評価する。

登場要素:

1. 参加者 (社員):

ワークショップに参加する社員は5名です。

社員ID 氏名 年齢 (\(a_i\)) スキルポイント (\(b_i\)) (1-10点)
E001 田中太郎 30 7
E002 佐藤花子 45 9
E003 鈴木一郎 25 6
E004 高橋次郎 38 8
E005 伊藤三郎 52 5

2. チーム:

編成するチームは2チームです。

  • チームA
  • チームB

3. チーム割り当て時の貢献度（利得） (\(p_{ij}\)): 各社員を各チームに割り当てた場合に期待される貢献度（アイデア発想力、専門性などを総合的に評価）。

社員ID チームAへの貢献度 チームBへの貢献度
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 (均等化 - 辞書的順序アプローチ):
    1. まず、チーム間の「平均年齢の差の絶対値」を最小化する。
    2. その上で（平均年齢差が最小となる割り当ての中で）、「平均スキルポイントの差の絶対値」を最小化する。

解決したい問題:

「未来技術研究所」のワークショップ運営担当者は、5名の社員を2つのチーム（チームA、チームB）に割り当てる必要があります。以下の条件と目標を考慮して、最適なチーム編成を決定してください。

  1. 全員割り当て: 各社員は、必ずチームAまたはチームBのいずれか1つのチームに割り当てられる。
  2. 貢献度の最大化: 全体の貢献度の合計が最も高くなるようにする。
  3. チーム属性の制約: 各チームの平均年齢と平均スキルポイントが、表4で定められた下限と上限の範囲にできるだけ収まるようにする（努力目標、あるいは厳密な制約）。
  4. チーム間の均等化: 上記「5. チーム間の均等化に関する目標」で述べた、重み和アプローチまたは辞書的順序アプローチのいずれかに基づいて、チーム間の平均年齢と平均スキルポイントのバランスを取る。

期待されるアウトプット:

  • 各社員がどのチームに割り当てられるかのリスト。

  • その割り当てによって達成される総貢献度。

  • 各チームの平均年齢と平均スキルポイント、およびチーム間のこれらの値の差。

  • （均等化目標を達成するための目的関数の値）

  • \(N\) 人の人を \(M\) 個のチームに割り振る。

  • 各人 \(i (i = 1, ..., N)\) はチーム \(j (i = 1, ..., M)\) へ割り振ったときの利得 \(p_{ij}\) が与えられていて、 その和を最大化したい。

  • 各人 \(i\) (i = 1, …, N) は年齢 \(a_i\) や能力 \(b_i\) というパラメータを持ち、目標は、各チームに割り振られた人の年齢や能力の平均値が、チーム間で可能な限り均等になるようにしたい。

  • チームごとに、年齢や能力値の下限と上限が与えられている。

  • 望ましい均等化はあいまいで、重み和を最小化するか、優先度（辞書的順序）に基づき計算したい。

定式化

1. 集合とパラメータ

  • I = {1, 2, ..., N}: 人の集合
  • J = {1, 2, ..., M}: チームの集合
  • a_i: 人 i の年齢 (既知のパラメータ, i ∈ I)

2. 決定変数

  • x_ij: 人 i がチーム j に割り振られる場合に 1、そうでない場合に 0 をとるバイナリ変数 (i ∈ I, j ∈ J)。
    • x_ij ∈ {0, 1}

3. 計算用の中間変数 (補助変数)

これらは厳密には決定変数ではありませんが、目的関数や制約条件を記述しやすくするために定義します。

  • NumPeople_j: チーム j に割り振られた人数
    • NumPeople_j = ∑_{i ∈ I} x_ij (j ∈ J)
  • TotalAge_j: チーム j に割り振られた人の年齢の合計
    • TotalAge_j = ∑_{i ∈ I} a_i * x_ij (j ∈ J)
  • AvgAge_j: チーム j の平均年齢
    • AvgAge_j = TotalAge_j / NumPeople_j (j ∈ J)
    • (注意: この形式は非線形であり、直接的な線形計画問題の定式化には工夫が必要です。後述の目的関数で対応します。)

4. 制約条件

  • 各人はちょうど1つのチームに所属する:
    • ∑_{j ∈ J} x_ij = 1 (すべての i ∈ I について)
  • (任意) 各チームの最小/最大人数 (必要に応じて追加):
    • L_j ≤ NumPeople_j ≤ U_j (すべての j ∈ J について)
    • ここで L_j はチーム j の最小人数、U_j は最大人数。もしチームが空になることを許容しないなら L_j ≥ 1 とします。
  • 変数の型:
    • x_ij ∈ {0, 1} (すべての i ∈ I, j ∈ J について)

5. 目的関数

チーム間の平均年齢のばらつきを最小化する方法はいくつか考えられます。

方法1: 平均年齢の最大値と最小値の差を最小化 (Min-Max)

  1. 全体の平均年齢 A_overall を計算します: A_overall = (∑_{i ∈ I} a_i) / N
  2. 各チームの平均年齢 AvgAge_j と全体の平均年齢 A_overall との乖離（ずれ）を考えます。
  3. 最大の乖離を最小化することを目指します。補助変数 D_max (最大乖離) を導入します。
  • 補助変数:
    • D_max ≥ 0: 各チームの平均年齢と全体平均年齢との間の最大の絶対差を表す連続変数。
  • 目的関数:
    • Minimize D_max
  • 追加の制約条件 (線形化): AvgAge_j の定義 TotalAge_j / NumPeople_j は非線形です。これを線形化するために、平均年齢そのものではなく、「チームの合計年齢」と「(全体平均年齢) × (チーム人数)」との差を考えます。この差が 0 に近いほど、そのチームの平均年齢は全体平均年齢に近くなります。
    • ∑_{i ∈ I} (a_i - A_overall) * x_ij ≤ D_max (すべての j ∈ J について)
    • ∑_{i ∈ I} (a_i - A_overall) * x_ij ≥ -D_max (すべての j ∈ J について)
    これらの制約は、 | ∑_{i ∈ I} a_i * x_ij - A_overall * ∑_{i ∈ I} x_ij | ≤ D_max を線形に表現したものです。つまり、| TotalAge_j - A_overall * NumPeople_j | ≤ D_max を意味します。 チーム人数 NumPeople_j が 0 でない限り、これを NumPeople_j で割ると | AvgAge_j - A_overall | ≤ D_max / NumPeople_j となり、間接的に平均年齢の乖離を抑えることになります。 (※もしチームサイズが大きく異なる場合、この目的関数は完全に平均年齢の差を最小化するわけではない可能性がありますが、実用上よく使われる線形化アプローチです。)

方法2: 平均年齢の分散 (または標準偏差) を最小化 (非線形)

  1. 各チームの平均年齢 AvgAge_j を計算します (上記定義)。

  2. 全チームの平均年齢の平均値 μ = (∑_{j ∈ J} AvgAge_j) / M を計算します。

  3. 目的関数: Minimize ∑_{j ∈ J} (AvgAge_j - μ)^2 (分散) または Minimize sqrt(∑_{j ∈ J} (AvgAge_j - μ)^2 / M) (標準偏差)

    • 注意: この目的関数は AvgAge_j の定義により非線形 (分数や二乗を含む) となり、混合整数非線形計画問題 (MINLP) となります。解くためには専用のソルバーが必要です。

方法3: 合計年齢の分散を最小化 (チームサイズが均等な場合の近似)

もし、各チームの人数 NumPeople_j がほぼ等しくなるように制約されているか、期待される場合、平均年齢の均等化は合計年齢 TotalAge_j の均等化で近似できます。

  1. 目標とするチームあたりの合計年齢 TargetTotalAge = (∑_{i ∈ I} a_i) / M を計算します。
  2. 目的関数: Minimize ∑_{j ∈ J} (TotalAge_j - TargetTotalAge)^2
    • Minimize ∑_{j ∈ J} (∑_{i ∈ I} a_i * x_ij - TargetTotalAge)^2
    • 注意: この目的関数は決定変数 x_ij の二乗を含むため、混合整数二次計画問題 (MIQP) となります。MIQPソルバーで解くことができます。

推奨される定式化 (MILP)

実用上、線形計画問題として扱える 方法1 の定式化がよく用いられます。

まとめ (方法1に基づくMILP定式化):

  • Sets: I, J
  • Parameters: a_i, N, M, A_overall = (∑ a_i) / N
  • Variables: x_ij ∈ {0, 1}, D_max ≥ 0
  • Objective: Minimize D_max
  • Constraints:
    1. ∑_{j ∈ J} x_ij = 1 (for all i ∈ I)
    2. ∑_{i ∈ I} (a_i - A_overall) * x_ij ≤ D_max (for all j ∈ J)
    3. ∑_{i ∈ I} (a_i - A_overall) * x_ij ≥ -D_max (for all j ∈ J)
    4. (Optional) L_j ≤ ∑_{i ∈ I} x_ij ≤ U_j (for all j ∈ J)

この定式化により、混合整数線形計画 (MILP) ソルバーを用いて、チーム間の平均年齢のばらつき（具体的には、各チームの合計年齢と期待される合計年齢との間の最大絶対差）を最小にするような人の割り当てを見つけることができます。

16. 献立問題

背景: 「ぷちデリ弁当」は、小規模ながら健康志向の宅配弁当サービスです。コストを抑えつつ、栄養バランスと日々の献立の目新しさを提供することを目指しています。今回は、月曜日から水曜日までの3日間の日替わり弁当（主菜1品、副菜1品）の献立を計画します。

目的: 3日間の各日において、主菜と副菜を1品ずつ選び、以下の目標を達成する献立を作成する。 1. 毎日の弁当が、定められた栄養素（カロリー、塩分）の摂取基準（下限と上限）を満たす。 2. 3日間の弁当の総費用をできるだけ安く抑える。 3. 献立のバラエティを豊かにするため、同じ日の主菜と副菜で、また連続する2日間の献立で、同じ「素材」や「調理法」ができるだけ重ならないようにする（ペナルティとして評価）。

登場要素:

1. 対象期間: 月曜日、火曜日、水曜日の3日間。

2. 食品候補: 弁当に使用できる食品の候補リスト。

  • 食品リストと基本情報:

    食品ID 食品名 主菜/副菜 費用(円) 主な素材 主な調理法
    M01 鶏の照り焼き 主菜 200 肉 焼き物
    M02 鮭の塩焼き 主菜 220 魚 焼き物
    M03 豚の角煮 主菜 250 肉 煮物
    S01 ほうれん草の胡麻和え 副菜 80 野菜 和え物
    S02 きんぴらごぼう 副菜 70 野菜 炒め物
    S03 だし巻き卵 副菜 90 卵 焼き物

  • 食品ごとの栄養素含有量（1食あたり）:

    食品ID カロリー(kcal) 塩分(g)
    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日間の「総費用（材料費）＋ 重複ペナルティの合計」を最小にする献立プランを見つけてください。

  1. 主菜・副菜の選択: 各日、表2の食品リストから、指定された主菜/副菜の区分に従い、主菜候補から1品、副菜候補から1品を選択する。
  2. 栄養基準の遵守: 毎日、選択された主菜と副菜の栄養素（カロリー、塩分）の合計が、表3の「栄養素の摂取基準」の下限と上限の範囲内に収まるようにする。
  3. 素材・調理法の重複回避の考慮: 表5で定義されたペナルティに基づき、素材や調理法の重複を評価する。
  4. 総コストの最小化: 3日間の食品費用と、発生した重複ペナルティの合計額が最も少なくなるようにする。

期待されるアウトプット: 月曜日、火曜日、水曜日の各日について、どの食品を主菜とし、どの食品を副菜とするかの具体的な献立リスト。そして、その献立によって達成される総費用（食品費用＋ペナルティ）、および各日の栄養摂取量。

問題の定義と定式化

この問題は、月曜日から水曜日までの3日間の弁当（主菜1品、副菜1品）の献立を、コストと各種ペナルティの合計を最小化するように決定する混合整数計画問題です。

集合とインデックス

  • \(T\): 曜日の集合 (月, 火, 水)。\(t \in T\)
  • \(T_{prev}\): 連続日を評価するための曜日の集合 (月, 火)。\(t \in T_{prev}\)
  • \(F\): 食品候補の集合。\(f \in F\)
  • \(F_M\): 主菜の集合。\(F_M \subset F\)
  • \(F_S\): 副菜の集合。\(F_S \subset F\)
  • \(N\): 栄養素の集合（カロリー, 塩分）。\(n \in N\)
  • \(M\): 素材の集合（肉, 魚, 野菜, 卵）。\(m \in M\)
  • \(C\): 調理法の集合（焼き物, 煮物, 和え物, 炒め物）。\(c \in C\)

パラメータ

  • \(cost_f\): 食品 \(f\) の費用
  • \(nutval_{n,f}\): 食品 \(f\) の栄養素 \(n\) の含有量
  • \(nut\_min_n, nut\_max_n\): 栄養素 \(n\) の1日の摂取基準（下限・上限）
  • \(mat_{m,f}\): 食品 \(f\) が素材 \(m\) を使うなら1、そうでなければ0
  • \(cook_{c,f}\): 食品 \(f\) が調理法 \(c\) を使うなら1、そうでなければ0
  • \(P_{ms}\): 同じ日の主菜・副菜の素材重複ペナルティ (30円)
  • \(P_{mc}\): 同じ日の主菜・副菜の調理法重複ペナルティ (20円)
  • \(P_{ds}\): 連続する日の素材重複ペナルティ (40円)
  • \(P_{dc}\): 連続する日の調理法重複ペナルティ (25円)

決定変数

  • \(x_{t,f} \in \{0, 1\}\): 曜日 \(t\) に食品 \(f\) を選択するなら1、しないなら0
  • \(y_{ms, t} \in \{0, 1\}\): 曜日 \(t\) の主菜と副菜で素材が重複した場合に1
  • \(y_{mc, t} \in \{0, 1\}\): 曜日 \(t\) の主菜と副菜で調理法が重複した場合に1
  • \(y_{ds, t} \in \{0, 1\}\): 曜日 \(t\) と \(t+1\) で素材が重複した場合に1
  • \(y_{dc, t} \in \{0, 1\}\): 曜日 \(t\) と \(t+1\) で調理法が重複した場合に1
  • \(u_{m, t} \in \{0, 1\}\): 曜日 \(t\) に素材 \(m\) が使用された場合に1
  • \(v_{c, t} \in \{0, 1\}\): 曜日 \(t\) に調理法 \(c\) が使用された場合に1

定式化

目的関数

総コスト（食品費用＋ペナルティ合計）を最小化します。 \[\text{Minimize} \quad \sum_{t \in T} \sum_{f \in F} cost_f \cdot x_{t,f} + \sum_{t \in T} (P_{ms} \cdot y_{ms, t} + P_{mc} \cdot y_{mc, t}) + \sum_{t \in T_{prev}} (P_{ds} \cdot y_{ds, t} + P_{dc} \cdot y_{dc, t})\]

制約条件

  1. 主菜・副菜の選択: 各日、主菜と副菜を1品ずつ選択する。 \[\forall t \in T: \quad \sum_{f \in F_M} x_{t,f} = 1\] \[\forall t \in T: \quad \sum_{f \in F_S} x_{t,f} = 1\]

  2. 栄養基準: 各日、栄養素の合計が基準範囲内にある。 \[\forall t \in T, \forall n \in N: \quad nut\_min_n \le \sum_{f \in F} nutval_{n,f} \cdot x_{t,f} \le nut\_max_n\]

  3. 補助変数の定義: その日に特定の素材・調理法が使われたかを判定する。 \[\forall t \in T, \forall m \in M: \quad \sum_{f \in F} mat_{m,f} \cdot x_{t,f} \le 2 \cdot u_{m, t}\] \[\forall t \in T, \forall m \in M: \quad \sum_{f \in F} mat_{m,f} \cdot x_{t,f} \ge u_{m, t}\] \[\forall t \in T, \forall c \in C: \quad \sum_{f \in F} cook_{c,f} \cdot x_{t,f} \le 2 \cdot v_{c, t}\] \[\forall t \in T, \forall c \in C: \quad \sum_{f \in F} cook_{c,f} \cdot x_{t,f} \ge v_{c, t}\]

  4. ペナルティ変数の関連付け:

    • 同じ日の重複: \[\forall t \in T, \forall m \in M: \quad \sum_{f \in F_M} mat_{m,f} \cdot x_{t,f} + \sum_{f \in F_S} mat_{m,f} \cdot x_{t,f} \le 1 + y_{ms, t}\] \[\forall t \in T, \forall c \in C: \quad \sum_{f \in F_M} cook_{c,f} \cdot x_{t,f} + \sum_{f \in F_S} cook_{c,f} \cdot x_{t,f} \le 1 + y_{mc, t}\]
    • 連続する日の重複: \[\forall t \in T_{prev}, \forall m \in M: \quad u_{m, t} + u_{m, t+1} \le 1 + y_{ds, t}\] \[\forall t \in T_{prev}, \forall c \in C: \quad v_{c, t} + v_{c, t+1} \le 1 + y_{dc, t}\]

17. エア・フロンティア航空の月間乗務員スケジュール作成

背景: エア・フロンティア航空は、ヨーロッパを拠点とする中規模航空会社です。同社は、乗務員の満足度と効率的な運航を両立させるため、乗務員の個々の事情や実行可能な勤務パターンを考慮した上で、月間の乗務スケジュール（個別月間ブロック）を作成する「乗務員勤務表問題 (Crew Rostering Problem)」に取り組んでいます。事前に、運航計画に基づいて効率的な「ペアリング」（ある出発地点（home base）から出発し， 再び同じ出発地点に戻る乗務員のスケジュール）が複数作成されており、これらのペアリングを各乗務員に適切に割り当てる必要があります。

目的: 全てのペアリングが必要な人数でカバーされ、各乗務員は実行可能な月間スケジュールを1つだけ担当し、会社全体としてスケジューリングのコスト（乗務員の特性や希望を反映）を最も低くすること。

登場要素:

1. 乗務員 今回の対象となるパイロットは3名です。

  • パイロットA
  • パイロットB
  • パイロットC

2. ペアリング と 必要人数 1ヶ月間に実施すべきペアリングと、各ペアリングに必要な乗務員の数は以下の通りです。

ペアリングID 必要な乗務員数
P1 2人
P2 1人
P3 1人
P4 2人

3. 乗務員ごとの実行可能な月間スケジュール候補 各パイロットには、実行可能な月間スケジュールの候補がいくつかあります。各スケジュールは、1つ以上のペアリングを含んでいます。

  • パイロットA のスケジュール候補:

    スケジュールID (パイロットA) 含まれるペアリング
    S_A1 P1, P3
    S_A2 P2, P4

  • パイロットB のスケジュール候補:

    スケジュールID (パイロットB) 含まれるペアリング
    S_B1 P1, P4
    S_B2 P2

  • パイロットC のスケジュール候補:

    スケジュールID (パイロットC) 含まれるペアリング
    S_C1 P1, P2, P3
    S_C2 P4

4. 各スケジュールの費用

各パイロットが特定の月間スケジュールを担当する場合の「費用」です。この費用が低いほど、会社や乗務員にとって望ましいとされます。

パイロット スケジュールID 費用
パイロット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つの条件を必ず満たした上で、全体の費用が最も少なくなるように、各パイロットにどの月間スケジュールを割り当てるか（または割り当てないか）を決めたいと考えています。

  1. ペアリングのカバー: 表に記載された全てのペアリング（P1からP4まで）は、それぞれ定められた「必要な乗務員数」が確保されるように、誰かしらのパイロットに担当されなければなりません。

    • 例えば、ペアリングP1は2人の乗務員が必要です。もしパイロットAがS_A1（P1を含む）を担当し、パイロットBがS_B1（P1を含む）を担当した場合、P1は2人の乗務員によってカバーされたことになります。

  2. 乗務員へのスケジュール割り当て: 各パイロット（パイロットA、B、C）は、表3で示された自身の実行可能なスケジュール候補の中から、最大で1つだけしか割り当てられません。

期待されるアウトプット: どのパイロットにどの月間スケジュールを割り当てるのが最適か、そしてその時の最も低い総費用。

集合:

  • \(P\): 実行可能なペアリングの集合．ここで ペアリング（paring, rotation）とは，ある出発地点（home base）から出発し， 再び同じ出発地点に戻る乗務員のスケジュールを表し，1つ以上のフライトとその間の休息期間から構成される．おおむね1週間以下の乗務員のスケジュールを表す．
  • \(L\): 乗務員（パイロットもしくはキャビンクルー）の集合
  • \(S_{\ell}\): 乗務員 \(\ell \in L\) に対する実行可能な個別スケジュールの集合

パラメータ：

  • \(C_s^{\ell}\): 乗務員 \(\ell \in L\) がスケジュール \(s\) を遂行したときの費用．選好する便や休暇を考慮して決定する。

  • \(n_p\): ペアリング \(p\) に必要な乗務員の数

  • \(e_{p}^{s, \ell}\): ペアリング \(p\) が乗務員 \(\ell\) のスケジュール \(s\) に含まれるとき \(1\)，それ以外のとき \(0\) の定数

  • 変数:

  • \(x_s^{\ell}\): 乗務員 \(\ell \in L\) がスケジュール \(s \in S_{\ell}\) を遂行するとき \(1\)，それ以外のとき \(0\)

18. ケーススタディ：首都圏フーズ物流の挑戦「最適化が導く共同配送計画」

登場人物と背景

佐藤さんは、中堅食品卸「首都圏フーズ物流」の物流企画マネージャー。彼の部署は、千葉と神奈川にある基幹倉庫から、需要が集中する渋谷と新宿のエリア配送センター（卸）へ、日々商品を補充する重要な役割を担っています。

近年、燃料費の高騰、ドライバー不足、そして「物流の2024年問題」の余波が、物流コストを圧迫していました。経営陣からは「コストを5%削減しつつ、都心店舗への欠品は絶対に回避せよ」という厳しい指示が出ています。

直面している課題

これまでの首都圏フーズ物流のやり方は、渋谷と新宿の各センターから個別に発注依頼が来たら、その都度、近い方の倉庫からトラックを手配するという、いわば「場当たり的」なものでした。この方法にはいくつかの問題がありました。

  1. 非効率なトラック稼働: 同じ日の午前中に千葉倉庫から渋谷へトラックが出たのに、午後にはまた千葉倉庫から少量の追加荷物を積んで渋谷へ向かう、といった無駄が発生していました。
  2. 低い積載率: 緊急の補充依頼に応えるため、トラックの荷台が半分も埋まらないまま輸送することがあり、輸送の固定費が収益を圧迫していました。
  3. トラック台数の制約: 提携している運送会社との契約上、1日に全社で利用できるトラックの合計台数には上限があり、繁忙期には手配できないリスクがありました。

佐藤さんは、個別の発注に個別に対応するやり方では限界があると感じていました。「渋谷と新宿、千葉と神奈川、製品在庫と輸送タイミング。これら全てを統合的に考え、最も効率的な計画を立てる必要がある」と考えた彼は、数理最適化モデリング言語AMPLを用いて、この複雑な問題を解決することにしました。

AMPLによる問題のモデル化

佐藤さんは、AMPLのエキスパートに相談し、自社の課題を数理モデルに落とし込んでいきました。

  • 目的: 複数日（まずは2日間の問題）にわたる「トラックの固定輸送費」と「配送センターでの在庫維持費」の合計を最小化すること。

  • 決定すべきこと（決定変数）:

    • いつ、どの倉庫から、どの配送センターへ、どの製品を、どれだけ輸送するか？ (Transport)
    • その際に、各ルートでトラックを何台使うか？ (NumTrucks)
    • その結果、毎日の終わりに各センターの製品在庫はどれだけになるか？ (Inventory)

  • 守るべきルール（制約条件）:

    1. 需要の充足: 渋谷と新宿の各センターでは、日々の需要を絶対に満たさなければなりません（欠品は許されない）。これは、今日の在庫は「昨日の在庫＋今日の入荷量－今日の需要量」で決まるという在庫バランス制約で表現されます。
    2. トラックの能力: 1台のトラックに積める量には上限があります。同時に、積載率が極端に悪い輸送をなくすため、「トラックを1台使うなら、最低でも積載可能量の20%は積む」というトラック容量の上下限制約を設けました。
    3. 保管スペースの限界: 渋谷と新宿のセンターは都心にあるため、保管スペースに限りがあります。全製品の合計在庫が、この上限を超えてはいけません（卸在庫容量制約）。
    4. 車両の確保: 運送会社との契約により、1日に千葉・神奈川の倉庫から出発できるトラックの合計台数には限りがあります（一日あたり総トラック台数制約）。

最適化の実行と得られた洞察

佐藤さんは、これらの条件をすべて盛り込んだ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週間モデルを実行することで、佐藤さんはさらに高度な計画を立てられるようになります。例えば、トラックの台数が制限される週末に向けて、木曜日や金曜日に少し多めに輸送して在庫を積み増しておく、といった先行補充の判断が可能になります。また、週明けの月曜日の高い需要に応えるため、輸送コストが安いルートを使って日曜日のうちに補充を済ませておくなど、より戦略的でコスト効率の高い物流網の構築が実現できるのです。