loading...

競技プログラミングで、日本を高度IT人材大国に!No.7

2021/01/27

高度IT人材が物流業界の「配送ルート最適化問題」を解く

競技プログラミング界のキーパーソンであるAtCoder社長 高橋直大氏と共に、優れたアルゴリズム開発能力を持つ「高度IT人材」の育成・採用について考える本連載。

今回は、「世界のラストワンマイルを最適化する」というミッションを掲げるスタートアップ、オプティマインドの社長・松下健氏と高橋氏の対談を実施しました。

「どの車両が、どの訪問先を、どの順で回ると最適か」を提示する、ラストワンマイルのルート最適化、いわゆる「配送計画問題」は、学問として長年研究されているテーマであると同時に、物流業界にとっては事業に直結する問題です。

トヨタ自動車などから10億円を超える資金調達をするなど、注目を集めるオプティマインドの取り組みと、高度IT人材が物流業界でどう活躍できるのかを、二人に熱く語っていただきました。

松下健氏、高橋直大氏
※対談はオンラインで実施しました。

「組合せ最適化」との出合い。これは社会課題を解決できる研究だ!

高橋:競技プログラミングの世界でも定番の「組合せ最適化」を実際に応用して、物流業界の課題解決に挑まれている松下さんには、以前から話を伺ってみたいと思っていました。改めて、ご自身の経歴とオプティマインドについて教えていただけますか?

松下:私は名古屋大学情報文化学部に入学後、柳浦睦憲先生が研究されていた「組合せ最適化」の存在を知りました。これは社会課題を解決できる研究に違いないと思い、柳浦先生の研究室に入れていただいたんです。

組合せ最適化
「組合せ最適化」とは、与えられた条件を満たす組み合わせを選ぶとき、一番良い組み合わせを短時間で探し出すための学問。

松下:しかし、すごく良い研究なのに、実社会では全く活用されていないことを知り、不思議に思いました。そこで、いろいろな業界の現場に聞いて回った結果、特に物流現場への「組合せ最適化」技術の活用が難しいことが分かったのです。課題が大きく、組合せ最適化の力を大いに発揮できる市場であると思い、選びました。

「組合せ最適化」という素晴らしい研究成果と物流現場の橋渡しをしたいと思い、在学中に会社を立ち上げ、ルート最適化クラウドサービス「Loogia(ルージア)」を開発しました。どの車両がどの訪問先をどの順番でどういうルートで訪問するのが最適なのかという「配送計画問題」を解決するためのサービスです。それをSaaS(※1)、もしくはAPI(※2)で企業に提供するのが当社の事業内容です。

※1=SaaS(Software as a Service)
買い切り型ではなく、ユーザーが必要な機能を必要なときに必要な分だけ利用できるタイプのソフトウエアサービス。
 
※2=API(Application Programming Interface)
ソフトウエアの機能を部分的に公開し、他のソフトウエアと機能を共有できるようにする仕組み。
 

高橋:オプティマインドの顧客は、どういった企業でしょうか?

松下:いわゆるラストワンマイルと呼ばれる、物流の最終拠点からエンドユーザーに届けるまでの配送を行っているお客さまが中心です。身近なところでいうと、宅配会社や宅食会社。あとは「店舗配送」といって、コンビニやドラッグストア、病院などに物資を運んでいる会社が多いですね。

高橋:なるほど。ラストワンマイルのためのアルゴリズムですね。「組合せ最適化」のアルゴリズムは、競技プログラミングでもよく出題されている「巡回セールスマン問題」(※3)がベースになると思うのですが。

※3=巡回セールスマン問題
いくつかの都市間の距離が与えられている中で、全ての都市をたどる経路のうち、最も短い経路を求める問題。
 

松下:そうですね。高橋さんはよくご存じかと思いますが、例えば配送先が20カ所あるとき、どの順番で回るのが最適なのか、一個一個順番を入れ替えながら検証すると、その組み合わせは243京通りもあります。それを、一つずつしらみつぶしに検証して、最適なルート、つまり“厳密解”を求めようとすると、スーパーコンピューターでも80年ほどかかるといわれています。

ですから、実際の業務に活用するためには“厳密解”は目指しません。「これがまあまあ良い解ではないか?」という見当をつけて計算し、その中からさらに良さそうな解に見当をつけて計算して…というように、時間がある限り、なんとなくの見当をつけながら「まあまあ最適な解」を探っていきます。つまり、厳密解ではなく“近似解”を求めるのです。例えば10分間など、与えられた制限時間内で求められる最良の解を見つけるため、アルゴリズムをどんどん改良しています。

現場ゆえの“制約”。アルゴリズムそのままでは通用しない

高橋:単純な「巡回セールスマン問題」の場合、既に数えきれないほどの研究がなされていて、例えば巡回する場所が20カ所だけであれば、競技プログラミングの初級問題として厳密解が求められてしまいますし、1000カ所あったとしても、最新のアルゴリズムを用いれば、特別な状況を除いて一瞬で厳密解が導き出されると言っても過言ではないほど進んでいます。

