NETWORK MODELS

Description
Many important optimization problems can be analyzed by means of graphical or network
representation. Among the most used network models are as given below:

 Shortest path problems

 Maximum flow problems
 Minimum spanning tree problems
 Minimum Cost Network Flow Problems (Network analysis diagrams)

THE GENERAL NETWORK-FLOW PROBLEM

A common scenario of a network-flow problem arising in industrial logistics concerns the distribution of a
single homogeneous product from plants (origins) to consumer markets (destinations). The total number of
units produced at each plant and the total number of units required at each market are assumed to be known.
The product need not be sent directly from source to destination, but may be routed through intermediary
points reflecting warehouses or distribution centres. Further, there may be capacity restrictions that limit
some of the shipping links. The objective is to minimize the variable cost of producing and shipping the
products to meet the consumer demand.

The sources, destinations, and intermediate points are collectively called nodes of the network, and the
transportation links connecting nodes are termed arcs. Although a production/distribution problem has been
given as the motivating scenario, there are many other applications of the general model.

The Shortest-Path Problem

The shortest-route technique is used to find the shortest path through a network. It can be used to find how a
person or item can travel from one location to another while minimizing the total distance traveled.

The shortest-route technique finds the shortest route to a series of destinations. This implies there is a
direction of the arcs through the network.

Steps of the Shortest-Route Technique

1. Find the nearest node to the origin (plant). Put the distance in a box by the node.
 2. Find the next-nearest node to the origin (plant), and put the distance in a box by the node. In some
cases, several paths will have to be checked to find the nearest node.

3. Repeat this process until you have gone through the entire network.

The last distance at the ending node will be the distance of the shortest route.

SHORTEST ROUTE TECHNIQUE EXAMPLE

Every day, the Ray furniture company must transport beds, chairs and other furniture items from the factory
to their warehouse. This involves going through many towns. Ray would like to find the route with the
shortest distance. The road network is shown below (distance in kilometres).

STEPS

1. Find the nearest node to the origin (plant). Put the distance in a box by the node. In this case node 2.
2. Find the nearest node to the origin (plant) excluding the node above. Put the distance in a box by the
node. In some instances, several paths will have to be checked to find the nearest node. In our case
here, it is node 3.
3. Repeat the process until you have gone through the entire network. The last distance at the ending
node is will be the distance of the shortest route. [node 5, then node 6]
In our case here, the shortest route path is 1-2-3-5-6 with a minimum distance of 290 kms.
Directed Network case
In our case here, the shortest route path is 1-2-5 with a minimum distance of 50 kms, OR
path 1-3-5 also with a minimum distance of 50 kms

Minimal-Spanning Tree Technique

Definition:

The minimal-spanning tree technique determines the path through the network that connects all the points
while minimizing total distance, e.g. If the points represent houses in an estate, the minimal spanning tree
technique can be used to determine the best way to connect all of the houses to electrical power, water
systems, etc. in a way that minimizes the total distance or length of power lines or water pipes. A cable
company wishing to lay lines to multiple neighborhoods; by minimizing the amount of cable laid and hence
the cable company will save money.

Minimal-Spanning Tree steps

Selecting any node in the network.

1. Connecting this node to the nearest node minimizing the total distance.

2. Finding and connecting the nearest unconnected node.

 If there is a tie for the nearest node, one can be selected arbitrarily.

 A tie suggests that there may be more than one optimal solution.

3. Repeating the third step until all nodes are connected.

Example

Let us consider the Tatu construction company which is currently developing luxurious housing project in
Ruiru town. The owner and president of the company must determine the least expensive way to provide
water and power to each house. The network of houses is as shown in the diagram below.
Minimal spanning tree method

Iteration 1: Select node 1 and connect it to node 3.

Iteration 2: Connect node 3 to the nearest node (here node 4)

Iteration 3: Look for the nearest unconnected node to nodes 1, 3 and 4. This is node 2 or 6
(distance of 3 from node 3). Pick node 2 and connect it to node 3.

Iteration 4: Repeat iteration 3 and look for the nearest unconnected node to nodes 1, 2, 3
and 4. Here 5 and 6. We can either connect 2 to 5 or 3 to 6 (distance of 3). Here, we connect
2 to 5.

Iteration 5: Next unconnected nodes 6 and 8. Here connect 3 to 6.

Iteration 6: Next unconnected nodes 7 and 8. Here connect 6 to 7.

Iteration 7: Next unconnected node is 8. Connect either 5 to 8, or 3 to 8 or 7 to 8. 7 to 8 (2)

is the minimum hence connect 7 to 8.

The final solution can be seen in iteration 7 where nodes 1, 2, 4 and 6 are all connected to
node 3. Node 2 is connected to node 5. Node 6 is connected to node 7 and node 7 is
connected to node 8. All the nodes are now connected.

Minimum distance = 2 + 3 + 2 + 3 + 3 + 1 + 2 = 16 units.

Kruskal’s algorithm example

Find the edge with the least weight and highlight it. For this example graph, I’ve highlighted
the top edge (from A to C) in red. It has the lowest weight (of 1):

Find the next edge with the lowest weight and highlight it:
Continue selecting the lowest edges until all nodes are in the same tree.
Notes:

If you have more than one edge with the same weight, choose an edge with the lowest
weight.

