アニーリングマシンによる
新規配送最適化手法の開発

取り組んだ内容

近年、配送需要が高まる一方で、再配達の増加および配送の担い手不足がローカルな小口配送において問題となっています。これ以上のコスト削減は難しく、「すぐ届く」という新たな付加価値をアニーリングマシンの計算高速化によって実現する必要があると考えました。そこで今回の未踏ターゲット事業では、配送者の移動距離が短い効率的なルート探索に加え、消費者の待ち時間の最小化を考慮した多目的最適化問題を高速に解くアルゴリズムの開発に取り組みました。

組合せ最適化問題の概要

容量制約付き経路最適化問題（CVRP）をベースに、消費者の待ち時間を最小限に抑えることを考慮した多目的最適化問題。各消費者地点において待ち時間が計測されており、待ち時間の合計が配送全体において最小化されるように配送経路を配送者人数分、同時に提案を行います。

決定変数

配送者(i)×消費者地点(j)の2次元の決定係数（配送地点に行く場合には1、そうでない場合は0）

目的関数

• 配送距離の最小化
• 消費者の待ち時間分布の分散最小化

制約条件

• 配送者が運べる重量に関する制約
• 同地点を繰り返し通過しないための制約

苦労した点

CVRPはいろいろと研究されている領域なので、既存の手法を調査して差別化を検討するのに苦労しました。インタビューや検討を進める中で、まだ最適化があまり進んでいないローカルな小口の配送という領域に着目し、効率化・コストダウンだけではなく、「すぐ届く」という新たな付加価値を提供するようなアルゴリズムの開発に取り組むことにしました。

プログラム開発においては、容量制約を含む不等式が問題に組み込まれているため、問題の規模が拡大すると、短時間内に高精度の解を導出することが困難になります。そのため、前処理や決定変数の工夫には多大な労力が必要でした。また、多目的最適化における目的関数間の重みや制約の重みの調整にも苦労しました。プロジェクトマネージャーの方や、他のチームの方との会話からヒントを得ながら一歩一歩改良を重ねました。

今後の展望

将来的にはサービス化できればいいなと思っていますが、現在のアプローチだと問題サイズを大きくしていくと短時間で精度の良い解を得ることが難しくなっていくという課題があります。問題の簡略化、前処理や決定変数の工夫、変数の削減、問題分割等、まだ考えなければいけないことがあると思っています。また、サービス化していくにあたっては、価格や運用コストなどを含め、ビジネス面においても更なる検討が必要だと思っています。

嬉しかった点

量子アニーリングの適用可能性は非常に大きく、従来のコンピュータでは解くことがとても難しかったNP困難な組合せ最適化問題に対する有効な手法であることを、実践を通して理解できた点がよかったと思っています。一度取り組むと、あれも組合せ最適化問題、これも組合せ最適化問題、という形で視野が広がった気がします。

見ている方に一言

量子コンピュータ（D-Wave）およびGPUアニーラーの発展により、実用的な課題に適用できるようになってきました。アプリケーション開発の観点で非常に面白くなってきたので、ぜひ皆さんも取り組んでみてください！

＊本記事の掲載内容は全て取材時の情報に基づいています