配送計画問題は学問として古くから研究されている分野であると同時に、物流業界にとっては事業に直結する重要な問題であり、物流現場の実務に即したシステム開発が長年求められています。当記事では、配送計画問題の概要と課題、そして弊社 VPoE 髙田のインタビューをもとに弊社開発の自動配車システム「Loogia」についてご紹介します。
配送計画問題(VRP)とは?
配送計画問題(VRP:Vehicle Routing Problem)とは、複数の車両がスタート地点から複数の配送先を巡回してゴール地点へと辿り着く経路の中で、配送先の全ての需要を満たしかつ総経路コストを最小とするものを求める問題のことを指します。
実社会における小売店への配送や宅配便・郵便の配達、ゴミの収集などもVRPの応用例として考えられており、物流における効率的な配送ルート設計に深く関わるテーマとして現在も研究が進められています。
実務と研究の溝
配送計画問題は長年にわたり研究が行われている分野ではありますが、実社会に照らし合わせる際には様々な制約を考慮したモデルやそれらに対する解法を適用する必要があり、現在でも物流業界では実務に即したシステムを求める声が多くあります。
実際の配送計画はドライバーの労務規定や貨物の性質、配送先ごとの軒先条件など非常に多くの考慮すべき条件があり、研究の世界では見過ごされがちな商慣習的な個別の制約をいかにシステムに反映できるかが非常に重要なポイントとなります。現実の複雑な条件を含む問題を解くためには、「その問題をどのようにしてモデル化するのか」「その問題にはどのようなアプローチが有効か」を見抜く力が必要であり、さらに実際に解法を見出すためには経験や思いつきから生み出されるアイデアや、アルゴリズムやデータ構造などへの高度な知識が求められます。

配送計画問題の実社会応用を目指してサービスを開発
弊社は名古屋大学の研究室からスタートした企業です。大学での研究技術を活かし、「研究と実社会の乖離を埋めたい」という想いから2015年に創業いたしました。
多くのお客様に弊社開発の自動配車システム「Loogia(ルージア)」を活用し業務効率化を実現していただけるよう、配送計画の最適化に向けたシステムの開発を進めています。
以下では、創業時よりLoogia開発チームを牽引する、弊社 VP of Engineering (VPoE) 髙田へのインタビューと、Loogiaの技術や開発への思いなどについてご紹介します。

―大学での研究分野は?
私は大学で配送計画問題を拡張した「被覆制約付き配送計画問題」に対するメタヒューリスティクスを開発するという研究を行っていました。
配送計画問題は、訪問しなければならない点を必ず1台の車両が訪問するという制約の元で、全車両の移動コストを最小化する問題です。一方で「被覆制約付き配送計画問題」は訪問できる点(訪問点)の集合と被覆しなければならない点(被覆点)の集合が与えられます。ある訪問点を訪れると、それに関連するいくつかの被覆点が被覆された状態となります。その上で訪問点の中からいくつかを選んで、すべての被覆点を被覆するような訪問点集合のみを訪問しつつ、それらを訪問するための車両の移動コストを最小化するという問題です。
応用イメージとしては、郵便ポストの設置場所を決める問題があります。すべての住民にとって十分近くに郵便ポストを設置するという制約の元で、郵便物の回収のための移動コストを最小化するというモデルを表現できます(住民が被覆点、ポストの設置位置候補が訪問点)。
他にも、宅配便においてある程度の位置に車を停車させて、その周囲に荷物を配るようなケースも同様の構造とみなせます(配達先が被覆点、停車位置候補が訪問点)。
この問題は配送計画問題をより一般化した問題であるため、配送計画問題に対する解法をそのまま適用することはできません。そこで、現実的な時間でより良い答えが出せるようなアルゴリズムを開発するという研究を行っていました。

―オプティマインドへの入社のきっかけは?
私が前職を退職し、博士課程で研究を進めるため大学に戻った際に、今のオプティマインドの創業メンバーである松下と斉東に出会いました。二人が物流最適化に関する事業を考えていたところ、私自身の研究が配送計画問題の発展型の研究であったこともあり、お手伝いのような形で事業に携わることになったのがきっかけです。
当初はこのまま大学に残ってアカデミックな分野に進もうと考えていました。しかしオプティマインドとして物流の現場をいくつも見ていく中で、組合せ最適化の技術が全く活用されていない現場がまだまだたくさんあるということに衝撃を受けました。研究者が何十年も研究してきて素晴らしい成果がたくさん出ているのに、それらが実社会で十分に活かされないままになっていたのです。そういった中で、まさにオプティマインドこそが組合せ最適化の研究成果を実社会に活かす存在であり、今物流業界に必要とされている存在であると改めて理解しました。そして、今まで研究に深く関わっていた自分だからこそ貢献できることがあるのではないかと思い、研究者の道ではなくオプティマインドの事業に全力で取り組む決断をしました。
Loogiaに関していうと、私が最初に事業に参加したのは2017年4月頃でしたが、その当時は物流事業者の方向けにシミュレーションをしていただけで、まだ「Loogia」のようなシステムはありませんでした。2018年に日本郵便株式会社様初のオープンイノベーションプログラム「POST LOGITECH INNOVATION PROGRAM」に参加し、弊社の最適化技術を活用した実証実験を経て最優秀賞を受賞したことで、本格的に物流にフォーカスした事業が開始され、Loogiaの開発が進められることになりました。

