Supcon'96 本選問題 -- カフェテリア問題 ---

高橋宏治 松田裕幸
本原稿は"SuperCon'96" (『bit』(共立出版) 1996.11掲載)を もとに書かれている。

4種類のセットメニューが用意されているカフェテリア(レイアウト図参照)がある。
[セットメニュー]

    Aセット ハンバーグ + サラダ + パン + スープ + ミルク
    Bセット エビフライ + ライス + ミルク + フルーツ
    Cセット ステーキ + サラダ + ライス+ スープ + フルーツ
    Dセット パン + サラダ + フルーツ + ミルク + スープ
客は、入口の前で、希望のセットメニューごとに列を作って待ち、支配人に 「呼ばれたら」、入口でトレーを受取ると共に、支配人から窓口を回る順序の 指定を受け、その指示どおりに窓口を回り自分のセットを完成させ出口より出る。

各セットごとの待ち客数を、Aセット1000人、Bセット 750人、Cセット 500人、 Dセット 500人とする。ただし、これは開始時点の人数で、それ以降新しい客は 来ないものと仮定する。

シミュレ-ション時間を基準に、なるべく早く全員がセットを完成し出口に 到達するような支配人用のスケジュ-ル(投入時刻、入口から出口までの経路)を 作成したものを優勝とする。

[コスト]
1区間の移動に要する時間は1単位時間(ut)とする。各窓口でサ-ビスを受け、 次の分割点に移動するまでの時間は次の通り。ハンバ-グ 3ut、海老フライ 4ut、 ビ-フステ-キ 5ut、サラダ 2ut、フル-ツ 1ut、ミルク 1ut、ス-プ 2ut、 パン 1ut、ライス 2ut。また、待ち行列(長さ4)に入るための時間は0utとする。

[移動規則]
カフェテリア内の客は常に区間、待ち行列、窓口のいずれかにいるものとする。

  規則1) 1区間内には一度に1人の客しか入れない。
  規則2) 先の区間が空いている時、進める時は進まなければならない。
  規則3) [分割点での衝突]
         分割点において互いに交差する2人の客は、次の単位時刻には、
         同時に次の区間に移動できる。
  規則4) [行き先経路の衝突]
         分割点において2人の客の行き先が重なった場合には、「交互に」
         スケジュールされる。そのため、衝突が発生する分割点においては
         直前の通過記録が保持されているものと仮定する。	 
  規則5) 一旦、待ち行列に入った後は、サ-ビスを受けるまで待たなければ
         ならない。
黒丸●は「分割点」を表す。分割点と分割点の間を「区間」と呼ぶ。 複数の連続する区間は「経路」を構成する。すべての経路は一方通行である。 横コの字形の図は、窓口に入るための「待ち行列」(太い棒線)の 部分)と、 「窓口」(待ち行列以外の部分) からなる。なお、窓口から 分割点に行くまでの区間は、窓口の一部とみなす。

1.本選課題解説

この問題のキーワードは、 である。その一般解の例をあげておく。

