ScottyHoag.com - Traveling Salesman Problem

Scotty Hoag
Programmer Portfolio

scotty.hoag@gmail.com (209)-298-2622

Traveling Salesman Problem

It's the classic "Traveling Salesman Problem" in computer science! Given a list of cities and their location, find the shortest path that visits each of them once.

It's an NP-Hard problem, which means that it has been mathematically proven that there is very likely no fast solution. Writing a solver for the problem using "genetic algorithms" was one of my homework assignments in graduate school, and a really fun one at that.

Genetic Algorithms work by creating many random solutions, evaluating how good of a solution they are, then "breeding" the best ones to make the next generation of solutions. You treat bits of the parents' data as DNA and mix them to make children solutions with a little bit of info from each parent, along with random mutations to the genome.

In my sim, I cut off the simulation by a max of 1600 generations to keep within the homework's time restrictions. You are often limited by time restrictions in the real world, so you have to come up with the best approximate answer that you can with the time that you have.

Some things I added to my sim included 3D visualizations using VPython, and something used primarily in video games: octrees. The octree, visible as the green wireframe grid in the video, is a way of partitioning 3D space. Games use it to help physics performance by figuring out which objects are close to each other faster than brute force distance checks, which you can do by just looking at what things are in your neighboring boxes. I used this to make the initial state of the system significantly less random, which results in a dramatically better solution within the same time frame (Something like 10,000 units shorter distance in the video above).