Question

Korina is a manager of Good Stuffing Sausage Company. The company produces meat products for many of the grocery stores and restaurants in the Las Vegas area. The company has a major plant in Henderson and a warehouse in Las Vegas. Korina’s problem is getting the finished product to the warehouse. However, she is not good at distances. She is more familiar with delivery times. Las Vegas is a big city with several roads that could be taken from the plant to the warehouse, shown below:

Exit 135 Exit 136 Exit 137 1-70 2 4. 4 8 West Street North Street High Street 5 7 9 Columbine Street 6 Rose Street 1 6th Avenue South Avenue Plant Warehouse 10

The manufacturing facility is located at the corner of North Street and Columbine Street. High Street also intersects North and Columbine Street at the plant. Twenty minutes due north of the plant on North Street is I-70, the major east–west highway in Las Vegas.

North Street intersects I-70 at Exit 135. It takes five minutes driving east on I-70 to reach Exit 136. This exit connects I-70 with High Street and 6th Avenue. Ten minutes east on I-70 is Exit 137. This exit connects I-70 with Rose Street and South Avenue.

From the plant, it takes 20 minutes on High Street, which goes in a northeast direction, to reach West Street. It takes another 20 minutes on High Street to reach I-70 and Exit 136.

It takes 30 minutes on Columbine Street to reach West Street from the plant. Columbine Street travels east and slightly north.

West Street travels east and west. From High Street, it takes 15 minutes to get to 6th Avenue on West Street. Columbine Street also comes into this intersection. From this intersection, it takes an additional 20 minutes on West Street to get to Rose Street, and another 15 minutes to get to South Avenue.

From Exit 136 on 6th Avenue, it takes 5 minutes to get to West Street. Sixth Avenue continues to Rose Street, requiring 25 minutes. Sixth Avenue then goes directly to the warehouse. From Rose Street, it takes 40 minutes to get to the warehouse on 6th Avenue.

At Exit 137, Rose Street travels southwest. It takes 20 minutes to intersect with West Street, and another 20 minutes to get to 6th Avenue. From Exit 137, South Avenue goes due south. It takes 10 minutes to get to West Street and another 15 minutes to get to the Warehouse.

A) This is a minimal spanning problem. True or False?

B) How many branches are there in this network?

C) How many hours will it take to drive through nodes 2-4-8?

D) What is the value of the optimal solution in minutes?

Answer 1

(a)

FALSE,

This is the shortest route problem.

The primary difference between the two types of problems is:

For the Minimum spanning problem, every node of the network has to be visited at least once and then the overall distance (or cost) has to be minimized. A typical example of such a network problem could be the distribution of goods to various sales nodes (or sales beat for a salesman trying to cover a number of retail outlets). The solution should be such that all the nodes are covered with minimum total distance or cost.

Here, in the given problem, it is a shortest route problem as the finished goods have to be transported from Plant (node 1) to the Warehouse (node 10) without any constraint on passing through any of the additional node points (2 to 9).

(b)

A branch is defined as a route that connects the plant to the warehouse.

The plant is location 1 and the warehouse is location 10.

We have 20 branch combinations possible irrespective of the total distance value

(c)

Total ways to reach warehouse (no. of branches) =9+7=16 ways

Time taken to travel through 2-4-8 nodes 1-2-4-8-9-10) is 35 + 10 + 15 = 60 minutes = 1 hour

(d)

The best route (that takes the minimum time) to reach the warehouse is 1-2-4-8-9-10 which takes 60 minutes which happens to be the minimum possible time taken to travel from plant to warehouse.

The optimal solution is 1-2-4-8-9-10 and the nodes involved are 2-4-8-9 i.e. through the North Street, I-70 highway and South Avenue road.

EXCEL Solution:

Please find below the Excel Solver solution:

24 45 48 Road Link Time in minutes 12 20 13 20 15 30 34 20 35 15 56 25 57 20 610 40 76 20 79 15 87 20 89 10 910 15 5 5 10 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 On Path or Not (Decision) Flow Constraints: Net OUT- FLOW 1 L.H.S. Net OUT-FLOW 1 1 1 1 -1 1 0 2 1 0 -1 1 = 0 3 4 1 -1 0 0 -1 1 0 1 -1 5 -1 -1 1 1 0 - 0 Net Out-Flow = 1 Flow Conservation Flow Conservation Flow Conservation Flow Conservation Flow Conservation Flow Conservation Flow Conservation Flow Conservation Net Out-Flow = -1 6 -1 1 0 — 0 -1 1 -1 1 0 0 -1 1 -1 = 0 7 8 9 10 1 -1 -1 0 0 -1 1 -1 0 -1 -1 Path Length (in mins) 60 Plant to Warehouse Path: 1-2-4-8-9-10

Objective function is to minimize the path length.

Decision variables will be On path or not

Constraints are that the On path or not variable has to be binary and LHS=Net Outflow

The solution remains the same as that of the manual solution mentioned above.