【カフェテリア問題の解法例】

  1. 各セットについて、窓口を回る順列を求める。
    例えば、{ハンバーグ、パン、スープ}というメニューの組合せに対し、
            ハンバ-グ => パン => スープ
            パン => ハンバーグ => スープ
            スープ => ハンバーグ => パン
            ・・・・・
           
    いう窓口の順列をすべて求める。
  2. 1で求めた中に含まれる各窓口間の経路と経路長を求める。
    例えば、ハンバーグ => パン を満たす経路と経路長 としては、
            e1-e15-e72-e73-‥‥-e64-e36-e8  長さ 13
            e1-e15-e16-‥‥-e24-e54 - ‥‥-e49-e69-‥‥-e64-e36-e8 長さ 25
            ・・・・・	
           
    という区間列と区間の数(経路長)を求める。
  3. 1と2より、各セットごとにそれを達成する経路を経路長の短い順にリスト する。
  4. 各セットについて、最も所要時間を要する窓口の時間を求める。この時間が 投入できる最小間隔である。ただし、待ち行列(長さ4)というバッファがある のでその数内での平均が満たされればよい。

    例えば、極端な場合、4人を連続して窓口(コスト3utとする)に送った場合、 次の組が窓口に入ることができるのはどう頑張っても、3ut x 4=12ut後 となる。

    セット間でメニュ-に関する干渉(同じ窓口に向かう)がある場合、投入間隔を あえてずらすのには意味が出てくる。あるセットの客を3ut間隔、別のセットの 客を4ut間隔で、入口から投入したとすると、窓口では公倍数ごとでかち合う 結果となるが、バッファ吸収できるの範囲で前後にずらして対処する。

  5. 3で求めた最短経路を利用したとして、4で求めた時間間隔で投入したとき、 入り口で待っている人数をさばくのに要する時間を求める。
  6. 各セットについて5で求めた時間を比較し、時間の掛かる順に優先順位を 決める。
  7. 最も優先順位の高いセットについては、経路は3で求めた最短のもの、投入 間隔は、4で求めたものを採用する。
  8. 他については、最も時間の掛かるセットが終わる時間を、それぞれのセット について待っている人数で割り、投入間隔とする。
  9. 最優先セットの構成メニュ-のうち、他のセットと干渉する窓口について、 その処理能力について、7と8の結果よりオーバーするか否かを判定する。 越えてなければそのまま、越えていれば、比例案分する。これで各セットの 投入間隔が変更される。

    例えば、ある窓口(コスト2ut)に、AセットとBセットの客が来るとする。 先の計算で、Aセットの投入間隔が3ut、Bセットが4ut であったならば、 この窓口には、12ut間にAの4人+Bの3人=7人が来る。しかし、この 窓口の処理能力は12ut間に6人(=12ut/(2ut/人))なので、投入間隔を適当に 比例案分する必要が出てくる。

  10. 優先順位の高い順に同様に行なう。
  11. 経路の能力についても判定する。能力不足の場合は、優先順位の低いものは、 可能な範囲で迂回路に回す。

    ある区間にAセット、Bセット、Cセットの客が通るとする。それぞれの 投入間隔を3ut、4ut、2utの時、12utの間に4+3+6=13人がこの通路を 通ることになる。しかし、区間あたり 1utに一人しか通すことができないので、 あきらかにこのこの投入間隔は経路の処理能力を越えていると判断される。

  12. 間隔調整と迂回路については、いくつかの案がでてくるので、シミュレ-ション を行ない、結果に応じて修正する。
  13. 立ち上げ・立ち下げの過渡状態に対して、投入間隔と経路を修正。

    もし、同じパターンで投入したとして、あるセットが4品目で構成されるので あれば、4人以上投入され、最初のものが出口に到達したときあたりまでを 過渡状態の 終りと判断する。

ここに示した解法例は一般的な方法の一つである。今回の問題においては、 案外簡単な方法で、最適解に近い値を得ることができる。それは、ボトル ネックとなる箇所が窓口で一箇所、区間で一箇所しかなく、かつ、それらの ボトルネックを解消した時、一般によくあるような、他の箇所のボトルネックを 引き起こすことがないためである。すなわち、ボトルネックを発見し、平準化 していくことが重要となる。

だれでも思いつく一番単純な方法は、絶対前の人を追い越すことのない時間間隔で、 客を投入することである。これを各セットごとに行なう。設定した経路内にル-プが あると、場合によっては先に進めない状況が発生するが、飢餓状態(一度も サ-ビスを受けることなく餓死してしまう)やデッドロック(だれも先に行けない)は 起こり得ない。この問題の良い解は4、500 utあたりにある。しかし この単純な方法を用いるとその倍以上の時間がかかることがわかる (1000 x 3ut + 750 x 4ut + 500 x 5ut + 500 x 2ut + α)。

では、複数のセットを混ぜ合わせて投入することを前提にした時、デッドロック が発生したらどうするか? 一般には、投入間隔で調整するか、迂回路を検討する。 この場合、一方だけを考慮する立場と、両方を考慮する立場に分かれる。当然、 両方の方針を検討した方がよりよい解が得られるが、両方とも試みたチ-ムは なかったようである。優勝した灘高等学校のnada-bチ-ムも、2位の関西大学第一 高等学校yotonakiチ-ムも、一旦投入時間を決めたら後は、迂回路の調整のみで スケジュ-ルを求めた。その結果は、それぞれ 6、540ut と 6、547ut であった。

一方、審査委員の一人(仮にtitechチ-ムとしよう)が試みた方法は、経路を セットごとに一つに固定し、ボトルネック(一番多くの客が殺到する場所)を 考慮した各セットごとの投入間隔と投入組合せを一つ決め、あとは、それを単純に 繰り返すというだけのもので、4、572ut という記録を出すことができた。

この例は教訓的である。カフェテリア問題という大きな森を前にして、個々の 経路の複雑さに幻惑されることなく、空の上から森を鳥瞰するように、うまい 隘路を見つけた方がいい結果を出したことになる。多くのチ-ムは、問題は 難しい、したがって、その解法も難しいだろうと決めてかかっていたろころが あった。

