Mathematical Model of the Shortest Route Problem
The decision variables are defined xij, The arc (i,j) is either included in the shortest route (xij = 1) or not (xij = 0).
We are searching for the shortest route from Prague to Singapore (Picture 8.6 in level 1).
For Node 1 (Prague) the net stock position is 1 and one of outgoing arcs (to Frankfurt, to Zurich or to Vienna) must be on the shortest route thus
x1,2 + x1,3 + x1,4 = 1
For Node 9 (Singapore) the net stock position is -1 and one of incoming arcs (from Bangkok or from Dubai) must be on the shortest route too, thus
-x6,9 – x8,9 = -1
This equation can be multiplied by –1 and so
x6,9 + x8,9 = 1
For nodes 2 to 8 the net stock position is 0 and the conditions are created in the same way as for Maximum Flow Problem.
Our objective is to minimize the sum of distances
between the transition airports on the route, i.e. the objective function
z = 410x1,2 + 252x1,3 + 526x1,4 + 4830x2,6 + 2442x3,5 + 2878x4,5 + 9026x4,8 +
+ 2026x5,6 + 6810x5,8 +
1937x6,7 + 5840x6,9 + 3000x7,8 + 1430x8,9
The entire bivalent linear programming model is