こんにちは。てぃろです。
2021年度のArumonの活動の一つとしてRoutingを計算することができる乗り合いバスの予約システムを開発しました。バスの予約アルゴリズムにはGoogleがOSSとして提供しているOR toolsを活用しました。
本記事では、OR toolsを使うにあたってのポイントを解説していきます。
特に以下のようなことを考えている方にとって役に立つ記事になっていると思います
- OR toolsでどんなことができるか知りたい
- OR toolsを使って経路最適化問題を解きたいけど、どう取り組めばいいかわからない
- 乗り合いバスの予約システムとして使うときの設計ポイントが知りたい
なお、少し記事が長くなるので記事を前編の要件定義編と後半の実装編に分けています。本記事は前編の要件定義編です。
後編の実装編はこちらです。
実装したソースコードについては現時点ではまだ公開できませんので、いまのところは文章だけの解説になります。あらかじめご了承ください。
OR toolsは、Googleが提供する最適化計算問題を解けるOSS
OR toolsのORは、Operations Research（オペレーションズリサーチ）の略で、ある最適化問題に対して解析的に解を導き出そうとする手法全般のことを言います。
要するに、ある問題に対して計算でうまい方法を探す、という手法です。
↑のページに行くと、でかでかと”Google AI”と書いてあったりするので混乱する人がいるかもしれませんが、OR toolsはAI（機械学習）ではありません。あくまでも解析的に解を導出するのであって学習をして賢くなっていくことはありません。
また、すべての問題に対して汎用的に解を導出できる手法や関数が一つ存在するのではなく、問題に応じて様々なアルゴリズムがあり、それらの中から自分の解きたい問題に対して最適なアルゴリズムを選択します。
では、どのようにして最適なアルゴリズムを選べばよいのでしょうか？
そのためには解きたい問題の設定と制約条件を整理することです。これが済めば自然に何を使うべきかが決まります。
まず、ここで扱う問題について考えます。
今回扱う問題は乗り合いバスが予約時間通りに走るルートを見つけるというものです。つまり、車両が走るルートを計算したい = 経路最適化問題を解きたい、ということになります。
OR toolsではRoutingというまとまりで経路最適化問題に対するアルゴリズムの実装が提供されています。
Routingには考えうる経路計算上の制約条件に合わせて、たくさんのアルゴリズムやパラメータが実装されていますので、その中から最適と思われるアルゴリズムやパラメータを選択します。
そのためにも、まずは今回の乗り合いバスの予約システムがどのような要件かを整理してみましょう。
乗り合いバスの予約システムの要件
乗り合いバスとは、乗客の予約に応じて運行されるバスであり、最初に乗った人が目的地に送られる前に、別の人を乗せるために多少遠回りするようなことがある、というバスです。
予約は先にリクエストされたものを優先し、あとからリクエストされた予約についてはバスの運行状況から見て受付可能である場合にのみ受け付けるという流れとします。
この予約のプロセスをアルゴリズムっぽく書くと、以下のように書けます。
- Aさんが目的地Xへの予約をリクエストする
- 既存の予約がないので、予約を無条件に受け付ける
- Bさんが目的地Yへの予約をリクエストする
- Aさんの予約内容と合わせて、Bさんの希望通り目的地Yへ到達可能であるか確認する
- 到達可能な経路がある場合、予約を受け入れ
- 到達可能な経路がない場合、予約を拒否
つまり、ステップ４がバスの運行ルートの計算が必要になるステップであり、新規予約が入るたびに既存の予約と合わせて毎回新たなルートを計算することが必要になるのです。
これが乗り合いバス運行において解かなければならない経路最適化問題です。
さらに詳細に乗り合いバスの運用シーンも考慮してみると、経路計算に関わりそうな要件として以下の４点を洗い出すことができます。
- 停車地の到着時刻は前後数分の誤差を許容する
- バスには、乗車人数の上限がある
- 停車地では、一定の待機時間がある
- 出発地点と最終地点は乗客の乗降はなく運行ルートの考慮に入れない
１点目は、予約時間きっかりにお迎えをしないことを意味します。乗り合いバスという性質上、直前で運行ルートが変更されて、到着時刻がブレる可能性があるからです。
２点目は、バスであれば当然ですね。乗れる人数には限りがあります。
３点目は、実際の運行のシーンを思い浮かべればわかりますが、バスは乗客を乗せる/降ろすために停車しますので、その分時間がかかります。つまり、実際には走行時間とは別にこの停車時間が存在しており、これを含めて考えることでより正確な運行ルートの計算が可能となります。
４点目は、今回のプロジェクトの特性とも言えますが、予約がないときにはバスは事務所に帰ることとなっています。また予約受付は３０分前までであり、各停車地は３０分以内には間違いなく行ける距離にあります。つまり、事務所にいる限り経路計算上の制約となるようなことにはなりません。
実はこの中でも1点目の制約条件から選択すべきアルゴリズムはVRPTWを選択することができます。それ以外の２～４点目については、アルゴリズム中のパラメータとして設定することで考慮可能です。
では、次になぜVRPTWを選択することができるのか、その理由も合わせて解説していきます。
VRPTW（Vehicle Routing Problem with Time Windows）
意訳すると、時間幅制約付き経路探索問題、となると思います。つまり、時間の制約を追加した経路計算のアルゴリズムです。要するに、各目的地に到達しなければならない時間帯が設定されているので、その時間通りに進むことができる経路を計算で発見しようというアルゴリズムです。
少し図で説明します。上図は出発地を図中央の０としてすべての点を指定された時間通りに巡回するための制約条件を示しています。各点に[5, 10]のような数字が書かれています。これが時間制約です。[5, 10]の意味は、出発時点の時間を0とし5～10の間にその点に到達していることという制約です。
VRPTWは、このように示された時間制約をもとに、最適な経路を計算するアルゴリズムなのです。
ここで制約になっている時間帯がそのまま今回の乗り合いバスの１点目の要件である到着時間の前後数分の誤差を許容すると同義であると言えます。
例えば、9:00到着が予約時刻であり、前後5分を許容誤差とします。そうすれば、[8:55, 9:05]という制約条件を定義することが可能です。
数字の入れ方は厳密には違いますが、実装でもこのようにして実際の予約に対して制約条件としての時間帯を計算して利用しています。
ちなみに上記で示す時間には単位はありません。逆に言えば、ユーザが自身で定義しておく必要があります。今回の場合はバスの運行ですので、時間の単位は”分”として計算しています。
またVRPTWは時間制約であることに注意が必要です。OR toolsのドキュメントをよく見るとVRPTW以外のアルゴリズムは距離制約を使っています。
コードの中でも見て取れますが、もとになっているVehicle Routing Problemなどで使われているのはdistance_matrixです。VRPTWで使うのはtime_matrixです。
まとめ
ここまででVRPTWが今回の乗り合いバスの運行要件にぴったり合うアルゴリズムであることがわかりました。
こういった最適化計算では、最適なアルゴリズムを選ぶことが最も重要であり、これでやりたいことの半分は終わったと言っても過言ではありません。逆に言えば、このアルゴリズム選定を間違えると、問題を解くことはできないということです。
また、ここまで見てきたとおり最適なアルゴリズムを選ぶためには、解きたい問題と制約条件をきちんと整理することが最重要です。
アルゴリズムを選ぶ際には整理した制約条件とアルゴリズムが合うかどうかを字面で判断せず、その本質的な意味を捉えて言い換えができることも重要です。今回で言えば、アルゴリズム上はTime Window（時間幅や時間帯）という言い方ですが、制約条件では前後数分の誤差を許容というように言い方が異なります。実際の現場ではもっといろいろな言い方をしていることもあり、本質理解の重要さが際立ちます。
もし、今回ご紹介したようなアルゴリズム選定に悩んでいる方は、まず一度自分が解きたい問題の本質を理解しているか確認してみるのもよいかもしれませんね。
では次に、ここまで定義した要件をもとにVRPTWを具体的にどのように実装するのかを解説していきます。
それを解説した後編：実装編はこちらです。是非続けてご覧ください。
