A car has to pick up each person and take them to their destination. I am trying to find the shortest tour that will do this. How can I find the shortest path between any s and t.... visiting all vertices, and without coming back to the start?
In this case I have 10 points. After each For[]
, I obtain an array with the distances from i to j.
t = {
{{2, 1}, {5, 2}},
{{7, 1}, {9, 4}},
{{9, 2}, {6, 6}},
{{5, 4}, {2, 3}},
{{4, 5}, {7, 9}},
{{8, 5}, {2, 4}},
{{3, 7}, {7, 7}},
{{4, 8}, {1, 10}},
{{3, 10}, {10, 7}},
{{9, 10}, {9, 8}}
}
(* t[[i,j,k] i\[Rule]Trip Nºi j\[Rule] \
1=Inicio=Pick-Up 2=Fin=Drop-Off k\[Rule] 1ª o 2ª componente (es \
decir x ó y) *)
Array[t2t, {10, 10}]
For[i = 1, i <= 10, i++,
For[j = 1, j <= 10, j++,
If[i != j,
t2t[i, j] =
Sqrt[(t[[j, 1, 1]] - t[[i, 2, 1]])^2 +
(t[[j, 1, 2]] - t[[i, 2, 2]])^2], t2t[i, j] = Infinity
(* In t2t there is the distance from i to j
different from distance from j to i, in general *)
]
]
]
I want to find the shortest tour through the 10 vertices, with the weight/distsances t2t[i,j]
visiting all vertices, and not coming back to the start.
-- After comments on March´2015 I add the original problem published in ORMS magazine -- Now this kind of puzzles are published in Amalytics ( for example electriying in page 74 http://viewer.zmags.com/publication/79b53367#/79b53367/74 )