Questions and Answers > Colorado Technical University MATH 451-1404B-Shortest-Path Model

Document Content and Description Below

Colorado Technical University MATH 451-1404B- Shortest-Path Model Shortest-Path Model Introduction In shortest path model, you are looking for the paths to get you from any node to any other no... de in shortest path with regard to distance, time, or other measure. In this section, you will consider an application of a delivery pizza man to deliver the pizza hot and fresh by the shortest time from the pizza store to the customer house. You will present the objective function as well as flow balance equations. You will then find the shortest time to deliver the pizza. Learning Materials Shortest Path Model is Important In some applications, it is critical to save time or mileage if you are repeating the same task over and over. Example A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. Of course, it may be possible to travel a longer distance to achieve shorter time in not congested roads. Chart The following table shows the required time in minutes going from node 1 (store) to node 6 (customer house). Other nodes are the intersection between any two roads. Why is the shortest path modeling considered a transshipment problem? Shortest path modeling can be considered as transshipment problem with the origin being the supply node (pizza store) and the destination node is the demand node (customer house). The value of the supply and destination nodes is unity with all other nodes as transshipment nodes because no pizza is made nor is consumed at those nodes. Write the Objective Function The objective function is to minimize the total time spent on the road. The objective function can then be written as: Minimize the time = T12 + T13 + T14 + T15 + T16 + T24 + T26 + … subject to the following flow balance equations T12 + T13 + T14 + T15 + T16 - (T21 + T31 + T51 + T61) = 1 Supply of 1 unit at supply node (store) T42 + T62 - (T24 + T26) = 0 Transshipment at node 2 T72 + T73 + T74 + T76 - (T27 + T37 + T47 + T67) = 1 Demand of 1 unit at destination node (house) Figure 1 shows the Excel’s Solver program used to solve the shortest path model containing all of the required excel functions. Figure 1: Excel’s Solver Program Used to Solve the Shortest Path Model Figure 2 shows the same program containing the numerical values of the decision-making variables and the amount of resources consumed. Figure 2: Results of the Application Using Excel’s Solver Understanding the Results As you may have noticed, you place a large amount of time (100 minutes) on the roads which actually do not exist between any two nodes and any nodes to itself to discourage the Excel’s Solver to consider such a nonexistence roads and looping in the intersections. A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. The following table shows the required time in minutes going from node 1 (store) to node 7 (customer house). What is the flow balance for node 1, the store? T13 + T14 + T16 + (T31 + T41 + T51) = 1 T13 + T14 + T16 + (T31 + T41 + T51) = 0 T13 + T14 + T16 - (T31 + T41 + T51) = 0 T13 + T14 + T16 - (T31 + T41 + T51) = 1 Suppose that there is a network with 13 nodes, 1 through 13, with the following distances: What is the length of the shortest path from node 1 to node 13? 84 115 185 104 Suppose that there is a network with 13 nodes, 1 through 13, with the following distances: Suppose that you accidentally miscode the length from node 2 to 8 as -23. For this problem, you can assume that the segment between nodes 2 and node 8 would not be used if the length was correctly entered as 23. When solving, you notice that the Solver seems to be assigning unreasonably large values to some of the segments, and because it makes sense that a segment is only used once, you limit the decision variables to be at most 1. What happens with this new restriction? The restriction does not help, and the Solver still reports an error. The correct path is found, and the negative link is added in both directions, resulting in a total distance that is too low by 46. The correct path and total distance are found. The negative path is added in both directions. Another path is found, which is not optimal. Suppose that there is a network of 13 nodes, with the costs shown below. Note that these are directed paths. How long is the shortest path from node 1 to node 13? 16 12 14 10 A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. The following table shows the required time in minutes going from node 1 (store) to node 7 (customer house). How many arcs does the network have? 48 24 7 49 What is the function of a shortest path model? Minimizing distance while maximizing time Minimizing total distance, cost, time, or other measure Finding the shortest distance connecting all nodes together Minimizing time while maximizing distance How many decision variables does the network have? 49 24 48 7 Suppose that there is a problem at node 3, so no traffic can come in or out. It turns out that your surveyor did not calibrate the instruments properly, and each path should be 1 longer. By how much does the length of the path increase? 7 4 6 3 Suppose that you accidentally miscode the length from node 2 to 8 as -23. For this problem, you can assume that the segment between nodes 2 and node 8 would not be used if the length was correctly entered as 23. What will happen if you attempt to solve this using the Solver? The Solver will find the correct path and ignore the bad data. The Solver will assign negative weights to the link with the negative distance. The Solver will fail with an error message about a failure to converge. The Solver will find the correct path, but the total distance shown will be lower by 23. It turns out that the link directly from node 1 to node 10 was a mistake and is not really there. Also, the link from 4 to 10 was misreported and should have a length of 69.38. How long is the shortest path? Round your answer off to the nearest tenth. 63.1 83.6 38.7 36.6 Which of the following nodes is not the starting and ending nodes? Destination Supply or destination Transshipment Supply What value is assigned to the starting (supply) node in shortest path model? It must be given by the application 0 Any large number is fine 1 What value do you insert for those arcs with no connections and for any node to itself? 1 0 Leave the cells blank Infinity or artificially a high number Which of the following is an objective function? Maximize the time = T12 + T13 + T14 + T15 + T16 + T17 + T21 + T23 + T24 + T25 + … Minimize the time = 3 * T13 + 12 * T14 + 20 * T16 + 20 * T24 + 18 * T26 + … Minimize the time = 3 + 12 + 20 + 20 + 18 + … Minimize the time = T13 + T14 + T14 + T16 + T24 + T26 + T31 + …, Minimize the time = T12 + T13 + T14 + T15 + T16 + T17 + T21 + T23 + T24 + T25 + … What is the flow balance for node 2? T32 + T42 + T52 - (T24 + T26) = 0 T32 + T42 + T52 - (T24 + T26) = 1 T32 + T42 + T52 + (T24 + T26) = 1 T32 + T42 + T52 + (T24 + T26) = 0 A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. The following table shows the required time in minutes going from node 1 (store) to node 7 (customer house). What is the value of the objective value? 100 minutes 4 minutes 19 minutes 20 minutes What value is assigned to the ending (demand) node in shortest path model? 0 Any large number is fine 1 It must be given by the application What is the length of shortest path from node 1 to node 10? Round your answer off to the nearest tenth. 59.3 24.4 41.8 37.0 [Show More]

Last updated: 1 year ago

Preview 1 out of 6 pages