Algorithms.Concorde.LinKern

Approximate a solution to 2D Euclidean TSP using the Lin-Kernighan heuristic.

The heuristic

tsp

Arguments

:: Config

Configuration.

-> (a -> R2)

Gives the rectangular coordinates of each point; see below.

-> [a]

List of points to visit.

-> IO [a]

Produces points permuted in tour order.

Approximate a solution to the two-dimensional Euclidean Traveling Salesperson Problem, using the Lin-Kernighan heuristic.

Invokes Concorde's linkern executable as an external process.

Note: linkern uses Euclidean distance rounded to the nearest integer. You may need to scale up coordinates in the function passed to tsp.

type R2 = (Double, Double)

A point in Euclidean two-dimensional space.

Configuration

data Config

Configuration for tsp.

Constructors

Config

Fields

executable :: FilePath

Path to the linkern executable. Searches $PATH by default.

verbose :: Bool

If set, write progress information to standard output.

timeBound :: Maybe Double

Stop looking for better solutions after this many seconds.

steps :: Maybe Int

Run this many optimization steps. Default is the number of points.

runs :: Int

Run this many separate optimizations. Default is 1.

otherArgs :: [String]

Other command-line arguments to the linkern executable.

Instances

Eq Config

Ord Config

Read Config

Show Config

defConfig :: Config

Default configuration.