輸送理論（数学）

数学と経済学 において、輸送理論または輸送理論は、最適な輸送と資源の配分の研究に付けられた名前です。この問題は、1781年にフランスの数学者 ガスパール・モンジュによって形式化されました。^[1]

1920年代、ANトルストイは輸送問題を数学的に研究した最初の人物の一人であった。1930年、ソ連国家運輸委員会のコレクション「輸送計画第1巻」の中で、彼は論文「宇宙での貨物輸送の最小距離を求める方法」を発表した。^{[2] [3]}

この分野は第二次世界大戦中にソ連の数学者で経済学者のレオニード・カントロヴィッチによって大きな進歩を遂げました。^[4]そのため、この問題はモンジュ・カントロヴィッチ輸送問題と呼ばれることもあります。^{[5]輸送問題の}線形計画法による定式化は、ヒッチコック・クープマンス輸送問題としても知られています。^[6]

鉄鉱石を採掘する鉱山の集合と、鉱山で生産される鉄鉱石を使用する工場の集合があるとします。議論のために、これらの鉱山と工場がユークリッド平面の2 つの互いに素な部分集合とを形成するとします。また、コスト関数があり、 がからへの 1 回の鉄の出荷を輸送するコストであるとします。簡単にするために、輸送にかかる時間は無視します。また、各鉱山は 1 つの工場にしか供給できず (出荷を分割しない)、各工場は正確に 1 回の出荷を稼働させる必要があると仮定します (工場は半分または 2 倍の能力で稼働することはできない)。上記の仮定を行った上で、輸送計画は一対一です。つまり、各鉱山は正確に 1 つの対象工場に供給し、各工場は正確に 1 つの鉱山から供給されます。最適な輸送計画を見つけたいとします。これは、総コストが${\displaystyle m}$${\displaystyle n}$ ${\displaystyle M}$${\displaystyle F}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,\infty )}$${\displaystyle c(x,y)}$${\displaystyle x}$${\displaystyle y}$ ${\displaystyle T:M\to F}$${\displaystyle m\in M}$${\displaystyle T(m)\in F}$${\displaystyle T}$

${\displaystyle c(T):=\sum _{m\in M}c(m,T(m))}$

は、 からへのすべての可能な輸送計画のうち最小のものです。輸送問題のこの特別なケースは、割り当て問題のインスタンスです。より具体的には、二部グラフで最小の重みマッチングを見つけることに相当します。 ${\displaystyle M}$${\displaystyle F}$

次の簡単な例は、最適な輸送計画を決定する際のコスト関数の重要性を示しています。棚 (実線)に幅の等しい本が1 つの連続したブロックに並べられているとします。これらの本を別の連続したブロックに並べ替えたいのですが、1 冊分の幅だけ右にずらします。最適な輸送計画の候補として、次の 2 つが考えられます。 ${\displaystyle n}$

1. すべての本を 1 冊分右に移動する (「小さな移動を多数」)。${\displaystyle n}$
2. 一番左の本の幅を右に移動し、他のすべての本は固定したままにします (「1 つの大きな移動」)。${\displaystyle n}$

コスト関数がユークリッド距離に比例する場合 ( ) 、これら 2 つの候補は両方とも最適です。一方、ユークリッド距離の 2 乗に比例する厳密に凸なコスト関数を選択した場合 ( ) 、 "多数の小さな移動" オプションが唯一の最小化関数になります。 ${\displaystyle c(x,y)=\alpha \|x-y\|}$${\displaystyle \alpha >0}$${\displaystyle c(x,y)=\alpha \|x-y\|^{2}}$${\displaystyle \alpha >0}$

上記のコスト関数は、本が移動する水平距離のみを考慮しており、各本を持ち上げて所定の位置に移動するために使用される装置が移動する水平距離は考慮していないことに注意してください。後者を考慮すると、2 つの輸送計画のうち、2 番目の輸送計画は常にユークリッド距離に対して最適ですが、少なくとも 3 冊の本がある場合、最初の輸送計画は 2 乗ユークリッド距離に対して最適です。

以下の輸送問題の定式化はFLヒッチコックによるものである^[7]。

