Home

The shortest driving route through all 48 contigous US states (Takes 113 hours) Source: http://t.co/eQpXlo4v8L - pic.twitter.com/sKt2zlPpl3

— Amazing Maps (@Amazing_Maps) June 8, 2014

<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

^{Shortest Hamiltonian path problem?}

TSP

NP-Hard

TSP is an NP-hard problem in combinatorial optimization. That's a term academics use to classify its complexity. When a problem is NP-hard, we cannot (yet) prove that a polynomial time solution exists.

A problem is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k). Polynomial-time algorithms are said to be "fast."

BUT WHAT DOES IT MEAN‽

In layman's terms, when a problem is described as "NP-hard", that means it belongs to a class of problems that very quickly become computationally expensive to solve as the input size grows. These problems are in fact rather easy to solve by enumerating all possible solutions and testing them, but solving them takes a long time on larger instances of the problems.

Optimization

TSP is one of the most intensively studied problems in optimization. It's used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of error.

Graph

TSP can be modelled as an undirected weighted graph.

• vertices = cities
• edges = paths
• edge weight = path distance

It's a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (i.e. each pair of vertices is connected). If no path exists between two cities, adding an arbitrarily long edge will complete the graph.

Note that the symmetry which undirected graphs provide is often an oversimplification. Traffic collisions, construction, one-way streets, and paid routes are examples of how this symmetry could break down. In such cases a directed graph will be more accurate.

GA

Parameters

There are 6 different (user specified) GA parameters used in this program:

1. Population Size
2. Maximum Generations
3. Crossover Rate or Crossover Probability
4. Mutation Rate or Mutation Probability
5. Number of Elites
6. K value for Tournament Selection

Optimal value ranges for these GA parameters:

1. 100 ≤ popSize ≤ 500
2. 100 ≤ maxGen ≤ 300
3. 0.7 ≤ Pc ≤ 0.9 (lower from 1.0)
4. 0.1 ≤ Pm ≤ 0.3 (raise from 0.0)
5. 1 ≤ numElites ≤ 3
6. 2 ≤ k ≤ 4