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.

Motivation

Mines and factories
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.
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:
 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 cost function proportional to the square of Euclidean distance (c(x, y) = α|x − y|2), 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:
Suppose there are m sources  for a commodity, with  units of supply at xi and n sinks  for the commodity, with the demand  at yj. If  is the unit cost of shipment from xi to yj, 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.

Numerical solution in Excel 

With large numbers of routes, the problem is solved numerically.

Inputs:     The Transportation cells are T . The Supply data cells are S .The Demand data cells are D .

Think of each unit of supply as a large box (a shipping container).

Outputs: The shipment plan is X.

The current shipping cost is K.

Objective: Maximize the cost reduction

MAX R(X)=K-T·X

The shipment plan, X, must satisfy three types of constraint

(1) Non-negativity constraints X >= 0

(2)  Supply constraints            S-1•X >= 0

(3)  Demand constraints         X•1-D >= 0

One way to set up the problem in Excel is depicted in the table below.

The total shipping costs T·X are the product of terms in the array [e2:H3]

R-V solution method (an update of the simplex method):

For a small number of routes, the problem can be solved rather like a beginner's cross word puzzle or Sudoku.

The R-V Solution Method introduces Virtual unit Costs  c, Virtual Prices p and a Virtual Trader.

The  VIrtual Trader provides Real implications.

Crucially, the V-trader is a price taker.

Then there will be excess demand on any strictly profitable route and demand will be zero on any strictly unprofitable route.

VIRTUAL PROFIT MAXIMIZATION VPM

The unit profit on each route is  pj - tij -ci    These are calculated in the V-PROFIT Box at the bottom right of the Table.

(If you are working with Excel, enter these formulas and then use SOLVER if for the numerically computed maximum.)

The profit must be zero on all utilized routs and no route is strictly profitable.

STEP 1: Build a table like the one below. in the table small numbers are data points. Large bold numbers are variables.

In each column the V-PRICE must at least be the minimum cost to satisfy VPM. 

STEP 2: Make the lowest cost supplier the #1 supplier (top row).

STEP 3; Fill the orders sequentially. The first route to be filled should be in the top row  [S1:D1]. Then fill sequentially by cost so [S2;D1] is filled next

STEP 3: The last order to be filled is in Italics. The source in this row is the less valuable source. Then C2 is zero. Fill in the cell to the left of C2

STEP 4: Solve for the V-Prices and V-costs.

On each route select V-COSTS and V-PRICES so that the V-Trader breaks even on all the active routes.

Start with the column that has the fewest entries (Column 2)

V-SUDOKU

The V-Costs are initially left blank 2 (zero). To break even in Column 2, P2 = C2 +T22 =0 + 5 =5

In Column 1 both routes are used. Since C2 is zero, C1 =1. Then P1=C1 + T21 =5

V-CHECK If you set this V-PUZZLE up on a spreadsheet, the profit BOX will already be filled in.

The real value of the V-prices

Supply:

If you add a unit of supply at S1 you can lower the transportation cost by adding 1 to cell [S1:C2]  and subtracting 1 from cell [S2;C2].

This lowers shipping costs by 1, This is the meaning of C1. If the firm can rent an additional container at less than 1 (think "one thousand") there are additional cost savings.

If you try this at S2, the additional container doe not lower shipping costs. This is the meaning of C1.

Demand:

What would be the reduction in shipping costs if another unit of the product could be obtained locally (at the Destination).

Try reducing D1 by one unit. The shipping cost falls by...?  Yes, by the V-PRICE

Using the V-virtual trader method therefore yields Virtual price and costs of Real importance.

Programming note:

If you use a canned maximizing program like Excels Add-In Solver, it will get to the correct answer in a flash.

If you look at the "Lagrange Multipliers" or "shadow prices" that may appear in a sensitivity report, they can be confusing.

Since Solver provides the solution, all you have to do is Sudoku your way to the V-Costs and V-prices.

