Keyword: 航空, 路線最適化, 収益最大化, 混合整数計画法, MILP
航空分野の最適化問題:航空路線の最適化
問題の概要
航空会社にとって、路線網の最適化は収益性と効率性を高める上で極めて重要です。この問題では、限られた機材と運航制約の中で、最大の利益を得るための最適な路線選択を行うことを目的としています。
航空路線の最適化問題は、各路線の需要予測、運航コスト、空港の発着枠制限などの要因を考慮しながら、最も収益性の高い路線の組み合わせを見出すものです。この最適化により、航空会社は限られたリソースを最大限に活用し、収益を最大化することができます。
主な制約条件としては、使用可能な航空機の数、各空港の発着枠制限、最小運航頻度などが挙げられます。目標は、これらの制約を満たしながら、総利益を最大化することです。
航空路線最適化問題(具体例)
ある地方航空会社が6つの都市(A, B, C, D, E, F)間を結ぶ路線網を最適化したいと考えています。会社は2種類の航空機(小型機と中型機)を所有しており、各路線の需要予測と運航コストのデータを持っています。
以下の表は、各路線の週当たりの需要予測、座席あたりの収入、および航空機タイプごとの運航コストを示しています。
路線 | 需要(人/週) | 座席収入(万円/席) | 小型機コスト(万円/便) | 中型機コスト(万円/便) |
---|---|---|---|---|
A-B | 800 | 2.5 | 100 | 180 |
A-C | 400 | 2.2 | 80 | 140 |
A-D | 250 | 2.0 | 90 | 160 |
A-E | 450 | 2.3 | 95 | 170 |
A-F | 300 | 2.4 | 105 | 190 |
B-C | 350 | 1.8 | 70 | 120 |
B-E | 900 | 2.6 | 110 | 200 |
C-D | 200 | 1.7 | 60 | 100 |
C-F | 300 | 2.4 | 100 | 180 |
D-E | 250 | 2.1 | 80 | 140 |
E-F | 400 | 2.3 | 95 | 170 |
会社は小型機(座席数80人)を6機、中型機(座席数120人)を4機所有しています。各空港には週当たりの発着枠制限があり、それぞれA:22回、B:18回、C:20回、D:15回、E:16回、F:14回となっています。また、各路線は週に少なくとも1便は運航する必要があります。
さらに、以下の追加条件があります:
- 効率的な運用のため、総運航回数を週20回以上35回以下に保つ必要があります。
- 環境配慮と乗務員の効率的な運用のため、小型機の運航回数が総運航回数の20%以上50%以下になるようにする必要があります。
- 各路線の提供座席数は、需要の20%以上100%以下を満たす必要があります。
この問題を解くことで、航空会社は最大の利益を得られる路線と機材の組み合わせを知ることができ、効率的な運航計画を立てることができます。
問題の定式化
パラメータ
パラメータ | 説明 | 値 |
---|---|---|
路線の集合 | {A-B, A-C, A-D, A-E, A-F, B-C, B-E, C-D, C-F, D-E, E-F} | |
空港の集合 | {A, B, C, D, E, F} | |
航空機タイプの集合 | {小型機, 中型機} | |
路線 |
表参照 | |
路線 |
表参照 | |
路線 |
表参照 | |
航空機タイプ |
小型機: 80, 中型機: 120 | |
航空機タイプ |
小型機: 6, 中型機: 4 | |
空港 |
A:22, B:18, C:20, D:15, E:16, F:14 |
決定変数
変数 | 説明 | 範囲 |
---|---|---|
路線 |
非負整数 |
目的関数
目的 | 式 |
---|---|
総利益の最大化 |
この目的関数は、各路線と航空機タイプの組み合わせによる収入から運航コストを差し引いた純利益の合計を最大化します。
制約条件
制約 | 式 | 説明 |
---|---|---|
需要制約 | 各路線の提供座席数は需要の20%以上100%以下 | |
機材制約 | 各タイプの航空機の週間総運航回数は保有数の7倍以下 | |
発着枠制約 | 各空港の週間発着回数は制限以下 | |
最小運航頻度制約 | 各路線は週に少なくとも1便運航 | |
総運航回数制約 | 週間総運航回数は20回以上35回以下 | |
小型機比率制約 | 小型機の運航回数が総運航回数の20%以上50%以下 | |
非負制約 | 運航回数は非負 | |
整数制約 | 運航回数は整数 |
ここで、
コード例
以下に、この混合整数線形計画問題を nAG Library for Python の MILP 問題専用ソルバー関数 mip_solve を用いて解くコード例を示します。
import numpy as np
from naginterfaces.library import opt
from naginterfaces.library import mip
# パラメータ
= ['A-B', 'A-C', 'A-D', 'A-E', 'A-F', 'B-C', 'B-E', 'C-D', 'C-F', 'D-E', 'E-F']
ROUTES = ['A', 'B', 'C', 'D', 'E', 'F']
AIRPORTS = ['小型機', '中型機']
AIRCRAFT_TYPES
= {
DEMAND 'A-B': 800, 'A-C': 400, 'A-D': 250, 'A-E': 450, 'A-F': 300,
'B-C': 350, 'B-E': 900, 'C-D': 200, 'C-F': 300, 'D-E': 250, 'E-F': 400
}= {
REVENUE 'A-B': 2.5, 'A-C': 2.2, 'A-D': 2.0, 'A-E': 2.3, 'A-F': 2.4,
'B-C': 1.8, 'B-E': 2.6, 'C-D': 1.7, 'C-F': 2.4, 'D-E': 2.1, 'E-F': 2.3
}= {
COST 'A-B', '小型機'): 100, ('A-B', '中型機'): 180,
('A-C', '小型機'): 80, ('A-C', '中型機'): 140,
('A-D', '小型機'): 90, ('A-D', '中型機'): 160,
('A-E', '小型機'): 95, ('A-E', '中型機'): 170,
('A-F', '小型機'): 105, ('A-F', '中型機'): 190,
('B-C', '小型機'): 70, ('B-C', '中型機'): 120,
('B-E', '小型機'): 110, ('B-E', '中型機'): 200,
('C-D', '小型機'): 60, ('C-D', '中型機'): 100,
('C-F', '小型機'): 100, ('C-F', '中型機'): 180,
('D-E', '小型機'): 80, ('D-E', '中型機'): 140,
('E-F', '小型機'): 95, ('E-F', '中型機'): 170
(
}
= {'小型機': 80, '中型機': 120}
SEATS = {'小型機': 6, '中型機': 4}
AIRCRAFT_COUNT = {'A': 22, 'B': 18, 'C': 20, 'D': 15, 'E': 16, 'F': 14}
SLOTS
# 制約条件のパラメータ
= 20
MIN_TOTAL_FLIGHTS = 35
MAX_TOTAL_FLIGHTS = 0.2
MIN_SMALL_AIRCRAFT_RATIO = 0.5
MAX_SMALL_AIRCRAFT_RATIO = 0.2
MIN_DEMAND_FULFILLMENT = 1.0
MAX_DEMAND_FULFILLMENT
# 決定変数の数
= len(ROUTES) * len(AIRCRAFT_TYPES)
n_vars
# 問題のハンドルを初期化
= opt.handle_init(n_vars)
handle
# 目的関数の設定
= [REVENUE[r] * SEATS[t] - COST[(r, t)] for r in ROUTES for t in AIRCRAFT_TYPES]
obj_coeffs
opt.handle_set_linobj(handle, obj_coeffs)
# 変数の上下限を設定
= [0] * n_vars
lower_bounds = [np.inf] * n_vars
upper_bounds
opt.handle_set_simplebounds(handle, lower_bounds, upper_bounds)
# 制約条件の設定
= []
a = []
irowb = []
icolb = []
bl = []
bu
= 1
constraint_index
# 機材制約
for i, t in enumerate(AIRCRAFT_TYPES):
= [1 if j % len(AIRCRAFT_TYPES) == i else 0 for j in range(n_vars)]
row
a.extend(row)* n_vars)
irowb.extend([constraint_index] range(1, n_vars + 1))
icolb.extend(0)
bl.append(7 * AIRCRAFT_COUNT[t])
bu.append(+= 1
constraint_index
# 需要制約 (需要の20%以上を満たし、需要を超えない)
for i, r in enumerate(ROUTES):
= [0] * n_vars
row *len(AIRCRAFT_TYPES)] = SEATS['小型機']
row[i*len(AIRCRAFT_TYPES)+1] = SEATS['中型機']
row[i
a.extend(row)* n_vars)
irowb.extend([constraint_index] range(1, n_vars + 1))
icolb.extend(* MIN_DEMAND_FULFILLMENT)
bl.append(DEMAND[r] * MAX_DEMAND_FULFILLMENT)
bu.append(DEMAND[r] += 1
constraint_index
# 最小運航頻度制約 (各路線で週に最低1便)
for i, r in enumerate(ROUTES):
= [1 if i*len(AIRCRAFT_TYPES) <= j < (i+1)*len(AIRCRAFT_TYPES) else 0 for j in range(n_vars)]
row
a.extend(row)* n_vars)
irowb.extend([constraint_index] range(1, n_vars + 1))
icolb.extend(1)
bl.append(
bu.append(np.inf)+= 1
constraint_index
# 発着枠制約
for i, p in enumerate(AIRPORTS):
= [1 if p in r.split('-') else 0 for r in ROUTES for _ in AIRCRAFT_TYPES]
row
a.extend(row)* n_vars)
irowb.extend([constraint_index] range(1, n_vars + 1))
icolb.extend(0)
bl.append(
bu.append(SLOTS[p])+= 1
constraint_index
# 総運航回数制約 (20-35便)
= [1] * n_vars
row_total
a.extend(row_total)* n_vars)
irowb.extend([constraint_index] range(1, n_vars + 1))
icolb.extend(
bl.append(MIN_TOTAL_FLIGHTS)
bu.append(MAX_TOTAL_FLIGHTS)+= 1
constraint_index
# 機材比率制約
# 小型機の運航回数が総運航回数の20%以上50%以下
= [-MIN_SMALL_AIRCRAFT_RATIO if i % 2 == 0 else MIN_SMALL_AIRCRAFT_RATIO for i in range(n_vars)]
row_small_min
a.extend(row_small_min)* n_vars)
irowb.extend([constraint_index] range(1, n_vars + 1))
icolb.extend(0)
bl.append(
bu.append(np.inf)+= 1
constraint_index
= [-MAX_SMALL_AIRCRAFT_RATIO if i % 2 == 0 else MAX_SMALL_AIRCRAFT_RATIO for i in range(n_vars)]
row_small_max
a.extend(row_small_max)* n_vars)
irowb.extend([constraint_index] range(1, n_vars + 1))
icolb.extend(-np.inf)
bl.append(0)
bu.append(+= 1
constraint_index
# 全ての制約条件を一度に設定
=bl, bu=bu, irowb=irowb, icolb=icolb, b=a)
opt.handle_set_linconstr(handle, bl
# 変数を整数に設定
'INTEGER', list(range(1, n_vars + 1)))
opt.handle_set_property(handle,
# ソルバーのオプションを設定
'Print Level = 1')
opt.handle_opt_set(handle, 'Task = Maximize')
opt.handle_opt_set(handle,
# 問題を解く
= mip.handle_solve_milp(handle)
result
# 結果の表示
= result[0]
x print("\n最適解:")
= 0
total_flights = 0
small_flights = 0
medium_flights = 0
total_profit
print("路線 | 小型機 | 中型機 | 総座席数 | 需要 | 充足率 | 利益(万円)")
print("----|--------|--------|----------|------|--------|------------")
for i, r in enumerate(ROUTES):
= round(x[i*len(AIRCRAFT_TYPES)])
small = round(x[i*len(AIRCRAFT_TYPES)+1])
medium = small * SEATS['小型機'] + medium * SEATS['中型機']
seats_provided = (REVENUE[r] * seats_provided - COST[(r, '小型機')] * small - COST[(r, '中型機')] * medium)
profit = seats_provided / DEMAND[r] * 100
fulfillment_rate
print(f"{r:4} | {small:6d} | {medium:6d} | {seats_provided:8d} | {DEMAND[r]:4d} | {fulfillment_rate:6.2f}% | {profit:10.2f}")
+= small + medium
total_flights += small
small_flights += medium
medium_flights += profit
total_profit
print("\n制約条件の確認:")
print(f"1. 総運航回数: {total_flights} 便 (制限: {MIN_TOTAL_FLIGHTS}-{MAX_TOTAL_FLIGHTS}) - {'満たす' if MIN_TOTAL_FLIGHTS <= total_flights <= MAX_TOTAL_FLIGHTS else '満たさない'}")
print(f"2. 小型機の比率: {small_flights/total_flights:.2%} (制限: {MIN_SMALL_AIRCRAFT_RATIO:.0%}-{MAX_SMALL_AIRCRAFT_RATIO:.0%}) - {'満たす' if MIN_SMALL_AIRCRAFT_RATIO <= small_flights/total_flights <= MAX_SMALL_AIRCRAFT_RATIO else '満たさない'}")
print("\n3. 発着枠制約:")
for p in AIRPORTS:
= sum(round(x[i*len(AIRCRAFT_TYPES)+j])
airport_flights for i, r in enumerate(ROUTES)
for j in range(len(AIRCRAFT_TYPES))
if p in r.split('-'))
print(f" {p}: 発着回数 {airport_flights}, 制限 {SLOTS[p]} - {'満たす' if airport_flights <= SLOTS[p] else '満たさない'}")
print("\n4. 需要充足率:")
for i, r in enumerate(ROUTES):
= round(x[i*len(AIRCRAFT_TYPES)])
small = round(x[i*len(AIRCRAFT_TYPES)+1])
medium = small * SEATS['小型機'] + medium * SEATS['中型機']
seats_provided = seats_provided / DEMAND[r] * 100
fulfillment_rate print(f" {r}: {fulfillment_rate:.2f}% (制限: {MIN_DEMAND_FULFILLMENT*100:.0f}%-{MAX_DEMAND_FULFILLMENT*100:.0f}%) - {'満たす' if MIN_DEMAND_FULFILLMENT*100 <= fulfillment_rate <= MAX_DEMAND_FULFILLMENT*100 else '満たさない'}")
print(f"\n5. 最小運航頻度: {'全路線で満たす' if all(sum(round(x[i*len(AIRCRAFT_TYPES)+j]) for j in range(len(AIRCRAFT_TYPES))) >= 1 for i in range(len(ROUTES))) else '満たさない路線あり'}")
print(f"\n総利益: {total_profit:.2f} 万円")
# ハンドルの削除
opt.handle_free(handle)
コードの詳細説明
このコードは、nAG Library for Pythonの混合整数計画ソルバー
handle_solve_milp
を用いて航空路線最適化問題を解いています。以下では、主要なnAG関数の使用方法と問題の定式化について説明します。
目的関数の設定
目的関数は総利益の最大化を表す線形式です:
maximize
ここで、R: 路線の集合、T: 航空機タイプの集合、
obj_coeffs = [REVENUE[r] * SEATS[t] - COST[(r, t)] for r in ROUTES for t in AIRCRAFT_TYPES]
opt.handle_set_linobj(handle, obj_coeffs)
目的関数が線形であるため、opt.handle_set_linobj
関数を使用して設定します。この関数は目的関数の係数のみを引数として受け取ります。線形式の構造が既知であるため、係数を指定するだけで目的関数を完全に表現できます。
変数の上下限の設定
lower_bounds = [0] * n_vars
upper_bounds = [np.inf] * n_vars
opt.handle_set_simplebounds(handle, lower_bounds, upper_bounds)
opt.handle_set_simplebounds
関数で変数の上下限を設定します。全ての変数に対して下限を0(非負制約)、上限を無限大に設定しています。
制約条件の設定
制約条件は opt.handle_set_linconstr
関数で設定します:
opt.handle_set_linconstr(handle, bl=bl, bu=bu, irowb=irowb, icolb=icolb, b=a)
bl
,bu
: 各制約式の下限と上限値irowb
: 各係数が属する制約式のインデックス(1から始まる)icolb
: 各係数が対応する変数のインデックス(1から始まる)b
: 制約式の係数
例えば、機材制約:
は以下のように実装します:
for i, t in enumerate(AIRCRAFT_TYPES):
row = [1 if j % len(AIRCRAFT_TYPES) == i else 0 for j in range(n_vars)]
a.extend(row)
irowb.extend([constraint_index] * n_vars)
icolb.extend(range(1, n_vars + 1))
bl.append(0)
bu.append(7 * AIRCRAFT_COUNT[t])
constraint_index += 1
同様に、需要制約、最小運航頻度制約、発着枠制約、総運航回数制約、機材比率制約も設定しています。
整数制約の設定
opt.handle_set_property(handle, 'INTEGER', list(range(1, n_vars + 1)))
opt.handle_set_property
関数で全ての変数を整数に設定します。
ソルバーオプションの設定と問題の解決
opt.handle_opt_set(handle, 'Print Level = 0')
opt.handle_opt_set(handle, 'Task = Maximize')
result = mip.handle_solve_milp(handle)
opt.handle_opt_set
関数でソルバーの動作を制御し、mip.handle_solve_milp
関数で問題を解きます。結果(最適解)は result[0]
に格納されます。
結果例
最適解:
路線 | 小型機 | 中型機 | 総座席数 | 需要 | 充足率 | 利益(万円)
----|--------|--------|----------|------|--------|------------
A-B | 1 | 6 | 800 | 800 | 100.00% | 820.00
A-C | 0 | 3 | 360 | 400 | 90.00% | 372.00
A-D | 1 | 0 | 80 | 250 | 32.00% | 70.00
A-E | 0 | 3 | 360 | 450 | 80.00% | 318.00
A-F | 2 | 0 | 160 | 300 | 53.33% | 174.00
B-C | 0 | 1 | 120 | 350 | 34.29% | 96.00
B-E | 10 | 0 | 800 | 900 | 88.89% | 980.00
C-D | 0 | 1 | 120 | 200 | 60.00% | 104.00
C-F | 3 | 0 | 240 | 300 | 80.00% | 276.00
D-E | 0 | 2 | 240 | 250 | 96.00% | 224.00
E-F | 0 | 1 | 120 | 400 | 30.00% | 106.00
制約条件の確認:
1. 総運航回数: 34 便 (制限: 20-35) - 満たす
2. 小型機の比率: 50.00% (制限: 20-50%) - 満たす
3. 発着枠制約:
A: 発着回数 16, 制限 22 - 満たす
B: 発着回数 18, 制限 18 - 満たす
C: 発着回数 8, 制限 20 - 満たす
D: 発着回数 4, 制限 15 - 満たす
E: 発着回数 16, 制限 16 - 満たす
F: 発着回数 6, 制限 14 - 満たす
4. 需要充足率:
A-B: 100.00% (制限: 20-100%) - 満たす
A-C: 90.00% (制限: 20-100%) - 満たす
A-D: 32.00% (制限: 20-100%) - 満たす
A-E: 80.00% (制限: 20-100%) - 満たす
A-F: 53.33% (制限: 20-100%) - 満たす
B-C: 34.29% (制限: 20-100%) - 満たす
B-E: 88.89% (制限: 20-100%) - 満たす
C-D: 60.00% (制限: 20-100%) - 満たす
C-F: 80.00% (制限: 20-100%) - 満たす
D-E: 96.00% (制限: 20-100%) - 満たす
E-F: 30.00% (制限: 20-100%) - 満たす
5. 最小運航頻度: 全路線で満たす
総利益: 3540.00 万円
この結果は、週当たりの最大利益が3,540万円であることを示しています。最適な運航計画では、各路線に対して小型機と中型機を適切に組み合わせて運航することが推奨されています。
この解は、需要予測、座席あたりの収入、空港の発着枠制限、最小運航頻度、総運航回数制限、機材比率制約などのすべての制約を満たしながら、最大の利益を実現する組み合わせを示しています。
まとめ
この航空路線最適化問題では、混合整数線形計画法を用いて複雑な制約条件下での最適な運航計画を導出しました。