When discussing VRP heuristics, we talked about how both TSP Partitioning and Sweep make use of...

Transcribed Image Text:

When discussing VRP heuristics, we talked about how both TSP Partitioning and Sweep make use of the Next Fit bin packing heuristic. In a couple of sentences, discuss why Next Fit is a better choice than First Fit or Best Fit to use within the context of these VRP heuristics. HINT: This is not related to the ability to immediately dispatch closed vehicles; there is another discussion we have had about this in class a few times. Table 1: Customer lot sizes (tons) and X-Y coordinates Y 5 2 4 4 Cust Lot size X 1 4 3 2 3 4 5 сл 6 7 APPENDIX 8 9 10 9 6 3 7 11 2 4 8 1 3 10 8 7 7 2 7 4 6 0 8 3 6 0 3 0 1 2 3 4 5 6 7 8 9 10 Table 2: Travel distances (based on Euclidean distances between x-y coordinates) 0 3 4 10.8 8.9 9.1 7.1 7.3 5.4 2.0 5.1 3.6 10.8 8.9 7.0 10.6 3.6 9.2 4.0 6.7 9 8 7 6 5 4 3 2 1 1 5.1 3.6 9.1 7.1 7.8 6.7 2.2 6.1 5.8 5.4 1 2 3.6 3.6 7.3 5.4 4.5 524 7.2 1.4 5.7 2.2 22 3.2 2.0 원원회 5.0 5.0 8.1 3.6 NH 7.2 4.1 446 4 4.1 4.1 6.1 2.2 177 5.7 52 2.2 5 7.0 7.8 4.5 5.0 4.1 8.0 5.8 6.0 3.0 3.2 10 6 10.6 6.7 7.2 5.0 4.1 8.0 7.1 2.0 8.5 5.1 5 7 3.6 2.2 1.4 8.1 6.1 5.8 7.1 5.8 3.6 4.0 8 9.2 6.1 5.7 3.6 2.2 6.0 2.0 5.8 6.7 3.2 9 4.0 5.8 2.2 7.2 5.7 3.0 8.5 3.6 6.7 3.6 2 6 8 10 12 Figure 1: Graphical depiction of instance (labels are customer indices) 10 6.7 5.4 3.2 4.1 2.2 3.2 5.1 4.0 3.2 3.6 Consider the vehicle routing problem defined by the data in Table 1 (Appendix), where the lot size in tons and the x and y coordinates are provided for each of 10 customers. Suppose the depot is located at the origin (0,0) and each vehicle has the capacity to hold 15 tons of goods. A complete distance matrix is provided in Table 2 and a graphical depiction is in Figure 1 (both in Appendix). Use this information to answer all questions in this assignment. When discussing VRP heuristics, we talked about how both TSP Partitioning and Sweep make use of the Next Fit bin packing heuristic. In a couple of sentences, discuss why Next Fit is a better choice than First Fit or Best Fit to use within the context of these VRP heuristics. HINT: This is not related to the ability to immediately dispatch closed vehicles; there is another discussion we have had about this in class a few times. Table 1: Customer lot sizes (tons) and X-Y coordinates Y 5 2 4 4 Cust Lot size X 1 4 3 2 3 4 5 сл 6 7 APPENDIX 8 9 10 9 6 3 7 11 2 4 8 1 3 10 8 7 7 2 7 4 6 0 8 3 6 0 3 0 1 2 3 4 5 6 7 8 9 10 Table 2: Travel distances (based on Euclidean distances between x-y coordinates) 0 3 4 10.8 8.9 9.1 7.1 7.3 5.4 2.0 5.1 3.6 10.8 8.9 7.0 10.6 3.6 9.2 4.0 6.7 9 8 7 6 5 4 3 2 1 1 5.1 3.6 9.1 7.1 7.8 6.7 2.2 6.1 5.8 5.4 1 2 3.6 3.6 7.3 5.4 4.5 524 7.2 1.4 5.7 2.2 22 3.2 2.0 원원회 5.0 5.0 8.1 3.6 NH 7.2 4.1 446 4 4.1 4.1 6.1 2.2 177 5.7 52 2.2 5 7.0 7.8 4.5 5.0 4.1 8.0 5.8 6.0 3.0 3.2 10 6 10.6 6.7 7.2 5.0 4.1 8.0 7.1 2.0 8.5 5.1 5 7 3.6 2.2 1.4 8.1 6.1 5.8 7.1 5.8 3.6 4.0 8 9.2 6.1 5.7 3.6 2.2 6.0 2.0 5.8 6.7 3.2 9 4.0 5.8 2.2 7.2 5.7 3.0 8.5 3.6 6.7 3.6 2 6 8 10 12 Figure 1: Graphical depiction of instance (labels are customer indices) 10 6.7 5.4 3.2 4.1 2.2 3.2 5.1 4.0 3.2 3.6 Consider the vehicle routing problem defined by the data in Table 1 (Appendix), where the lot size in tons and the x and y coordinates are provided for each of 10 customers. Suppose the depot is located at the origin (0,0) and each vehicle has the capacity to hold 15 tons of goods. A complete distance matrix is provided in Table 2 and a graphical depiction is in Figure 1 (both in Appendix). Use this information to answer all questions in this assignment.

Answer rating: 100% (QA)

Ans a ZA 2C ZB ZD OA Oc In given ... View the full answer