Ads Top

Traveling Salesman Art


The Traveling Salesman Problem is a classic mathematical problem that asks the question, “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" (https://en.wikipedia.org/wiki/Travelling_salesman_problem). The problem dates back to at least the 19th century and continues to be a challenge for mathematicians and computer scientists to this day.

In February, 2009, Robert Bosch—the Robert and Eleanor Biggs Professor of Natural Science at Oberlin College, who's primary research is the use of optimization techniques to create artwork—created a 100,000-city version of the traveling salesman problem which replicates Leonardo da Vinci's Mona Lisa (http://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html). Since that time, researchers have worked to find the most optimal “tour” for the Mona Lisa’s cities. Additionally, new artworks have emerged including a 140,000-city version of Botticelli’s The Birth of Venus and a 200,000 city rendering of Vermeer’s Girl with a Pearl Earring (http://www.math.uwaterloo.ca/tsp/data/art/).

Having just learned of this interesting challenge and seeing the results drawn as static images, I couldn’t resist downloading the data for some of the best known solutions and visualizing them in Tableau.



The visualization allows you to choose from six famous works of art. By hovering over the art, you can see each individual point and its location within the overall path. In addition, you can choose how to color the lines:

Single Color - Colors the entire tour using a single color (shown above)
Ordered by Path - Colored by the path in which the "cities" (points) are connected, from light to dark.
Ordered by Point - Colored by the city numbers, from light to dark.

For example, here’s The Birth of Venus colored by path.



And, as an added bonus, I've created an animation showing the connection of points, this time using the Mona Lisa.



Hope you enjoy these! And please take some time to read through the articles I’ve linked to above. The challenge is fascinating, as is the work of Robert Bosch and his colleagues. Thanks for reading!

Ken Flerlage, March 4, 2020

4 comments:

  1. Hi,
    How order column was created?

    ReplyDelete
    Replies
    1. I opened the data in Excel then just added a sequential number column.

      Delete
  2. How was this animation developed?

    ReplyDelete
    Replies
    1. I grouped the line segments into groups of a few thousand, the used pages to animate. I captured all of that with a screen recording tool called ScreenToGif.

      Delete

Powered by Blogger.