So, there’s this traveling salesman who wants to …. Wait! This is not the prelude to a bad joke, this is a mathematical problem of current importance. The traveling salesman is headquartered in city 0, and needs to visit cities 1, 2, 3, …, n on a business trip and then return to city 0. The problem, called the traveling salesman problem (or TSP) is to find the cheapest route to complete the trip. How important is the TSP ? UPS and FedEx have to solve it daily in each of their delivery areas; a small inefficiency in route times the number of trucks times 365 days in a year could cost a company hundreds of millions of dollars in a year. So, this is no joke. Unfortunately, the TSP is truly no laughing matter mathematically. There is an algorithm for finding the best route: list all of the routes and find the cheapest one. However, if you have just n=30 sites for delivery the total number of routes to check is 265,252,859,812,191,058,636,308,480,000,000 which will choke even the fastest of computers. So this algorithm is impractical. There is a strong possibility that there is no algorithm that is both accurate and fast. So, the big money is on developing TSP algorithms that are fast enough and give good enough approximations to the exact answers (i.e., do not waste too much of the company’s money). Meanwhile, researchers are working hard to improve algorithms and, as mathematicians tend to do, some are devising whimsical uses of TSP code. What does the following image look like?
It shouldn’t be hard to recognize the Mona Lisa. However, some zooming in reveals a surprise: the image is actually the path generated by a TSP algorithm. The “cities” are located randomly but with a density equal to the gray scale of the target image (Mona Lisa). The punch line for this traveling salesman story is that art is something that Brown can do for us today.
