航空機の乗務員スケジューリングシステム
伊倉義郎
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111.

料金，はじめにピジネス客を対象とした正規のエコノミー料金など，あの手この手の設定になっている.しかも，これら北米の航空業界は，良きにつけ悪しきにつけ現在一番の料金に対応した座席数が時間とともに変化したり，混オベレーションズ・リサーチが華々しく使われている業

んでいるフライトにはオーパープッキングしたりするこ界ではないだろうか. 60年代から 70年代にかけて，石油ともある.

会社で LP による石油精製モデルが流行したのに似て，北米での航空運賃は， 70年代後半から自由化され，各80年代には航空会社での OR の利用が盛んで、あった.

社各社まちまちになった.それに加えて，最近のイールその時代時代の花形産業で， OR が一番よく使われるドマネージメントの流行により，ますます複雑怪奇になという現象なのかもしれないが，米国の主要産業が製造ってきている.そこで，昨年夏，アメリカン航空はこの業からサーピス業へ移行しつつあるのに並行して，サー複雑な、ンステムを簡素化し，しかも乗客に有利になるよ

ビス部門での OR の利用例が最近多く見うけられるよううな“値下げ"を発表した.になった.金融，運輸，通信等のサーピス産業での OR系がはっきりしていなかったので，ある路線では値下げが今後ますます発展して L 、く様子である.

で、あっても矧!な路線では値上げであったのかもしれないが.いずれにしても，心機一転経営収支の黒字化という2. 1992年のイールドマネージメント

ホームランをねらったものだが，結果としては各社がそさて本題に入る前に，現在の北米の航空会社の体質を浮き彫りにする l つのトピックスをご紹介したい.

1992

年は，米国の航空業界にとっては大変な年であった.といっても，もとの料金体

2年続きの赤字傾向がさらに悪化し，大手航空会社が軒並れに追随したため，逆に競争が激し，収益も悪化してしまうはめになった.おまけに，経済全体に不景気であったことも加わり，1992年は航空業界にとっては最悪の年となってしまった.

み大幅損失を報告した年であった.業界全体に競争が進

このイールドマネージメントというものは，いわば航みすぎていて，各社の成績不振は急に改善される見通し

空会社と乗客とのゲームのようなものである.航空会社がない.おまけに，米圏内の競争に加えて，ヨーロッパ，は，乗客に高い切符をできるだけ早く買わせたいが，逆アジア地区のキャリアーとのグローパルな競争も始まりに大衆は安い切符をできるだけ遅〈買いたいのが本音.

つつある.

そこで航空会社では，優秀な OR マンを雇って，確率最このような過当競争をひきおこしている原因の 1 つ適化モテツレ等を駆使し，ゲームに勝つベく努力している.に，イールドマネージメントと L 、う概念があげられる.

OR アナリストの視点からは，この問題は会社にとってこれは簡単にいうと，各フライトの満杯度をどうやって重要であり，大変チャレンジングではある.しかし，過作り出すかということであるが，具体的には，各座席グぎたるは及ばざるがごとしで，はたして期待どおりの効ラス(ファースト，エコノミー等)の数，およびそれら果が出るかどうかは明らかではない.の料金の設定のノウハウを意味し，~、かに各フライトか

ちなみに，最近ではこのイールドマネージメントのコらの利益を最大化するかを主眼としている.たとえば，ンセプトがホテル，1 カ月前までに予約すると正規料金の半額以下になるスにまで応用されつつあるということである.

ーパーセイパーや週間前までの特別ディスカウント

いくら

よしろう

SAITECH I
nc.

3Wagner Court , Holmdel , NewJersey07733 ,U.S.A.
1993 年 8 月号

レンタカー，そしてついには通信業

3. クルースケジューリング
3.1 航空会社でのスケジ 2 ーリングシステム
航空会社では，普からよく OR が使われてきた.路線
ダイヤのスケジューリング，機材割当，乗務員(クルー)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(25)408

スケジューリング等のシステムが開発され，盛んに利用されている.その中でも，Crewbase

クルースケジューリングは一番古典的で，投資効果のはっきりする応用例である.前述のイールドマネージメントや機材割当て最適化は，収入の増大と L 、う不確実な目的をもっている.それがゆえにシステムを開発しても，どれだけの投資効果があるのか L 、まひとつはっきりしない.それに比べて，クルースケジューリングは，コストの削減という 100% 明らかな指標があるので，投資効果がはっきりと測定できる.よりよいクルースケジューリングを行なうことによって月

