配送計画問題

配送計画問題（はいそうけいかくもんだい、運搬経路問題、うんぱんけいろもんだい、英: vehicle routing problem、略称：VRP）とは、組合せ最適化問題、整数計画問題の一種であり、複数の顧客に配る荷物の運搬の効率を最も良くする各車両の運搬経路を求める問題である。配送計画問題は巡回セールスマン問題を一般化した問題とされる。1959年にジョージ・ダンツィーグとジョン・ラムザーによって初めて定義された問題として知られ^[1]、このとき配送計画問題に対する初のアルゴリズムが提案されると同時に、ガソリン運搬に事例に応用された。配送計画問題が想定される状況としては、中央のデポを出発地点として複数の顧客に対して商品を届けることが挙げられる。配送計画問題において求めたいものとして配送にかかる総費用の最小化となる車両の経路を求めることである。1964年には、クラークとライトによりセービング法と呼ばれる貪欲法を用いてダンツィーグとラムザーのアプローチを改良した。

配送計画問題の最適解を求めることはNP困難として知られており^[2]、数理最適化や組合せ最適化のアプローチによって最適解を求めることは問題のサイズによっては限界がある。このことから、配送計画問題を解決するための商用ソルバーにおいては現実世界の配送計画問題の規模と発生する頻度の高さから、しばしば発見的解法によるアプローチをとられることが多い。

また配送計画問題は工業において様々な応用がなされている問題である。配送計画問題を解くことで得られる経路を用いることで5%から30%の費用削減が可能であるとの主張も存在している^[3]。

配送計画問題は運送会社の事業において発生する問題である。どのようにして所与の複数の車両群が配置された一つあるいは複数のデポから道路ネットワーク上を移動できる運転手によって顧客集合へ配送が行われるかを扱う問題である。これはすべての顧客の要求と運用上の制約を満たしつつ、全体の輸送にかかる費用を最小化するような配送経路の集合 ${\displaystyle S}$（各車両に対して所属するデポを出発し、顧客を巡りまた同一のデポへ戻る）を決定することである。ここでいう費用とは運送費や距離などを指すことが多い^[2]。

道路のネットワークは道路を有向辺、交差点などを頂点とするグラフによって表現することが可能である。有向辺は道路が一方通行である場合や進行方向によって異なる費用の設定によって、有向または無向の両方を考慮することができる。各有向辺には一般的にその距離や所要時間に基づいた費用が割り当てられており、これは車両の種類によって変化することがある^[2]。

各配送経路の全体的な費用を把握するためには、各顧客とデポ間の移動費用および移動時間を把握する必要がある。そのために、元のグラフを変換し頂点を顧客およびデポとし、有向辺をそれらの間の道路とする新たなグラフを構成する。各有向辺の費用は、元の道路ネットワーク上の2点間における最小費用とする。この計算は比較的容易に解くことができる最短経路問題を解くことで容易に求まる。この変換によって、疎な元のグラフは完全グラフに変換される。各頂点対 ${\displaystyle i}$ および ${\displaystyle j}$ に対して、完全グラフ上に有向辺 ${\displaystyle (i,j)}$ が存在し、その費用 ${\displaystyle C_{ij}}$​ は、元の道路グラフ上における ${\displaystyle i}$ から ${\displaystyle j}$ への最短経路の費用として定義される。移動時間 ${\displaystyle t_{ij}}$​ は、元の道路グラフ上の ${\displaystyle i}$ から ${\displaystyle j}$ への最短経路に含まれる有向辺の移動時間の総和である。

場合によってはすべての顧客の需要を満たすことが不可能なことがあり、その場合は配送計画問題を解くソルバーでは一部の顧客の需要を削減したり、配送のサービスを行わないといったことを行うことがある。これを回避するために、各顧客に対応した優先度の変数を導入することや、配送のサービスが行えない場合にペナルティを設定することがで考慮することができる^[2]。

配送計画問題で用いられる目的関数^{[注釈 1]}は生じている問題によって異なることも多いが、一般的に設定されるものとしては以下が挙げられる^[2]:

• 車両や運転手を運用することで生じる固定費や配送経路の距離に応じた運送費などの総費用の最小化
• 全顧客にサービス提供を行うために必要な車両数の最小化
• 各車両に対応する経路での稼働時間や運搬量のばらつきの最小化（均等化）
• 許容されない低品質なサービスに応じたペナルティの最小化
• 収集した利益、得点の最大化

配送計画問題ではいくつかの変種や特殊ケースの問題が存在しており:

