52.219 The Travelling Salesman Problem (tsp)

Given a set of locations, each with an x-y coordinate, produce a tour that visits all cities once only, and returns to the starting city. Find this tour such that distance travelled is a minimum.

Instances of the tsp

Euclidean and Manhattan. Single machine scheduling, with setups Control of a x-y drilling machine ...

Complexity

Find all permutations. Assume only 4 cities, ABCD then may have to consider

  ABCD, ABDC, ACBD, ACDB, ADBC, ADCB
  BACD, BADC, BCAD, BCDA, BDAC, BDCA
  CABD, CADB, ....
  DABC, DACB, ....

There will be 24 to consider. More generally, given n we may have to consider n! to find optimal. The growth of n! is shown below

           n         n!
           1         1
           2         2
           3         6
           4        24
           5       120
           6       720
           7      5040
           8     40320
           9    362880
          10   3628800

It appears that in order to find the best tour we must consider many different possible solutions, and examine them in turn to decide which is best. That is, we must explore many possibilities.

These possibilities can be viewed/considered as a tree, to be explored (or searched, but don't confuse this with earlier definition of search as in searching and sorting!).

Decision Problem

The TSP is often described as a decision problem: Is there a tour of cost less than or equal to k? We can express the optimisation problem as a sequence of decision problems.

  1. Is there a tour of cost <= k?   yes!
  2.                         <= k-1? yes!
  3.                         <= k-2? no!
  4. k-1 is the optimal tour length

Permutations
The scheme code below produces all permutations of objects in the list x
(also see /home/s7/pat/scheme/pub/perm.scm)
(define (perm x)
  (let ((all-perms '()))
    (define (perm' source sink)
      ;(display source) (display sink) (newline)
      (cond ((null? source) (set! all-perms (append all-perms (list sink))))
	    (t (do ((y' source (cdr y')))
		   ((null? y'))
		 (let ((e (car y')))             ;
		   (perm' (remove e source) (append sink (list e))))))))
    (perm' x '())
    all-perms))
;;; Produce all permutations of the list x. 
;;; This corresponds to all possible ordering of the elements in x. 
;;;
;;; For the tsp a permutation corresponds to a tour
;;; We can explore all permutations and choose the best
;;; Alternatively we can make the recursive call to perm'
;;; conditionally. That is, if the current partial tour in 
;;; sink costs less than the best so far we might extend it.
;;;
;;; We can now go 1 step further and look at a lower bound on extending
;;; the partial tour in sink ... can you think of some of these?
;;;


Branch and Bound (BnB)
Assume we have a 6 city TSP with cities ABCDEF, and the tours are
built up systematically, such that we extend a partial tour as in the
above function perm. 
 - Assume that the best solution found so far had a  cost of 100
 - the current partial tour is  and has a cost of 90.
 - the minimum cost of going from D->E is 12 
 - the minimum cost D->F is 10
 - there is no way to extend ACBD at a cost less than 100.
 - Consequently we can abandon the partial tour ACBD.

That is, in the process of searching for a solution we can put bounds
on what is acceptable. If the current partial tour cannot meet those bounds
we can abondon it, thus pruning the search space. 

The more effort we put into computing a lower bound the more pruning we do, 
with less search as a result. But this might not be economical
Branch and bound is a systematic search, and is a complete algorithm.

Heuristics
A heuristic is a rule of thumb. That is, a heuristic is generally a 
good idea but some times iyt doesn't work. An example of a heuristic
for packing a suitcase might be, put in the big objects first such as your shoes,
then put the small items in using up the remaining fragmented space.
For the tsp we might have heuristics for selecting the next city to visit.
Maybe go to the nearest?

Some Engineering Decisions
The cost matrix, where C[i,j} is the cost of going from i to j. Should we
precompute this? Is the cost matrix symmetric? 
Is the cost always distance, Manhattan or Euclidean? (By the way, what is
Manhattan and Euclidean?)


Greedy and Stochastic Search
Complete search may be impossible when n gets large, and we may resort
to incomplete methods, not guaranteed to find the best solution.
Examples may be 2-opt as a move operator
    1. given a tour S and a cost of that tour cost(S)
    2. generate a neighbouring tour S' from S
    3. if cost(S') < cost(S) then S <- S'
    4. if still time remaining go to step 2.
    5. S is the best tour found

The best tour found (step 5) does not mean the very best.
How do we extend the above?
    - good neighbourhood moves, such as 2-opt
      NOTE: do not need to re-evaluate entire tour!
    - above is hill descending/climbing
    - steepest descent, generate entire neighbourhood
      in step 2, and select best from neighbourhood.
      (question: how big is the neighbourhood?)
    - allow occassional uphill move