TSP

(method of vector3d)

traveling salesman problem on the 2 dimensional unit-sphere

Syntax

TSP(S2,'metric','goniometer','chispeed',[1/2.55 4.5],'phispeed',[1/9.45 4.5]) - applies  goniometer metric
TSP(S2,'method','christophides2opt') - is the default method
TSP(S2,'method','christophides2opt',[4 3 3 2]) - sets the breadth of the
  2opt search tree for the lin kerninghan heuristics.

Input

S2

S2Grid

param,val Parameters and values that control TSP
Parameter Description
'Method'

Selects a heuristics or external solver

  • 'direct' -
  • '2opt' - two opt heuristics
  • 'dmst' - double minimum spanning tree heuristics
  • 'dmst2opt' - double minimum spanning tree heuristics + 2opt improvement
  • 'dmstdouble' - invokes the 2opt improvement before and after the short cut
  • 'christophides',|'chris'| - christophides heuristics
  • 'christophides2opt', 'chris2opt' - christophides heuristics + 2opt improvement
  • 'chrisdoubleopt' - invokes the 2opt improvement before and after the short cut
  • 'insertion' - insertion heuristics.
  • 'insertion2opt' - insertion heuristics + 2opt improvement
  • 'linkern' - invoke external solver
  • 'concorde' - invoke external solver
  • 'lkh' - invoke external solver
'Metric'

sets the spherical metric

  • 'manhatten' - manhatten distance on sphere.
  • 'goniometer' - maximum polar angle, requires 'PhiSpeed' and 'ChiSpeed'.
  • 'angle' - normal spherical distance.
'MaxTime'

aborts 2- or n-opt after given seconds if specified.

Remarks

Option xxx2opt invokes lin-kerninghan heuristics. If no further breadth is specified it uses the default breadth of [1].