The Transportation Problem—Optimizing Flour Deliveries to Bakeries Using an Operations-Research Algorithm

The transportation problem is one of the most effective optimization methods. The method consists in minimizing transportation costs by indicating the optimal configuration of routes between a set of suppliers and a set of recipients. Mills located in different places supply flour to bakeries located in different places. If the mills belong to different owners, every mill will attempt to supply flour to the greatest possible number of bakeries.

The situation is different when several mills in different locations belong to one owner. The owner will then strive to organize transportation in such a way that the sum of the route distances to the bakeries is as small as possible. The same may apply when several bakeries belong to one company. That company will attempt to reduce delivery costs by minimizing the sum of deliveries to its bakeries.

W-MOSZCZYNSKI-2021-4-44

History of the transportation problem

The transportation problem (transportation task) is used to calculate the most advantageous allocation of the quantities of a homogeneous good delivered between m suppliers and n recipients.¹

In mathematics and economics, transportation theory is the name given to the study. The problem of optimizing transportation and the allocation of resources was first formulated by the French mathematician Gaspard Monge in 1781.²

Monge’s concept was revisited in the Soviet Union in the 1920s.³

These methods were developed during the Second World War by the Soviet mathematician Leonid Kantorovich, the inventor of operations research. The transportation problem is sometimes called the Monge–Kantorovich transportation problem.⁴

Today, the transportation problem is a commonly used method for optimizing logistics processes.

¹ https://pl.wikipedia.org/wiki/Zagadnienie_transportowe

² G. Monge (1781), 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, pp. 666–704.

³ Schrijver, Alexander (2003), Combinatorial Optimization, Berlin; New York: Springer, p. 362.

⁴ Cédric Villani (2003), Topics in Optimal Transportation. American Mathematical Society, p. 66.

Optimizing deliveries by a group of mills

A company that owns three mills in a region supplies flour to five regional bakeries. The supply contracts are constructed in such a way that customers buying flour pay a fixed transportation charge for deliveries, irrespective of the distance that the flour tankers have to travel.

In this situation, minimizing the routes is in the interest of the company managing the mills.

Every bakery has a constant monthly level of demand for flour, resulting directly from the local level of demand for bread.

Thus:

• bakery 1 needs 70 tonnes of flour per month,
• bakery 2—160 tonnes of flour,
• bakery 3—90 tonnes of flour,
• bakery 4—65 tonnes of flour,
• bakery 5—92 tonnes of flour.

The bakeries can accept more flour than the quantities listed above, but if they receive less, they will not meet the needs of the local population. The listed values are therefore minimum quantities.

Minimum requirements of the bakeries

This rule can be expressed by a simple system of equations:

x₁₁ + x₂₁ + x₃₁ ≥ 70   (1)
x₁₂ + x₂₂ + x₃₂ ≥ 160  (2)
x₁₃ + x₂₃ + x₃₃ ≥ 90   (3)
x₁₄ + x₂₄ + x₃₄ ≥ 65   (4)
x₁₅ + x₂₅ + x₃₅ ≥ 92   (5)

where, for example, the value x₂₄ denotes the quantity of flour delivered by mill B to bakery 4.

As we remember, bakery 4 must have at least 65 tonnes of flour per month to meet local needs.

Inequalities 1–5 can be written as one consistent expression:

∑ x₍ₘ,ₚ₎ ≥ dₚ   ∀ p ∈ P                       (6)
m∈M, p∈P

This expression means: the sum of the number of tonnes of flour x delivered from individual mills m (belonging to the set of mills M) to bakery p (belonging to the set of bakeries P). This sum cannot be smaller than demand d occurring at every bakery p belonging to the set of bakeries P.

The apparently very complicated expression (6) is only a condensed form of the simple inequalities 1–5.

Maximum production capacities of the mills

On the other hand, the mills have specified production capacities, and their stocks of flour are not very large. The flour produced is sold on an ongoing basis.

The mills’ monthly supply is as follows:

• mill A produces 92 tonnes of flour,
• mill B—210 tonnes of flour,
• mill C—175 tonnes of flour.

We can write this in the form of simple inequalities. Each row specifies the production capacity of one mill.

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ ≤ 92   (7)
x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ ≤ 210  (8)
x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ ≤ 175  (9)

This can be written in condensed form:

∑ x₍ₘ,ₚ₎ ≤ Sₘ   ∀ m ∈ M                         (10)
m∈M, p∈P

where Sₘ is the production-capacity limit of mill m.

A balanced transportation problem

It is important that, collectively, the mills can produce at most as much flour as all the bakeries can accept at a minimum. This is, of course, a phenomenon that we are unlikely to encounter in economic reality.

There is usually no equilibrium in this area. To solve a transportation problem, supply and demand must be balanced by introducing a fictitious transfer warehouse. In our case, bakery demand and mill supply are equal, which can be written using the formula:

