on June 28, 2020, 6:53 pm
That concept from graph theory and Computer Science is called the traveling salesman problem, as in going from town to town with your stuff nobody really wants. It has been very heavily studied for many years, and it has been shown that no algorithm can be proven to be optimal at scale. In real-world scaled applications the idea is to get within some threshold compared to optimal.
So I played around with it and have what I believe is the right answer (14 nodes is not that bad to compute with a few heuristics), using the first-shown driving distances from Google Maps.
Consider taking a shot at what might look reasonable to you for a path starting at UIUC or any other school (where you start does not matter because it's a loop). There are some non-optimal routes that are close to what I computed in mileage (e.g., it is no big deal whether you go to MSU or UM first in the pair, because they are so close, and the optimal path has them together).
A sample approach of simply going to the closest campus to the one you are at without repeating, starting in Urbana, came within 20%, starting with the sequence Urbana -> Purdue -> IU -> OSU -> Mich -> MSU. Closing the loop was a killer.
1
Message Thread Traveling salesman problem and Big Ten campuses - Potomac June 28, 2020, 6:53 pm
« Back to index | View thread »