131/2hourlayover々何億円ものコストが削減でき，しかもそれが必ず実現可能である.と L 、うわけでト，各社独自のシステムを作っ

図 1たり，アメリカン航空のように自社システムを他社へ売トリップの例ったり，これを専門とするシステムハウスもあり，話題

タ経由でオースチン泊り，翌日ダラス，に事欠かない業界となっている.

経てニューアークへ戻るというスケジューんとなっていレキシントンをクルースケジューリングシステムは単独として稼働する.このあと自宅で何日か休息後，再び似たような乗務るわけではない.その上流には，営業マーケティング部

パターンを繰り返すか，または訓練や講習へ参加するこ門の作成する毎月の路線スケジュール，それに合わせたととなる.このような，ベースからベースへ戻る乗務パ機材の割当て等がある.また，ターンはトリップと呼ばれていて，クルースケジューリング

トリップを何個か継と並行して，機材のメンテナンススケジュール，燃料のぎ合わせたもので 1 人のクルーの月次乗務パターンが決

調達プラン，空港での地上乗務員スケジューリング等もめられることになっている.個々のトリップは，政府 (Fある.これらのシステム全体が航空会社でのプラニングAA) や航空会社のさまざまな制約条件を満足していな.スケジューリングシステムを構成する.

ければならない.この制約条件の中には，たとえば 1 日

プランナーたちは，これらのシステムを駆使して月次の最大飛行時間とか，空港での最小休息、時間等があり，のスケジューんを作成する.実際の業務にかかわること数十にものぼることもある.ちなみに，日本の航空会社

