Road Segment Endpoints Highway(s) Time Distance (Min) (Miles) Yellowstone N.P., WY Livingston, MT US-89 84 59 Yellowstone N.P., WY Idaho Falls, ID US-20 128 100 Livingston, MT Butte, MT I-90 100 104 Butte, MT Butte, MT Missoula, MT Idaho Falls, ID I-15 210 205 Missoula, MT I-90 110 119 Boise, ID US-12, US-95 475 371 Idaho Falls, ID Salt Lake City, UT I-15 206 208 Idaho Falls, ID Twin Falls, ID I-15, 1-86, I-84 155 161 Boise, ID Twin Falls, ID I-84 128 131 Boise, ID Winnemuca, NV US-95 303 256 Twin Falls, ID Salt Lake City, UT Salt Lake City, UT Wells, NV US-93 141 118 Wells, NV 1-80 174 181 Ely, NV I-15, US-6 262 241 Wells, NV Winnemuca, NV 1-80 162 175 Wells, NV Ely, NV US-93 180 140 Winnemuca, NV Reno, NV 1-80 153 164 Ely, NV Bishop, CA US-6 337 283 Reno, NV Bishop, CA US-395 255 205 Reno, NV Sacramento, CA 1-80 152 133 Reno, NV Yosemite N.P., CA US-395, CA-120 225 154 Sacramento, CA Yosemite N.P., CA CA-99, CA-120 277 193 Bishop, CA Yosemite N.P., CA US-395, CA-120 132 65 Figure 1: Bi-directional Distance and Travel Time Data Sacramento 1-80 US-12, US-95 Missoula I-90 Butte 1-90 Livingston I-15 US-89 Boise US-20 Idaho US-95 I-84 W Yellowstone Falls NP Twin 1-15, Falls I-86, I-84 US-93 Winnemuca 1-15 1-80 Reno 1-80 I-80 Wells US-93 Salt Lake City Ely 1-15, US 6 US-395 CA-120 US-395 CA-99 CA-120 Yosemite NP US-395, CA-120 Bishop US-6
In this problem, we will consider problems of finding minimum cost paths in directed networks. You are performing logistics analysis for a company that distributes products from several distribution centers located around the US. You are considering adding a new distribution center to serve key cities in the Great Basin area. Currently, you operate single distribution center in Sacramento and serve all of the Great Basin cities from there. You are considering opening a new DC in Salt Lake City to improve service and reduce outbound transportation costs from the DC. See the map at the end of this assignment. Currently, your customers are located in all of the major and mid-sized cities represented by blue circles on the map. You have compiled data on the major highway routes that your truck fleet will use when traveling between your key customer areas and your distribution centers. Figure 1 summarizes the data. You have decided to collect both travel time and travel distance data. Travel distance will influence the costs of your truck transportation while travel time will allow you to understand you quickly you can deliver customer orders.
To provide a baseline, we will first consider the current sole distribution center in Sacramento. We would like to know the distance from Sacramento to each of the customer cities (including Salt Lake City) and the travel time.
1. Use Dijkstra’s Algorithm to separately compute two minimum cost path directed outtrees from Sacramento. For the first tree, minimize the travel distance from Sacramento. Recall that an out-tree from an origin will specify a unique path from that origin to every destination. For this part of the problem, please use the python code that I provided to you that implements Dijkstra’s Algorithm. To help you get started, I start specifying a directed network for the problem using networkx in attached python code and also show you how to extract the tree information.
2. Does the minimum travel distance out-tree from Sacramento specify all the same paths as the minimum travel time out-tree? If you had to choose a set of paths, which do you think are more reasonable in this application?
Step by step
Solved in 2 steps
