Transportation theory
Encyclopedia
In mathematics
and economics
, transportation 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
/Russia
n mathematician
and economist
Leonid Kantorovich
. Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem.
s M and F of the Euclidean plane R2. Suppose also that we have a cost function c : R2 × R2 → [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
— i.e. an arrangement whereby each mine 
supplies precisely one factory 
. We wish to find the optimal transport plan, the plan 
whose total cost
is the least of all possible transport plans from
to 
. This motivating special case of the transportation problem is in fact an instance of the assignment problem
.
), 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:
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 (
), then the "many small moves" option becomes the unique minimizer.
Interestingly, while mathematicians prefer to work with convex cost functions, economists prefer concave
ones. The intuitive justification for this is that once goods have been loaded on to, say, a goods train, transporting the goods 200 kilometres costs much less than twice what it would cost to transport them 100 kilometres. Concave cost functions represent this economy of scale.
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
and 
be two separable metric space
s such that any probability measure
on
(or 
) is a Radon measure
(i.e. they are Radon space
s). Let
be a Borel-measurable function
. Given probability measures
on 
and 
on 
, Monge's formulation of the optimal transportation problem is to find a transport map 
that realizes the infimum
where
denotes the push forward
of
by 
. A map 
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
satisfying 
: 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 
that attains the infimum
where
denotes the collection of all probability measures on 
with marginals
on 
and 
on 
. It can be shown that a minimizer for this problem always exists when the cost function 
is lower semi-continuous and 
is a tight
collection of measures (which is guaranteed for Radon spaces
and 
). (Compare this formulation with the definition of the Wasserstein metric
on the space of probability measures.)
where the supremum
runs over all pairs of bounded
and continuous function
s
and 
such that
, let 
denote the collection of probability measure
s on
that have finite 
th moment
. Let
and let 
, where 
is a convex function
.
be a separable Hilbert space
. Let
denote the collection of probability measures on 
such that have finite 
th moment; let 
denote those elements 
that are Gaussian regular: if 
is any strictly positive
Gaussian measure
on
and 
, then 
also.
Let
, 
, 
for 
, 
. Then the Kantorovich problem has a unique solution 
, and this solution is induced by an optimal transport map: i.e., there exists a Borel map 
such that
Moreover, if
has bounded
support
, then
for 
-almost all 
for some locally Lipschitz, c-concave and maximal Kantorovich potential
. (Here 
denotes the Gâteaux derivative
of
.)
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
, transportation theory is a name given to the study of optimal transportation and allocation of resources.
The problem was formalized by the French
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Gaspard Monge
Gaspard Monge
Gaspard Monge, Comte de Péluse was a French mathematician, revolutionary, and was inventor of descriptive geometry. During the French Revolution, he was involved in the complete reorganization of the educational system, founding the École Polytechnique...
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
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
by the Soviet
Soviet Union
The Soviet Union , officially the Union of Soviet Socialist Republics , was a constitutionally socialist state that existed in Eurasia between 1922 and 1991....
/Russia
Russia
Russia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...
n mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and economist
Economist
An economist is a professional in the social science discipline of economics. The individual may also study, develop, and apply theories and concepts from economics and write about economic policy...
Leonid Kantorovich
Leonid Kantorovich
Leonid Vitaliyevich Kantorovich was a Soviet mathematician and economist, known for his theory and development of techniques for the optimal allocation of resources...
. Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem.
Mines and factories
Suppose that we have a collection of n mines mining iron ore, and a collection of n factories which consume the iron ore that the mines produce. Suppose for the sake of argument that these mines and factories form two disjoint subsetSubset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s M and F of the Euclidean plane R2. Suppose also that we have a cost function c : R2 × R2 → [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
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
— i.e. an arrangement whereby each mine supplies precisely one factory . We wish to find the optimal transport plan, the plan whose total costis the least of all possible transport plans from
to . This motivating special case of the transportation problem is in fact an instance of the assignment problemAssignment problem
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...
.
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 lineReal line
In mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...
), 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 books one book-width to the right; ("many small moves")
- 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
Convex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
cost function proportional to the square of Euclidean distance (
), then the "many small moves" option becomes the unique minimizer.Interestingly, while mathematicians prefer to work with convex cost functions, economists prefer concave
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...
ones. The intuitive justification for this is that once goods have been loaded on to, say, a goods train, transporting the goods 200 kilometres costs much less than twice what it would cost to transport them 100 kilometres. Concave cost functions represent this economy of scale.
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 geometryRiemannian geometry
Riemannian geometry is the branch of differential geometry that studies Riemannian manifolds, smooth manifolds with a Riemannian metric, i.e. with an inner product on the tangent space at each point which varies smoothly from point to point. This gives, in particular, local notions of angle, length...
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
and be two separable metric spaceMetric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
s such that any probability measure
Probability measure
In mathematics, a probability measure is a real-valued function defined on a set of events in a probability space that satisfies measure properties such as countable additivity...
on
(or ) is a Radon measureRadon measure
In mathematics , a Radon measure, named after Johann Radon, is a measure on the σ-algebra of Borel sets of a Hausdorff topological space X that is locally finite and inner regular.-Motivation:...
(i.e. they are Radon space
Radon space
In mathematics, a Radon space, named after Johann Radon, is a separable metric space such that every Borel probability measure on M is inner regular. Since a probability measure is globally finite, and hence a locally finite measure, every probability measure on a Radon space is also a Radon...
s). Let
be a Borel-measurable functionMeasurable function
In mathematics, particularly in measure theory, measurable functions are structure-preserving functions between measurable spaces; as such, they form a natural context for the theory of integration...
. Given probability measures
on and on , Monge's formulation of the optimal transportation problem is to find a transport map that realizes the infimumInfimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
where
denotes the push forwardPushforward measure
In measure theory, a pushforward measure is obtained by transferring a measure from one measurable space to another using a measurable function.-Definition:...
of
by . A map 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
satisfying : 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 that attains the infimumwhere
denotes the collection of all probability measures on with marginalsConditional probability
In probability theory, the "conditional probability of A given B" is the probability of A if B is known to occur. It is commonly notated P, and sometimes P_B. P can be visualised as the probability of event A when the sample space is restricted to event B...
on and on . It can be shown that a minimizer for this problem always exists when the cost function is lower semi-continuous and is a tightTightness of measures
In mathematics, tightness is a concept in measure theory. The intuitive idea is that a given collection of measures does not "escape to infinity."-Definitions:...
collection of measures (which is guaranteed for Radon spaces
and ). (Compare this formulation with the definition of the Wasserstein metricWasserstein metric
In mathematics, the Wasserstein metric is a distance function defined between probability distributions on a given metric space M....
on the space of probability measures.)Duality formula
The minimum of the Kantorovich problem is equal towhere the supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
runs over all pairs of bounded
Bounded function
In mathematics, a function f defined on some set X with real or complex values is called bounded, if the set of its values is bounded. In other words, there exists a real number M...
and continuous function
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
s
and such thatOptimal transportation on the real line
For, let denote the collection of probability measureProbability measure
In mathematics, a probability measure is a real-valued function defined on a set of events in a probability space that satisfies measure properties such as countable additivity...
s on
that have finite th momentMoment (mathematics)
In mathematics, a moment is, loosely speaking, a quantitative measure of the shape of a set of points. The "second moment", for example, is widely used and measures the "width" of a set of points in one dimension or in higher dimensions measures the shape of a cloud of points as it could be fit by...
. Let
and let , where is a convex functionConvex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
.
- If
has no atomAtom (measure theory)In mathematics, more precisely in measure theory, an atom is a measurable set which has positive measure and contains no set of smaller but positive measure...
, i.e., if the cumulative distribution functionCumulative distribution functionIn probability theory and statistics, the cumulative distribution function , or just distribution function, describes the probability that a real-valued random variable X with a given probability distribution will be found at a value less than or equal to x. Intuitively, it is the "area so far"...
of 
is a continuous functionContinuous functionIn mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
, then
is an optimal transport map. It is the unique optimal transport map if 
is strictly convex. - We have
Separable Hilbert spaces
Let be a separable Hilbert spaceHilbert space
The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions...
. Let
denote the collection of probability measures on such that have finite th moment; let denote those elements that are Gaussian regular: if is any strictly positiveStrictly positive measure
In mathematics, strict positivity is a concept in measure theory. Intuitively, a strictly positive measure is one that is "nowhere zero", or that it is zero "only on points".-Definition:...
Gaussian measure
Gaussian measure
In mathematics, Gaussian measure is a Borel measure on finite-dimensional Euclidean space Rn, closely related to the normal distribution in statistics. There is also a generalization to infinite-dimensional spaces...
on
and , then also.Let
, , for , . Then the Kantorovich problem has a unique solution , and this solution is induced by an optimal transport map: i.e., there exists a Borel map such thatMoreover, if
has boundedBounded set
In mathematical analysis and related areas of mathematics, a set is called bounded, if it is, in a certain sense, of finite size. Conversely, a set which is not bounded is called unbounded...
support
Support (measure theory)
In mathematics, the support of a measure μ on a measurable topological space is a precise notion of where in the space X the measure "lives"...
, then
for -almost all for some locally Lipschitz, c-concave and maximal Kantorovich potential
. (Here denotes the Gâteaux derivativeGâteaux derivative
In mathematics, the Gâteaux differential or Gâteaux derivative is a generalization of the concept of directional derivative in differential calculus. Named after René Gâteaux, a French mathematician who died young in World War I, it is defined for functions between locally convex topological vector...
of
.)