Solution Found!
Locations for a New Factory Darren Magot works for US
Chapter 14, Problem 14.1.136(choose chapter or problem)
Darren Magot works for US Paper Products in New York City. His company is investigating locations for a new factory that will produce a line of disposable clothing. The cities Darren needs to visit are Atlanta, Dallas, Philadelphia, and Washington, DC. The one-way flight prices between these cities are given in the table below.
\(\begin{array}{lccccc} & \text { Atlanta } & \text { Dallas } & \begin{array}{c} \text { New } \\ \text { York } \end{array} & \begin{array}{c} \text { Philadel- } \\ \text { phia } \end{array} & \text { Washington } \\ \hline \text { Atlanta } & * & \$ 182 & \$ 197 & \$ 159 & \$ 180 \\ \text { Dallas } & \$ 182 & * & \$ 115 & \$ 115 & \$ 110 \\ \text { New York } & \$ 197 & \$ 115 & * & \$ 55 & \$ 156 \\ \text { Philadelphia } & \$ 159 & \$ 115 & \$ 55 & * & \$ 205 \\ \text { Washington } & \$ 180 & \$ 110 & \$ 156 & \$ 205 & * \end{array}\)
a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges.
b) Use the nearest neighbor method to approximate the optimal route for Darren to travel to each city and return to New York City. Give the cost of the route determined.
c) Randomly select another route for Darren to travel from New York City to the other cities and return to New York City and then compute the cost of this route. Compare this cost with the cost determined in part (b).
Questions & Answers
QUESTION:
Darren Magot works for US Paper Products in New York City. His company is investigating locations for a new factory that will produce a line of disposable clothing. The cities Darren needs to visit are Atlanta, Dallas, Philadelphia, and Washington, DC. The one-way flight prices between these cities are given in the table below.
\(\begin{array}{lccccc} & \text { Atlanta } & \text { Dallas } & \begin{array}{c} \text { New } \\ \text { York } \end{array} & \begin{array}{c} \text { Philadel- } \\ \text { phia } \end{array} & \text { Washington } \\ \hline \text { Atlanta } & * & \$ 182 & \$ 197 & \$ 159 & \$ 180 \\ \text { Dallas } & \$ 182 & * & \$ 115 & \$ 115 & \$ 110 \\ \text { New York } & \$ 197 & \$ 115 & * & \$ 55 & \$ 156 \\ \text { Philadelphia } & \$ 159 & \$ 115 & \$ 55 & * & \$ 205 \\ \text { Washington } & \$ 180 & \$ 110 & \$ 156 & \$ 205 & * \end{array}\)
a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges.
b) Use the nearest neighbor method to approximate the optimal route for Darren to travel to each city and return to New York City. Give the cost of the route determined.
c) Randomly select another route for Darren to travel from New York City to the other cities and return to New York City and then compute the cost of this route. Compare this cost with the cost determined in part (b).
ANSWER:Step 1 of 4
Since there are 5 cities for Darren to visit, the weighted graph has 5 vertices. This problem is a classic Travelling Salesman Problem.
Since there are 5 vertices, we will use a pentagon as a geometric figure to arrange the cities. You can select any suitable geometric figure according to the number of vertices you have (i.e.) if it's three, then a triangle will be appropriate, if it's 4 vertices then a rectangle or any quadrilateral, and so on.