配送業務を効率化する「ルート最適化サービス」の仕組みとは？自社アルゴリズムの秘密を紹介！

こんにちは、広報担当の小森です。

オプティマインドのエンジニアはどんな開発をしているの？どんな技術を使っているの？という疑問にお答えすべく、4回に分けてエンジニアの開発秘話を連載形式でご紹介しています。

第3回は、ルート最適化の根幹を担うアルゴリズム開発エンジニアの郭岩松（Guo Yansong）さんです！

オプティマインドに入社しようと思った理由を教えてください。

私は名古屋大学の素粒子宇宙物理専攻に所属しており、ブラックホール周りの分子雲を流体として取り扱い、スパコン上で流体シミュレーションを行う研究をしています。研究室で今まで多数の研究成果を出してきましたが、こういった研究成果を人々の生活に応用できないか、サイエンスでのイノベーションを普段の生活でも実感できないかという疑問を抱いていました。そんな中、同じ名古屋大学に所属していた弊社のCEO松下、COO斉東に出会い、「新しい世界を、技術で創る」というオプティマインドのビジョンに共感し、入社を決意しました。

現在はどんな業務を担当していますか？

Loogiaに入力された訪問先間の所要時間や経路を探索するエンジンの開発をしています。ルートの最適化を行うためには、全ての訪問先の出発・到着の向きを考慮した2点間経路コストを計算しなければいけません。例えば、A, B, Cという3つ訪問先が入力されると，A→B、B→C、B→A、C→B、A→C、C→Aの6つの最短経路を計算します。次に、各訪問先の出発・到着の向きを考えます。下の図を例にとると、訪問先SとTそれぞれの出発・到着可能な方向は4パターンあります。道路特性（三叉路・十字路）によって計算するパターンの数が変わります。

そのため、先の6ルートに対して、向きの組み合わせを掛け合わせた、24パターンの2点間経路コストを計算しなくてはなりません。式でまとめると、条件にもよりますが、 約4*N(N-1)になります。Nは訪問先数であり、もし仮にお客様が訪問先を30件入力したとすると、約3500パターンの計算をする必要があります。 ここで重要なのは、計算量がO(4*N^2)という膨大な数になってしまう最短経路の行列の計算を、「アルゴリズム」と「インフラ」の観点からいかに高速化し、低コストかつ正確に解くかという課題です。さらには、最適化計算によって出された一番効率のいい訪問先の組み合わせ・順番に対し、ドライバーさんにとって最適な経路提案を可能にできるかが重要で、こういった議題と日々格闘しています。

非常に複雑な業務ですね！開発にはどんな技術を使っていますか？

2点間経路探索の計算と最適化エンジンに投げるための距離行列（全訪問先における全組み合わせの所要時間を1つの行列としてまとめたもの）の大規模計算を開発しています。

距離行列の計算では、計算量が膨大なため数十分以上かかってしまう反面、経路探索は秒単位で計算できます。つまり、２種類の計算タイムスケールが混ざっているHeterogeneousのサービスになり、インフラのデザインにとっては非常に厳しい条件になっています。

距離行列の計算の速さと実際に表示させるルートの質は、グラフ構造、探索アルゴリズム、インフラという3つの柱で支えています。

データの前処理としては、道路ネットワークをNodeとEdgeに分類し、グラフを構築します。このグラフのデザインは、柔軟なものにすればするほど、経路探索を行う際に考慮できる要素が多くなるため、ルートの質が高くなります。しかし、探索速度が遅くなってしまい、メモリ・CPUの使用量が増えてしまいます。そのため、 従来のMonolithic的なデザインでは、大容量のメモリを使い、速いCPUを使うほど、同じ質のルートを出すのに必要な時間が短くなります。一方で、現在では、どんどんCloud Nativeの時代に移り変わっており、先のメモリ容量やCPUの速さがボトルネックになっている時代から、ネットワークのスループットがサービスのレスポンスの決め手になります。Monolithic的なデザインからサービスメッシュ化することによって、スペックが低いMachineを数多く組み合わせた方がはるかにスループットが増え、UXの改善にも寄与できると考えています。さらに、個々のモジュールを分離させることができ、モジュールごとのLogicが相対的に簡素化され、多数の開発者が自分のスキルによって好きなモジュールを選んで速やかに開発でき、開発者に非常に優しい開発環境が出来上がります。

ここまでで、「サービスメッシュ化することによって大量なモジュールが発生するため、Production環境に持っていくまでの期間が長くなってしまうのでは？」と疑問に思われるかもしれないですが、弊社においてはGitOpsとDevOpsから生み出した知恵や、CI/CD・GKEなどの技術を活かしたインフラ構築を目指しました。アルゴリズムの開発者でもGitさえ使えば簡単にDeployでき、開発者は簡単に自分のモジュールを試しにデプロイできるような環境も整いつつあります。自分の成果をすぐ見ることができるという強みがありつつ、Production環境に持っていく際は低いリスクで完結できるという点が魅力です。

開発の中で苦労した点を教えてください。

お客様から「あるルートが使いにくい」というフィードバックをもらった時に、経路探索エンジンはなぜAからB点に対してこのようなルートを出したのかという問題をDebugする時に苦労しました。その原因を特定し、解決策を練り、実装まで落とし込むという一連の作業をいかに軽減するかという課題に直面しました。そこで、探索アルゴリズムの可視化が非常に重要であることが分かり、０から探索アルゴリズムの可視化ツールを作成しました。

仕事のやりがいについて教えてください。

大きく２つのやりがいがあります。１つ目は、最先端のプロダクトをゼロから作れるという点です。日々プロダクトの成長を実感することができるので非常に面白いですね。２つ目は、開発の喜びを仲間と分かち合える点です。開発の中で様々な分野を専門とするエンジニアと関わるため、それぞれの知見が１つとなって新規機能を開発できた時には大きな達成感があります。

今後、新たにチャレンジしたいことや目標はありますか？

たくさんあります！直近ですと、リアルタイムの交通状況を含め、工事中、交通事故の情報などを含む渋滞を予測し、現場状況に即したルートを出せるようになることです。ベテランドライバーさんにも「さすがLoogia！」と言ってもらえるサービスを目指して頑張ります！

郭さん、有難うございました！！

オプティマインドでは現在一緒に働く仲間を募集中です！弊社での開発や、郭さんにご興味をお持ちの方は、ぜひお気軽にご連絡ください！あなたにお会いできるのを楽しみにしています！

最後までお読みいただき、ありがとうございました。