TSP

I've just attended one of the best conference presentations I've ever witnessed!

The "Travelling Salesman Problem" is the most famous problem in Operational Research, and its intuitive nature makes it a great way to give the layman an idea of what OR is about. The classical problem is to find the shortest tour around a set of cities, given the distances between them. The speaker recalled that the 49-city problem [the lower-48 US state capitals plus Washington DC] was solved in 1954, and the record now is 85,900 cities! As well as being a rich field for Maths and computing, and having widespread applications [think shortest path for a robot collecting items in a warehouse, for example] the subject has great scope for visualisation and amusement. One problem solved by the speaker was the ultimate pub crawl in the UK [49,687 pubs!] illustrated with a Google maps "movie"! The image above illustrates a technical result, for which the progress of the algorithm was set to music! For the orienteers reading this - if anyone still is! - if you limit the length of the tour and look to maximize the value of visiting cities you have the "(Score) orienteering problem" that is studied by people who have never visited a control in their lives, and which we've all solved sub-optimally at times!

Oh, and my talk went well, with new interesting people met and chats with old friends. Second days at conferences are always better!