• 利益付き配送計画問題（Vehicle Routing Problem with Profits: VRPP）: この問題は必ずしも全顧客を訪問する必要がない最大化問題である。目標としては各顧客に設けられた利益を時間制限の範囲内で各車両が、顧客は一度のみ訪問ができるという条件下で回収した利益の総和を最高する問題である。また車両は開始時と終了時に必ずデポに滞在しなければならない。利益付き配送計画問題の枠組みで研究されている問題としては:
  • チームオリエンテーリング問題（The Team Orienteering Problem: TOP）が VRPP の変種問題として最も研究されている^[4][5][6]。
  • 容量制約付きチームオリエンテーリング問題（The Capacitated Team Orienteering Problem: CTOP）
  • 時間枠付きチームオリエンテーリング問題（The TOP with Time Windows: TOPTW）
• 集配送計画問題（積み込み・積み降ろし型配送計画問題^[7]、Vehicle Routing Problem with Pickup and Delivery: VRPPD）: それぞれが独立した集送地と配送地を持った複数の荷物があり、これらの集配送を行う。目標としては集配送を行う地点を巡る中で最適な各車両の配送経路を求めることである。
• LIFO付き配送計画問題（Vehicle Routing Problem with LIFO）: 集配送計画問題（VRPPD）と類似した問題であるが、車両の積載に関する追加の制約が課される。これは任意の配達地点において配達される荷物は直近に積み込まれた荷物に限定されるという条件である。この条件により、配達すべき荷物以外のものを一時的に降ろす必要がなくなるため、配達地点での積み下ろしの時間が短縮される。
• 時間枠付き配送計画問題（Vehicle Routing Problem with Time Windows: VRPTW）^[8]: 配達場所ごとに配達（あるいは訪問）が可能な時刻（時間枠）が設けられた問題。
• 容量制約付き配送計画問題（積載量制約付き配送計画問題、Capacitated Vehicle Routing Problem: CVRP あるいは CVRPTW）: 各車両に荷物の積載制限の制約が設けられた問題
• 回転を考慮した配送計画問題（Vehicle Routing Problem with Multiple Trips: VRPMT）^[8]: 車両は複数個の経路を担当することを想定する。配送経路の途中でデポに立ち寄ることを想定する問題。
• パス型配送計画問題（Open Vehicle Routing Problem: OVRP）: 車両が必ずしもデポに戻ることを必要としない問題である。
• 在庫配送計画（Inventory Routing Problem: IRP）^[8]: 車両は各顧客の需要量を満たすように商品を送運経路を立案しなければならない^[9]。
• 複数デポ配送計画問題（Multi-Depot Vehicle Routing Problem: MDVRP）^[7]: 車両は開始時と終了時に複数のデポを使用することができる問題^[10]。
• トランスファー型配送計画問題（Vehicle Routing Problem with Transfers: VRPWT）: 各商品は特別に設けられたトランスファーハブによって輸送することが可能な問題である。
• 電気自動車配送計画問題（Electric Vehicle Routing Problem: EVRP）: この問題は配送計画問題の特殊ケースであり、電気自動車がかかえるバッテリー容量やその充電に関する制約を考慮する問題である。

上記の問題に対していくつかのソフトウェアベンダーが解くためのソフトウェアを提供している。

また配送計画問題はジョブショップスケジューリング問題と関連があるが、一般的にそれぞれ異なったアプローチで問題を解かれることが多い^[11]。

配送計画問題が研究として初めて明示的に扱われたのは1959年のダンツィーグおよびラムザーによってトラック配送問題として提案されたことが始まりとされる^[12]。1964年にはクラークおよびライトにより提案された「セービング法」（節約法）と呼ばれるヒューリスティックである貪欲法が提案された^[12]。セービング法は当時の大型計算機に実装され、実践による解法の有効性が示された^[12]。1970年代にはギレットとミラーにより提案されたスイープ法に挙げられるように、顧客をエリアごとにクラスター化（グルーピング）し、各クラスター内での効率の良い配送経路を求めるクラスター先・ルート後法に分類されるヒューリスティック解法が多数提案されるようになった^[13]。1980年代にはコンピュータと地理情報システムの発達により、現実問題に対する応用事例が報告されるようになった^[13]。顧客のクラスター分けを行うヒューリスティック解法においても、クラスター分けを別の最適化問題に変形して決定することで効率の良い解を求める方法がフィッシャーとジャイクマールにより提案された^[13]。1990年代には計算機のさらなる発達や、解法の性能の良し悪しを測るためのベンチマーク問題の整備がなされたことで配送計画問題の研究がより一層発展を遂げている^[14]。また、解法として古典的なヒューリスティック解法だけでなく、メタヒューリスティックスや厳密な最適解を求める厳密解法の研究に盛り上がりを見せた^[14]。

