MIPソルバーで求める”最適な”海外旅行計画 ~NY旅行の実例~
おことわり
これは真面目に書いた記事ですが、文献調査はあまりしてませんし数理最適化にも詳しくないので、内容の正確性は保証できません。ただ、タイトルのことをやってみたという記事です。なお、非常に初歩的な内容ですので特にコード等は含みません。
はじめに
最適な海外旅行計画を立てることは、多くのホモサピエンスにとっては困難であることが知られています。往復の航空便・宿泊先のホテル・訪問する場所などの旅行で決めるべき要素は数多く互いに依存しているため、ホモサピエンスが使える単純な手法では良い旅行計画が得られる保証はありません。なので、大体の場合はどこかで妥協せざるを得ないという悲しい状況があります。
そこで苦労せずとも良い旅行をするために、ヒューリスティクスを用いない解法を考えます（わざわざ旅行のためだけに解法は考えたくない）。ナイーブな発想では日帰り旅行では単にTSPTW（時間制約つき巡回セールスマン問題）として解けそうです。これをN泊に拡張し訪問先候補の選好と営業時間を導入して、海外旅行計画を求めてみて、実際に旅行に行きます。なお、N泊への拡張方法は、ポテンシャルをホテル出発時にリセットすることで実現しています。
問題設定
海外旅行計画は、次の手順で計画されるとします：
- 旅行先（空港）の決定
- 滞在先ホテルの決定
- 訪問場所と訪問時刻の決定（狭義の旅行計画）
ここでMIPソルバーを用いる問題は、3の狭義の旅行計画です。仮に、2について、複数ホテルのうちどれが最も効率的に観光先を回れるかといった検討を行いたい場合は、それぞれのホテルについて、3を行ってその結果を比較することでおこないます。
また情報収集の方法としては、1,2はExpediaなどの比較サイト、3はInstagramなどのSNSやまとめサイトを想定しています。さらに3については、訪問先候補の選好度・営業時間・最小/最大滞在時間も適当に設定します。
解き方
単にMIPソルバーを叩くだけです。ただし、そのままでは非現実な解をはき出すので旅行者のフィードバックを何度か得てモデルを改良する必要があります。フィードバックの実例としては、一日に軽食が偏ってる/到着日の夜までバックパックを持ち歩きたくないから一度夕方にホテルに寄りたいなどです。これらをいい感じに定式化し、問題を繰り返し解き直す必要があります。
このフィードバックサイクルを10-20回ほどやらないと、単に最適化問題として解いた旅行計画は使いものになりませんでした。そのため往路の機内にラップトップを持ち込み、同行者と話し合いながら何度も計算を回すことをおすすめします。最終的にみんなが納得できればOKです。ただし、事前予約が必要なものについては予めある程度ちゃんと解いて予約しておきましょう。
移動方法はtransit（公共交通）かdrive（自動車）です。これらの移動時間はgoogle maps apiから取得します。またdriveはuberかlyftを使うことになります。これらはpickupまで時間がかかることがありますので、余裕を持って10-15分くらい時間時間を多めに見積もります。
具体的な制約の定式化については、特に触れませんが，いい感じの連立方程式/不等式を立てればだいたいOKです。目的関数は、選好や門限ペナルティなどいろいろ適当にフィードバックを反映しつつ設定しています（解法を考えない代わりに目的関数を頑張って考える）。
NY旅行の実例
去年と今年の2度、私的な旅行で上記の手法を実際に用いましたのでそれらについて記します。旅行先はロサンゼルス（LAX）とニューヨーク（JFK）で、どちらも3泊4日のスケジュールです（出発地は日本ではないため、3泊6日ではない）。
ここでは、後者の旅行計画を簡単に紹介します。なお実現可能性を疑うホモサピエンスも多いと思いますが、筆者と同行者が実際にこの計画の下で、大きな遅延なくすべての場所をちゃんと回って来ました。また、下記の旅行計画は我々の訪問先の候補と選好を組み込んだモデル内での最適解です。真の意味での最適解である保証はありませんのでご注意ください。ちなみに、この実例での問題規模は、変数・制約ともに数千程度です。
Day 1
13:03 に JFK Terminal 4 (A) を出発 13:43 に Supermoon Bakehouse (1) に到着 14:13 に Supermoon Bakehouse (1) を出発 14:25 に Popbar (2) に到着 14:53 に Popbar (2) を出発 15:04 に チェルシー・マーケット (3) に到着 16:04 に チェルシー・マーケット (3) を出発 16:05 に ザ・ハイ・ライン (4) に到着 17:05 に ザ・ハイ・ライン (4) を出発 17:27 に ホテル (5) に到着 17:57 に ホテル (5) を出発 18:07 に タイムズスクエア (6) に到着 18:37 に タイムズスクエア (6) を出発 18:40 に マジェスティック劇場 (7) に到着 22:25 に マジェスティック劇場 (7) を出発 22:40 に ホテル (H) に到着
Day 2
9:03 に ホテル (H) を出発 9:21 に バッテリー・パーク (9) に到着 12:21 に バッテリー・パーク (9) を出発 12:29 に ブルックリン橋 (10) に到着 13:37 に ブルックリン橋 (10) を出発 13:43 に OddFellows Ice Cream Co. DUMBO (11) に到着 14:13 に OddFellows Ice Cream Co. DUMBO (11) を出発 14:28 に Morgenstern's Finest Ice Cream (12) に到着 14:48 に Morgenstern's Finest Ice Cream (12) を出発 15:00 に World Trade Center (13) に到着 17:00 に World Trade Center (13) を出発 17:11 に LROOM CAFE (14) に到着 17:41 に LROOM CAFE (14) を出発 17:51 に シェイク シャック (15) に到着 19:31 に シェイク シャック (15) を出発 19:43 に ホテル (H) に到着
Day 3
9:00 に ホテル (H) を出発 9:04 に エッサ ベーグル (17) に到着 9:35 に エッサ ベーグル (17) を出発 9:44に 5th Ave (18) に到着 13:31 に 5th Ave (18) を出発 13:44 に アメリカ自然史博物館 (19) に到着 15:59 に アメリカ自然史博物館 (19) を出発 16:02 に セントラル・パーク (20) に到着 17:06 に セントラル・パーク (20) を出発 17:19 に Cha Cha Matcha (21) に到着 17:34 に Cha Cha Matcha (21) を出発 17:40 に エンパイア・ステート・ビル (22) に到着 19:40 に エンパイア・ステート・ビル (22) を出発 19:52 に ホテル (H) に到着
Day 4
9:03 に ホテル (H) を出発 9:18 に Sarabeth's (24) に到着 10:40 に Sarabeth's (24) を出発 10:48 に ニューヨーク近代美術館 (25) に到着 13:03 に ニューヨーク近代美術館 (25) を出発 13:40 に JFK Terminal 4 (A) に到着
機内で1時間みっちりとフィードバックと解き直しを繰り返したので、（この計画をみても分からないと良し悪しが思いますが）個人的には完璧な計画が出来上がりました。しかしながら、この計画通りに旅行すると、濃すぎて疲れ、ホテルですぐに爆睡してしまいました。まあ、これが最適ということなのでしょう。本当に濃い旅行でした。
おわりに
MIPソルバーという、組合せ問題でのチートツールを用いることで満足度の高い旅行ができました。これならアウストラロピテクスでもできそうですので、誰にでもおすすめできます。
また、このような旅行に付き合ってくれた同行者には、深く感謝します。