ある商品の供給元がで、その商品の需要がであるとします。 が から への出荷単位コストである場合、供給元から需要を満たし、フローコストを最小化するフローを見つけます。物流におけるこの課題は、DR Fulkerson ^[8]と、 LR Ford Jr. ^[9]との共著による書籍Flows in Networks (1962)で取り上げられました。${\displaystyle m}$${\displaystyle x_{1},\ldots ,x_{m}}$${\displaystyle a(x_{i})}$${\displaystyle x_{i}}$${\displaystyle n}$${\displaystyle y_{1},\ldots ,y_{n}}$${\displaystyle b(y_{j})}$${\displaystyle y_{j}}$${\displaystyle c(x_{i},\ y_{j})}$${\displaystyle x_{i}}$${\displaystyle y_{j}}$

チャリング・クープマンスは、交通経済学と資源配分 の定式化でも知られています。

現代の、あるいはより技術的な文献で述べられている輸送問題は、リーマン幾何学と測度論の発展により、多少異なって見えます。鉱山と工場の例は、単純ではありますが、抽象的なケースを考える際の便利な参照点となります。この設定では、すべての鉱山と工場を営業したままにしておく必要がない可能性を考慮し、鉱山が複数の工場に鉄を供給し、工場が複数の鉱山から鉄を受け入れることを許可します。

とを2つの分離可能な計量空間とし、 (または)上の任意の確率測度がラドン測度となる(つまり、これらはラドン空間である)ものとする。をボレル測定可能な関数とする。と上の確率測度が与えられたとき、モンジュの最適輸送問題の定式化は、下限値を実現する輸送マップを見つけることである。${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle X}$${\displaystyle Y}$${\displaystyle c:X\times Y\to [0,\infty )}$${\displaystyle \mu }$${\displaystyle X}$${\displaystyle \nu }$${\displaystyle Y}$${\displaystyle T:X\to Y}$

${\displaystyle \inf \left\{\left.\int _{X}c(x,T(x))\,\mathrm {d} \mu (x)\right|T_{*}(\mu )=\nu \right\},}$

ここで、 はによるの押し出しを表します。この最小値を達成するマップ（つまり、を最小値ではなく最小値にするマップ）は、「最適輸送マップ」と呼ばれます。 ${\displaystyle T_{*}(\mu )}$${\displaystyle \mu }$${\displaystyle T}$${\displaystyle T}$

モンジュの最適輸送問題の定式化は、満足するが存在しない場合があるので、不適切となる場合があります。これは、たとえば、がディラック測度であるが ではない場合に発生します。 ${\displaystyle T}$${\displaystyle T_{*}(\mu )=\nu }$${\displaystyle \mu }$${\displaystyle \nu }$

これを改善するために、カントロヴィッチの最適輸送問題の定式化を採用することができる。これは、最小値を達成する 確率測度を見つけることである。${\displaystyle \gamma }$${\displaystyle X\times Y}$

${\displaystyle \inf \left\{\left.\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right|\gamma \in \Gamma (\mu ,\nu )\right\},}$

ここで、 はおよび上の周辺値を持つ上のすべての確率測度の集合を表します。この問題の最小化関数は、コスト関数が下半連続で、 が測度の密な集合であるとき常に存在することが示されています (これは、ラドン空間およびに対して保証されています)。 (この定式化を確率測度の空間上のワッサーシュタイン計量の定義と比較してください^。)モンジュ–カントロビッチ問題の解法の勾配降下法の定式化は、シグルド・アンジェネント、スティーブン・ヘイカー、アレン・タンネンバウムによって与えられました。^[11]${\displaystyle \Gamma (\mu ,\nu )}$${\displaystyle X\times Y}$ ${\displaystyle \mu }$${\displaystyle X}$${\displaystyle \nu }$${\displaystyle Y}$${\displaystyle c}$${\displaystyle \Gamma (\mu ,\nu )}$${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle W_{p}}$

カントロビッチ問題の最小値は次の式に等しい。

${\displaystyle \sup \left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\psi (y)\,\mathrm {d} \nu (y)\right),}$

ここで、上限はすべての有界かつ連続な関数 のペアと、 ${\displaystyle \varphi :X\rightarrow \mathbb {R} }$${\displaystyle \psi :Y\rightarrow \mathbb {R} }$