ここでは配送計画問題に対するモデリング方法として三種類取り挙げる:

1. 運搬車定式化^[15] — これは有向辺に対応する整数の変数を導入して車両が顧客間を結ぶ辺の通った状態を求める方法である。基本的な配送計画問題に対して広く用いられる定式化である。この定式化では有向辺に対応した配送費用の総和として表すことのできる問題に対して相性の良い方法となっている。しかしながら、この定式化ではより実用的な配送計画問題の例に適用することができない^[2]。
2. 品種フロー定式化^[16] — 辺、有向辺に対応した整数の変数を導入し、その上で車両の通る経路上での商品の運ばれるフローを表現する方法である。この定式化は比較的最近になって用いられる厳密解法のアプローチとなっている^[2]。
3. 集合分割定式化^[17] — 相異なる実行可能な巡回路を考え、これに対応した指数乗個の0-1変数を用いた定式化。配送計画問題においては配送計画問題の制約を満たす中で費用が最小となる巡回路の集合はどのようなものであるかという集合分割問題としてみなすことができる。この定式化ではより汎用的な配送経路にかかる費用を設定することができる^[2]。

ダンツィーグ、ファルカーソン（英語版）、ジョンソン（英語版）の巡回セールスマン問題に対する定式化を拡張した配送計画問題に対する定式化は以下の通りに表される:

${\displaystyle \min }$		${\displaystyle \sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle \sum _{i\in V}x_{ij}=1}$		${\displaystyle \forall j\in V\backslash \left\{0\right\}}$		(1)
		${\displaystyle \sum _{j\in V}x_{ij}=1}$		${\displaystyle \forall i\in V\backslash \left\{0\right\}}$		(2)
		${\displaystyle \sum _{i\in {V\backslash \left\{0\right\}}}x_{i0}=K}$				(3)
		${\displaystyle \sum _{j\in {V\backslash \left\{0\right\}}}x_{0j}=K}$				(4)
		${\displaystyle \sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S)}$		${\displaystyle \forall S\subseteq V\setminus \{0\},S\neq \emptyset }$		(5)
		${\displaystyle x_{ij}\in \{0,1\}}$		${\displaystyle \forall i,j\in V}$		(6)

この定式化において ${\displaystyle c_{ij}}$ は頂点 ${\displaystyle i}$ から頂点 ${\displaystyle j}$ への移動費用を表し、${\displaystyle x_{ij}}$ はある経路において頂点 ${\displaystyle i}$ から頂点 ${\displaystyle j}$ へ移動するとき ${\displaystyle 1}$、そうでないとき ${\displaystyle 0}$ をとる0-1変数を表す。また、${\displaystyle K}$ は利用可能な車両数の数を表し、${\displaystyle r(S)}$ は顧客の部分集合 ${\displaystyle S}$ への需要を満たすのに必要な車両数の最小値に対応している。なお、頂点 ${\displaystyle 0}$ はデポの頂点である。

ここで制約1および制約2は各顧客に対応した頂点において入る有向辺と出る有向辺の本数は必ず一つずつとなることを表している。制約3および制約4はデポの頂点から出る有向辺と入る有向辺の本数は必ず車両数の合計 ${\displaystyle K}$ と一致することを表している。制約5は容量カット制約として知られ、各経路の顧客の総需要量が車両の容量を超過しないことを保証している。最後に、制約6は整数条件を表している^[2]。

制約1および制約2の計 ${\displaystyle 2|V|}$ 個の制約のうち任意の一つは他の ${\displaystyle 2|V|-1}$ 個の制約によって暗示的に満たされるため、制約1、2から制約の一つを取り除くことができる。それぞれの顧客の部分集合 ${\displaystyle S}$ に対するカット制約では r(S)（集合 ${\displaystyle S}$ 内での荷物の総需要量を輸送するために必要な最小の車両数）以上の有向辺を持たなければならないことを意味している^[2]。この r(S) を厳密に求めることは配送計画問題と同様にNP困難な問題として知られるビンパッキング問題を解くことで求められるため、厳密な値を求めることは難しいとされる^[18]。このことから、r(S) は集合 ${\displaystyle S}$ 内の総需要量 ${\displaystyle \sum _{i\in S}q_{i}}$（${\displaystyle q_{i}}$ は各顧客 ${\displaystyle i}$ に対応する需要量）を車両の最大積載容量 ${\displaystyle Q}$ で割った ${\displaystyle \lceil {\frac {\sum _{i\in S}q_{i}}{Q}}\rceil }$ による推定値で代用されることが多い^[18]。

