こんにちは。てぃろです。
今回は後編の実装編です。前編はコチラから読んでみてください。本記事の内容を実施するまでに考えた要件定義について記載していますので、一読することをおすすめします。
ここからは前編で整理した要件や制約に従って、どのようにOR toolsの設計をしていったのか？を書いていきます。
VRPTWの具体的な使い方
データの作り方の工夫も含まれていますが、それも含めてVRPTW（Vehicle Routing Problem with Time Windows）を要件に合わせて使うために実施したことを解説していきます。
以下が実施した内容の一覧です。
- 移動時間を距離と走行速度から計算する
- バス停での停車時間を計算に入れる
- 出発地と帰還地は考慮しない
- バスの乗車人数を考慮に入れる
- リアルタイム計算とするための計算最大時間の設定
- 予約が多くなった時のための工夫
では、順番に見ていきます。
移動時間を距離と走行速度から計算する
前編でも説明しましたが、今回使用するVRPTWは時間を使って経路計算をします。そのため、地点間の移動時間を求める必要があります。
移動時間の計算には距離と走行速度が必要になります。それぞれどのように求めればよいのか見ていきます。
距離の求め方
各地点の緯度経度は明らかになっているものとします。その場合には各地点の緯度経度から距離を計算することが可能です。
以下にそのまま使用できるサンプルが紹介されています。今回はこれをそのまま活用しました。
走行速度の求め方
上記のように緯度経度を使って地点間距離というのは、本来バスが走る道路を無視して地点間を直線移動したことを意味します。
つまり、本来は走るはずのない最短距離を走る走行速度である、ということを前提とすると、本来の走行速度よりも少し遅めの速度を設定しないと現実的にはありえないスピードで走行していることになってしまいます。
今回は大きなマス目で畑が配置された農村地域の道を通常50km/h程度で走ることを想定していたので少し遅くして35km/hを設定値としました。
これで距離と走行速度が求められましたので、地点間の移動時間を計算することができるようになりました。
ただし、先にも述べた通りここで設定した走行速度は特に論理立てて計算した速度ではないため必ず確からしい設定であることを検証することをオススメします。特に、車両の走行という特性を考慮すると、土地の地形や道路状況によって走行速度は一定ではありませんので、実際に走行して移動時間や走行速度を測定してみるのがよいでしょう。
ちなみに、今回私も実際の現場を車で走行してその確からしさを確認しています。
バス停での停車時間を計算に入れる
バスはバス停に到着すると停車し乗客が乗降します。現実的にはこのとき停車時間が数分発生します。
厳密な経路計算を行うためには、このような数分の停車時間も考慮に入れる必要がありますが、停車時間というものはOR tools上の設定値が存在するわけではありませんので、どのように移動時間を計算に含めるか考えなければなりません。
そもそものOR toolsの計算に使用されるパラメータをよく見ると、移動時間の計算において本当に走行しているか停車しているかは考慮していません。つまり、移動時間の中に停車時間が含まれていてもよいわけです。
そのため、上記で求めた地点間の移動時間に一律停車時間を加算することで一定の停車時間を表現することが可能と思われます。
出発地と帰還地は考慮しない
今回の要件では、予約を30分前までで受け付けておりバス待機場所から最も遠いバス停でも30分はかからないなど、計算上出発地を考える必要がありませんでした。また、バスは最後の人を降ろしたあとにバス待機場所（帰還地）に戻る必要もありません。
このように、出発地と帰還地への移動を考慮する必要がないときの設定としてdepotの設定を活用します。詳しくは以下を参照ください。
depotはもともと物流拠点という意味の英単語で、今回のような最適経路計算では出発・帰還地点として使われます。
定義上は出発地から出発しているのでdepot = 0と設定します。
また、経路計算時に毎回計算するのは冗長なので、depotはいつでも行ける場所として定義しておくと楽です。これは到達時刻の制約は営業時間帯を含むように、depotに対するtime_windowsの設定を[0, max]とすることで定義可能です。
※ max = 営業時間（営業時間が8時間（480分）なら[0, 480]とする）
バスの乗車人数を考慮に入れる
バスは物理的に人が乗れる人数が決まっていますので、乗車人数の制約は必須です。
乗車人数といえば最大乗車人数ですが、これはCapacity Constraintsで表現できます。
設定は以下のようになります。これは上記の公式ドキュメントからの抜粋です。
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities （ここが最大乗車人数の設定値）
True, # start cumul to zero
'Capacity')乗車人数の制約はこれだけではありません。
バスでは乗車すると１人増えますがどこかで降ろすと１人減ります。つまり乗車されるときに最大乗車人数を超えていなければ、延べで言えば最大乗車人数以上を乗せることは可能なはずです。
つまり、最大乗車人数だけの制約では足りず、乗降による乗車人数の変化も制約に入れる必要があるのです。
これには以下のようにdemandsという入力値の一つを追加することで表現可能です。
data['demands'] = [1, -1, 1, -1, 1, -1, 1, -1, 1, -1]上記では、乗車は+1、降車は-1として表現しています。このようにすれば各地で乗車と降車を制約として表現できます。
ただし、これは今回バスの予約は必ず1人でされるという前提によります。1か所あたりの乗車と降車の人数が異なればその通りに数値を変えるなどのカスタマイズをしてください。
リアルタイム計算とするために予約が多くなった時のための工夫
予約が多くなるとは、計算に含める地点が多くなることを意味します。これは最適化問題を解くための計算時間が増大してしまうことを意味します。
予約はリアルタイムで行いたいので、10秒以内くらいにはレスポンスしたいものです。
今回、OR toolsの実行基盤としてGCPの Cloud Run（vCPU 2コア）を使っていましたが、予約件数が９件になったときに30秒以上経過しても計算が終わりませんでした。毎回最適な経路を計算したいために、1日の予約全てを最適化計算に入れていたので9件以上で計算するケースがあるところからテストした結果でした。
そこで、もう一度要件を見直しました。
今回の要件では、予約間の時間が30分開いていることに着目すると、多少の予約時間のズレはバスの走行状況によっては誤差の中で吸収できそうだと考えました。そこで、予約の最適化計算を新規予約の時間に対し前後1時間以内の予約内容との間でのみ経路計算することにしました。
今回経路計算したい理由は新規予約が既存の予約の経路に組み込めるかどうかだけなので、1時間以上離れてしまえば関係ないのです。関係あるのは新規予約の前後の予約のみですから。
このようにすることで、経路計算の対象とする予約情報の件数を絞ることができ、リアルタイムな予約が可能となりました。
まとめ
今回は後編の実装編ということで、実装に当たっての工夫を解説していきました。
まだコードが公開できないので、文字の解説ばかりでわかりにくかったかもしれません。
ですが、本記事ではまずOR toolsはそのままパッと使えるものではなく、きちんと要件の整理をすることが大事であること、OR toolsには様々な制約を表現する方法があり、その工夫次第で様々な最適化計算に適用可能であることを知っていただきたかったのです。
今回は乗り合いバスということで実装しましたが、本来想定されているのは積み荷を扱う大型トラックの物流経路の計算などだと思います。
そういう意味でも、定義の仕方でいろんな使い方できるということもご理解いただけたことと思います。
後日コードが公開できるようになりましたら、コードも交えた解説記事も公開したいと思います。
まだご覧になっていない方は、前編：要件定義編もぜひご覧ください。
