Network flows and linear programming

Transshipment Problem

The transshipment problem aims to find the cheapest way to ship goods across the nodes, while satisfying the given constraints. When solving the transshipment problem, we also assume that total supply equals the total demand.

Here is a toy example of a transshipment problem.

Here, the nodes 1,2,3 and 4 can be thought of as “cities” where goods are shipped, and the arrows can be thought of as railroad lines. The nodes also provide set of constraints.

For example, let’s say there are supplies of

5 units at the node 1,

11 units at the node 2.

And also the demands of

7 units at the node 3,

1 unit at the node 4. Therefore, we need to find the cheapest way to ship the goods while satisfying these 4 constraints. The corresponding LP problem is;

Minimize

                   z=c13x13+c21x21+c23x23+c24x24+c34x34

Subject to

                   -x13 + x21  ≥ -5
                   -x21 –x23 –x24 ≥ -11
                   x13+x23 –x34  = 7
                   x24 +x34 = 1
                   x13,x21,x23,x24,x34≥0

Here, xij stands for the amount of goods shipped directly from i to j. cij stands for the cost of shipping a unit amount of goods along arc ij.

Note that the right hand sides of the constraints 1 and 2 have to be negative since node 1 and 2 have supplies, meaning the total amount of goods entering the node 1 - total amount of goods leaving node 1 can be as small as -5, hence the first constraint.

In this LP problem, we assumed that the demands at nodes 3 and 4 have to be satisfied exactly (as we have equality sign in the constraints 3 and 4), and also assumed that the supplies at nodes 1 and 2 do not need to be exhausted fully (as we have inequality signs in the constraints1 and 2). However, we can convert this LP problem into transshipment problem (which assumes that total supply must exactly equal to total demand) by introducing a new node 5.

This new node is a “dummy node” where unused supplies are stored. Now the new LP problem reads;

Minimize

                  z= c13x13+c21x21+c23x23+c24x24+c34x34

Subject to

                   -x13 + x21 –x15  = -5
                   -x21 –x23 –x24 – x25 = -11
                   x13+x23 –x34  = 7
                   x24 +x34 = 1
                   x15 + x25 = 8
                   x13,x21,x23,x24,x34,x15,x25≥0

Where we have 8 in the right hand side of the constraint 5 since the excess supply is 5+11-7-1=8. Thus,we converted the original problem into a transshipment problem. This can be done to any problems involving actual shipment of goods.

Now, we are ready to solve the transshipment problem.

Dijkstra's Algorithm：

Step1: Set a vector D, which contains the distances. D[i] from to initial node to final node vi.

Step2: Set v0 as initial and current node. If v0 can go to vi, then set the D[i] as the length between v0 and vi. Otherwise, set the D[i]=∞.

Setp3: Choose the shortest path. If the final node is vk, the path can be (v,vk), or can be (v,vj,vk) which goes though vj. But the total distance has to be the smallest.

Step4: Add the vk to the set S (initial with v0, then add each node after every computing till the set S contains all the nodes)

Step5: Repeat Step3 for n-1 times so that S contains all the shortest path. n is the number of the nodes.

This graph shows how the Dijkstra Algorithm works.

There is another example :

If the start node is a:

v	a	b	c	d	e	f	g
a	0a	3a	5a	6a	∞	∞	∞
b	0a	3a	5a	5b	∞	∞	∞

The first row shows that a goes to node a have 0 length . To b, the length is 3. To c the length is 5. Node a can't go to nods e f g, therefore is ∞. And a goes the smallest number, which is b. And change the current node to b.

If go through b, then will not optimize the a,b,c,e,f,g solution. But can optimize the d, since if a goes to c through b, the total length is just 5 less than the 6 before. so change the number to 5b. 5b means through b, and the shortest length is 5.

Go on, till the set contains all the shortest path to every node. (repeat the steps by n-1 times, n is the number of the nodes)

Another example of Dijkstra's Algorithm:

Example problem for Dijkstra's Algorithm

Our starting point is node A. Our goal is node E. We want to find the shortest path from A to E.

First iteration:

Nodes to check: B, C, and D

Paths: AB = 2, AC = 5, AD = 4

Shortest Path: AB = 2

Add B to path.

Second iteration:

Nodes to check: C, D, and E

Paths: AC = 5, AD = 4, ABC = 3, ABE = 7

Shortest Path: ABC

Add C to path.

Third iteration:

Nodes to check: D and E

Paths: AD = 4, ABE = 9, ABCD = 4, ABCE = 5

Shortest Path: Tie between AD and ABCD. Both end at node D, arbitrarily pick ABCD and note AD as alternative.

Add D to path.

Fourth iteration:

Nodes to check: E

Paths: ABE = 9, ABCE = 5, ABCDE = 7

Shortest Path: ABCE

Add E to path.

We've reach the goal node E, so the fourth iteration was the last and the process is over. The shortest path is ABCE with length 5.