The following table shows the travel costs on the directed links of a fully connected network....

Transcribed Image Text:

The following table shows the travel costs on the directed links of a fully connected network. Using the data given in this table, 0 1 28.55 2 3 12.10 43.15 23.10 28.85 52.95 4 5 6 66.10 38.35 79.70 52.55 53.65 66.90 88.55 54.75 79.00 41.40 71.30 7 8 17.00 77.60 4.15 71.70 0 1 15.80 2 54.95 48.90 3 39.80 27.95 37.85 4 49.80 63.95 46.15 43.50 5 46.50 55.70 28.10 72.30 93.65 6 99.55 84.25 86.15 60.40 63.70 99.85 7 31.00 28.80 21.35 34.55 69.55 67.65 67.95 8 60.35 75.35 46.85 68.15 39.05 75.05 48.90 52.60 66.00 61.10 60.75 83.50 87.30 92.50 86.40 62.00 64.00 9 77.80 42.55 91.45 79.05 19.15 44.95 41.60 35.55 67.30 55.30 54.20 72.30 9 55.20 61.90 76.40 35.35 78.60 93.70 94.40 88.35 81.90 77.40 68.30 80.35 1) Present the integer programming model of the Asymmetric TSP (ATSP). You need to explicitly present at least 3 "sub-tour breaking" constraint functions in the model. 2) Use an optimization software to solve the corresponding Assignment Problem (AP). 3) If the solution found in 2) is not feasible, find a feasible ATSP solution based on the AP solution and evaluate its quality. 4) Perform 2 iterations of the 2-exchange procedure for finding new (and possibly better) feasible solutions of the ATSP problem. The following table shows the travel costs on the directed links of a fully connected network. Using the data given in this table, 0 1 28.55 2 3 12.10 43.15 23.10 28.85 52.95 4 5 6 66.10 38.35 79.70 52.55 53.65 66.90 88.55 54.75 79.00 41.40 71.30 7 8 17.00 77.60 4.15 71.70 0 1 15.80 2 54.95 48.90 3 39.80 27.95 37.85 4 49.80 63.95 46.15 43.50 5 46.50 55.70 28.10 72.30 93.65 6 99.55 84.25 86.15 60.40 63.70 99.85 7 31.00 28.80 21.35 34.55 69.55 67.65 67.95 8 60.35 75.35 46.85 68.15 39.05 75.05 48.90 52.60 66.00 61.10 60.75 83.50 87.30 92.50 86.40 62.00 64.00 9 77.80 42.55 91.45 79.05 19.15 44.95 41.60 35.55 67.30 55.30 54.20 72.30 9 55.20 61.90 76.40 35.35 78.60 93.70 94.40 88.35 81.90 77.40 68.30 80.35 1) Present the integer programming model of the Asymmetric TSP (ATSP). You need to explicitly present at least 3 "sub-tour breaking" constraint functions in the model. 2) Use an optimization software to solve the corresponding Assignment Problem (AP). 3) If the solution found in 2) is not feasible, find a feasible ATSP solution based on the AP solution and evaluate its quality. 4) Perform 2 iterations of the 2-exchange procedure for finding new (and possibly better) feasible solutions of the ATSP problem.

Answer rating: 100% (QA)

3 Feasibility Check and Evaluation If the solution from the AP is not feasible for the ATSP you ne... View the full answer