7月 222010
 

今夏もポケモンの新しい映画が封切られ,新種のポケモン「ゾロアーク」などが登場し,「セブン-イレブン ポケモンスタンプラリー2010」が始まった.

このスタンプラリーでは,セブンイレブンの店舗に行って,台紙にポケモンのスタンプを押す.スタンプは合計24種類あり,店舗ごとに異なるスタンプが設置されている.4種類のスタンプを集めるとポケモンのシールが,8種類のスタンプを集めるとポケモンのポスターがもらえるという仕組みだ.

我が家の長男7歳と長女4歳も当然,参戦したいと騒ぐ.問題はいかに効率よくスタンプを集めるかだ.

この猛暑の中,歩いてセブンイレブンの店舗めぐりをするなんて考えられない.最低でも8店舗に行かなければならないのだから.子供2人を連れて自転車もありえない.こんなことに自動車を使うのは反社会的だ.そこで,夏休み期間中は市バスの小児運賃が無料になる京都市の「エコサマー」という制度を利用して,市バスでセブンイレブンの店舗を渡り歩くことにする.私は通勤定期券を持っているし,幼稚園児は元々無料だ.

さて,どうすれば市バスで最短時間でポケモンスタンプラリーを完結させられるだろうか.これは巡回セールスマン問題と呼ばれる最適化問題に似ているが,さらにレベルが高い.というのも,最低8店舗に行かなければならないのは確かだが,8店舗でスタンプラリーを終われる保証はないからだ.もし訪問した2つの店舗に同一のスタンプが設置してあれば,もう1店舗増やさなければならなくなる.仮に,計画通りに自宅近くに戻ってきた最後の8店舗目のスタンプがどこかと同じスタンプだとしたら,スタンプ1つのために,かなり遠くまで往復しなければならなくなるだろう.このようなリスクを考慮しなければならない.さらに,距離は事前に計測しておけば変化しようがないが,市バスで移動する場合,所用時間は交通状況に依存する.京都の市バスは時刻表通りには運行されず,本数の少ないバスを計画に組み入れると,バス停で長時間待ちぼうけをくらう恐れがある.スタンプの種類と市バスの運行に不確定性があるわけだ.そこまで考慮した最適計画を立案しなければならない.

市バスに乗ってポケモンスタンプラリーを最短時間で完結させよう in 京都

問題: 以下に示すような制約条件の下で,評価関数を最小化する行動計画を立案せよ.

評価関数: 自宅を出発してから,ポケモンスタンプラリーを完結させて,自宅に戻って来るまでの所要時間.

制約条件:

  • 8種類の異なるスタンプを集めなければならない.
  • 夏休み期間中の平日,土曜,休日のいつ実行してもよい.ただし,開始は9時以後,終了は18時以前とする.
  • セブンイレブンの店舗位置は事前にすべて正確に把握できる.
  • 各店舗にどのスタンプが設置してあるかは事前に全く把握できない.
  • 移動手段は市バスと徒歩のみとする.
  • 市バスの時刻表は参照できるが,交通状況によって時刻表通りに運行されるとは限らない.
  • 自宅の最寄りバス停は金閣寺道とし,自宅とバス停の間の移動時間は0とする.

夏休みの自由研究にどうでしょうか.

operations researchを専門にする大学院生になら解いてもらえるだろうか.まあ,この程度の意思決定問題に何らかの形で解答を与えられないようなら,およそ現実の重要な意思決定問題は解けそうにない.

この「セブン-イレブン ポケモンスタンプラリー2010」は8月15日まで実施されているので,8月上旬に見込みのある解答を提出してもらえれば,私が自分の身体を張って,評価値を測定します.最大3ケースくらいなら何とか...優勝者にはポケモンスタンプラリーでもらえるポケモンポスターをプレゼント!