Traveling Salesman Problem Visualization

Over the last 9 weeks I've had the pleasure of being enrolled in the Discrete Optimization course at Coursera taught by Pascal Van Hentenryck. I had previously taken several of other massive open online courses (MOOCs), but this was the most challenging and rewarding. The key ingredients of this course were the unquestionable enthusiasm by its instructor and assistants, who created an excellent series of lectures and were personally involved at every step, as well as a game-like grading system, where the better your algorithm, the better your grade. It was rather intense! None of the programming assignments are issued with a well-defined strategy for creating a solution. Instead, the lectures cover various types of techniques and tools to be implemented and tinkered with by the students. Another interesting feature of the course is that all of the lectures and assignments are available from the first day. Most courses impose a schedule of lectures and assignments to be watched and completed on a week-by-week basis. The open structure of Discrete Optimization had me feeling a bit bewildered at first. They do provide a suggested study plan, so I (mostly) stuck with that and was able to make steady progress throughout the course.

One of the topics that resonated with many of the students, myself included, was that of Local Search. It's an idea that's easy to conceptualize and program, yet very powerful. I implemented a Local Search solution for the Traveling Salesmen Problem and, along the way, added some code to visualize some of the larger solutions. It looked pretty cool to see so many points connected together by a continuous route. I began experimenting with animating the algorithm as it finds a solution. Later, the professor's assistant (AKA graciously-answering-forum-questions-Carleton Coffrin) put out a call for the students to create visualizations of various heuristics that can be used to solve TSP. Here is my contribution – it displays Greedy algorithm, Local Search, and Simulated annealing strategies for a group of US cities.

• www.youtube.com/v/SC5CX8drAtU?hl=en_US&version=3&rel=0

I’ve seen some interest in knowing how this was created. Here are the steps:

• I wanted to use some "real" map data to help illustrate the problem.  From a list of cities from geonames.org, filtered by country and population to generate data sets
• Ran these through my TSP solver from the Discrete Optimization course assignment, collecting the intermediate routes as improvements are made
• Generated a metric ton of still images to illustrate the transitions between the routes - this involves:
• translating the points and lines onto a bitmap
• "tweening" many frames between each route to provide smooth transitions. I tried several different "easing functions" but ended up with something like "easeInOutQuad" shown on this Easing Functions page
• … also generate images for the distance and temperature
• Imported these as numbered frames into Adobe Premiere Elements - I don't use anything fancy, just the text, some cross-dissolve transitions, and alter the speed of the frames - the same could likely be done with open source editors ( VLMC?)
• The map of the US is a "flat" Mercator projection so that the latitude and longitude coordinates from the city list will show up in approximately the correct location - it's from here: Mercator Projection.svg
• ... and then a bunch of slicing and dicing and mixing and matching inside the video editor to "tell the story"

The code was done in .NET – here’s some pseudo-code used to generate the animation:

minX, minY = points.Minimum(X), points.Minimum(Y) maxX, maxY = points.Maximum(X),
  points.Maximum(Y) w = maxX - minX h = maxY - minY imgW = 720 imgH = 480 frame = 0
  
foreach routePair in routes.Pairwise() edgePairs = CalculateEdgePairs(routePair.Current,

route.Next) for tween in [0..30] tweenFactor = EaseInOut(tween) using (var bitmap

= new Bitmap(imgW, imgH)) using (var g = Graphics.FromImage(bitmap)) RenderPoints(g,

points, brush); RenderEdges(g, edgePairs, tweenFactor, pen); bitmap.Save(filename

+ frame++, ImageFormat.Png); RenderPoints(g, points, brush) foreach (var p in points)

point = Translate(p); g.FillEllipse(brush, point.X, point.Y, _pointSize); RenderEdges(g,

edgePairs, tweenFactor, pen) // interpolate the edge changes foreach (var edgePair

in edgePairs) point1Current = Translate(points[edgePair.Current.Point1]); point1Next

= Translate(points[edgePair.Next.Point1]); point2Current = Translate(points[edgePair.Current.Point2]);

point2Next = Translate(points[edgePair.Next.Point2]); g.DrawLine(pen, (point1Next.X

- point1Current.X)*tweenFactor + point1Current.X, (point1Next.Y - point1Current.Y)*tweenFactor

+ point1Current.Y, (point2Next.X - point2Current.X)*tweenFactor + point2Current.X,

(point2Next.Y - point2Current.Y)*tweenFactor + point2Current.Y); Translate(point)

new Point( X = (point.X - minX) / w * _imgW, Y = (point.Y - minY) / h * _imgH) EaseInOut(x)

(x*x)/(x*x + (1 - x)*(1 - x))