しかし、実際の仕事の現場では、「指定の場所に何時から何時の間に届けなければいけない」といった制約をたくさん考慮する必要があるところが、競技プログラミングの世界や、広く知られている研究との一番の違いになりますよね。

松下:おっしゃる通りです。具体的には、40以上もの“制約”があります。届ける時間指定はもちろん、ドライバーの勤務時間、休憩時間、資格の有無。車両に対しては、積載容量の制約だったり、冷蔵・冷凍が両方積める「多温度帯」と呼ばれる車両があるのですが、どちらかのスペースに空きがあるともったいないので、両温度帯とも目いっぱい荷物を積むように考慮したり。

あとは、配送先でトラックを止められる場所が複数あったときに、前後の配送先の位置を考慮しながら、どこに止めるのが最適なのかを計算する必要もあります。

その上で、「ピック&デリバリー」という制約もあります。これは、「運ぶ荷物をピックアップしてから、その荷物を降ろす配送先に向かう」という“順序”を考慮してルーティングしなければならないという制約です。「荷物は積んでからしか降ろせない」なんて、人間だったら当たり前に分かることが、実はコンピューターでは自動で考慮できないのです。

その他にも、時間帯ごとの渋滞状況も考慮する必要があります。言葉で言うと簡単に思えるかもしれませんが、そういった制約すべてをアルゴリズムに落とし込むのには、かなり苦戦していますね。

高橋:競技プログラマーの感覚だと、配送計画問題を解こうとしたら、2-opt法(※4)など、いくつか基本になるアルゴリズムが思い浮かびます。でも、距離を最適化するためにルートを入れ替えてしまったら、ピック&デリバリーや時間指定など、ほぼすべての制約に引っかかってしまいますね(笑)。普通の巡回セールスマン問題の最適化アルゴリズムが全然効かないということは、すごく大変だと思います。

※4=2-opt法:経路の中からランダムに2個の辺を選択して、ルートを入れ替えてみる方法。その結果、距離が短縮されれば、その新ルートを採用するという処理を繰り返す。
 

松下:でも、基本的な考え方自体は一般的なアルゴリズムと一緒です。ある程度の見当をつけてランダムに計算しながら、どうすればさらに良くなるのかを、ひたすらコンピューターに解かせていきます。大変ですが、すごく面白いですし、やりがいはありますね。

「研究」と「事業」の違い。大学発スタートアップが事業に挑む難しさとは?

高橋:大学の研究成果を実社会に還元するために会社を始められたというお話でしたが、「大学発のスタートアップ」として、どんなところに強みと弱みを感じていますか?

松下:強みは、アカデミアと研究連携しながら、質の担保されたシステムをつくっていけるところです。当社でも、私の恩師であり、この分野における世界最高レベルの研究者である柳浦先生に技術顧問をしていただいています。採用の面でも、柳浦先生の研究室や学生と濃厚なつながりがあるので、技術に直結する人材を採用しやすい利点があります。

一方でサービスが、大学での研究ありきで始まったいわば“プロダクトアウト型”なので、どんなに優れたアルゴリズムをつくっても、それだけでは売れないのは弱みです。単に良いものをつくるだけではなく、それをビジネスにしていくという面では、ビジネス側から入った起業家と比べるとハンディがあると感じています。

高橋:なるほど。そんな中でも、トヨタ自動車をリードインベスターとして10億円を超える資金調達をするなど、着実に事業を拡大されていて素晴らしいと思います。ちなみに、配送計画問題に対して、アカデミックからアプローチするのと、ビジネスとしてアプローチするのにはどんな違いがありますか?

松下:アカデミックの世界では、「Aくんは自転車で20キロで走行するとします」というような前提条件が定められていますよね。でも現実では、10キロで走るときもあれば、15キロで走るときもあります。そもそも、Aくんが休みで、Bくんが出社することだってあり得ます。それをアルゴリズムにしなければいけないのが大きな違いです。

もう一つ、力の入れどころが違うというのもあります。アカデミックの世界では、精度やスピードを改善することが一番の目標になると思うのですが、私たちとしては、お客さまの事業に与えるインパクトに重きを置いています。

高橋:具体的にはどういったインパクトでしょうか?

松下:大きく二つあります。一つ目は、走行距離の削減によってドライバーの残業時間が30分減ったら、ドライバーの人数を削減できたら、どれほどのビジネスインパクトがあるのか。いわゆるROI的な数値の改善です。

もう一つ、今回のコロナ禍で人手不足になり急増しているのが、「誰でも配送・配車できるようにしてほしい」というニーズです。

高橋:それは、アルゴリズムで解決できるものなのでしょうか?

松下:スキルの高い人に、すべての人を近づけていくようなアルゴリズムを開発するということですね。今まで人の頭で考えて行っていた配車の仕方を現場の方々に話していただき、それを数式に落とし込んでいくのです。