∑ Mᵢ = ∑ Pⱼ = 477 t                            (11)
i=1..3   j=1..5

As a supplement to the fundamental assumptions, it should be mentioned that mills cannot deliver negative quantities of flour to bakeries.

x₍ₘ,ₚ₎ ≥ 0   ∀ m ∈ M, p ∈ P                    (12)

To be more precise, we should specify that the algorithm is to take the quantities delivered into account only as positive integers, which can be expressed by a simple formula:

x₍ₘ,ₚ₎ ∈ Z⁺   ∀ m ∈ M, p ∈ P                   (13)

Distances between mill warehouses and bakeries

The bakeries and mills are distributed relatively evenly across the region. To determine the optimal delivery routes, we need a grid of distances between the individual entities.

The table presents the distances from the individual mills to the individual bakeries. It also contains information about supply and receipt limits.

Table 1. Distance grid including supply and receipt limits

	Bakery 1	Bakery 2	Bakery 3	Bakery 4	Bakery 5	Mill limit
Mill A	26 km	23 km	27 km	32 km	21 km	92 t
Mill B	27 km	31 km	21 km	24 km	20 km	210 t
Mill C	17 km	30 km	20 km	26 km	23 km	175 t
Bakery limit	70 t	160 t	90 t	65 t	92 t	477 t

For the transportation problem to be complete, an objective function must be introduced.

We will write this function in condensed form:

∑ c₍ₘ,ₚ₎ x₍ₘ,ₚ₎ → min                          (14)
m∈M, p∈P

where c denotes the number of kilometres. Regarding the objective function, it should be noted that the purpose is not merely to minimize kilometres, but to minimize the product of the kilometres and the mass of flour transported from the mills to the bakeries.

Solving the transportation equation

The limiting conditions and objective function formulated above can be entered into any simplex processor in order to obtain the optimization result. The greatest challenge in the operations-research process has always been to reflect the problem in mathematical form. Today, solving a coherently described problem is easy because computers perform this task. Many calculators that solve such a task online can be found on the Internet.

The solution of objective function (14) in our task is a distance matrix. Below, I present the result of calculations performed by the PuLP library in the Python programming environment.

Route_Mill_A_Bakery_1 = 0.0
Route_Mill_A_Bakery_2 = 92.0
Route_Mill_A_Bakery_3 = 0.0
Route_Mill_A_Bakery_4 = 0.0
Route_Mill_A_Bakery_5 = 0.0
Route_Mill_B_Bakery_1 = 0.0
Route_Mill_B_Bakery_2 = 53.0
Route_Mill_B_Bakery_3 = 0.0
Route_Mill_B_Bakery_4 = 65.0
Route_Mill_B_Bakery_5 = 92.0
Route_Mill_C_Bakery_1 = 70.0
Route_Mill_C_Bakery_2 = 15.0
Route_Mill_C_Bakery_3 = 90.0
Route_Mill_C_Bakery_4 = 0.0
Route_Mill_C_Bakery_5 = 0.0

It is worth checking whether the calculations obtained are correct. Taking the supply and receipt limits from Table 1 into account, we substitute the results.

We can do this manually in the manner shown below:

x11 = 0
x12 = 92
x13 = 0
x14 = 0
x15 = 0
x21 = 0
x22 = 53
x23 = 0
x24 = 65
x25 = 92
x31 = 70
x32 = 15
x33 = 90
x34 = 0
x35 = 0

k = 26*x11+23*x12+27*x13+32*x14+21*x15+27*x21+31*x22+21*x23+24*x24+20*x25+17*x31+30*x32+20*x33+26*x34+23*x35

p1 = x11 + x12 + x13 + x14 + x15
p2 = x21 + x22 + x23 + x24 + x25
p3 = x31 + x32 + x33 + x34 + x35

p4 = x11 + x21 + x31
p5 = x12 + x22 + x32
p6 = x13 + x23 + x33
p7 = x14 + x24 + x34
p8 = x15 + x25 + x35

We can enter the results in the table below:

	Tonnes	Limits
Mill A	92	≤ 92
Mill B	210	≤ 210
Mill C	175	≤ 175
Bakery 1	70	≥ 70
Bakery 2	160	≥ 160
Bakery 3	90	≥ 90
Bakery 4	65	≥ 65
Bakery 5	92	≥ 92
Transportation volume	10599	km × tonne

As can be seen, the transportation algorithm determined the minimum routes perfectly while preserving all of the delivery and receipt limits specified above.

Wojciech Moszczyński
In collaboration with Ewa Moszczyńska

Wojciech Moszczyński — graduate of the Department of Econometrics and Statistics of Nicolaus Copernicus University in Toruń; specialist in econometrics, finance, data science, and management accounting. He specializes in the optimization of production and logistics processes. He conducts research in the area of the development and application of artificial intelligence. For years he has been engaged in the popularization of machine learning and data science in business environments.