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.
Article
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.
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".
Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich. Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem. The linear programming formulation of the transportation problem is also known as the Hitchcock–Koopmans transportation problem.
Contents
Motivation
Mines and factories
Suppose that we have a collection of
m
{\displaystyle m}
mines mining iron ore, and a collection of
n
{\displaystyle 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
{\displaystyle M}
and
F
{\displaystyle F}
of the Euclidean plane
R
2
{\displaystyle \mathbb {R} ^{2}}
. Suppose also that we have a cost function
c
:
R
2
×
R
2
→
[
0
,
∞
)
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
{\displaystyle 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:
move all
n
{\displaystyle n}
books one book-width to the right ("many small moves");
move the left-most book
n
{\displaystyle 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
−
Hitchcock problem
The following transportation problem formulation is credited to F. L. Hitchcock:
Suppose there are
m
{\displaystyle m}
sources
x
1
,
…
,
x
m
{\displaystyle x_{1},\ldots ,x_{m}}
for a commodity, with
a
(
x
i
)
{\displaystyle a(x_{i})}
units of supply at
x
i
{\displaystyle x_{i}}
and
n
{\displaystyle n}
sinks
y
1
,
…
,
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
{\displaystyle X}
and
Y
{\displaystyle Y}
be two separable metric spaces such that any probability measure on
X
{\displaystyle X}
(or
Y
{\displaystyle Y}
) is a Radon measure (i.e. they are Radon spaces). Let
c
:
X
×
Y
→
[
0
,
∞
)
{\displaystyle c:X\times Y\to [0,\infty )}
Cost duality
Given a cost function
c
(
x
,
y
)
{\displaystyle c(x,y)}
, it produces a duality transformation
ψ
↦
ψ
c
{\displaystyle \psi \mapsto \psi ^{c}}
defined by
ψ
c
(
y
)
:=
inf
x
(
c
(
x
,
y
)
−
ψ
(
x
)
)
Existence and uniqueness
Under fairly permissive assumptions, optimal transport plan exists.If
is lower semicontinuous, and there exists some upper semicontinuous functions
a
∈
L
1
Stability
The optimal transportation is stable in the following sense:Assume that
(
X
,
μ
)
,
(
Y
,
ν
)
{\displaystyle (X,\mu ),(Y,\nu )}
are Polish probability spaces,
c
:
X
×
Y
→
R
{\displaystyle c:X\times Y\to \mathbb {R} }
is continuous, and
inf
c
{\displaystyle \inf c}
is finite. Given a sequence of continuous functions
c
:
X
×
Y
→
Economic interpretation
The optimal transport problem has an economic interpretation. Cédric Villani recounts the following interpretation from Luis Caffarelli:Suppose you want to ship some coal from mines, distributed as
μ
{\displaystyle \mu }
, to factories, distributed as
ν
{\displaystyle \nu }
. The cost function of transport is
c
{\displaystyle c}
. Now a shipper comes and offers to do the transport for you. You would pay him
is the cost of transporting one shipment of iron from
x
{\displaystyle x}
to
y
{\displaystyle 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
{\displaystyle T:M\to F}
.
In other words, each mine
m
∈
M
{\displaystyle m\in M}
supplies precisely one target factory
T
(
m
)
∈
F
{\displaystyle T(m)\in F}
and each factory is supplied by precisely one mine.
We wish to find the optimal transport plan, the plan
T
{\displaystyle T}
whose total cost
c
(
T
)
:=
∑
m
∈
M
c
(
m
,
T
(
m
)
)
{\displaystyle c(T):=\sum _{m\in M}c(m,T(m))}
is the least of all possible transport plans from
M
{\displaystyle M}
to
F
{\displaystyle 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.
This can be generalized to the continuous case, where there are infinitely many mines and factories distributed on the real line, or generally in any metric space. This case is usually pictured as "changing the shape of a pile of dirt", and thus called the earth mover's problem.
y
‖
{\displaystyle c(x,y)=\alpha \|x-y\|}
for some
α
>
0
{\displaystyle \alpha >0}
) 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
‖
2
{\displaystyle c(x,y)=\alpha \|x-y\|^{2}}
for some
α
>
0
{\displaystyle \alpha >0}
), then the "many small moves" option becomes the unique minimizer.
Note that the above cost functions consider only the horizontal distance traveled by the books, not the horizontal distance traveled by a device used to pick each book up and move the book into position. If the latter is considered instead, then, of the two transport plans, the second is always optimal for the Euclidean distance, while, provided there are at least 3 books, the first transport plan is optimal for the squared Euclidean distance.
y
n
{\displaystyle y_{1},\ldots ,y_{n}}
for the commodity, with the demand
b
(
y
j
)
{\displaystyle b(y_{j})}
at
y
j
{\displaystyle y_{j}}
. If
c
(
x
i
,
y
j
)
{\displaystyle c(x_{i},\ y_{j})}
is the unit cost of shipment from
x
i
{\displaystyle x_{i}}
to
y
j
{\displaystyle 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 and in the book Flows in Networks (1962) written with L. R. Ford Jr.
Tjalling Koopmans is also credited with formulations of transport economics and allocation of resources.
be a Borel-measurable function. Given probability measures
μ
{\displaystyle \mu }
on
X
{\displaystyle X}
and
ν
{\displaystyle \nu }
on
Y
{\displaystyle Y}
, Monge's formulation of the optimal transportation problem is to find a transport map
Consider the second case, where we can actually arrive at an exactly optimal plan, instead of merely getting closer and closer. In this case, an optimal transport plan
.Similarly, the optimal transport map is also stable.Assume that
(
X
,
μ
)
,
(
Y
,
ν
)
{\displaystyle (X,\mu ),(Y,\nu )}
are Polish probability spaces,
X
{\displaystyle X}
is locally compact,
c
:
X
×
Y
→
R
{\displaystyle c:X\times Y\to \mathbb {R} }
is lower semicontinuous, and
inf
c
{\displaystyle \inf c}
is finite. Given a sequence of lower semicontinuous functions
c
:
X
×
Y
→
R
{\displaystyle c:X\times Y\to \mathbb {R} }
converging uniformly to
c
{\displaystyle c}
over
X
×
Y
{\displaystyle X\times Y}
, a sequence
ν
k
→
ν
{\displaystyle \nu _{k}\to \nu }
weakly,
.
For you to accept the deal, the price schedule must satisfy
f
(
x
)
+
g
(
y
)
≤
c
(
x
,
y
)
{\displaystyle f(x)+g(y)\leq c(x,y)}
. The Kantorovich duality states that the shipper can make a price schedule that makes you pay almost as much as you would ship yourself.In the interpretation, the duality transformation transforms a loading cost function
φ
(
x
)
{\displaystyle \varphi (x)}
into the optimal (for the shipper) unloading cost function
ψ
(
y
)
=
φ
c
(
y
)
{\displaystyle \psi (y)=\varphi ^{c}(y)}
. If the unloading cost function
ψ
(
y
)
{\displaystyle \psi (y)}
were any higher at any point, then there would be some route
x
→
y
{\displaystyle x\to y}
on which
c
(
x
,
y
)
<
φ
(
x
)
+
ψ
(
y
)
{\displaystyle c(x,y)<\varphi (x)+\psi (y)}
, meaning that there is some route on which you would rather ship yourself. But if the unloading cost function were any lower at any point, then the shipper could have earned more money by raising the price there. Therefore, the shipper should always choose
ψ
=
φ
c
{\displaystyle \psi =\varphi ^{c}}
. The same argument applied again then states that the shipper should always choose
φ
=
ψ
c
{\displaystyle \varphi =\psi ^{c}}
, and therefore we obtain the lower bound half of the duality formula:
The Kantorovich duality states that it is in fact an equality, i.e. the shipper can make you pay as much as you would pay yourself, though the shipper might never exactly reach the bound (thus the use of infimum and supremum, instead of minimum and maximum).
Assume that the shipper in fact must pay the same cost function and us, and can exactly reach the maximum revenue using
(
φ
,
ψ
)
{\displaystyle (\varphi ,\psi )}
as their pricing chart. Then the shipper must use an optimal plan, at which point the shipper just breaks even with no profit. Conversely, any shipping plan that allows the shipper to exactly break even must be optimal.
c
(
x
,
y
)
=
h
(
x
−
y
)
{\displaystyle c(x,y)=h(x-y)}
, where
h
:
R
→
[
0
,
∞
)
{\displaystyle h:\mathbb {R} \to [0,\infty )}
is a convex function.
If
μ
{\displaystyle \mu }
has no atom, i.e., if the cumulative distribution function
. The existence of such matrices generalizes Sinkhorn's theorem and the matrices can be computed using the Sinkhorn–Knopp algorithm, which simply consists of iteratively looking for
φ
x
{\displaystyle \varphi _{x}}
to solve Equation 5.1, and
ψ
y
{\displaystyle \psi _{y}}
to solve Equation 5.2. Sinkhorn–Knopp's algorithm is therefore a coordinate descent algorithm on the dual regularized problem.
