路線の開設と廃止を考慮した航空ネットワーク設計モデル
2012SE189大庭大樹 指導教員：佐々木美裕1
はじめに
航空ネットワーク設計モデルの過去の研究は，その多く がハブの設置を前提として設計している[1, 2]. 時間軸を 考慮し，利用者の変動によって路線の開設・廃止を決定し ながらネットワークを構築する航空ネットワークモデルは あまり研究されていない．そこで，本研究ではハブ空港の 配置を前提としない逐次型ネットワーク設計モデルを考 える．2
モデル
本研究では，ハブ空港の配置を前提とせず，路線を1つ ずつ順に開設する新規路線開設モデルと，廃止も考慮する 開設・廃止するモデルを提案する．開設モデルは，ネット ワークの総利用者が最大に増加する路線を1 つずつ順に 開設していく．その際，乗り換えを必要とすることや直行 距離に比べ極端な遠回りを必要とするサービスは，利便性 が低く，利用者が減少することが考えられるため，乗り換 え回数と迂回率によって利用者の利用率が決定すると仮定 する．また，一般的に乗り換え回数が多いと利用しなくな ると考えられるため，乗り換え回数が3 回以上必要な場 合，利用者は利用しないとする．図1の場合，移動可能な ODペア(出発地と目的地の組み合わせ)は直行路線がある (A,B), (B,C), (C,D)と1回乗り換えの(A,C), (B,D)，2 回乗り換えで移動可能な(A,D)がすべての移動可能なOD ペアとなる．図2の場合，(A,C)のように，乗り換えをお こなっても到達できない場合,移動可能ではない．よって， このネットワークで移動可能なODペアは(A,B), (C,D) となる. A B C D 図1 ネットワークの例 A B C D 図2 ネットワークの例2 また路線を開設していくと，空港間に複数の経路がで き，利用者は自由に経路を選択できる．一般的には利便性 が高い路線を選択すると考えられる．既存の路線の利用者 は減少し，新規路線は利用者が増加する．つまり，新規路 線を開設することでネットワークの各路線の利用者が変動 する．本研究では，路線開設・廃止モデルとして，各路線 の利用者が最大のときにくらべ半数以下になった場合，採 算が取れないとし，路線を廃止するモデルを提案する．3
迂回率と利用者予測
本研究では, 直行距離に比べ，迂回総距離から，利用者 を予測する．また，乗り換え回数の増加に伴う利用者の 減少を，乗り換えにかかる時間から計算する．一般的に飛 行機の乗り換えには，数時間かかることが多い．そこで乗 り換え時間を距離に換算した乗り換えコストsを定義す る．例えば，飛行機の平均速度が時速500マイルとすると, s = 500は乗り換えにかかる時間を1時間として想定して いることに相当し，s = 0は乗り換えにかかる時間を考慮 しない． 直行距離に比べ, 移動距離と乗り換えコストから，迂回 率を以下の式(1)で求める． 迂回率=移動距離+ s 直線距離 − 1 (1) 迂回率をx，迂回率から予測される利用者の利用率をrと した時，利用率を(2)で求め, グラフにしたものを，図3 に示す． r =−1 ax + 1 a :パラメータ (2) 図3 迂回率と利用率の関係r = a1x + 1 x = 1のとき，迂回総距離と乗り換えコストとの和が直 行距離の2倍を表し．x = 2のとき直線距離の3倍を表 す．aの値が小さいほど利用者は遠回りや乗り換え回数に 足して敏感であることを示し，迂回率が少し大きくなると 急激に利用者が減少する．aの値によらず，迂回率が0の とき，すなわち直行便が開設されたときは利用率は1 で ある． a = 1の時，迂回率が1.5の時に需要の75％の利用者 が，2の時に利用者が0となる．a = 4の時，迂回率が2の 時に需要の75％の利用者が，3の時に利用者が0となる． 14
貪欲算法
本研究では，利用者が最大に増加する路線を順に開設し ていく． 4.1 記号の定義 以下のように記号を定義する． E 空港の集合 xij 空港i ∈ Eから空港j ∈ Eへ路線が開設するなら1 そうでないなら0． u ネットワーク全体の総利用者数 p 路線開設数 k 既設路線数 dij 空港i∈ Eから空港j∈ Eの迂回率 r(dij) 空港i∈ Eからj∈ Eの利用率 wij 空港i∈ Eから空港j∈ Eの需要 4.2 路線開設・廃止モデルのアルゴリズム 1. 初期条件として路線が1つも開設されてないとする． ∑ i∈E ∑ j∈Exij = 0, u = 0, k = 0. 2. 開設していない路線を1つ開設したときの総利用者数の最大値u = max∑o∈E∑d∈Ewodr(dod)を求め， 路線(i, j) = argmax∑o∈E∑d∈Ewodr(dod)を開設 する. xij = 1，k := k + 1． 3. 空港間の経路を求める．複数ある場合は，迂回率の低 い経路を選択する． 4. 各路線の利用者を求める．また，ある路線(i, j)の利 用者がピーク時に比べ半数以下になった場合路線を廃 止する.xij = 0． 5. 路線の本数がp = kのとき終了，満たさない場合 2. に戻る．
5
計算実験
実験には1970年のCAB(民間航空委員会)が提供した 需要データを用いる．また，実験に使用した計算機はCPUは，Intel(R) Core(TM) i5-4210U CPU，メモリは4GB である．開設モデルの乗り換えコストの値を変更した場合 の完成したネットワークと，完成したネットワークにより の移動可能となる乗り換え回数ごとのODペア数を比較 する． 路線の本数p = 50，パラメータa = 1としたときの比較 図4 s = 0としたときの完成したネットワーク 図5 s = 500としたとき完成したネットワーク 図6 乗り換えコストの違いによる移動可能なODペア数 の変化 赤が直行で移動可能，黄色が1回乗り換えで移動可能， 緑が2回乗り換えで移動可能なODペアを示す．ODペア 数は最大300である.
6
考察
新規路線開設モデルでは，図4と図5から，乗り換えコ ストs = 500のとき特にシカゴがハブの役割を果たす結 果となった．s = 0は乗り換えコストがないため，各空港 がハブのような役割を担っていると考えられる．また，図 6から，乗り換えコストを増加すると移動可能なODペア が減少，また2回乗り換えを行い移動可能なODペアは s≧ 600以降見られなくなった．この3つの図から，乗り 換えコストを増やすと，1か所に集中して路線を開設して いることがわかる．参考文献
[1] J.F. Cambell：“Integer programming formulations of discrete hub location problem”. European Journal of
Operational Research, 72, pp. 387-405, 1994.
[2] M. O’Kelly：“The location of interacting hub facili-ties”. Transportation Science, 20, pp. 92-106, 1986. 2
