IOE 899 Seminar: William J. Cook, University of Waterloo
WHEN: November 1, 2017 4:10 pm-5:00 pm
Title: The traveling salesman problem with road distances
Abstract: Following Dantzig, Fulkerson, and Johnson, we show that a certain tour of 49,603 sites in the US is shortest possible, measuring distance with point-to-point routes obtained from Google Maps. We highlight a cost-refinement technique that allows the cutting-plane method to generate lower bounds on the tour length without explicit knowledge of the full distance matrix. The talk is based on joint work with Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun.