第 202 号・2023 年 1 月

住友電工テクニカルレビュー

自動車

量子コンピューティングによる配送計画の最適化
Optimization of Delivery Plan by Quantum Computing
＊増田健一

八川剛志

Kenichi Masuda

露峰祐衣

羽賀剛

北田Yui Tsuyumine

Takeshi Hachikawa

智之

Tomoyuki Kitada

Tsuyoshi Haga

複雑な組合せ最適化問題を高速に解く技術として量子コンピューティングが注目されている。当社では物流事業者に向けた業務支援ツールの一つである配送計画システムを20年前から販売しており、継続的に研究開発を行っている。配送計画システムは輸配送コストが少なく効率的な配送経路を計算する機能を有するが、この機能の実現には複雑な最適化計算が不可欠である。我々は、この最適化計算に量子コンピューティングを適用することを目指し、この実現に必要となる定式化と実装・性能評価を行っているが、実用化に向けては解の精度の検証が不可欠である。本論文では、イジングマシンと古典コンピュータを用いた結果を比較評価することで定式化の妥当性が確認できたため、その成果を報告する。

Quantum computing is attracting attention as a technology for solving complex combinatorial optimization problems at
high speed. We have been selling delivery planning systems, one of the business support tools for logistics companies,
for 20 years and have been conducting research and development of related technologies. The delivery planning systems
have a function to calculate efficient delivery routes with low transportation and delivery costs, but it requires complex
optimization calculations. With the aim of applying quantum computing to this optimization computation, we areformulating, implementing, and evaluating the performance required for this purpose. In this paper, we report the findingsof the validation of the formulation by comparing the results obtained using the Ising machine and conventional
computers.
キーワード：物流、配送計画、量子コンピューティング、アニーリングマシン

1.

緒

言

イバーに任されることが多く、全体最適となる新たな配送オンラインショッピングの普及により、配送単位が小口化したことで物流量や配送の回数が増加している 。加え（1）

計画を再立案してドライバーに指示することは極めて困難であった。て、共働きや単身者の増加によりオンラインショッピング配送計画に代表される組合せ最適化問題は、従来のコンの利用者が急増しており 、配送サービスの競争が激化した

ピュータ（以下、古典コンピュータ）では厳密解を求める

ことで翌日配送に代表される配送時間の短縮といった顧客ことが困難であり、解を逐次的に探索し許された時間内でニーズが高まっている。そのため、物流事業者は大量の荷近似解を求めている。これに対し、量子コンピュータは量物を多頻度で配送する計画の立案が必要となっている。ま子力学の重ね合わせの原理を用いることで一種の並列計算た、配送サービスの競争激化は現在の翌日配送だけにとどまを行い、より厳密解に近く良い解を求められる可能性があらず、即日配送や即時配送といったより高度な配送サービる技術として脚光を浴びている。一方、量子コンピュータ

スが要求されるようになってきている。一方、道路の渋滞はまだ発展途上の技術であり、ハードウェア上の制約から状況や事故状況、豪雨や降雪といった気象などは時々刻々大規模な問題を解く計算ができないといった課題がある。と変化するが、そのような場合にも当初予定していた計画

当社は配送計画に関する研究開発（3）とその製品である「配を迅速に変更することで配送サービスを可能な限り維持す送デス」の販売を長年行っており、その実績や知見をもとるといったことも求められている。今後、自動配送ロボッに量子コンピュータでの実際の配送を想定した複雑な配送トやドローンによる配送が実現すると、さまざまな配送手計画の定式化と適用有効性の検証を行ったので報告する。

（2）段を考慮した非常に複雑な配送計画を瞬時に立案することも必要になる。

2.

これまでの配送計画計算では、例えば車両100台といっ量子コンピュータとはた多くの車両で多量の荷物を配送する場合は長時間の計算

量子コンピュータで扱う情報の単位を量子ビットと呼を要するため、前日の夜などに配送計画を立案し、翌日のぶ。量子ビットは、量子力学における重ね合わせの原理を配送に適用する運用となっている。また、配送の開始後に用いて、0と1の状態を同時に取りながら計算できる。これ生じた渋滞や災害などによる配送順序の変更は現場のドラにより、量子ビットが n 個ある場合には2 通りの状態を同n量子コンピューティングによる配送計画の最適化

