飛行機スケジュール最適化問題 PuLP

飛行機スケジュール最適化問題

飛行機スケジュール最適化問題は、与えられた制約条件の下で、最小限のコストまたは最大限の利益で運ぶように航空便をスケジュールする問題です。

この問題に対する一つのアプローチは、線形プログラミングを用いることです。

PuLPは、Pythonで線形プログラミング問題を解くためのオープンソースのライブラリです。

以下に、飛行機スケジュール最適化問題の例を示します。

例：

ある航空会社が、3つの都市（A、B、C）を結ぶ便を運航しています。

各都市の間には、以下のような航空路があります。

  • 都市Aから都市Bへの便
  • 都市Aから都市Cへの便
  • 都市Bから都市Cへの便

各都市への到着時刻、出発時刻、フライト時間、最大搭乗可能人数が与えられています。

以下の制約条件を満たしながら、最大限の利益を得るために、どのようなスケジュールを立てるかを決定する必要があります。

  • 各便の発着は、出発地の時刻よりも遅れることはできない。
  • 各便の出発時刻は、前の便の到着時刻よりも遅れることはできない。
  • 各便の乗客数は、最大搭乗可能人数を超えてはなりません。

解き方・ソースコード

PuLPを使って飛行機スケジュール最適化問題を解決しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# ①pulpライブラリをインポート
import pulp

# ②制約条件を定義する
problem = pulp.LpProblem('Flight Schedule', pulp.LpMaximize)

# ③便ごとに決定変数を作成する
flight_AB = pulp.LpVariable('Flight_AB', lowBound=0, cat='Integer')
flight_AC = pulp.LpVariable('Flight_AC', lowBound=0, cat='Integer')
flight_BC = pulp.LpVariable('Flight_BC', lowBound=0, cat='Integer')

# ④目的関数を設定する
problem += 1000 * flight_AB + 1500 * flight_AC + 1200 * flight_BC

# ⑤制約条件を追加する
problem += flight_AB <= 50
problem += flight_AC <= 70
problem += flight_BC <= 80

problem += flight_AB <= 8
problem += flight_AC <= 11
problem += flight_BC <= 12

problem += flight_AB + flight_AC <= 70
problem += flight_AB + flight_BC <= 60
problem += flight_AC + flight_BC <= 75

# ⑥最適化を実行する
problem.solve()

# ⑦結果を表示する
print('Flight AB:', pulp.value(flight_AB))
print('Flight AC:', pulp.value(flight_AC))
print('Flight BC:', pulp.value(flight_BC))
print('Total profit:', pulp.value(problem.objective))

①PuLPライブラリをインポートしています。

②pulp.LpProblemを使用して、最適化問題を定義しています。

‘Flight Schedule’は問題の名前であり、pulp.LpMaximizeは目的関数を最大化することを示しています。

③各便に対して決定変数を作成します。

ここでは、都市Aと都市Bの間のフライトをflight_AB、都市Aと都市Cの間のフライトをflight_AC、都市Bと都市Cの間のフライトをflight_BCとしています。

各決定変数の値は、整数であることを指定し、0以上の値を取るように制限されています。

④目的関数は、各便の利益の合計を設定します。

ここで、flight_AB、flight_AC、およびflight_BCは各便の数を表します。

⑤制約条件を設定します。

これらの条件は、便の数に関する制限を設定するものです。

⑥problem.solve()で最適化問題を解きます。

⑦結果を表示しています。

pulp.valueを使用して、各便の数と総利益を取得しています。

[実行結果]

Flight AB: 8.0

Flight AC: 11.0

Flight BC: 12.0

Total profit: 38900.0

この結果は、都市Aと都市Bの間に8便、都市Aと都市Cの間に11便、都市Bと都市Cの間に12便の便をスケジュールすることが最適であり、その結果、最大の利益である38900ドルを得ることができることを示しています。