${\displaystyle \varphi (x)+\psi (y)\leq c(x,y).}$

符号を反転すると、経済的な解釈はより明確になります。は労働者の特性のベクトル、は企業の特性のベクトル、 は企業 とマッチした労働者によって生み出される経済生産高を表します。 と を設定すると、モンジュ・カントロビッチ問題は次のように書き換えられます。 ${\displaystyle x\in X}$${\displaystyle y\in Y}$${\displaystyle \Phi (x,y)=-c(x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle u(x)=-\varphi (x)}$${\displaystyle v(y)=-\psi (y)}$

${\displaystyle \sup \left\{\int _{X\times Y}\Phi (x,y)d\gamma (x,y),\gamma \in \Gamma (\mu ,\nu )\right\}}$

これには二重のものがあります:

${\displaystyle \inf \left\{\int _{X}u(x)\,d\mu (x)+\int _{Y}v(y)\,d\nu (y):u(x)+v(y)\geq \Phi (x,y)\right\}}$

ここで、最小値は有界かつ連続な関数および上を通ります。双対問題に解がある場合、次のことがわかります。 ${\displaystyle u:X\to \mathbb {R} }$${\displaystyle v:Y\to \mathbb {R} }$

${\displaystyle v(y)=\sup _{x}\left\{\Phi (x,y)-u(x)\right\}}$

したがって、はタイプの労働者の均衡賃金として解釈され、はタイプの企業の均衡利潤として解釈されます。^[12]${\displaystyle u(x)}$${\displaystyle x}$${\displaystyle v(y)}$${\displaystyle y}$

に対して、 は有限次のモーメントを持つ上の確率測度の集合を表すものとします。 およびとします。ここで は凸関数です。 ${\displaystyle 1\leq p<\infty }$${\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}$${\displaystyle \mathbb {R} }$${\displaystyle p}$${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )}$${\displaystyle c(x,y)=h(x-y)}$${\displaystyle h:\mathbb {R} \to [0,\infty )}$

1. にアトムがない場合、つまりの累積分布関数が連続関数である場合、 は最適な輸送マップです。が厳密に凸である場合、 は唯一の最適な輸送マップです。${\displaystyle \mu }$ ${\displaystyle F_{\mu }:\mathbb {R} \to [0,1]}$${\displaystyle \mu }$${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R} }$${\displaystyle h}$
2. 我々は持っています

${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\int _{\mathbb {R} ^{2}}c(x,y)\,\mathrm {d} \gamma (x,y)=\int _{0}^{1}c\left(F_{\mu }^{-1}(s),F_{\nu }^{-1}(s)\right)\,\mathrm {d} s.}$

この解の証明はRachev & Rüschendorf (1998)に掲載されている。^[13]

マージンとが離散的である場合、とをそれぞれとに割り当てられる確率質量とし 、割り当ての確率をとします。原始カントロビッチ問題における目的関数は、 ${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle \mu _{x}}$${\displaystyle \nu _{y}}$${\displaystyle x\in \mathbf {X} }$${\displaystyle y\in \mathbf {Y} }$${\displaystyle \gamma _{xy}}$${\displaystyle xy}$

${\displaystyle \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}}$

そして制約は次のように表される。 ${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$

${\displaystyle \sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} }$

そして

${\displaystyle \sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} .}$

これを線形計画問題に入力するには、行列の列または行を積み重ねてベクトル化する必要があります。この操作をと呼びます。列優先順序では、上記の制約は次のように書き換えられます。 ${\displaystyle \gamma _{xy}}$${\displaystyle \operatorname {vec} }$