Be careful not to complete a cycle (route one node back to itself). If your choice completes a
cycle, discard your choice and move onto the next largest weight.

The finished minimum spanning tree for this example looks like this:

Prim’s Algorithm

What is Prim’s Algorithm?

Prim’s algorithm is one way to find a minimum spanning tree (MST).

A minimum spanning tree (shown in red) minimizes the edges (weights) of a tree.
How to Run Prim’s Algorithm

Step 1: Choose a random node and highlight it. For this example, we choose node C.

Step 2: Find all of the edges that go to un-highlighted nodes. For this example, node C has
three edges with weights 1, 2, and 3. Highlight the edge with the lowest weight. For this
example, that’s 1.

Step 3: Highlight the node you just reached (in this example, that’s node A).

Step 4: Look at all of the nodes highlighted so far (in this example, that’s A and C).
Highlight the edge with lowest weight (in this example, that’s the edge with weight 2).

Note: if you have more than one edge with the same weight, pick one in random.

Step 5: Highlight the node you just reached.

Step 6: Highlight the edge with the lowest weight. Choose from all of the edges that:

Come from all of the highlighted nodes.

Reach a node that you haven’t highlighted yet

Step 7: Repeat steps 5 and 6 until you have no more un-highlighted nodes. For this particular
example, the specific steps remaining are:

a. Highlight node E.

b. Highlight edge 3 and then node D.

c. Highlight edge 5 and then node B.

d. Highlight edge 6 and then node F.

e. Highlight edge 9 and then node G.

The finished graph is shown at the bottom right of this image:

The Maximal Flow Problem

The maximal-flow technique helps the user to find the maximum flow of any quantity or substance through a
given network. For example the number of vehicles (cars, trucks and so forth) that go through a network of
roads from one location to another.

For example:

 It has been used to find the maximum number of automobiles that can flow through a state highway
system,

 County planners would like to determine the maximum number of cars that can flow through the
town from all directions.

Ford-Fulkerson Algorithm

Given a graph which represents a flow network where every edge has a capacity. Also given two
vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following
constraints:
  Flow on an edge doesn’t exceed the given capacity of the edge.
 Incoming flow is equal to outgoing flow for every vertex except s and t.
For example, consider the following graph from CLRS book.

The maximum possible flow in the above graph is 23.

Ford-Fulkerson Algorithm
The following is simple idea of Ford-Fulkerson algorithm:
1. Start with initial flow as 0.
2. While there is an augmenting path from source to sink.
 Add this path-flow to flow.
3. Return flow.

ASSIGNMENT 4
1. The network of figure below shows the highways and towns surrounding Town A. Tom Ogechi a
bicycle helmet manufacturer, must transport his helmets to a distributor based in Town B. To do this, he
must go through several towns 2 to 15. Tom would like to find the shortest way to get from town A to
town B. What do you recommend? [10 marks]
2. Mutua construction company would like to determine the least expensive way of connecting houses it is
building with cable TV. It has identified 11 possible branches or routes that could be used to connect the
houses. The cost in hundreds of shillings and the branches are summarized in the following table.
(a) What is the least expensive way to run cable to the houses? [14 Marks]
Branch Start node End node Cost (hundreds of shillings)

1 1 2 5
2 1 3 6
3 1 4 6
4 1 5 5
5 2 6 7
6 3 7 5
7 4 7 7
8 5 8 4
9 6 7 1
10 7 9 6
11 8 9 2

(b) After reviewing cable and installation costs, Mutua construction company would like to alter the
costs for installing cable TV between its houses. The first branches need to be changed. The changes
are summarized in the following table. What is the impact of this on total costs? [6 Marks]
Branch Start node End node Cost (hundreds of shillings)

1 1 2 5
2 1 3 5
3 1 4 2
4 1 5 6
5 2 6 7
6 3 7 4
7 4 7 3
8 5 8 4
9 6 7 3
10 7 9 6
11 8 9 2

Illustration (Queuing theory)

Trucks at a single platform weigh-bridge arrive according to Poisson probability distribution. The time
required to weigh the truck follows an exponential probability distribution. The mean arrival rate is 15
trucks per day, and the mean service rate is 18 trucks per day. Determine the following:
(i) What is the probability that no trucks are in the system?
(ii) What is the average number of trucks waiting for service?
(iii) What is the average time a truck waits for weighing service to begin?
(iv) What is the probability that an arriving truck will have to wait for service?
(v) What is the traffic intensity (utilization factor) for this problem?

(i) What is the probability that no trucks are in the system, Po?

P0 =1 – ρ = The proportion of time the server is idle = 1 – 15 / 18 = 1 / 6 = 0.17

(ii) What is the average number of trucks waiting for service, Nq?

Nq = Lq = λ2 / μ (μ - λ) = 152 / 18 (18 – 15) = 225 / 54 = 4.17 trucks

(iii) What is the average time a truck waits for weighing service to begin, Tq?
Tq = λ / μ (μ - λ) = 15 / 18 (18 – 15) = 15 /54 = 0.28 * 24 hours = 6.72 hours

(iv) What is the probability that an arriving truck will have to wait for service?
ρ = probability the server is busy = 5 / 6 = 0.83

(v) What is the traffic intensity (utilization factor) for this problem?
The traffic intensity of a queue is defined in general to be:

ρ = mean arrival-rate, λ = 15 = 5 = 0.83

mean service rate, μ 18 6