Scattered Thoughts on the TSP for a baseball road trip

I have done a number of applications  that have a flavor of the Traveling Salesman Problem (TSP). That is, they concern themselves with visiting a number of locations in an efficient manner. None of these applications have ever concerned themselves with finding the optimal manner of visiting all the locations; a “good enough” solution has sufficed to date, and I’m not sure I have the mental horsepower to understand all that is involved in producing optimal or even near-optimal solutions.

That said, the problem that has always particularly intrigued me is that of the baseball road trip. This problem has an additional twist to it. On the one hand, it is only a 30 stop tour, which when using programs like Concorde is a piece of cake. But the additional twist is that there is not a game in every city every day. So it is as if the traveling salesman can only visit certain of his or her clients on certain days (Jones in Boise will only see you on Monday or Tuesday).

This twist really throws a wrench into any formulation of the TSP that I have ever come across (granted, I am not a professional researcher in the field). Essentially ,everyday, the cities which can be visited are just a subset of the 30 cities with baseball stadiums. And the next day, it is also a subset , but now possibly a different subset.

I’ve never been able to formulate this into any sort of structure, and as such have used greedy-ish algorithms of a sort. They simplify the solution, but that solution is likely far from optimal. So it is something I think about, though not all the time, and not particularly successfully !

UPDATE: It turns out the formulation of this variation of the TSP is called Traveling Salesman Problem with Time Windows (TSPTW)