なので，数多くの制約条件があり，それらを十分順守しの例としては文献 [2J ，たスケジューんを組む必要がある.年々業務条件は複雑になっていくので，おのおののステップで使われるシス

さて，[4J 等を参照されたい.

トリップにも効率の良いものと悪いものとがある.もしクルーの空港での待ち時間や，デッドヘッド(クテムは短時間でより複雑なモデルを解く能力を要求されルーが乗務せずに次のフライトに乗り継ぎをすること)る.

が多いと，そのようなトリップは効率がよくない.特に，

3.
1 クルースケジューリング問題

北米の航空会社では，このような非実働時聞をソフトタ

航空会社のクルー(操縦士や客室乗務員)用乗務スケイムとして，その長さに比例した手当を支払うことにな

ジュール作成、ンステムは，航空会社にとって欠くことのっている.であるから，できないシステムの 1 つである.大手航空会社では，何るほど，千人というクルーをかかえており，これらのクルーをいつながるわけである.また?ルーにしても，待ち時間かに効率よく活用するかというのは重要な管理問題であは少なければ少ないほど，ホームベースに早く帰れるわる.これは，単にクルーの運用コストのみならず，乗客けで，その方がよりよき家庭生活をおくれるという話でへ対する+ーピスの向上やクルーの労働条件，仕事へのある.

満足度等にも関係する種々の側面をもっているからである.

ソフトタイムを少なくすればす

クルーの実働時間の割合が増し，経費の削減に

アジア・ヨーロッパ地区の航空会社は，このようなソフトタイムに比例した手当というシステムはとっていな

クルーの乗務パターンというのは，図 1 に示されたよ
うなものになっている.この乗務パターンの例では，ニューアークを自宅のあるベースとして日目アトラン

4
10(26)

いが，効率のよいトリップを使用するにこしたことはな
L 、.

全クルーの月次乗務パターンを決めるためには，多数© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

の異なったトリップを生成しなければならない.たとえば，北米の大手航空会社では，数十の都市の聞で毎日千C
ost (事 MM)$64近いフライトを運行しているが，そのすべてのフライトをトリップでもってカバーしなければならない.この最62

適トリップの決定問題というのが，じつは厄介なシロモノである.というのも，まず可能なトリップの数が莫大60であること.これは，全米の航空システムが，ハブとスポークの形になっていて，ハブでのグルーの乗り継ぎの58可能性が数多くあり，可能なトリップの数が指数関数的に増加することによる.莫大な中から最適なものを選ぶ

56のは容易でない.

さらに問題を複雑にするのは，フライトのパターンが54

毎日少しずつ変わっていくという点である.週日のフライトスケジューんはだいたい毎日同じであるが，月水金

52と火木の違いもある.また，休日や週末は特別なスケジュールとなる.それらを考慮した上で，最適なトリップを発生させて，うまい具合にすべてのフライトをカバーするのがトリップの最適化問題である.

50

ロ給与し使うということを行なっている.しかしながら，毎月毎月のスケジュールは需要に合わせて変化するだろう

し，路線の削除や追加等が頻繁に起こるであろうから，その月々に合わせた最適トリップの選択を行なうのがベストである.

最適トリップの効果例

ーンを入札するシステムになっている.この場合，まず最適トリップを使った月次乗務パターンが人数分だけ表示される.

クルーはそれを見て，自分の希望パターンを何個かビッドする.会社側は，出されたピッドと各クルーの勤続年数等を考慮して順次パターンを各クルーに割り当てる.この場合，割り当てのルールは細かく決まっ

最適なトリップを選択することによって，上記のソフトタイムを最小化でき，経費の削減につながる.これは北米での航空会社ではクルー手当の減少という形になる
し，アジア・ヨーロッパ型の航空会社では，同じ人員数でより多くの路線をカパーできる，と L 、う恩恵をもたらす.このような投資効果は年間数十億円に達するという報告もある(文献 [6J. 図 2 参照).て L 、て，タイプレカーが何段階にも設定されている.
このシステムの問題は，一般的に年巧者は常に条件のよ L 、パターンを選べるが，経歴の浅いクルーには希望のパターンがなかなか回ってこないことにある.最近になってそのような弊害が指摘されて，若干修正されつつあるという話もある.また，上記入札の場合，月次パターンの替わりに，最適トリップ決定問題の解法については. 4. で説明す
るとして，

After
圏諸経費

図 2

航空会社によっては，長年の経験からあらかじめ決まったパターンのトリップをもっていて，それらを繰り返

B
efore
圏デッドヘッド

トリップを個々のクルーに割り当てるプロセスを次にご紹介したい.

トリップのピッドをするという改良版なども導入されている.この場合には，各クルーの希望トリップに合わせて，訓練や地上勤務も入れた月次乗務パターンが作成されることとなる.

3.
2 月次乗務パターンの割り当て

北米以外の地域では，上記の入札システムはなく，個ひとまず最適トリップが決定された後に，今度は個々々のクルーの資格や希望に合わせて，個別にトリップをのクルーにそれらを割り当てなければならない.このプつなぎ合わせて月次乗務パターンを作るという.その場ロセスも，クル一個人個人の資格，条件，希望等が入っ合，あまり一部のクルーに条件のよいトリップが集まらてきて，大変込み入った問題となる.また，この段階にないように，なるべく平等に乗務パターンを割りふる考なると，さらに“文化の違い"が目立ってきて，世界各慮がなされているようである.また，過去の乗務パター地域で大きな違いがでてくる.

ンをある程度システムに記憶させておいて，同じトリッ

たとえば，北米の航空会社ではクルーが月次乗務パタ
1993 年 8 月号

プに毎回毎回当たらないようにするなどの工夫がなされ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(27)4
11

にあるように，ている.

いずれにしても，世界各国の労働基準や習慣，航空会クルースケジューリング用のセットカパリングは， 1jjIJ約式は千程度でも，変数の数は百万を越え

社の運営方針，クルー組合の有無等によって，種々のパるものも存在する.このサイズの問題では，単に線形問リエーションが出てくる.会社のコスト削減の観点のみ題を解くだけでも単体法では難しくなる.内点法によりでなく，クルーの仕事に対する満足度，生活の質の問題

線形問題を解き，その後整数条件を満足する解を見つけ等いろいろな側面をふまえてシステム化きれなければなるというようなアプローチが必要となってくる.

らない.

デルタ航空白]やカナダ航空[7]では，内点法をベース経済的観点からすると，この乗務パターンの割り当てにしたクルースケジューリングの解法システムが稼働しに最適化の入る可能性はあまりない.というのも，割りていて非常によい結果を生んでいることが報告されてい当てのルールによってすべてのケースが網巌されておる.投資効果についても，年間数千万ドルのオーダーとり，最適化の余地がないことになる.この点からしても推定されている.このような多額の投資効果を可能にす

上記のトリップの選択を最適する方が，はるかによい投るのも，内点法をベースとした解法によって超大型のセ資効果が得られるものと考えられる.

ットカパリング問題が解けること，またその解が以前の

4. 内点法によるクルースケジューリングの解法解 (A 1 ベース等)よりずっと質のよいスケジュール解であることによると考えられる.従来の方法では限られた数のトリ v プしか処理できなかったものが，内点法に最適トリップ選択問題は，古典的整数計画問題の l つよる新解法ソフトウェアにより，より広範囲のトリップ集合被覆(セットカパリング)問題として定式化できる.の可能性が吟味できるようになった.また，最新の RI

この場合つ 1 つのフライトが集合の要素に対応し，SC ワークステーションの活用により，データベースや各トリップが 1 つの部分集合となり，そのコストも計算グラフイカルユーザインターフェースも含めた新しいスされる.結果として，元の問題は与えられた多数のトリケジューリング支援システムの開発が可能になっていップから最小コストで複数のトリップを選び，集合要素る.のすべて(すなわち路線全部)をカパーするというセットカパリング問題に帰着する.
このようなセットカパリング問題はじつはそう簡単に

5. 今後の可能性について航空会社のクルースケジューリングシステムは今後もは解けないことがわかっている.特に，可能なトリップますます性能が改善されていくものと考えられる.現在をより多く生成して，選択候補を多くすればするほど，のところつの月次乗務スケジュール計算で-何時間も見つかる解の質は向上するかもしれないが，解法時聞がかかるケースも，将来は計算時聞が大幅に短縮されるで余分にかかってしまう恐れがある.逆に，候補の数を少なくすると最適の組合せが見つかってもコストはさほどあろう.
クルースケジューリングは，航空業界に限ったものではない.他の輸送機関，鉄道，地下鉄，パス等にも共通良くないという結果になってしまう.
以前では，このようなセットカパリング問題を直接解いてクルースケジューリングの解とするというシステムは少なかったが，最近ではアルゴリズムの開発とハードウェアの性能の向上によって最適化システムも可能になっている.とりわけ，セットカパリング問題の元にあるした問題が存在する.今後は，そのような業界にも同じようなワークステーションベースのスケジューリング最適化支援システムが開発導入され，よりよいスケジューリングが可能になるものと思う.

参芳文献

線形計画問題が超大型であることより，カーマーカ一法を使った解法が注目を集めている.カーマーカー(内点、[1J BixbyR. etal.:Very Large.scale Linear法)については，種々の論文や計算結果が報告されていProgramming: A Case Study in Combiningて，ここでは詳しくは紹介しないが，文献 [3J ，Interior Pointand Simplex Methods , Opera‑[5J 等を参照されたい

tions Research , Vol.40, No.5 , (1992) , 885-897.

内点法が従来の単体法に比べて，格段に威力を示すのは変数の数が 1 万を越えるあたりからである.論文 [IJ412 (28)[2J コンピユートピア:運行乗務員乗務割作成支援システム:スケジューラのオーパーロードを解消，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1988オベレーションズ・リザーチ

年 11 月号.

-最新刊・

[3J 伊倉義郎:検証が進むカーマーカ一法の実用的価
値と応用の可能性，日経コンピュータ，日号，1991 年 6 月 17149ー 156.

[4J 片山修:日航の運命，

NESCCO BOOKS ,1987年.

[5J 水野真治:線形計画問題に対する内点法について
第 1 回 RAMP シンポジウム論文集，日本オペレーションズ・リサーチ学会，

1989年 10 月，[6J Takahashi , D.

15‑
25.

New Formula Taking

Off;DeltaPurchases Bell Labs System for
Scheduling , Dallas Times Herald , April 1,
1989.
[7J Toronto Star

Canadian Airlines buys

Perlの園ヘょうこそ
ユーザのためのUNIX

ッ→レとしてのUNIX
現代数学の風景

SystemforCrews , January9, 1992.

数学のための薦書案内
7 月号/発売中/定価 930 円
特集

ステレオグラム進化論

3D ステレオグラムはなぜ立体に見えるのか?

どうやったら作れるのか?

そのしくみとプログラムを公|持1.

3次元を復元する
2 次元図を読みこんで 3 次元図形を構築するための研究と製品を紹介する.

装勢
8 月号/発売中/定価 980 円

推論「黄昏の領域」の定式化
推論について/論理と推論/定性推論/演縛の認知的モデル/確率推論/人は論理的に推論しているか 7/ 直観的推論

サイエンス社
東京都千代田区神間須 IU 町2-4

安部徳ビル

宮 03-3256-1091 振符東京 7 ‑2387
1993 年 8 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(29)413