hw5

.docx

School

Georgia Institute Of Technology *

*We aren’t endorsed by this school

Course

6203

Subject

Industrial Engineering

Date

May 8, 2024

Type

docx

Pages

10

Uploaded by MegaFrog4307

HOMEWORK ASSIGNMENT 5 ISYE 6203: Transportation and Supply chain Systems Shounak Kshirsagar Question (a): The input, SymmetricDistances_a.txt , contains a symmetric distance matrix representing the travel times between each pair of locations. The Concorde solver processed this matrix to compute an optimal route with a total travel time of 7879 units. The sequence of locations visited in this optimal route is: 0 → 2 → 17 → 22 → 5 → 13 → 6 → 25 → 4 → 16 → 10 → 20 → 24 → 1 → 11 → 23 → 26 → 3 → 8 → 12 → 27 → 14 → 28 → 18 → 29 → 21 → 7 → 9 → 19 → 15 → 0. This route begins and ends at location 0, completing a full cycle as required. Number of Nodes: 30 Explicit Lengths (CC_MATRIXNORM) Set initial upperbound to 7879 (from tour) LP Value 1: 7827.000000 (0.00 seconds) LP Value 2: 7833.500000 (0.00 seconds) LP Value 3: 7841.500000 (0.01 seconds LP Value 4: 7845.500000 (0.01 seconds) LP Value 5: 7845.500000 (0.01 seconds) LP Value 6: 7848.000000 (0.01 seconds) LP Value 7: 7850.875000 (0.02 seconds) LP Value 8: 7863.333333 (0.02 seconds) LP Value 9: 7866.250000 (0.02 seconds) LP Value 10: 7870.428571 (0.02 seconds) LP Value 11: 7875.000000 (0.02 seconds) LP Value 12: 7879.000000 (0.02 seconds) New lower bound: 7879.000000 Final lower bound 7879.000000, upper bound 7879.000000 Exact lower bound: 7879.000000 DIFF: 0.000000 Final LP has 46 rows, 56 columns, 326 nonzeros Optimal Solution: 7879.00 Number of bbnodes: 1 Total Running Time: 0.04 (seconds) *** ***
*** You chose the Concorde(CPLEX) solver *** *** Cities are numbered 0..n-1 and each line shows a leg from one city to the next followed by the distance rounded to integers*** 30 30 0 2 57 2 17 156 17 22 118 22 5 335 5 13 101 13 6 133 6 25 124 25 4 194 4 16 97 16 10 110 10 20 337 20 24 85 24 1 340 1 11 189 11 23 223 23 26 370 26 3 699 3 8 231 8 12 654 12 27 563 27 14 233 14 28 259 28 18 238 18 29 254 29 21 295 21 7 350 7 9 125 9 19 399 19 15 332 15 0 278 Question (b): To meet the requirement that the campaign can start from any location and end at any other location, a dummy node (node 30) was introduced in the SymmetricDistances_b.txt file. This node is connected to all other nodes with zero-cost edges, effectively handling the flexibility needed for an open tour. The solver, treating the dummy node as any regular node, starts and ends the tour at this node due to its zero-cost connections. This strategic addition ensures that the solver treats the route
as a closed loop while actually allowing the campaign to begin and conclude at any chosen real location. For example, in the solver's output, transitions involving the dummy node — from node 8 to node 3 via node 30, followed by node 12 to node 5 — indicate that the actual tour begins at node 12 and ends at node 3, omitting the dummy node from practical consideration. Tour Sequence : 12 → 5 → 22 → 13 → 6 → 25 → 4 → 16 → 10 → 20 → 24 → 0 → 2 → 17 → 11 → 1 → 15 → 19 → 9 → 7 → 21 → 29 → 18 → 28 → 23 → 26 → 14 → 27 → 8 → 3 Total Travel Time : The solver computed the total distance as 7131 units. Solver output: Number of Nodes: 31 Explicit Lengths (CC_MATRIXNORM) Set initial upperbound to 7131 (from tour) LP Value 1: 7056.500000 (0.00 seconds) LP Value 2: 7109.500000 (0.00 seconds) LP Value 3: 7114.000000 (0.00 seconds) LP Value 4: 7121.000000 (0.00 seconds) LP Value 5: 7122.000000 (0.00 seconds) LP Value 6: 7122.200000 (0.01 seconds) LP Value 7: 7122.857143 (0.01 seconds) LP Value 8: 7124.000000 (0.01 seconds) LP Value 9: 7129.200000 (0.01 seconds) LP Value 10: 7130.666667 (0.01 seconds) LP Value 11: 7131.000000 (0.02 seconds) New lower bound: 7131.000000 Final lower bound 7131.000000, upper bound 7131.000000 Exact lower bound: 7131.000000 DIFF: 0.000000 Final LP has 46 rows, 91 columns, 470 nonzeros Optimal Solution: 7131.00 Number of bbnodes: 1 Total Running Time: 0.03 (seconds) *** Your comments *** Question (b) *** *** *** You chose the Concorde(CPLEX) solver *** *** Cities are numbered 0..n-1 and each line shows a leg from one city to the next
followed by the distance rounded to integers*** 31 31 0 2 57 2 17 156 17 11 114 11 1 189 1 15 346 15 19 332 19 9 399 9 7 125 7 21 350 21 29 295 29 18 254 18 28 238 28 23 250 23 26 370 26 14 467 14 27 233 27 8 459 8 3 231 3 30 0 30 12 0 12 5 586 5 22 335 22 13 87 13 6 133 6 25 124 25 4 194 4 16 97 16 10 110 10 20 337 20 24 85 24 0 178 Question (c): the tour should start at the node 0 and end at node 1. This fixes the starting and end points. To tackle this, we add a dummy node but this time we give least cost to the connection from dummy node to node 0 and dummy node to node 1. Besides this we keep the connection from the dummy node to every other node to be very high number, so that the solver does not pick these routes in the optimal solution. Keeping least cost to between dummy node and node 0 will make solver pick the this as the start and at the end of tour to complete the full cycle it will have to again connect back to the dummy node, here, assignment of high costs of the connection between the dummy node and other nodes will enforce the solver to pick the node as the ending node and connect it back to the dummy node completing the full cycle. Now, in the output we can see node 30 being the dummy node which connects node 0 and node 1. From the output we can observe that, node 2 <- node 0 <- node 30 <-
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help