Running a business requires making a lot of decisions. To be competitive, they have to be good. There are two complications, though: 1. Some problems are computationally very hard to solve. 2. In reality, we are dealing with uncertainty, so we do not even know what exact problem setting we should optimize for.
The AI4TSP Competition is trying to foster research on the intersection of optimization (addressing the first issue of efficient computation for hard problems) and artificial intelligence (addressing the issue of handling uncertainty). TSP stands for Traveling Salesperson Problem, one of the most studied routing problems in the optimization community. The task is to determine the order in which to visit a given set of locations, starting from, and returning to, a given home location, such that the total travel time is minimized. In its original form, the travel times between all locations are known upfront. In the competition, these times were not known but sampled according to a probability distribution. The objective was to visit as many locations as possible within a given period of time, whereby each location was associated with a specific reward. To complicate matters further, the locations that were visited on the tour had to be reached within fixed time windows. Arriving too early meant having to wait until the location would open, arriving too late was associated with penalties.
When travel times are known, the problem looks innocent enough. However, consider this: The number of possible tours grows more than exponentially and is given by “n! = 1 * 2 * 3 … * n” (n factorial) for a problem instance with n locations. If we could evaluate, in parallel, one potential tour for every atom in the universe, and each atomic processor could evaluate the tours at Planck time, which is the shortest time unit that anything can be measured in, and we run that computer from the Big Bang until today - then we could not even enumerate all solutions for just one TSP instance with 91 locations. The biggest problems at the competition had 200 locations - with over 10 to the power of 375 potential solutions.
The competition consisted of two tracks. In the first, we had to determine a tour for a given TSP instance that would work well on expectation when averaged over all possible travel time scenarios. That is to say: A tour had to be chosen, and then we had to stick to that tour no matter how the travel times turned out when executing the tour. The results were then averaged ten times over 100,000 scenarios to determine the winner.
In the second track, we were allowed to build the tour on the fly. At every location, we could choose which location we were to go to next, taking into account how much time had already elapsed. The policy that determined how to choose the next location was evaluated on 100 travel time realizations for each of 1,000 different TSP instances to determine the winner.
InsideOpt optimization expert Dr. Meinolf Sellmann collaborated with Prof. Dr. Kevin Tierney, Dr. Tapan Shah at GE Research, Fynn Schmitt-Ulms, and Andre Hottung from the University of Bielefeld to compete and win 1st Prize in both tracks.
Congratulations, Meinolf and Team!