Transportation problem: Construction of starting solution 1

Transportation problem: Find an initial solution

Introduction

The transportation problem is a general problem for every company, especially in logistics, to get a balance between supply and demand quantity. That means, you have j locations which need the product x and i locations which could send it to each of these. The supply quantity is declared by the variable a_i, the quantity of demand by the variable b_j. A necessary condition for this is that the total supply is equal to the total demand. Furthermore the problem consists of an allocation of the quantity in a cost minimal way. That shows basically the theoretical problem.

Mathematical formulation of a general transportation problem

a_i : supply quantity at location i (i=1,…,m)
b_j : demand quantity at location j (j=1,…,n)
c_ij :transportation cost per unit from supply location i to demand location j
x_ij : transportation quantity from i to j

Minimize K=∑i ∑j c_ij*x_ij
∑j x_ij = a_i for every i
∑i x_ij = b_j for every j
x_ij ≥ 0 for every i,j
A solution only exists, if ∑i a_i = ∑j b_j

Example

There is a company named Physics Rules The World which has 4 manufacturing bases. They produce high technology light amplification of stimulated emission of radiation, short LASER in Rom, Lissabon, Berlin and Moskau. An important furnisher is placed in Madrid, Istanbul and Peking. The following cost matrix is depending on the distance between the place of supply and the place of demand. In addition there are a few possibilities to send the material like by truck, plane or train. That is why the shortest distance doesn’t have to be the possibility with the shortest costs.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

In the following part we explain you the possibilities to find an initial solution.

    1. North-West corner method
    2. Simple row sequence
    3. Row-column succession
    4. Matrix-Minimum method
    5. Cost difference method
    6. Frequency method
    7. Modified North-West corner method 

3. Row-column succession:

Redline:
1. Allocate the cheapest field of the whole matrix the highest possible quantity.
2. The next cheapest field in row or column should get the remaining quantity.
3. Move forward till every demand is tiled.

Because of the redline is depending on the lowest costs it shows a good approximation to the optimal solution.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

At first searching the cost minimal field gives Madrid /Lissabon with 15 per unit. The maximal quantity which you can place there is 60 restricted by the row. Then you are finishing the according column and place 15 to Istanbul/Lissabon. After that move on with the row, Istanbul/Moskau gets 25. There is only Peking remaining yet. Next you send 25 from Peking to Moskau, then 30 Peking/Berlin and at last step to complete supply= demand Pekings /Rom 45.

6. Frequency method by Habr:

The frequency method considers the interdependence of costs. In addition a modified matrix minimum method is part of this algorithm. In the most cases the results of frequency method are adequate solution and nearly optimal. The problem of this method is based on the time which you need to determine the modified matrix. You get this modified matrix by following this mathematical formulation.

k_ij= m*n*c_ij-n*∑ c_pj -m∑c_iq+∑∑c_pq

∑ c_pj from p=1 to m
∑c_iq from q=1 to n

∑∑c_pq combined by both, is adding all fields of the matrix
i = row ; j= column
m = number of rows; n= number of columns;

Example:
k₁₁= 3*4*20- 4*(20+30+40) -3*(20+15+25+60)+ (20+15+25+50+30+35+60+20+40+55+35+80) = 240-360-360+465= -15