巡回経路探索の品質改善戦略 配達遅延の削減とルート最適化の実現
こんにちは、${NAME}です。
ナビタイムジャパンで経路探索エンジンの開発を担当しています。
はじめに
この記事では、ナビタイムジャパンにおける 巡回経路探索の品質改善 についてご紹介します。特に、 ユーザーが指定した希望配達時間帯に間に合う経路を提供 できるようにするための品質向上の取り組みについてまとめました。
ナビタイムジャパンの経路探索について
ナビタイムジャパンの経路探索では、出発地から目的地までの最適な経路を、時間、距離、コスト、煩雑さなどを考慮したコストモデルを基に決定しています。このコストモデルを活用し、最適なルートを算出することを可能にしています。
巡回経路探索について
巡回経路探索 とは、複数の訪問先を効率よく回るために、最適な順序を決定する探索手法です。特に、物流や配送業務など、多数の地点を巡回する際に非常に有効な手法とされています。
ナビタイムジャパンの巡回経路探索は基本的に以下の流れで行われています。
地点の組み合わせの数だけ経路探索をしてコストモデルを構築
1. のコストモデルを利用して、訪問先を巡回する最適な経路順の決定
2.の最適な経路順の決定には、メタヒューリスティックな解法 を用いています。この手法では、初期解から改善を繰り返し、より良い解を目指します。計算にかかる時間が長ければ長いほど、より良い解が得られる可能性が高くなります。
ナビタイムジャパンが巡回経路探索を行うことの強みは、最適な経路順の決定にナビタイムジャパン独自のコストモデルを適用することができる点にあります。
巡回経路探索の品質とは？
通常の経路探索では、以下のような点が経路の品質に関わってきます。
安全かつ快適に通れる経路である
所要時間や距離がかかりすぎない（不自然に迂回しすぎていないかどうか）
物流サービスで求められる巡回経路探索の品質には、これらに加えてもう1つ重要な要素があります。それは、配送元が指定した希望配達時間帯内に間に合うような探索結果が得られているかどうかです。
希望配達時間帯に合わせた最適な経路を算出することは、配送元の信頼性を高めるとともに、配送先の方の期待に応えるためにも非常に重要です。
今回私が行った品質改善は、この「希望配達時間帯内に間に合うか」を最優先にして、探索結果を改善することに焦点を当てました。
今回取り入れた施策
配送する地点数が数十地点と多くなると、配送元が指定した希望配達時間帯に間に合わない結果が多く見受けられることがわかりました。
さらに、同じ地点で同じ希望配達時間帯が設定された経由地が2つ以上存在する場合、1度訪問すれば配達が完了するにもかかわらず、その地点に2度以上訪問されるという問題も明らかになりました。
下図は、経由地が100地点ある巡回経路探索結果の一部です。緑色のピンが示す地点に、同じ地点で同じ希望配達時間帯の経由地が重なって表示されており、この地点が2度訪問されていることが確認できます。
そこで今回私はその問題を解消するために、巡回経路探索の品質改善を行いました。
具体的に行った改善は、巡回経路探索の中で最適な経路順を決定する計算を行う際の最適化時間を延長させる機能を開発することでした。最適化時間を延ばすことで、経路順を計算するためにより多くの時間を確保できるため、経路の品質が向上し、より精度の高い結果が得られるようになります。
今回私が対応した機能は、『NAVITIME API』 の「多地点巡回ルート検索」の機能としてリリースされました。
この機能を開発するにあたって、最適化時間をどれだけ延ばすかの落としどころを決めていく必要があります。
なぜかというと、インフラコストを考慮すると、最適化にかける時間は過度に延ばさないようにしたい一方で、品質改善の効果が明確に現れるようにするためには、最適化にある程度の時間をかける必要があるからです。
最適化時間を決定するに至った過程の一部をご紹介します。
巡回経路探索の最適化時間延長過程
上記の最適化時間を決定するために、多地点の巡回経路探索で最適化時間が A, B, C, D, E（A < B < C < D < E）だった場合に、希望配達時間帯と到着時間の差がそれぞれどれぐらい改善したかを調査しました。その結果が以下の図になります。
この図から読み取れるように、最適化時間が大きくなっていくにつれて徐々に改善割合の変化量が小さくなっていることが分かります。このことから、最適化時間を延ばしすぎることなく、かつ大きな改善が期待できる値にすることができそうだと分かります。この施策では、最適化時間をCに決定しました。
最適化時間をCにすることで、この章の冒頭で説明した100地点ある経路例で、同じ地点かつ同じ希望配達時間帯の経由地が2つ以上設定されている場合に、その地点に2度以上訪問される探索結果が出てしまうという問題が解消されました。
さらに、この経路例で希望配達時間帯と到着時間の差が2日+14時間あったものが0時間になり、経路品質が大幅に改善されました。
まとめ
上記のような開発・検討を経て、今回の巡回経路探索の品質改善の施策をお客様の手に届く形にすることができました。
今後もユーザーからのフィードバックを元により良い経路品質を究め、提供していきたいと思います。
最後に
この記事では、「巡回経路品質改善」についてご紹介いたしました。
最後に、本記事が、ナビタイムジャパンのコア技術である経路探索エンジンについて理解を深める一助となれば幸いです。引き続き、最適な経路探索を提供できるよう努力してまいります。
最後までお読みいただきありがとうございました。