Here is the set-up for 3 suppliers and 3 destinations. I suggest that you set S3=0 initially and Sudoku your way to the solution..

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 . 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.) A gradient descent formulation for the solution of the Monge–Kantorovich problem was given by Sigurd Angenent, Steven Haker, and Allen Tannenbaum.

Duality formula
The minimum of the Kantorovich problem is equal to

where the supremum runs over all pairs of bounded and continuous functions  and  such that

Economic interpretation

The economic interpretation is clearer if signs are flipped. Let  stand for the vector of characteristics of a worker,  for the vector of characteristics of a firm, and  for the economic output generated by worker  matched with firm .  Setting  and , the Monge–Kantorovich problem
rewrites:

which has dual :

where the infimum runs over bounded and continuous function  and . If the dual problem has a solution, one can see that:

so that  interprets as the equilibrium wage of a worker of type , and  interprets as the equilibrium profit of a firm of type .

Solution of the problem

Optimal transportation on the real line

For , let  denote the collection of probability measures on  that have finite -th moment. Let  and let , where  is a convex function.
 If  has no atom, i.e., if the cumulative distribution function  of  is a continuous function, then  is an optimal transport map. It is the unique optimal transport map if  is strictly convex.
 We have

The proof of this solution appears in Rachev & Rüschendorf (1998).

Discrete version and linear programming formulation

In the case where the margins  and  are discrete, let 
and  be the probability masses respectively assigned to  and , and let  be the probability of an  assignment. The objective function in the primal Kantorovich problem is then

 

and the constraint  expresses as

 
and
 

In order to input this in a linear programming problem, we need to vectorize the matrix  by either stacking its columns or its rows, we call  this operation. In the column-major order, the constraints above rewrite as

  and 

where  is the Kronecker product,  is a matrix of size  with all entries of ones, and  is the identity matrix of size . As a result, setting , the linear programming formulation of the problem is

 

which can be readily inputted in a large-scale linear programming solver (see chapter 3.4 of Galichon (2016)).

Semi-discrete case

In the semi-discrete case,  and  is a continuous distribution over , while  is a discrete distribution which assigns probability mass  to site . In this case, we can see that the primal and dual Kantorovich problems respectively boil down to:

for the primal, where  means that  and , and:

for the dual, which can be rewritten as:

which is a finite-dimensional convex optimization problem that can be solved by standard techniques, such as gradient descent.

In the case when  , one can show that the set of  assigned to a particular site  is a convex polyhedron. The resulting configuration is called a power diagram.

Quadratic normal case

Assume the particular case , , and  where  is invertible. One then has

 

 

 

The proof of this solution appears in Galichon (2016).

Separable Hilbert spaces
Let  be a separable Hilbert space. Let  denote the collection of probability measures on  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 Gateaux derivative of .)

Entropic regularization 
Consider a variant of the discrete problem above, where we have added an entropic regularization term to the objective function of the primal problem

 

One can show that the dual regularized problem is

where, compared with the unregularized version, the "hard" constraint in the former dual () has been replaced by a "soft" penalization of that constraint (the sum of the  terms ). The optimality conditions in the dual problem can be expressed as

 

 

Denoting  as the  matrix of term , solving the dual is therefore equivalent to looking for two diagonal positive matrices  and  of respective sizes  and , such that  and . 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  to solve , and  to solve . Sinkhorn–Knopp's algorithm is therefore a coordinate descent algorithm on the dual regularized problem.

Applications 
The Monge–Kantorovich optimal transport has found applications in wide range in different fields. Among them are:
 Image registration and warping
 Reflector design
 Retrieving information from shadowgraphy and proton radiography
 Seismic tomography and reflection seismology
 The broad class of economic modelling that involves gross substitutes property (among others, models of matching and discrete choice).

See also

 Wasserstein metric
 Transport function
 Hungarian algorithm
 Transportation planning
 Earth mover's distance
Monge–Ampère equation

References

Further reading
 

Calculus of variations
Matching (graph theory)
Mathematical economics
Measure theory
Transport economics
Optimization in vector spaces
Mathematical optimization in business