Optimization and Graphs: The travelling salesman problem

The Travelling salesman problem was introduced by William Hamilton. The problem states that you require a Hamiltonian path (a path with no vertices repeated) in a graph so as to minimize the cost/distance function. It is a NP hard problem.

TSP on the major cities in Germany

You may want to keep in mind that using brute force for such problems may take infinite time to run to completion since there are at least N! possibilities for traversing the graph with N nodes (the cities). So you can use some searching informed techniques.

An approach that could prove helpful is start from a node, keep traversing the next closest/cheapest node until you have traversed all the nodes. Then use stimulated annealing with different temperature changing functions (linear, exponential and so on) to get an improved version of your initial feasible solution. This method first finds a feasible solution (in accordance with the problem statement) and then constantly improving the solution and finding an approximated solution in case of very large number of nodes.

You could also attack the problem by constructing solutions which are minimized during the construction itself, but that may prevent you from getting a feasible solution if the conditions aren't checked.

Also you can use techniques such as k-opt or a pairwise swap of edges in the graph genetic algorithms, simulated annealing, Tabu search or ant colony optimization. Hybrid techniques that use more than one of the above techniques usually proves to be more efficient and accurate.