Loogia開発に活かされるメタヒューリスティクス研究
―メタヒューリスティクスとは?
メタヒューリスティクスとは、簡潔にいうと、さまざまな組合せ最適化問題に適用できる近似解法のことを指します。近似解法とは、最適解(すべての組み合わせの中で一番良い解)を求める代わりに、より短い時間の中である程度精度の高い解を求める手法のことをいい、組合せ最適化問題を解く際にも用いられます。
理論的には、配送計画問題を含む多くの組合せ最適化問題において、最適であると保証された解を求めることは極めて困難であるとされています。しかし現実では、最適性の保証はなくとも十分精度の高い解が求められれば満足であるというケースも多く存在します。このような比較的短い現実的な時間の中で、ある程度精度の高い解へとたどりつくことを目的とする際に、メタヒューリスティクスは有効な手法として用いられます。
―Loogiaのシステムにどのように活かしているのか?
弊社開発の最適化アルゴリズムはメタヒューリスティクスの枠組みを用いています。この手法を用いることで、手作業で行う配車計画と比べ、限られた時間でより精度の高い解を導き出すことが可能となります。
メタヒューリスティクスの開発においては、新しい制約条件を考慮できるようにするということが非常に難しいポイントです。現場で求められる多種多様な制約に対応できるようアルゴリズムを改修していると、あるとき急激に解の精度が下がってしまうということがよくあります。そうならないよう、これまでの研究で培った経験を元にどのようにすれば効率的なアルゴリズムを作成できるのか日々試行錯誤しています。

現場百遍と技術力で作り上げられたLoogia
―Loogiaを開発する中で大切にしてきたこととは?
Loogiaを開発する中で重視していることは、研究と現場の両方にしっかりと向き合いながら開発を進めるということです。Loogiaは大学の研究技術を軸として生まれたシステムであり、開発メンバーも日々論文を読んだり学会に参加するなど常に理論を学び続けることを大切にしています。一方でそればかりに目を向けると、現場のニーズを満たせない、実際の配送現場では使えないシステムが出来上がってしまう可能性もあります。お客様がどのような業務をされていて何を求めているのかということをしっかりと把握することが重要であると考えています。
―開発を行う中で悩んだことや難しかったことは?
現場のニーズをどのようにしてシステムに反映するのかということが難しい問題ですね。
過去に「ドライバーごとの負荷の均等化をしたい」というご要望をお客様からいただいた時には、お客様のいう「均等」とは何か、勤務時間の差を少なくしたいということか、平均値からの広がりを少なくしたいということか、お客様の考えをしっかりとヒアリングすることからまずは始めました。その上で社内で何度も話し合いを重ねたり、参考になる論文を読み込んだり、技術アドバイザーの教授の方にアドバイスをいただいたりしながら開発を進めていきました。最終的にこの均等化のケースは完成まで数か月かかりましたし、今もお客様からご意見をいただきながら改善を続けています。
お客様のニーズに応えられるよう、良いアルゴリズムを提供するためにはどのようにすれば良いのか、そのための有効なアプローチ方法とは何かを考える際にこれまでの研究で培った知識や経験が活きていると感じています。
現場で”使える”システムを目指して
―Loogiaの良いところは?
何より「加味できる条件がたくさんある」ということですね。実際の配送現場では考慮すべき条件が非常に多くありますので、その複雑な条件を加味した精度の高い配送計画が作成できるというところは大きなポイントだと考えています。また、弊社では大学教授や研究者の方々にも開発にご協力をいただいています。弊社開発チームはもちろんのこと、こうした皆様のお力も借りながら今後も積極的に研究を続けて、Loogiaの発展を目指していきます。
―お客様へお伝えしたいことは?
弊社はアルゴリズムを作る力に長けていると自負していますが、それだけではダメだとも考えています。Loogiaの本当の強みは、エンジニア含め社員全員が物流現場を良くしたい、物流業界を変えていきたいという思いを持っているということです。それが根底にあるからこそ、本当に必要とされる機能の開発ができると私は考えています。システムを売ることを目的とせず、現場を変えるためにはどうすれば良いのかを全員が情熱を持って考え、お客様のお力になれるよう努めています。
まとめ
当記事では、配送計画問題の概要と課題について、そして弊社開発の「Loogia」について、弊社 VPoE 髙田へのインタビューをもとにご紹介しました。
弊社では、配送現場のニーズに合わせたサービスの開発に日々尽力しています。自動配車システムの提供を通してより多くのお客様の業務効率化を支援し、持続可能な物流の実現を支援いたします。Loogiaにご興味のある方はぜひ下記より資料をご覧ください。