Part a: $(2\mathrm{.}5$ points$)$

Logistics is important not only for providers of goods, but also for providers of services. Transportation is often the primary concern for companies that provide on$-$site or in$-$person services. One such example is a traveling circus like Ringling Brothers and Barnum $\backslash$& Bailey, "The Greatest Show On Earth".

The Ringling Brothers and Barnum $\backslash$& Bailey circus "cheats" by actually having two touring circuses, the "red" circus and the "blue" circus, which tour the country simultaneously and thus are able to cover more cities.

In this homework, we will be looking at the travels of a fictional circus with just a single touring unit. This Atlanta$-$based circus plans to visit $24$ cities, listed in the table below. After visiting all of the cities, the circus will return to Atlanta.

As one might imagine, the travel costs associated with a circus are quite high. Special vehicles, equipment, foods, etc. are needed to transport the tigers, elephants and other circus animals. Other equipment, such as high$-$wire apparatus and set construction materials, are also expensive to transport. Therefore, the circus would like to minimize its transportation costs during its national tour. Of course, a benefit of minimizing travel time is that the circus will have more time to perform, and thus generate more revenue. Because the special circus vehicles can only travel on major highways, we can assume a constant speed for every highway. Therefore, minimizing travel time is equivalent to minimizing travel distance in this case.

The goal of the circus is to find a good tour of all the cities; that is$,$ to find a path that visits each city and then returns to its starting point. Of course, some tours are shorter thanothers, and the optimal tour is the one which covers the least total distance.

The raw city$-$to$-$city distance data $($HW$2$data.xls$)$ can be found in an Excel spreadsheet on Canvas. All distances are symmetric; the distance from city A to city B is the same as the distance from city B to city A$.$

$1.$ Use your own intuition to get the shortest$-$distance circus tour you can find. Do not use any of the algorithms from class $-$ don't worry, you'll have plenty of opportunity for that in the rest of the homework, and your grades will not depend on the quality of the solution you find in this part. For now, just try using your intuition and logic. Draw your best answer clearly on a copy of the map $($HW$1$map.gif$),$ and give the total distance.

$2.$ Using the distances provided on the website $($do not just go by eye, as the graphical plot is not to scale$),$ use the traditional Nearest Neighbor heuristic from class to find the best route for the circus to take. Draw your answer clearly on a copy of the map, provide a list of the edges in the order that you choose them, and give the total distance.

$3.$ Repeat the above question, but use the Nearest Insertion heuristic instead of Nearest Neighbor. Start your tour by choosing first the arc with minimum cost. Draw your answer clearly on a copy of the map, provide a list of the nodes in the sequence that you insert them, and give the total distance. $4.$ A truck stationed at the depot $($location $0)$ is to serve the demand of sales points $1$ through $7,$ depicted in Figure $1,$ using a single tour. The distances between the depot and the sales points are given in Table $1.$ The network is symmetric. $(3$ points$)$

Table $1$: Distances between depot and sales points

Figure $1$: Geographic Locations of Depot and Sales Points

Figure $2$: Minimum spanning tree

List of edges added:

$4$b$)$ The second step of Christofides heuristic is to identify the set of nodes $\backslash ($ S $\backslash )$ with odd degree with respect to the minimum spanning tree, and then find the minimum cost perfect node matching, $\backslash ($ W$^\{*\}\backslash ),$ of the nodes in $\backslash ($ S $\backslash ).$ In the minimum spanning tree you identified in $($a$),$ there should be $6$ nodes with odd degree with respect to the minimum spanning tree: $\backslash ($ S$=\backslash \{1,2,3,4,6,7\backslash \}\backslash ).$ If this is not the case, go back and rework your solution before proceeding. One of the pairs in the minimum cost perfect matching $\backslash ($ W$^\{*\}\backslash )$ is $\backslash ((1,4)\backslash ).$ Determine the two additional pairs included in $\backslash ($ W$^\{*\}\backslash ),$ and show your work. $4$c$)$ Draw the minimum spanning tree again on the network below, but this time, also include the arcs in $\backslash ($ W$^\{*\}\backslash )$ as dotted lines. Then, specify a tour $\backslash ($ T$^\{$C$\}\backslash )$ of the nodes that uses each arc in your diagram exactly once. Note that in order to use each arc exactly once, you will visit some nodes more than once in the tour $\backslash ($ T$^\{$C$\}\backslash ).$

$2$

$3$

$5$

$7$

$1$

$4$

$6$

Figure $3$: Minimum spanning tree with perfect node matching

Tour using each arc in this diagram:

$4$d$)$ Complete Christofides heuristic by introducing shortcuts to avoid revisiting nodes in $\backslash ($ T$^\{$C$\}\backslash ),$ such that a feasible solution to this instance of TSP results. Draw your TSP tour on the diagram provided. Indicate the cost of the TSP tour.

$2$

$3$

$7$

$1$

$5$

$4$

$6$

Figure $4$: TSP tour

Cost of TSP tour: