Sarah and Jennifer have just graduated from college at the University of Washington in Seattle and want to go on a road trip.They have always wanted to see the mile-high city of Denver.Their road atlas shows the driving time (in hours)between various city pairs,as shown below.Formulate and solve a network optimization model to find the quickest route from Seattle to Denver?

Question

Quizplus · Accepted Answer

The Answer is This is a shortest path problem.To set up a spreadsheet model,first list all of the arcs as shown in B4:C19,along with their travel time (E4:E19).Then list all of the nodes as shown in G4:G12 along with each node's supply or demand (J4:J12).We are sending one unit (Sarah and Jennifer's car)from Seattle to Denver,so the supply is 1 at Seattle and the demand is 1 at Denver.Every other node has demand 0 because if you enter the node,you must also leave it.

This is a shortest path problem.To set up a spreadsheet model,first list all of the arcs as shown in B4:C19,along with their travel time (E4:E19).Then list all of the nodes as shown in G4:G12 along with each node's supply or demand (J4:J12).We are sending one unit (Sarah and Jennifer's car)from Seattle to Denver,so the supply is 1 at Seattle and the demand is 1 at Denver.Every other node has demand 0 because if you enter the node,you must also leave it. The changing cells are whether or not to include an arc on the route.These are shown in OnRoute (D4:D19)below.If the one unit (Sarah and Jennifer's car)is shipped through an arc,it must mean they traveled along that route. For each node,calculate the net flow as a function of the changing cells.This can be done using the SUMIF function.In each case,the first SUMIF function calculates the flow leaving the node and the second one calculates the flow entering the node.For example,consider the Seattle node (H4).SUMIF(From,G4,OnRoute)sums each individual entry in OnRoute (the changing cells in D4:D19)if that entry is in a row where the entry in From (B4:B19)is the same as in G4 are rows 4,5,and 6,the sum in the OnRoute column is only over these same rows,so this sum is D4+D5+D6. The goal is to minimize the total time of the route.The cost is the SUMPRODUCT of the Time with OnRoute,or Total Time = SUMPRODUCT(OnRoute,Time).This formula is entered into TotalTime (D21). The Solver information and solved spreadsheet are shown below. OnRoute (D4:D19)indicates whether that arc should be included in the route.The optimal route is to go Seattle-Butte-Billings-Cheyenne-Denver.The minimum TotalTime (D21)is 22 hours.

The changing cells are whether or not to include an arc on the route.These are shown in OnRoute (D4:D19)below.If the one unit (Sarah and Jennifer's car)is shipped through an arc,it must mean they traveled along that route.

For each node,calculate the net flow as a function of the changing cells.This can be done using the SUMIF function.In each case,the first SUMIF function calculates the flow leaving the node and the second one calculates the flow entering the node.For example,consider the Seattle node (H4).SUMIF(From,G4,OnRoute)sums each individual entry in OnRoute (the changing cells in D4:D19)if that entry is in a row where the entry in From (B4:B19)is the same as in G4 are rows 4,5,and 6,the sum in the OnRoute column is only over these same rows,so this sum is D4+D5+D6.

The goal is to minimize the total time of the route.The cost is the SUMPRODUCT of the Time with OnRoute,or Total Time = SUMPRODUCT(OnRoute,Time).This formula is entered into TotalTime (D21).

The Solver information and solved spreadsheet are shown below.

OnRoute (D4:D19)indicates whether that arc should be included in the route.The optimal route is to go Seattle-Butte-Billings-Cheyenne-Denver.The minimum TotalTime (D21)is 22 hours.

Sarah and Jennifer Have Just Graduated from College at the University