とはいえ人の頭は非常に優れており、それをどれだけ数字に落とし込んでも勝てませんから、「ベテランと同等」を目指してはいません。これまで、ベテランの配車スキルが100点で、新人は30点だったところを、新人が入社した次の日から80点のパフォーマンスを出せるようにするのが、アルゴリズムの役割だと思っています。

IT人材とビジネス現場。アルゴリズム開発能力だけでは足りない?

高橋:私も現役の競技プログラマーなわけですが…松下さんの目には、競技プログラマーってどのように映っていますか?

松下:自分はもう競技には参加できないな、と思っていますが(笑)。当社のエンジニアにも、 AtCoderに親しんでいるメンバーがそろっていて、社内部活でコンテストを開いたりしています。AtCoderユーザーである社員同士が、レベルを競い合って切磋琢磨しているのは、優れたアルゴリズムをつくらなければならない当社にとってもありがたいです。今後もバックアップしていきたい存在だと思っています。

もちろん、AtCoderに参加していないエンジニアがダメということはありませんが、ある意味プライベートな時間にもトレーニングしているので、AtCoderに参加している人は成長速度が速いなと感じています。

高橋:オプティマインドのように、がっつりアルゴリズムを考える必要がある会社では、まさに競技プログラミングがすごく生きると思います。膨大なデータの解析や複雑な計算を行う場合、ロジックを考えることに慣れているかどうかは、非常に大きな差につながりますよね。

ただ、競技プログラマーがオプティマインドのような会社で活躍するために必要なスキルは、他にもあると思うんです。例えば、もしこれからAtCoderがアルゴリズム部隊を組織して、配送計画問題を解決しようと思った場合、アルゴリズム自体は追いつけるかもしれません。

松下:本当にやめてほしいですね(笑)。

高橋:しかし、「現場で何が求められているのか」を知るのに、ものすごく時間がかかると思うのです。というのも、頭の中で考えていることを一度にすべて言葉にするのは難しいので、現場の方に一回話を聞いただけでは、足りない部分が後からどんどん出てくるはずです。そのすり合わせを、一社に対して行うだけでも大変なのに、複数社とやりとりしなければならない。さらに、運ぶものによっても細かく条件が変わってきますよね。

ただアルゴリズムをつくれればいいというわけではなく、各社としっかり向き合い、真摯にサポートしていくところが、非常に難しいのではないかと思いますね。

松下:自画自賛するわけではないのですが、まさに高橋さんのおっしゃる通りかなと。当社は、“翻訳者”として、現場の要件をくみ取り、それを優秀なエンジニアに通訳できる人がいる点が、いわゆる“秘伝のタレ”になっていると思います。

当社のエンジニアに求める能力は二つあります。一つはコンサルティング的な能力です。そもそも、話をよく聞いたら、アルゴリズム以外の方法で解決できることもあります。そういった、開発側の要件を理解した上でビジネス課題を解決できる能力が大事だと思っています。そしてもう一つが、「やはりアルゴリズムでしか解決できない」となった場合に、複合的なアルゴリズムを考慮しながら数式に落とし込める能力。理論的に破綻しないか、上流の設計段階から考えられるかが重要だと考えています。

競技プログラマーに知ってほしいこと。活躍の舞台はウェブやゲーム業界だけじゃない!

高橋:競技プログラマーをはじめとする高度IT人材が社会で活躍するためには、先ほど伺った能力の他に、どういうスキル、マインドを持っているとよいでしょうか。

松下:これまでは、情報の可視化や管理に対してのみITが導入されていましたが、今は物流に限らず、「意思決定レベル」にまでITの導入が進んでいます。だからこそ、アルゴリズムを考える能力がより大事になってきていると感じています。

当社が採用を行う場合、謙虚さを持ち合わせているかなど、もちろん人柄なども見ていますが、そこを満たしていれば、あとはもう基礎能力とアルゴリズム思考ができるかどうかがポイントとなります。AtCoderに挑戦するマインドも持っていた方がいいと思います(笑)。

高橋:ありがとうございます(笑)。あと、私見ですが、ITを学んでいる人、特に若い方たちは、IT人材が活躍できるのはウェブ業界やゲーム業界だけだと思っていて、「世の中の問題解決」という視点を持っている人は少ないと思うんですよね。でも、オプティマインドのように、物流業界の問題解決にITを役立てることもできるということを、若いIT人材たちにも知ってほしいですね。

松下:おっしゃる通り。これからのITは、実社会の動きにどう絡んでいくかが重要です。僕らの場合だったら、トラックが動く、ものが動くところにどうITを入れ込んでいくか。自分たちが研究している技術が、どれだけ「手触り感のあるビジネス」になっていくか、という視点を持つことが大事だと思います。

高橋:物流業界以外にも、ITを使わないと解決できない問題は世の中にたくさん転がっています。だから、アルゴリズムがどこかに役立つのではないか、IT系企業以外の全然違う業界でも最適化できるところがあるのではないか。そういったことを見逃さないように、広い視野を持って世の中を見てほしいということを、競技プログラマーたちにも伝えていきたいと思いました。今日はありがとうございました。

新規CTA
新規CTA