Traveling Salesperson

Slides: History and TSP.pdf

NP-complete Problems

  • Def. NP-complete problems are very difficult to compute, but easy to verify, problems

Traveling Salesperson Problem

  • Def. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city (except the last one) exactly once.

This takes time to compute the optimal solution by brute force!

Formal Definition

Instance: n vertices, distance between every pair of vertices
Question: Find shortest cycle to visit every vertex

Solutions

Random

Session 1 - TSP Random.png

Problems With Random
  • Does random always give an answer?
  • Does it always give a good answer?
  • Does it always give a good answer?

The "Greedy" Approach

  1. Visit (start at) the start city
  2. As long as sone city has not been visited:
    1. Look through all unvisited cities and pick the closest
    2. Visit that closest city
  3. Return to the start city
Problems With Greedy
  • Does greedy always give us an answer?
  • Does it always give us a good answer?
  • Does it always give us the best answer?

The "Random Restarts" Approach

  1. Solve the Problem using the random approach
  2. Record the result as the "best solution so far"
  3. Do the following some number of times:
    1. Solve the problem using the random approach
    2. If the result is better than the best solution so far, record this better result as the best so far
  4. Report best solution so far
Problems with Random Restart
  • Does it always give us an answer?
  • Does it always give us a good answer?
  • Does it always give us the best answer?

Project 1

Learning objectives

  1. Implement a method to generate all permutations of a set of numbers
  2. Trace a Hamiltonian path through an undirected graph
  3. Use brute force to find the minimum cost solution to a Traveling Salesperson Problem

Problem Description

  • You will be expected to use brute force to calculate the minimum cost paths for a series of problems.
  • Data for each problem will be supplied in a .tsp file (a plain text file).
Hints
  • Be careful of exponential explosion. 10 cities will have over 3 million possible paths.
  • The largest data set will be 12 cities.
  • I strongly urge you to create reusable code. It will be needed for the future projects.
  • In the future projects, we will be dealing with MUCH larger datasets. So large that brute force approach would not be possible.

Deliverables

  1. Project report (2-3 pages). Describe how you generated the permutations representing the tours. Show the route and the cost of the optimal tour for each provided dataset (see template).
  2. Well-commented source code for your project (You can use any language you like, but I reserve the right to ask you to demo performance of your algorithm on a new dataset).
  3. You don’t have to include a GUI with visual representation of the solutions for this project, but it might be useful for your future TSP related projects in this course.

Data Format

Sample Data

NAME: concorde7
TYPE: TSP
COMMENT: Generated by CCutil_writetsplib
COMMENT: Write called for by Concorde GUI
DIMENSION: 7
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 87.951292 2.658162
2 33.466597 66.682943
3 91.778314 53.807184
4 20.526749 47.633290
5 9.006012 81.185339
6 20.032350 2.761925
7 77.181310 31.922361
EOF

Distance Formula