他の定式化として容量カット制約の代わりに部分巡回路除去制約（generalised subtour elimination constraints: GSECs）を一般化した制約を用いることができる:

${\displaystyle \sum _{i\in S}\sum _{j\in S}x_{ij}\leq |S|-r(S)}$

このとき、顧客の部分集合の ${\displaystyle S}$ からは少なくとも r(S) 個の有向辺が ${\displaystyle S}$ に含まれない顧客のいずれかに接続しなければならないことを表している^[2]。

GCECs および CCCs では、指数乗個の制約が含まれるため、大規模な問題では定式化を解くために必要な線形計画緩和問題を解くことがそのままでは不可能である。この問題を解消するための方法としてはこれらの制約集合を制限した（含まない）状態で問題を解き、必要に応じて適切な制約を追加していく手法が挙げられる。必要に応じて追加する制約の特定方法は分離手順によって行われる。このような逐次制約を追加していく(混合整数計画問題に基づいた)効率の良い分離手法が知られている^[19]。

また異なる方法としては巡回セールスマン問題で初めて提案され、後にクリストフィード、ミンゴッツィ、トスによって拡張されたMTZ制約と呼ばれる非負の整数の解集合を持つ制約を用いる方法である^[20][21]。

${\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})}$		${\displaystyle \forall i,j\in V\backslash \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}$
${\displaystyle 0\leq u_{i}\leq C-d_{i}}$		${\displaystyle \forall i\in V\backslash \{0\}}$

ただし、${\displaystyle u_{i},~i\in V\backslash \{0\}}$ は顧客 ${\displaystyle i}$ を訪れた際にそれまでに運送し終えた荷物の累計の量に対応する追加の変数であり、${\displaystyle d_{i}}$ は顧客 ${\displaystyle i}$ に対する需要量を表している。これらの制約によって経路の連結性と容量の制約が課せられる。${\displaystyle x_{ij}=0}$ のときは、顧客 ${\displaystyle i}$ においては ${\displaystyle u_{i}\leq C}$ であり、${\displaystyle u_{j}\geq d_{j}}$ であるため、束縛されない状態となり、${\displaystyle x_{ij}=1}$ のときは、${\displaystyle u_{j}\geq u_{i}+d_{j}}$ という制約が課せられる。

これらの方法による定式化は基本的な配送計画問題（VRP、CVRP、VRPB）に広く適用されてきた。しかしながら、これらの方法では簡潔な問題に対してのみ適用することができない。例としては、運送にかかる費用が車両が通る経路の顧客間の辺に対応し、その総和として表される場合にのみ適用が可能である。また、これらの定式化ではどの車両がどの経路を担当するかということが求められないことが問題として挙げられる。したがって、費用や実行可能性が顧客の性質や車両の属性に依存して求まるような問題ではこれらの定式化をそのまま適用することが不可能である^[2]。

集合分割定式化はバリンスキーおよびクヴァントにより提案された定式化である^[22]。これはあらかじめ車両が配送を行える配送経路を列挙し、この配送経路の集まりの中から目的関数が最小となるような組合せを考える方法である^[22]。この方法により表される定式化が同じ組合せ最適化問題の一種である集合分割問題に帰着させることができることから、このような名称が付けられている^[22]。ここで、車両が配送を行える実行可能な配送経路の集合を ${\displaystyle R}$ とする。集合 ${\displaystyle R}$ は、ある配送経路 ${\displaystyle r\in R}$ において訪れる顧客の集合を ${\displaystyle V_{r}}$とすると、${\displaystyle \sum _{i\in V_{r}}q_{i}\leq Q}$ を満たさなければならない^[22]。すなわち、車両が配送を行える配送経路は車両の容量に関する制限などが厳密に守られるもののみの集合である。また、${\displaystyle a_{ir}}$ をある配送経路 ${\displaystyle r}$ において顧客 ${\displaystyle i}$ を訪れるとき ${\displaystyle 1}$、そうでないとき ${\displaystyle 0}$ をとる行列の要素とし、${\displaystyle d_{r}}$ をある車両が配送経路 ${\displaystyle r}$ を巡回するにかかる費用とする^[23]。このとき、定式化は以下の通りに与えられる^[17]:

