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 is

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