The Traveling Salesman Problem: Package Deliveries, Pub Walks, and Astro Tours
-
19 November 2025
4:30 PM - Meeting room nr. 300, Komenského náměstí 220/2
Before the lecture, there will be small refreshments outside the hall at 4 pm. During this time, you can discuss with each other and meet the speaker.
William Cook is a University Professor in the Department of Combinatorics and Optimization at the University of Waterloo, where he received his Ph.D. in 1983. Bill is a member of the U.S. National Academy of Engineering, a fellow of the American Mathematics Society, a fellow of the Society for Industrial and Applied Mathematics, and a fellow of the Institute for Operations Research and Management Science. He is the author of the popular book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Bill is a former Editor-in-Chief of the journals Mathematical Programming (Series A and B) and Mathematical Programming Computation. He is a past chair of the Mathematical Optimization Society and a past chair of the INFORMS Computing Society. Bill is currently visiting the Institute for Discrete Mathematics at the University of Bonn as a Research Fellow.
Abstract
Amazon drivers hit the road every day, each taking a delivery van in a traveling salesman problem (TSP) 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 in September 2025 reported "a laptop computer would take 1,000 years to figure out the best course" for 22 cities. Claims such as this ignore 70 years of intense study. A 22-city TSP can be handled easily 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 bars in 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.00016 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.
Share event