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.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.
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".Schrijver, Alexander, Combinatorial Optimization, Berlin; New York : Springer, 2003. . Cf. p. 362Ivor Grattan-Guinness, Ivor, Companion encyclopedia of the history and philosophy of the mathematical sciences, Volume 1, JHU Press, 2003. Cf. p.831
Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich.L. Kantorovich. On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942. 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.
Motivation
Mines and factories
Suppose that we have a collection of mines mining iron ore, and a collection of 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 and of the Euclidean plane . Suppose also that we have a cost function , so that is the cost of transporting one shipment of iron from to . 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 . In other words, each mine supplies precisely one target factory and each factory is supplied by precisely one mine. 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 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.
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 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 books one book-width to the right ("many small moves"); move the left-most book book-widths to the right and leave all other books fixed ("one big move"). If the cost function is proportional to Euclidean distance ( for some ) 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 ( for some ), 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.
Hitchcock problem The following transportation problem formulation is credited to F. L. Hitchcock:Frank L. Hitchcock (1941) "The distribution of a product from several sources to numerous localities", MIT Journal of Mathematics and Physics 20:224–230 . Suppose there are sources for a commodity, with units of supply at and sinks for the commodity, with the demand at . If is the unit cost of shipment from to , find a flow that satisfies demand from supplies and minimizes the flow cost. This challenge in logistics was taken up by D. R. FulkersonD. R. Fulkerson (1956) Hitchcock Transportation Problem, RAND corporation. and in the book Flows in Networks (1962) written with L. R. Ford Jr.L. R. Ford Jr. & D. R. Fulkerson (1962) § 3.1 in Flows in Networks, page 95, Princeton University Press
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 and be two separable metric spaces such that any probability measure on (or ) is a Radon measure (i.e. they are Radon spaces). 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 .
Cost duality Given a cost function , it produces a duality transformation defined byThis generalizes Legendre transformation, which is the case where with a sign flip.
.
We say that a function is c-convex if for some . Note that because , we can always assume that is c-convex. The c-convexification of a function is . Equivalently, it is the smallest c-convex function such that pointwise. Like in the case of convex transformation, is c-convex iff .
If is c-convex, then the set of c''-subdifferential of at is the set of such that . Similarly for .
When , the graph can be constructed as follows: Take the graph of , and flip it upside down. At each point , construct a graph of apexed at . That is, it is the graph of . We obtain a whole set of such graphs. Their lower-edge envelope is the graph of .
In the same image, we can see what it means for a function to be c-convex. It is c-convex iff its entire graph can be "touched" by a "tipped tool" that is moving and shape-shifting. When the tipped tool is at , it has a shape of and is raised to a height of . The graph of the c-convexification is constructed by running the tipped tool so that it is lowered as much as possible, while still touching graph of on the upper side. The lower envelope swept out by the tipped tool is the graph of .
For example, if is a metric space and , then is c-convex iff it is 1-Lipschitz. This is used in the definition of 1-Wasserstein distance. If , then is c-convex iff its graph could be touched from above by a tipped tool with the shape of a paraboloid.
Existence and uniqueness
Under fairly permissive assumptions, optimal transport plan exists.If
are Polish probability spaces, is lower semicontinuous, and there exists some upper semicontinuous functions of type such that ,
then an optimal transport plan exists. That is, exists such that it reaches the infimum.Note that the infimum could be infinite if all transport plans turn out to be infinite. For example, if is the Cauchy distribution, and .If
are Polish probability spaces, is lower semicontinuous, there exists some upper semicontinuous functions of type such that , there exists a finite-cost transport plan, and for any c-convex function , for -almost all , has a unique c-subdifferential at
then an optimal transport map exists.A restriction of an optimal transport plan is still optimal. That is, suppose is optimal, and , and define the normalized transport plan , then is an optimal transport plan between its own marginals. If isn't optimal, then there exists an improvement of it, which then translates back to an improvement of the original .
Kantorovich duality
The Kantorovich duality states that:If are Polish probability spaces, is lower semicontinuous, and there exists some upper semicontinuous functions of type such that , thenIf furthermore, only takes real values, there exists a transport plan with finite cost, and there exists some functions such that , thenConsider 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 , constrains the form of an optimal pricing pair , and vice versa.
Given such an optimal pricing pair ,
given an arbitrary transport plan , if all satisfies the exact equality , then is an optimal plan; given an optimal transport plan , any must satisfy the exact equality . More succinctly, a transport plan is optimal iff it is supported on the set of c-subdifferential pairs of .
Stability The optimal transportation is stable'' in the following sense:Assume that are Polish probability spaces, is continuous, and is finite. Given a sequence of continuous functions converging uniformly to over , a sequence weakly, a sequence weakly, and a sequence of optimal transport plans .
If the transport costs satisfy and , then converges weakly to some , and is an optimal transport plan from to .Similarly, the optimal transport map is also stable.Assume that are Polish probability spaces, is locally compact, is lower semicontinuous, and is finite. Given a sequence of lower semicontinuous functions converging uniformly to over , a sequence weakly,
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 , to factories, distributed as . The cost function of transport is . Now a shipper comes and offers to do the transport for you. You would pay him per coal for loading the coal at , and pay him per coal for unloading the coal at .