Jump To中央區塊/Main Content :::
:::

Seminars

Colloquium

The Traveling Salesman Problem: Amazon Deliveries, Pub Walks, and Astro Tours

2025/06/19 (Thu.) 10:30~11:30
  • Date : 2025/06/19 (Thu.) 10:30~11:30
  • Location : Auditorium, 6 Floor, Institute of Mathematics (NTU Campus)
  • Speaker : William Cook (University of Waterloo)
  • Abstract :
    Amazon drivers go out on the road every day, each taking a Prime van in a traveling salesman problem tour through 150 or more customer stops, But even a whisper of the TSP strikes fear in the heart of the computing world. A Washington Post article reported it would take "1,000 years to compute the most efficient route between 22 cities." Claims such as this, however, ignore 70 years of intense study. A 22-city TSP can be easily handled with modern methods, even on an iPhone. And, coming to the aid of Amazon drivers, we describe techniques used to win the $100,000 top prize in the Amazon Last Mile Routing Challenge, together with Stephan Held and Keld Helsgaun.

    Going larger, we discuss methods used to find to precise optimality the shortest walking tour to 81,998 pubs in South Korea. Even larger, if you want to visit 136,606,128 stars, there is a 3D route, ready to go, that is guaranteed to be no more than 1.00018 times longer that a shortest-possible tour.

    The general setting is the following. Complexity theory suggests there are limits to the power of general-purpose computational techniques, in engineering, science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this discussion, demonstrating whether or not focused efforts on a single, possibly unsolvable, model will produce results beyond our expectations.
:::