AI for Traveling Salesperson Problem

This feature thread tracks the development and application of AI and optimization techniques to solve complex routing problems like the Traveling Salesperson Problem (TSP). Initial efforts focused on addressing computationally hard problems and handling uncertainty in real-world scenarios. Shopify's optimization expert Meinolf Sellmann collaborated with colleagues to win first prize in both tracks of the AI4TSP Competition. The first track involved determining a tour that would work well on expectation, averaged over all possible travel time scenarios, using dialectic search. The second track allowed for building the tour on the fly at every location, taking into account elapsed time, using deep reinforcement learning. Key to both approaches is allowing the machine to learn from prior experience and adjust the program automatically, embodying the concept of self-programming machines.