Transportation theory (mathematics)

In mathematics and economics, transportation theory or transport theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French mathematician Gaspard Monge in 1781.[1]

In the 1920s A.N. Tolstoi was one of the first to study the transportation problem mathematically. In 1930, in the collection Transportation Planning Volume I for the National Commissariat of Transportation of the Soviet Union, he published a paper "Methods of Finding the Minimal Kilometrage in Cargo-transportation in space".[2][3]

Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich.[4] Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem.[5] The linear programming formulation of the transportation problem is also known as the Hitchcock–Koopmans transportation problem.[6]

Motivation

Mines and factories

Suppose that we have a collection of n mines mining iron ore, and a collection of n factories which use the iron ore that the mines produce. Suppose for the sake of argument that these mines and factories form two disjoint subsets M and F of the Euclidean plane R². Suppose also that we have a cost function c : R² × R² → [0, ∞), so that c(x, y) is the cost of transporting one shipment of iron from x to y. For simplicity, we ignore the time taken to do the transporting. We also assume that each mine can supply only one factory (no splitting of shipments) and that each factory requires precisely one shipment to be in operation (factories cannot work at half- or double-capacity). Having made the above assumptions, a transport plan is a bijection T : M → F. In other words, each mine m ∈ M supplies precisely one factory T(m) ∈ F and each factory is supplied by precisely one mine. We wish to find the optimal transport plan, the plan T whose total cost

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

is the least of all possible transport plans from M to F. This motivating special case of the transportation problem is an instance of the assignment problem. More specifically, it is equivalent to finding a minimum weight matching in a bipartite graph.

Moving books: the importance of the cost function

The following simple example illustrates the importance of the cost function in determining the optimal transport plan. Suppose that we have n books of equal width on a shelf (the real line), arranged in a single contiguous block. We wish to rearrange them into another contiguous block, but shifted one book-width to the right. Two obvious candidates for the optimal transport plan present themselves:

1. move all n books one book-width to the right ("many small moves");
2. move the left-most book n book-widths to the right and leave all other books fixed ("one big move").

If the cost function is proportional to Euclidean distance (c(x, y) = α|x − y|) then these two candidates are both optimal. If, on the other hand, we choose the strictly convex cost function proportional to the square of Euclidean distance (c(x, y) = α|x − y|²), then the "many small moves" option becomes the unique minimizer.

Hitchcock problem

The following transportation problem formulation is credited to F. L. Hitchcock:[7]

Suppose there are m sources ${\displaystyle x_{1},...x_{m}}$ for a commodity, with ${\displaystyle a(x_{i})}$ units of supply at x_i and n sinks ${\displaystyle y_{1},...y_{n}}$ for the commodity, with the demand ${\displaystyle b(y_{j})}$ at y_j. If ${\displaystyle a(x_{i},\ y_{j})}$ is the unit cost of shipment from x_i to y_j, find a flow that satisfies demand from supplies and minimizes the flow cost.

This challenge in logistics was taken up by D. R. Fulkerson[8] and in the book Flows in Networks (1962) written with L. R. Ford Jr..[9]

Tjalling Koopmans is also credited with formulations of transport economics and allocation of resources.

Abstract formulation of the problem

Monge and Kantorovich formulations

The transportation problem as it is stated in modern or more technical literature looks somewhat different because of the development of Riemannian geometry and measure theory. The mines-factories example, simple as it is, is a useful reference point when thinking of the abstract case. In this setting, we allow the possibility that we may not wish to keep all mines and factories open for business, and allow mines to supply more than one factory, and factories to accept iron from more than one mine.

Let X and Y be two separable metric spaces such that any probability measure on X (or Y) is a Radon measure (i.e. they are Radon spaces). Let c : X × Y → [0, ∞] be a Borel-measurable function. Given probability measures μ on X and ν on Y, Monge's formulation of the optimal transportation problem is to find a transport map T : X → Y that realizes the infimum

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

where T_∗(μ) denotes the push forward of μ by T. A map T that attains this infimum (i.e. makes it a minimum instead of an infimum) is called an "optimal transport map".

Monge's formulation of the optimal transportation problem can be ill-posed, because sometimes there is no T satisfying T_∗(μ) = ν: this happens, for example, when μ is a Dirac measure but ν is not.

We can improve on this by adopting Kantorovich's formulation of the optimal transportation problem, which is to find a probability measure γ on X × Y that attains the infimum

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

where Γ(μ, ν) denotes the collection of all probability measures on X × Y with marginals μ on X and ν on Y. It can be shown[10] that a minimizer for this problem always exists when the cost function c is lower semi-continuous and Γ(μ, ν) is a tight collection of measures (which is guaranteed for Radon spaces X and Y). (Compare this formulation with the definition of the Wasserstein metric W₁ on the space of probability measures.) A gradient descent formulation for the solution of the Monge–Kantorovich problem was given by Sigurd Angenent, Steven Haker, and Allen Tannenbaum.[11]

Duality formula

The minimum of the Kantorovich problem is equal to

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

where the supremum runs over all pairs of bounded and continuous functions ${\displaystyle \varphi :X\rightarrow \mathbf {R} }$ and ${\displaystyle \psi :Y\rightarrow \mathbf {R} }$ such that

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

Solution of the problem

Optimal transportation on the real line

Optimal transportation matrix

Continuous optimal transport

For ${\displaystyle 1\leq p<\infty }$, let ${\displaystyle {\mathcal {P}}_{p}(\mathbf {R} )}$ denote the collection of probability measures on ${\displaystyle \mathbf {R} }$ that have finite ${\displaystyle p}$-th moment. Let ${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbf {R} )}$ and let ${\displaystyle c(x,y)=h(x-y)}$, where ${\displaystyle h:\mathbf {R} \rightarrow [0,\infty )}$ is a convex function.

