Traveling Salesman Problem - Maple Application Center
Application Center Applications Traveling Salesman Problem

Traveling Salesman Problem

: Bruno Guerrieri
Engineering software solutions from Maplesoft
This Application runs in Maple. Don't have Maple? No problem!
 Try Maple free for 15 days!
The Traveling Salesman Problem (TSP) is a fascinating optimization problem in which a salesman wishes to visit each of N cities exactly once and return to the city of departure, attempting to minimize the overall distance traveled. For the symmetric problem where distance (cost) from city A to city B is the same as from B to A, the number of possible paths to consider is given by (N-1)!/2. The exhaustive search for the shortest tour becomes very quickly impossible to conduct. Why? Because, assuming that your computer can evaluate the length of a billion tours per second, calculations would last 40 years in the case of twenty cities and would jump to 800 years if you added one city to the tour [1]. These numbers give meaning to the expression "combinatorial explosion". Consequently, we must settle for an approximate solutions, provided we can compute them efficiently. In this worksheet, we will compare two approximation algorithms, a simple-minded one (nearest neighbor) and one of the best (Lin-Kernighan 2-opt).

Application Details

Publish Date: November 10, 2008
Created In: Maple 12
Language: English

More Like This

A Recursive Algorithm to Generate a Superpermutation of length n! + (n-1)! + (n-2)! + (n-3)! + n-3
Solving the World's Hardest Sudoku
Joint Cumulants of Polykays
Number of Graphs or Digraphs with n Vertices
Pascal's triangle and its relationship to the Fibonacci sequence
Solving constraint satisfaction problems II: More difficult logic problems
A new approach to Sheppard’s corrections
Recurrence relations and recursion
Solving constraint satisfaction problems I: Logic problems