${\displaystyle \min }$		${\displaystyle \sum _{r\in R}d_{r}z_{r}}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle \sum _{r\in R}a_{ir}z_{r}=1}$		${\displaystyle \forall i\in V}$
		${\displaystyle \sum _{r\in R}z_{r}=K}$
		${\displaystyle z_{r}\in \{0,1\}}$		${\displaystyle \forall r\in R}$

目的関数は、ある車両が配送経路 ${\displaystyle r}$ を採用したときに、それに付随する費用 ${\displaystyle d_{r}}$ を足し合わせることを意味している。一つ目の制約は、各顧客 ${\displaystyle i}$ には必ず一つの車両が訪れることを表している^[24]。この制約は等式であるが、これの代わりに不等式の ${\displaystyle \sum _{r\in R}a_{ir}z_{r}\geq 1\quad \forall i\in V}$ を用いることがある^[24]。移動にかかる費用がユークリッド距離のような単純な場合^{[注釈 2]}には、制約を不等式に置き換えても同等の最適な配送経路を求めることが可能であるため、しばしば採用されることがある^[24]。二つ目の制約は採用される配送経路の総数はちょうど車両の数の合計 ${\displaystyle K}$ と一致することを表している^[24]。この制約を加えると厳密には集合分割問題の枠組みではなくなるが、この制約を含んでいたとしても集合分割問題を解くための解法が適用できることが多い^[24]。最後の制約は変数の整数条件を表している^[24]。

集合分割定式の特徴としては、複雑な配送計画問題の類題に対しても広く適用が可能で汎用性に富んだ定式化であることが挙げられる^[25]。また、あらかじめ実行可能な配送経路を列挙することから、実行可能な配送経路の総数が少ないような問題に対しては有効な方法となる^[25]。この定式化の応用例としては、あらかじめすべての配送経路の集合を求めず、配送経路の一部を初期の集合として定式化を与え、必要に応じて配送経路を適宜追加して最適な配送経路を求めるといった解法が編み出されている^[25]。

配送計画問題は大規模な問題を最適に解くことが難しいことから、遺伝的アルゴリズムやタブーサーチ、焼きなまし法、適応的巨大近傍探索法（ALNS）などのメタヒューリスティック解法によるアプローチの重要性が増している。近年、いくつかの研究により効率の良い配送計画問題に対するメタヒューリスティック解法によって顧客の数が数百から数千の問題例に対しても最適値からの誤差が0.5%から1%程度の値となる良好な解を求めることが可能となっている^[26]。これらの手法は類似問題に由来する複雑な制約に対しても容易に適応できる堅牢性も兼ね備えている。そのため、複雑な制約や意思決定を伴う大規模な応用事例においてはメタヒューリスティック解法の適用が行われやすい。

• 久保幹夫 著「第16章　運搬経路問題」、久保幹夫、田村明久、松井知己 編『応用数理計画ハンドブック』（1版）、2002年、983-1080頁。CRID 1130000795637802368。ISBN 4254270046。 NCID BA56729727。OCLC 674964887。 
• Oliveira, H.C.B.de; Vasconcelos, G.C. (2008). “A hybrid search method for the vehicle routing problem with time windows”. Annals of Operations Research 180: 125–144. doi:10.1007/s10479-008-0487-y. 
• Frazzoli, E.; Bullo, F. (2004). “Decentralized algorithms for vehicle routing in a stochastic time-varying environment”. 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601). 4. IEEE. pp. 3357–3363. doi:10.1109/CDC.2004.1429220. ISBN 0-7803-8682-5. ISSN 0191-2216 
• Psaraftis, H.N. (1988). “Dynamic vehicle routing problems”. Vehicle Routing: Methods and Studies 16: 223–248. http://www.martrans.org/documents/2008/rst/dvrp%20psaraftis%2088.pdf. 
• Bertsimas, D.J.; Van Ryzin, G. (1991). “A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane”. Operations Research 39 (4): 601–615. doi:10.1287/opre.39.4.601. hdl:1721.1/2353. JSTOR 171167. 
• “Heuristics for multi-attribute vehicle routing problems: A survey and synthesis”. European Journal of Operational Research 231 (1): 1–21. (2013). doi:10.1016/j.ejor.2013.02.053. https://www.cirrelt.ca/documentstravail/cirrelt-2012-05.pdf. 
• Hirotaka, Irie; Wongpaisarnsin, Goragot; Terabe, Masayoshi; Miki, Akira; Taguchi, Shinichirou (2019). "Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity". arXiv:1903.06322 [quant-ph]。

• 巡回セールスマン問題
• 中国人郵便配達問題