${\displaystyle \left(1_{1\times |\mathbf {Y} |}\otimes I_{|\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\mu }$そして${\displaystyle \left(I_{|\mathbf {Y} \|}\otimes 1_{1\times |\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\nu }$

ここではクロネッカー積、はすべての要素が1であるサイズの行列、 はサイズの単位行列です。結果として、 と設定すると、問題の線形計画法定式化は次のようになります 。${\displaystyle \otimes }$${\displaystyle 1_{n\times m}}$${\displaystyle n\times m}$${\displaystyle I_{n}}$${\displaystyle n}$${\displaystyle z=\operatorname {vec} (\gamma )}$

${\displaystyle {\begin{aligned}&{\text{Minimize }}&&\operatorname {vec} (c)^{\top }z\\[4pt]&{\text{subject to:}}&&z\geq 0,\\[4pt]&&&{\begin{pmatrix}1_{1\times |\mathbf {Y} |}\otimes I_{|\mathbf {X} |}\\I_{|\mathbf {Y} |}\otimes 1_{1\times |\mathbf {X} |}\end{pmatrix}}z={\binom {\mu }{\nu }}\end{aligned}}}$

これは大規模線形計画ソルバーに簡単に入力できる（Galichon（2016）^[12]の第3.4章を参照）。

半離散的なケースでは、およびは上の連続分布ですが、 はサイトに確率質量を割り当てる離散分布です。この場合、 ^[14]から、主カントロビッチ問題と双対カントロビッチ問題はそれぞれ次のように要約されること がわかります。${\displaystyle X=Y=\mathbb {R} ^{d}}$${\displaystyle \mu }$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}$${\displaystyle \nu _{j}}$${\displaystyle y_{j}\in \mathbb {R} ^{d}}$

${\displaystyle \inf \left\{\int _{X}\sum _{j=1}^{J}c(x,y_{j})\,d\gamma _{j}(x),\gamma \in \Gamma (\mu ,\nu )\right\}}$

主項については、およびを意味し、次のようになります。 ${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$${\displaystyle \int _{X}d\gamma _{j}(x)=\nu _{j}}$${\displaystyle \sum _{j}d\gamma _{j}(x)=d\mu (x)}$

${\displaystyle \sup \left\{\int _{X}\varphi (x)d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}:\psi _{j}+\varphi (x)\leq c(x,y_{j})\right\}}$

双対の場合は、次のように書き直すことができます。

${\displaystyle \sup _{\psi \in \mathbb {R} ^{J}}\left\{\int _{X}\inf _{j}\left\{c(x,y_{j})-\psi _{j}\right\}d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}\right\}}$

これは、勾配降下法などの標準的な手法で解くことができる有限次元の凸最適化問題です。

の場合には、特定のサイトに割り当てられたの集合が凸多面体であることを示すことができる。結果として得られる構成はべき乗図と呼ばれる。^[15]${\displaystyle c(x,y)=|x-y|^{2}/2}$${\displaystyle x\in \mathbf {X} }$${\displaystyle j}$

特別な場合、、 を仮定し、 は可逆であるとする。すると、 ${\displaystyle \mu ={\mathcal {N}}(0,\Sigma _{X})}$${\displaystyle \nu ={\mathcal {N}}(0,\Sigma _{Y})}$${\displaystyle c(x,y)=|y-Ax|^{2}/2}$${\displaystyle A}$

${\displaystyle \varphi (x)=-x^{\top }\Sigma _{X}^{-1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{1/2}\Sigma _{X}^{-1/2}x/2}$

${\displaystyle \psi (y)=-y^{\top }A\Sigma _{X}^{1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{-1/2}\Sigma _{X}^{1/2}Ay/2}$

${\displaystyle T(x)=(A^{\top })^{-1}\Sigma _{X}^{-1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{1/2}\Sigma _{X}^{-1/2}x}$

この解の証明はGalichon (2016)に掲載されている。^[12]

を可分ヒルベルト空間とします。を 上の有限- 次モーメントを持つ確率測度の集合とします。 をガウス正則な要素とします。をおよび上の任意の正定値ガウス測度とすると、も成り立ちます。 ${\displaystyle X}$ ${\displaystyle {\mathcal {P}}_{p}(X)}$${\displaystyle X}$${\displaystyle p}$${\displaystyle {\mathcal {P}}_{p}^{r}(X)}$${\displaystyle \mu \in {\mathcal {P}}_{p}(X)}$${\displaystyle g}$ ${\displaystyle X}$${\displaystyle g(N)=0}$${\displaystyle \mu (N)=0}$

、についてとします。すると、カントロビッチ問題には唯一の解 があり、この解は最適輸送写像によって誘導されます。つまり、次のような ボレル写像が存在するのです。${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$${\displaystyle c(x,y)=|x-y|^{p}/p}$${\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}$${\displaystyle \kappa }$${\displaystyle r\in L^{p}(X,\mu ;X)}$

${\displaystyle \kappa =(\mathrm {id} _{X}\times r)_{*}(\mu )\in \Gamma (\mu ,\nu ).}$

さらに、が有界サポートを持つ場合、 ${\displaystyle \nu }$

${\displaystyle r(x)=x-|\nabla \varphi (x)|^{q-2}\,\nabla \varphi (x)}$

に対して、局所的にリプシッツ、-凹、最大カントロビッチポテンシャルに対して、ほぼすべて となります。(ここで はのガトー導関数を表します。) ${\displaystyle \mu }$${\displaystyle x\in X}$${\displaystyle c}$${\displaystyle \varphi }$${\displaystyle \nabla \varphi }$${\displaystyle \varphi }$

上記の離散問題の変形として、主問題の目的関数にエントロピー正則化項を追加したものを考える。

${\displaystyle {\begin{aligned}&{\text{Minimize }}\sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}+\varepsilon \gamma _{xy}\ln \gamma _{xy}\\[4pt]&{\text{subject to: }}\\[4pt]&\gamma \geq 0\\[4pt]&\sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} \\[4pt]&\sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} \end{aligned}}}$

双対正規化問題は、

${\displaystyle \max _{\varphi ,\psi }\sum _{x\in \mathbf {X} }\varphi _{x}\mu _{x}+\sum _{y\in \mathbf {Y} }\psi _{y}v_{y}-\varepsilon \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)}$

ここで、正規化されていないバージョンと比較すると、以前の双対（）の「ハード」制約は、その制約の「ソフト」ペナルティ（項の合計）に置き換えられています。双対問題における最適条件は次のように表すことができます。 ${\displaystyle \varphi _{x}+\psi _{y}-c_{xy}\geq 0}$${\displaystyle \varepsilon \exp \left((\varphi _{x}+\psi _{y}-c_{xy})/\varepsilon \right)}$

式5.1: ${\displaystyle \mu _{x}=\sum _{y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall x\in \mathbf {X} }$

式5.2: ${\displaystyle \nu _{y}=\sum _{x\in \mathbf {X} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall y\in \mathbf {Y} }$

を項の行列として表すと、双対を解くことは、およびとなる、それぞれサイズがおよびの２つの対角正行列およびを探すことと同等です。このような行列の存在はシンクホーンの定理を一般化し、行列はシンクホーン・クノップアルゴリズム^[16]を使用して計算できます。このアルゴリズムは、単に を繰り返し探して式5.1を解き、 を繰り返し探して式5.2を解きます。したがって、シンクホーン・クノップのアルゴリズムは、双対正規化問題に対する 座標降下アルゴリズムです。${\displaystyle A}$${\displaystyle |\mathbf {X} |\times |\mathbf {Y} |}$${\displaystyle A_{xy}=\exp \left(-c_{xy}/\varepsilon \right)}$${\displaystyle D_{1}}$${\displaystyle D_{2}}$${\displaystyle |\mathbf {X} |}$${\displaystyle |\mathbf {Y} |}$${\displaystyle D_{1}AD_{2}1_{|\mathbf {Y} |}=\mu }$${\displaystyle (D_{1}AD_{2})^{\top }1_{|\mathbf {X} |}=\nu }$${\displaystyle \varphi _{x}}$${\displaystyle \psi _{y}}$

Monge-Kantorovich 最適輸送は、さまざまな分野で幅広く応用されています。その例としては、次のものがあります。

• 画像登録とワーピング^[17]
• 反射鏡の設計^[18]
• シャドウグラフィーと陽子線撮影からの情報取得^[19]
• 地震トモグラフィーと反射地震学^[20]
• 総代替特性を含む経済モデリングの広範なクラス（マッチングモデルや離散選択モデルなど）。

ウィキメディア・コモンズには、輸送理論に関連するメディアがあります。

• ワッサーシュタイン計量法
• 輸送機能
• ハンガリーアルゴリズム
• 交通計画
• 地球移動距離
• モンジュ・アンペール方程式

• Brualdi, Richard A. (2006).組み合わせ行列クラス. 数学とその応用百科事典. 第108巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-86565-4.ZBL1106.05001  。​