1. If ${\displaystyle \mu }$ has no atom, i.e., if the cumulative distribution function ${\displaystyle F_{\mu }=\mathbf {R} \rightarrow [0,1]}$ of ${\displaystyle \mu }$ is a continuous function, then ${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbf {R} \to \mathbf {R} }$ is an optimal transport map. It is the unique optimal transport map if ${\displaystyle h}$ is strictly convex.
2. We have

${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\int _{\mathbf {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.}$

The proof of this solution appears in.[12]

Separable Hilbert spaces

Let ${\displaystyle X}$ be a separable Hilbert space. Let ${\displaystyle {\mathcal {P}}_{p}(X)}$ denote the collection of probability measures on ${\displaystyle X}$ such that have finite ${\displaystyle p}$-th moment; let ${\displaystyle {\mathcal {P}}_{p}^{r}(X)}$ denote those elements ${\displaystyle \mu \in {\mathcal {P}}_{p}(X)}$ that are Gaussian regular: if ${\displaystyle g}$ is any strictly positive Gaussian measure on ${\displaystyle X}$ and ${\displaystyle g(N)=0}$, then ${\displaystyle \mu (N)=0}$ also.

Let ${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$, ${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$, ${\displaystyle c(x,y)=|x-y|^{p}/p}$ for ${\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}$. Then the Kantorovich problem has a unique solution ${\displaystyle \kappa }$, and this solution is induced by an optimal transport map: i.e., there exists a Borel map ${\displaystyle r\in L^{p}(X,\mu ;X)}$ such that

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

Moreover, if ${\displaystyle \nu }$ has bounded support, then

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

for ${\displaystyle \mu }$-almost all ${\displaystyle x\in X}$ for some locally Lipschitz, c-concave and maximal Kantorovich potential ${\displaystyle \varphi }$. (Here ${\displaystyle \nabla \varphi }$ denotes the Gateaux derivative of ${\displaystyle \varphi }$.)

Applications

The Monge–Kantorovich optimal transport has found applications in wide range in different fields. Among them are:

• Image registration and warping [13]
• Reflector design [14]
• Retrieving information from shadowgraphy and proton radiography [15]
• Seismic tomography and reflection seismology [16]

See also

• Wasserstein metric
• Transport function
• Hungarian algorithm
• Transportation planning
• Earth mover's distance

References

1. G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666–704, 1781.
2. Schrijver, Alexander, Combinatorial Optimization, Berlin ; New York : Springer, 2003. ISBN 3540443894. Cf. p.362
3. Ivor Grattan-Guinness, Ivor, Companion encyclopedia of the history and philosophy of the mathematical sciences, Volume 1, JHU Press, 2003. Cf. p.831
4. L. Kantorovich. On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942.
5. Cédric Villani (2003). Topics in Optimal Transportation. American Mathematical Soc. p. 66. ISBN 978-0-8218-3312-4.
6. Singiresu S. Rao (2009). Engineering Optimization: Theory and Practice (4th ed.). John Wiley & Sons. p. 221. ISBN 978-0-470-18352-6.
7. Frank L. Hitchcock (1941) "The distribution of a product from several sources to numerous localities", MIT Journal of Mathematics and Physics 20:224–230 MR0004469.
8. D. R. Fulkerson (1956) Hitchcock Transportation Problem, RAND corporation.
9. L. R. Ford Jr. & D. R. Fulkerson (1962) § 3.1 in Flows in Networks, page 95, Princeton University Press
10. L. Ambrosio, N. Gigli & G. Savaré. Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel. (2005)
11. Angenent, S.; Haker, S.; Tannenbaum, A. (2003). "Minimizing flows for the Monge–Kantorovich problem". SIAM J. Math. Anal. 35 (1): 61–97. CiteSeerX 10.1.1.424.1064. doi:10.1137/S0036141002410927.
12. Rachev, Svetlozar T., and Ludger Rüschendorf. Mass Transportation Problems: Volume I: Theory. Vol. 1. Springer, 1998.
13. Haker, Steven; Zhu, Lei; Tannenbaum, Allen; Angenent, Sigurd (1 December 2004). "Optimal Mass Transport for Registration and Warping". International Journal of Computer Vision. 60 (3): 225–240. CiteSeerX 10.1.1.59.4082. doi:10.1023/B:VISI.0000036836.66311.97. ISSN 0920-5691.
14. Glimm, T.; Oliker, V. (1 September 2003). "Optical Design of Single Reflector Systems and the Monge–Kantorovich Mass Transfer Problem". Journal of Mathematical Sciences. 117 (3): 4096–4108. doi:10.1023/A:1024856201493. ISSN 1072-3374.
15. Kasim, Muhammad Firmansyah; Ceurvorst, Luke; Ratan, Naren; Sadler, James; Chen, Nicholas; Sävert, Alexander; Trines, Raoul; Bingham, Robert; Burrows, Philip N. (16 February 2017). "Quantitative shadowgraphy and proton radiography for large intensity modulations". Physical Review E. 95 (2): 023306. arXiv:1607.04179. Bibcode:2017PhRvE..95b3306K. doi:10.1103/PhysRevE.95.023306. PMID 28297858.
16. Metivier, Ludovic (24 February 2016). "Measuring the misfit between seismograms using an optimal transport distance: application to full waveform inversion". Geophysical Journal International. 205 (1): 345–377. doi:10.1093/gji/ggw014.

Further reading

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.