91（1）住友電工テクニカルレビュー

第 202 号・2023 年 1 月

時に表現できるため、量子コンピュータは計算ステップを■配送先や荷物の条件・作業可能な時間帯・作業の所要時間・積載可能な車両や車種・積み合わせ禁止の荷物劇的に減らすことが可能になる。
量子コンピュータは、動作方式により量子ゲート方式と量子アニーリング方式に分類される。量子ゲート方式は古訪問先

典コンピュータの上位互換を目指し、特定の問題を汎用的11:50

10:00

グモデルで表現された組合せ最適化問題を解くことに特る形式で対象の問題を定式化する必要がある。量子アニー

17:00
15:00

10:00

車両Cリング方式は、量子ゲート方式と比較して多くの量子ビッ

13:00

16:10

10:50

トを扱えるものの、実用的な組合せ最適化問題を解く場合

車両B

14:30

15:20

10:00
13:10

■車両の条件・拠点出発時刻
・拠点帰着時刻・時間帯別の移動時間
・運転手の休憩時間

拠点

16:30

15:50

化した方式であり、QUBO（Quadratic Unconstrained

13:40

11:00

15:00

かつ高速に処理する。量子アニーリング方式は、イジン

Binary Optimization：二次制約なし二値最適化）と呼ばれ車両Aにはさらに多くの量子ビットが必要になる。今回は、GPU

11:00

図1

12:30

配送計画の例や FPGA などの従来技術を応用して QUBO により定式化された問題を高速に計算できるイジングマシンで検証を実施した。
適な配送計画を求める。配送計画問題は代表的な組合せ最3.

組合せ最適化問題の難しさ

適化問題の一つであり、CVRP（5）（Capacitated VRP：容量（7）制約付き配送計画問題）や VRPTW（6）、（VRP with Time

最適化問題とは、与えられた制約条件の中で目的関数をWindows：時間枠付き配送計画問題）など、より現実に即最小・最大にする解を求める問題である。最適化問題は目した配送計画の定式化やその解法などが研究・提案されてい的関数の形式や決定変数の取り得る値によって、線形計画る。本論文では、地点間の移動所要時間が時間帯によって変問題や非線形計画問題などの汎用問題に分類される。汎用化することを想定した時間枠付き配送計画問題 TDVRPTW

問題のうち、決定変数が整数である問題は整数計画問題と（Time-Dependent VRP with Time Windows）につい呼ばれ、ナップサック問題や巡回セールスマン問題などにて QUBO で定式化し、イジングマシンを用いて評価検証し代表される組合せ最適化問題はこれに分類される。整数計たので、その結果を報告する。

画問題は計算複雑性理論において NP 困難であるとされ、多項式時間で解くことができない。すなわち、問題の規模5.

が大きくなるにつれて計算量が指数関数的に増えるため、TDVRPTW の QUBO による表現

現実的な時間で厳密解を求めることが不可能となる。その車両の集合を K とし、車両 k の出発地点を sk 、帰着地点をため、規模が大きな問題を解く際には汎用的なメタヒューek とする。また、荷物の配送先地点を表す集合を D とし、リスティクスやその問題に特化した手法を用いて近似解を車両 k が訪問する可能性のある地点および訪問しなければ求めることが一般的である。

ならない地点の和集合を Pk ＝ D∪{sk,ek} とする。さらに、すべての車両に共通した拠点出発から拠点帰着までの時刻の4.

対象とする配送計画問題

集合を T ＝ {1,2,…,N} とする。そして、車両が時刻 t に地点p から地点 p' へ移動し、地点 p' から移動することが可能と

一般に、物流事業者は複数の車両を用いて荷物を配送すなるまでの時間、すなわち、時刻 t における地点 p から地点る。このとき、車両の走行距離やドライバーの拘束時間などp' への移動時間や移動中の休憩時間、地点 p' に到着した後の各種コストを考慮しながら、複数の荷物をそれぞれどのの待機時間や作業時間などをすべて合計した時間を車両に割り当て、どのような順序で配送するのかを計画すする。なお、る必要がある（図1）。配送先の件数が少ない場合には比較で決定変数となる二値変数的容易に計画を立てることが可能だが、車両の台数や荷物とは非負整数とする。次に、今回の定式化を次のように定義する。

