はじめに
NearMeの相乗りサービスの特徴として、事前予約の注文が入るたびに相乗りの最適化を行っているという点があげられます。 これは、特定の時間で締め切りして一気に相乗りを決めるという素朴な方法に比べると、 相乗り状況が事前に把握できることで配車手配しやすくなったり、直前まで最適化できたりするといったメリットがあります（参考１、参考２）。
一方で、最適化の観点では、注文のたびに最適化しようとすると計算リソースが限られてしまうので、妥協した解に留まる可能性あります。 特に、現実装では計算量を減らすため、入ってきた注文に対して時間的・空間的に近しい注文同士で再計算していますが、 その場合、部分部分、瞬間瞬間で最適化できても、刻々と注文が入ってくる中で、その部分的な解が"陳腐化"していきます。
全体の注文数が限られている状況ではそれでも満足な解は得られていたのですが、注文数が増えるにつれて、こう組み合わせるともっといいのではというパタンが少しずつ現れてきます。
そこで、陳腐化していく解に対して、巨大近傍探索(Large Neighborhood Search / LNS)(参考文献：Pisinger 2010)と呼ばれる手法を用いて解を再構築するようにしました。 名前は難しそうですが、手法自体は比較的単純です。社内ではその動作イメージから通称、ガラポン(ガラガラポン)と呼んでいます(笑)。
この再構築の処理を定期的に実行することで、よりよい解が得られるようになります。 ここでは、巨大近傍探索について説明すると共に、相乗りサービスへの適用および、そのシステム概要について述べていきます。
巨大近傍探索について
※このセクションは、ほとんどChatGPTによる説明です。
巨大近傍探索は、最適化問題を解くためのヒューリスティック手法の一つです。特に、組合せ最適化問題（例: 車両ルーティング問題やスケジューリング問題）において、解を効率的に改善するために使用されます。
巨大近傍探索の基本的なアイデアは以下の通りです：
基本的な流れ
- 初期解の構築: 問題の解をまず1つ生成します。これは何らかの簡易的なヒューリスティック手法（例: グリーディアルゴリズム）を使用することが一般的です。
- 部分解の破壊 (Destroy): 解の一部を「壊す」操作を行い、一部の構成要素（ルート、スケジュールなど）を取り除きます。
- 修復 (Repair): 壊した部分を再構築して、新しい解を生成します。この修復ステップでは、元の制約を満たすように工夫されます。
- 評価と更新: 新しい解を元の解と比較し、採用するかどうかを決定します。通常、メタヒューリスティック（例: 焼きなまし法や禁忌探索）のルールを用います。
- 繰り返し: これを繰り返すことで、解を徐々に改善します。
特徴
局所探索を拡張した手法で、探索空間の「大きな」部分を再評価することから名前が付けられています。 局所最適解からの脱出が可能で、より良いグローバル解を見つける可能性を高めます。 壊す・修復するステップで柔軟性が高いため、さまざまな問題に適用可能です。
- メリット
計算コストを抑えながら、質の良い解を探索可能。 メタヒューリスティック手法（例: 焼きなまし法）と組み合わせることで、より高い性能を発揮。
- デメリット
破壊・修復の設計が問題依存であり、適切に設計しないと効果が出ない。 最適性保証はない（近似解しか得られない場合が多い）。
巨大近傍探索は特に複雑な制約のある問題や大規模な問題で有用で、柔軟性の高さと効果的な探索性能が評価されています。
※ 経路最適化問題でよく用いられる2-opt近傍操作も解の一部を壊して再構築するという点ではアイデアを共有しています。2-optは単純で固定的な破壊/修復手法を用いた、狭い探索空間での解法。特に巡回順序最適化に特化しています。一方で、巨大近傍探索は柔軟で大規模な破壊/修復手法を用いて、広い探索空間で解を改善します。多様な問題に適応でき、局所最適から脱出する能力が高いです。巨大近傍探索は2-opt を含むより一般的なフレームワークと考えることもできます。
相乗りサービスへの適用
さて、巨大近傍探索を我々の相乗りサービスに適用するのは比較的簡単です。 なぜなら既に、注文が入った時、また、注文を取り除くとき(キャンセルされたとき)に、 時間的・空間的に近しい注文同士で再計算して部分的な解を生成する実装は済んでいるからです。 そうなると、注文をいくつか取り除いて、その後、それらを再度入力していけばいいだけです。 そして、各試行において、再構築された解が元の解よりも評価関数として上回れば解を上書きするというロジックを加えれば基本的には完成です。
※ 制約条件のせいで与えられた車両で解が得られなかったら、車両を増やすというアプローチで必ず制約条件を満たす部分的な解を得ています。
以下は、その方法により再構築された部分的な解の例です。
ここで、左の黒い３つのルートは元の解で、右の赤い２つのルートが再構築された解です。 それぞれのルートはいくつかの経由地を経て、目的地の空港に着きます。 左右とも経由地は同じですが、ルートの数が再構築によって減っているのが分かります。 また、元の解の２つの近いルート同士の経由地の再配置だと、このような再構築は起こらず、 全部の経由地の再配置によってこのような再構築が起こることも見てとれます。
なお実際には、どの注文同士が再配置できるかも時間と共に変わっていきます。 例えば、ある運行会社が受注した注文した時は、その注文はその運行会社内で注文した同士でのみ再配置可能とするなど。 そのようなダイナミックな運用上の制約も考慮して実装しています。
また、日単位でサービス毎に巨大近傍探索のを適用しているのですが、 注文数が少なかったり、前回の適用から時間が経ってなかったり、配車直前で再配置が許されない場合などは適用は不要です。 そのような適用条件も考慮して実装しています。
システム概要
全体のシステムは、注文が入るたびに相乗りの最適化するリアルタイムなプロセスと、巨大近傍探索を定期的に行うバッチプロセスから成り立っています。
リアルタイムなプロセスはさらに、純粋に最適化を行うRoutingサービスと、状態を管理して全体のフローをコントロールするRideサービスからなります。
バッチプロセスは、巨大近傍探索を司るLNSジョブと同じくRoutingサービスからなります。 何回も再構築を試行するため、Routingサービスはリアルタイムのそれとは別系統で動かしています。 解を更新するときは、Rideサービスに、組み合わせの再配置をリクエストします。
Rideサービスにおける組み合わせの再配置では、 リクエスト元のJobがバグで変な値を返すことも想定して、幾重にもバリデーションを設けています。 データの整合性は保っているか、制約条件を守っているか、基本的な指標で解は改善されてるかなど。 こうすることで、今後さらにLNSジョブの改修が進んでも安全に運用できるようになります。
おわりに
巨大近傍探索は、シンプルですが強力で、幅広く複雑な課題にも適用できる汎用性の高い手法です。 特に、刻々と環境が変化して、解が陳腐化していく中でも効果的に適用できるので、我々の相乗りサービスの実装と相性がいいです。 実際この手法を用いて着実に解が改善されました。今後、機械学習の要素なども取り入れてさらに改善していけると期待しています。
最後になりますが、NearMeではエンジニアを募集しています！まだまだ多くの可能性が潜んでいる領域です。興味を持った方はぜひ以下から応募いただければと思います。
Author: Kenji Hosoda
