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. 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. Suppose that we have a collection of m 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 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 T : M → F. In other words, each mine m ∈ M supplies precisely one target 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 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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (2)

Related people (1)

Related concepts (5)

Related courses (1)

Related lectures (19)

MATH-476: Optimal transport

The first part is devoted to Monge and Kantorovitch problems, discussing the existence and the properties of the optimal plan. The second part introduces the Wasserstein distance on measures and devel

Distribution-on-distribution regression via optimal transport maps

Victor Panaretos, Laya Ghodrati

We present a framework for performing regression when both covariate and response are probability distributions on a compact interval. Our regression model is based on the theory of optimal transportation, and links the conditional Frechet mean of the response to the covariate via an optimal transport map. We define a Frechet-least-squares estimator of this regression map, and establish its consistency and rate of convergence to the true map, under both full and partial observations of the regression pairs. Computation of the estimator is shown to reduce to a standard convex optimization problem, and thus our regression model can be implemented with ease. We illustrate our methodology using real and simulated data.

OXFORD UNIV PRESS2022

Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case

Valentin Hartmann

We consider the problem of finding an optimal transport plan between an absolutely continuous measure and a finitely supported measure of the same total mass when the transport cost is the unsquared Euclidean distance. We may think of this problem as closest distance allocation of some resource continuously distributed over Euclidean space to a finite number of processing sites with capacity constraints. This article gives a detailed discussion of the problem, including a comparison with the much better studied case of squared Euclidean cost. We present an algorithm for computing the optimal transport plan, which is similar to the approach for the squared Euclidean cost by Aurenhammer et al. (Algorithmica 20(1):61-76, 1998) and Merigot (Comput Graph Forum 30(5):1583-1592, 2011). We show the necessary results to make the approach work for the Euclidean cost, evaluate its performance on a set of test cases, and give a number of applications. The later include goodness-of-fit partitions, a novel visual tool for assessing whether a finite sample is consistent with a posited probability density.

SPRINGER HEIDELBERG2020

Transportation theory (mathematics)

Wasserstein metric

In mathematics, the Wasserstein distance or Kantorovich–Rubinstein metric is a distance function defined between probability distributions on a given metric space . It is named after Leonid Vaseršteĭn. Intuitively, if each distribution is viewed as a unit amount of earth (soil) piled on , the metric is the minimum "cost" of turning one pile into the other, which is assumed to be the amount of earth that needs to be moved times the mean distance it has to be moved. This problem was first formalised by Gaspard Monge in 1781.

Radon measure

In mathematics (specifically in measure theory), a Radon measure, named after Johann Radon, is a measure on the σ-algebra of Borel sets of a Hausdorff topological space X that is finite on all compact sets, outer regular on all Borel sets, and inner regular on open sets. These conditions guarantee that the measure is "compatible" with the topology of the space, and most measures used in mathematical analysis and in number theory are indeed Radon measures.

Optimal Transport: Theory and Applications MATH-476: Optimal transport

Covers the theory and applications of optimal transport, focusing on infimal convolution and Kantorovich potentials.

Optimal Transport: Introduction and Kantorovich Problem MATH-476: Optimal transport

Introduces the course on optimal transport, covering historical background, concepts of push forward measures, transport maps, and the Kantorovich problem.

Optimal Transport: In-Depth Evaluation MATH-476: Optimal transport

Explores optimal transport theory with a focus on heat equations and Wasserstein distance.