車両 k が時刻 t に地点 p を出発するの数が多い場合には計画の複雑さが増すため、人手で対応することが困難になる。このように複雑な配送計画を立案することを支援するツールの一つとして、配送計画ソフト

以上を用いて TDVRPTW を QUBO で表現すると、エネル

ウェアがある。配送計画ソフトウェアは、車両や荷物などギー関数種々の条件を入力することで、各種コストを最小化した配は次の式（1）で表せる。
............................................................（1）

送計画を自動的に立案してくれるものである。このソフト
ウェアは、配送計画問題 （Vehicle Routing Problem：（4）VRP）と呼ばれる非常に複雑な最適化問題を解くことで最

ここで、wi は各項に対する重み付けの係数であり、iは以量子コンピューティングによる配送計画の最適化

92（2）住友電工テクニカルレビュー

第 202 号・2023 年 1 月

下の式（2）から式（10）で構成される、最適化の目的関数6.と制約条件を表現する項である。
....................................（2）決定変数の削減

今回、式（1）で表現した QUBO では、決定変数の個数が車両台数と地点数、そして時刻数を乗じた O（¦K¦¦D¦N）となるため、計算には非常に多くの量子ビットが必要とな............................................（3）る。しかし、TDVRPTW の性質から解の一部を事前に求めることができるため、それらの決定変数に予め0を代入し固定することで必要な量子ビットの数を削減可能である。

....（4）

ここでは、配送先地点から帰着地点への移動時間に着目した変数固定と、ドライバーに指定される休憩時間に関する変数固定を行う。

..........（5）

今回の問題設定では、車両の拠点帰着時刻が N より大きくなることを制約違反としており、また地点間の移動時間は非負としている。そのため、車両がある地点から出発可.........................（6）

能な状態であるとき、その時点で拠点へ直行したときの帰着時刻が N 以下でなければならないことは自明である。すべての時刻と地点の組に対する拠点への帰着時刻は事前に計算可能なため、以下の式（11）に従って変数を固定する。

.........................（7）.....................（8）......（11）
また、ドライバーの休憩時間が指定されている場合、休憩中に車両が地点から移動を開始してはならないことは明ら........................................（9）かである。ドライバーに区間（ts ,te）の休憩時間が指定されているとき、以下の式（12）に従い変数を固定する。
......................（12）.....................................（10）7.
まず、およびは各車両定式化した QUBO の正当性を確認し、古典コンピュータが出発地点から帰着地点に至るまでの総稼働時間を最小化との性能を比較することを目的として、TDVRPTW のサン

し、1は目的関数であり、それぞれイジングマシンによる評価とその結果

2

1は配送される荷物の個数を最大化することを表す。

プルデータを用いて評価を行った。評価は車両の台数と配すなわち、できるだけ多くの荷物を可能な限り短い時間で送する荷物の数が異なる12種類の配送計画問題を用意し、配送することをこれらの項で表現する。また、それぞれについて古典コンピュータとイジングマシンで解23から9は制約条件に相当するものであり、各項は制約が満足されいた結果を比較した。また、古典コンピュータで動作させるときに0、満足されないときに正の値を取ることでペナるソフトウェアは当社で開発した配送計画エンジンを利用ルティが与えられる。

3は車両が地点間を移動するとき、し、イジングマシンは Fixstars Amplify 社の Annealing

与えられた所要時間未満で移動することを禁止することをEngine（AE）を用いた。なお、評価ではベーシックプラ

表し、はそれぞれの配送先地点に訪れる車両は1台以下ンの計算環境を利用し、Amplify AE は v0.7.0、Amplify

4で、かつ1回以下であることを表す。ただし、4はそれぞSDK は v0.9.1を使用した。
評価の結果を表1に示す。表1はアニーリング時間を10秒れの地点に対して同じ時刻で異なる車両が訪問することの違反は表現していないため、が与えられる。さらに、と65でそれに対するペナルティ

は車両の拠点出発前および7

拠点帰着後に配送先地点へ訪問することを禁止し、 8と9

