Part B: (4.5 points) 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) 0 1 2 3 4 5 6 7 0 - 27.9 54.6 42.0 56.5 37.0 30.9 34.1 1 - - 67.2 25.6 28.8 48.4 57.4 21.6 2 - - - 60.5 95.8 18.8 60.4 52.1 3 - - - - 39.4 43.1 70.2 12.2 4 - - - - - 77.2 84.5 44.4 5 - - - - - - 51.6 34.0 6 - - - - - - - 59.3 7 - - - - - - - - Table 1: Distances between depot and sales points Figure 1: Geographic Locations of Depot and Sales Points 2 3 5 1 0 4 6 7 2 4a) The first step of Christofides heuristic is to find the minimum spanning tree on the network. Use Kruskals algorithm to identify the MST on the network, and draw your solution on the copy of the network provided. Also, provide a list of the edges that you added to the MST, in the order that you added them. Figure 2: Minimum spanning tree List of edges added: 4b) The second step of Christofides heuristic is to identify the set of nodes S with odd degree with respect to the minimum spanning tree, and then find the minimum cost perfect node matching, W , of the nodes in S . In the minimum spanning tree you identified in (a), there should be 6 nodes with odd degree with respect to the minimum spanning tree: S = { 1, 2, 3, 4, 6, 7} . If this is not the case, go back and rework your solution before proceeding. One of the pairs in the minimum cost perfect matching W is (1,4). Determine the two additional pairs included in W , and show your work. 2 3 5 1 0 4 6 7 3 4c) Draw the minimum spanning tree again on the network below, but this time, also include the arcs in W as dotted lines. Then, specify a tour T C 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 T C . Figure 3: Minimum spanning tree with perfect node matching Tour using each arc in this diagram: 4d) Complete Christofides heuristic by introducing shortcuts to avoid revisiting nodes in T C , 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. Figure 4: TSP tour Cost of TSP tour: 2 3 5 1 0 4 6 2 3 5 1 0 4 6 7 7 4 5 5. An online book retailer packs books into boxes, and the retailer has a contract with a shipper specifying that any box weighing less than or equal to 20 pounds can be shipped for $8 per box. Because the boxes are relatively large, and books relatively small, it is safe to assume that the volume of the boxes is not a constraint for any order. Instead, assume that the 20- pound weight is the relevant constraint on each box. Obviously, one book cannot be split across separate boxes. An order is received from an avid reader in Fayetteville, AR, for the books specified in Table 3. (1.5 points) Table 2: Book weights (lbs) 5a) What is lower bound on the shipment cost for this order? 5b) Use the best fit bin packing heuristic to pack the books into boxes, and process the books in the order they are indexed in Table 3 above. Specify the cost of the associated shipment. 6 6 5c) Theoretically, offline bin packing heuristics have better performance than online bin packing heuristics. In this case, we do have access to all item sizes when starting a heuristic, so it should be advantageous to use an offline heuristic. Use the first fit decreasing bin packing heuristic to pack the books into boxes, and specify the cost of the associated shipment.