なお、待ち行列をバッファとして積極的に使用したチ-ムは桐朋 kitsuneチ-ム のみであった。ただ、今回の問題の場合、ボトルネックは窓口だけとは限らず、 特定の通路区間もなりうるために、仮に、待ち行列を使うことを仮定して、投入間隔を 縮めてしまうと、待ち行列に入る前に前の区間が塞がって先に行けない状況が 発生する場合もある。

また、岡山waskyチ-ムは、最初からスパコンを意識し、全経路の組合せを テ-ブルで持ち、確率的な戦略を用い、適正な経路を枝苅りで求める方法を 試みたが途中で力尽きてしまった。

[titechチ-ムの場合]

以下のような考察を行なうことで、本来なら、コンピュ-タを使って求めるで あろう経路、投入間隔、投入順番を人間が求めてしまった。したがって、当然の ごとくこのプログラムは短い。

(1) A:B:C:D = 4:3:2:2 なので、A 4 人, B 3 人, C 2 人, D 2 人の計 11 人 を、適当な間隔でサイクリックに送り出す。
(2) サイクルの間隔が短いと何周かしたところでデッドロックを引き起こすの で、その直前に少し待ちを入れる(ただし、この例ではデッドロックは起きない)。

この間隔は次のようにして求める。区間36のところに4、500ut のボトルネック がある(1000 x 1 + (750 + 500 + 500) x 2 = 4500(ut))。上記サイクルを 250回((1000+750+500+500)/11=250)繰り返すので一回あたりの投入間隔は 18ut(4500/250 = 18)が下限となる。

各セットの経路を次のように決める。実際に、絵を書いてみるとすぐわかるが、 各セットともできるだけ同じ経路を通るようにしている。したがって、ボトル ネックとなる状態を回避できるだけの間隔で投入することによって、ほとんど 待ちを作らずに、全員を出口まで送りだすことができる。

セットAの経路: 82, 83, 13, 1, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 54, 
    6, 52, 51, 50, 49, 48, 4, 46, 45, 44, 43, 42, 41, 40, 39, 7, 37, 36, 8, 
    34, 33, 32, 31, 86, 87
セットBの経路: 82, 83, 13, 14, 15, 16, 2, 18, 19, 20, 21, 22, 23, 24, 54, 
    6, 52, 51, 50, 49, 69, 68, 67, 66, 65, 64, 36, 35, 34, 33, 9, 31, 30, 
    29, 28, 55, 56, 57, 58, 5, 60, 66, 65, 64, 36, 35, 34, 33, 32, 31, 86, 87
セットCの経路: 82, 83, 13, 14, 15, 16, 17, 18, 19, 3, 21, 22, 23, 24, 54, 
    53, 52, 51, 50, 49, 48, 4, 46, 45, 44, 43, 42, 41, 40, 39, 7, 37, 36, 
    35, 34, 33, 9, 31, 30, 29, 28, 55, 56, 57, 58, 5, 60, 66, 65, 64, 36, 
    35, 34, 33, 32, 31, 86, 87
セットD0の経路: 82, 83, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
    54, 6, 52, 51, 50, 49, 48, 4, 46, 45, 44, 43, 42, 41, 40, 39, 7, 37, 
    36, 8, 34, 81, 80, 79, 58, 5, 60, 66, 65, 64, 36, 35, 34, 33, 32, 31, 
    86, 87
セットD1の経路: 82, 83, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
    54, 6, 52, 51, 50, 49, 48, 4, 46, 45, 44, 43, 42, 41, 40, 39, 7, 37, 
    36, 8, 34, 81, 80, 79, 58, 5, 60, 61, 62, 63, 42, 41, 40, 39, 38, 37, 
    36, 35, 34, 33, 32, 31, 86, 87

1サイクル 18utの中身は
   D0, C, B, -, D1, C, B, A, -, B, A, A, A, -, -, -, -, -
とする。ここで、「- 」の部分はどのセットの客も投入されないことを表す。 また、この投入順序は、(1)経路長の長いセットをなるべく前に持ってくる、 (2) 36 番の edge が詰まらないギリギリのレートで客をカフェテリアに誘導する、 (3)「入り口から 36 番へ至る経路全体」と「38 番からぐるっと回って 36 番へ 戻ってくる経路全体」をそれぞれバッファとして利用する、の発想の元に 決められている。

上記の経路を用い、このサイクルを250回繰り返すと、4、572ut の 時間で全処理を完了した。なお、解の立ち上がり、立ち下がりのチュ-ニング まで行なうと4、561程度まで縮めることができた。