は車両の拠点出発と拠点帰着がそれぞれ1回ずつでなけれと指定したときの結果であり、誤差率は古典コンピュータによる立案結果と車両の総稼働時間を比較した値である。
表1から、車両9台・荷物54個までの問題であれば古典コンピュータと同等の計算結果が得られたことがわかる。

ばならないことを表現する項である。

一方、問題のサイズがそれよりも大きい場合にはいずれも古典コンピュータよりも車両の総稼働時間が長く、配送効率が低下した結果となった。これは、問題のサイズが大きくなるに伴い、式（1）で表されるエネルギー関数の構造
量子コンピューティングによる配送計画の最適化

93（3）住友電工テクニカルレビュー
表1

第 202 号・2023 年 1 月

問題サイズとイジングマシンによる評価結果

車両台数

荷物数

総稼働時間

誤差率

16

スピン数
151

23±0％

21144845±0％317948

70±0％

423

1,529

97±0％

5292,425

121±0％

6363,552

149±0％

7424,746

176±0％848

6,072

204

±0％

954

7,632

229

±0％

10

60

9,410

259

+1.6％

1166

11,319

296

+5.3％

12

71

13,188323+5.6％

が複雑になり、今回指定したアニーリング時間の10秒では

参 考 文 献（1）	国土交通省、「令和3年度 宅配便取扱実績について」、2022-08-10		https://www.mlit.go.jp/report/press/jidosha04_hh_000255.
html（参照 2022-12-12）（2）	総務省統計局、「家計消費状況調査年報 令和3年」		https://www.stat.go.jp/data/joukyou/2021ar/index.html（参照 2022-12-12）（3）	吉井 他、「道路交通情報の配送計画への適用」、SEIテクニカルレビュー
第161号、p. 66-70（2002）（4）	Dantzig, George B.; Ramser, John H. The Truck Dispatching
Problem. Management Science. 1959, vol. 6, no. 1, p. 80-91（5）	Ralphs, Ted K.; et al. On The Capacitated Vehicle Routing
Problem. Mathematical Programming. 2003, vol. 94, no. 2, p.
343-359（6）	O. Bräysy.; M. Gendreau. Vehicle Routing Problem with Time
Windows, Part I: Route Construction and Local Search
Algorithms. Transportation Science. 2005, vol. 39, no. 1, p.
104-118（7）	O. Bräysy.; M. Gendreau. Vehicle Routing Problem with Time
Windows, Part II: Metaheuristics. Transportation Science.
2005, vol. 39, no. 1, p. 119-139

解の探索が十分になされなかったためだと考えられる。実際、式（3）から式（10）で表される制約条件の項の総数は車両1台・荷物6個の場合で約2万、車両6台・荷物36個の場合で約300万、車両12台・荷物71個の場合で約2,000万

執 筆 者 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーとなっており、指数関数的に増加している。これらのこと

増田健 一＊ ：情報ネットワーク研究開発センター

露峰

祐 衣 ：情報ネットワーク研究開発センター

北田

智 之 ：情報ネットワーク研究開発センター
主査

八川

剛 志 ：情報ネットワーク研究開発センター
グループ長

羽賀

剛 ：情報ネットワーク研究開発センター部長

から、イジングマシンでより効率的な配送計画を立案するには、制約条件を可能な限り平易な QUBO で表現する、もしくはアニーリング時間を長く確保するなどの工夫が必要だと考えられる。

8.

結言

本論文では、TDVRPTW を QUBO で表現し、イジングマシンによる性能評価の結果を示した。今回の評価では、車両9台・荷物54個の小規模な問題において、古典コンピュータと同等の結果が得られることを確認し、QUBO による定式化が正しいことを確認した。今後は、より複雑な条件を考慮した配送計画の定式化や、大規模な問題に対しても優れた解を得るための手法の開発を行う。

9.

謝辞

本研究の成果は、早稲田大学理工学術院戸川研究室との共同研究により得られたものである。本研究の遂行にあたり、研究室の皆様には多大なご助言、ご協力をいただきました。ここに感謝の意を表します。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー＊主執筆者

・配送デスは住友電気工業㈱の登録商標です。

量子コンピューティングによる配送計画の最適化

94（4）