Portability | portable |
---|---|
Stability | provisional |
Maintainer | Richard Senington <sc06r2s@leeds.ac.uk> |
A library for the representation and manipulation of travelling salesperson
problems.
The approach taken is the creation of a complex data structure called
TSPProblem which contains both the problem, the current solution and
the current value of the route.
The route is stored as a dictionary (Data.Map
) of vertex indexes
to a pair of values, the previous vertex and the next vertex in the
sequence. This is to facilitate changing the route quickly, and
avoid searching for data in lists.
The data structure also contains two additional fields, the
routeElementToIndex
and indexToRouteElement
components.
These exist to allow manipulation either by the vertex number
or the position in the current solution.
Solutions are hamiltonian cycles.
For ease of reasoning it is recommended that users do not
attempt to move vertex 0, or index 0, so that solutions
are cycles from 0 to 0. I may change this in the future to
lock this down a bit. In the meantime, there is no
actual problem with making these changes, however
later manipulations may not match up clearly with
the way the show routines work.
Currently only two functions are provided for manipulating routes,
either by position in the sequence (exchangeCitiesOnIndex
) or
by vertex name (exchangeCities
).
I am not sure how this will clearly support meta-heuristics that work by deleting edges and recombining subsequences. However since I am storing association lists I think it should be possible to make this work, I will worry about it later.
- data TSPProblem = TSPProblem FP (Map Int (Int, Int)) (Int -> Int -> FP) Int (Map Int Int) (Map Int Int)
- edgeCost :: Floating a => TSPProblem -> Int -> Int -> a
- solutionValue :: Floating a => TSPProblem -> a
- getTSPPathAsList :: TSPProblem -> [Int]
- data InternalStorage
- showEdgeWeights :: TSPProblem -> String
- exchangeCities :: Int -> Int -> TSPProblem -> TSPProblem
- exchangeCitiesOnIndex :: Int -> Int -> TSPProblem -> TSPProblem
- evaluateRouteNaive :: TSPProblem -> TSPProblem
- randomiseRoute :: RandomGen g => g -> TSPProblem -> TSPProblem
- setRoute :: [Int] -> TSPProblem -> TSPProblem
- makeASymmetricTSPMap :: RandomGen g => (Double, Double) -> Int -> g -> TSPProblem
- makeSymmetricTSPMap :: RandomGen g => InternalStorage -> (Double, Double) -> Int -> g -> TSPProblem
- makeEuclideanTSPMap :: RandomGen g => InternalStorage -> (Double, Double) -> (Double, Double) -> Int -> g -> TSPProblem
Documentation
data TSPProblem Source
The data type for carrying the combination problem and solution to the TSP. The route is stored as a dictionary of associations from vertex name to a pair of values, the name of the preceding vertex and the next vertex. This forms an infinite loop, so use carefully.
The routeElementToIndex
/indexToRouteElement
pair store
fixed indexes to the cities. This is intended to allow
a dumb heuristic to decide to switch elements 0 and 2,
knowing they must be separated by 1 element, rather than
vertices 0 and 2, which may be next to each other, or
very different parts of the cycle.
edgeCost :: Floating a => TSPProblem -> Int -> Int -> aSource
Internally all edge costs are stored as a fixed point values. For external visibility however this function is provided, converting the values into floating point numbers.
solutionValue :: Floating a => TSPProblem -> aSource
Internally the value of the solution is stored as a fixed point value, stored in an Int64 data type. For external visibility however this function is provided, converting the value into a floating point numbers.
getTSPPathAsList :: TSPProblem -> [Int]Source
data InternalStorage Source
There are three possible internal storage forms. A full explicit matrix, an upper triangular matrix or recomputation from data points. The advantage of full explicit is speed, but it takes more memory. It is also the only option for asymmetric TSP problems. The triangular matrix is also fast, but can only be used in symmetric problems, and also still requires quite a bit of memory. Recomputation is the last option, it is slow because it is no longer a lookup table, but will take much less room. Can only be used with problems where the distance between two points can be calculated. Currently I am only supporting symmetric TSPs for this.
showEdgeWeights :: TSPProblem -> StringSource
Converts the lookup table of a problem into a comma and newline delimited string. This should facilitate copying into spreadsheets for checking the problem being used and validating solutions by hand.
exchangeCities :: Int -> Int -> TSPProblem -> TSPProblemSource
Will perform a switch of 2 cities in the path. This is by city name, not current index
in the path. It looks up the current indexes by city name and passes the work off to
exchangeCitiesOnIndex
.
exchangeCitiesOnIndex :: Int -> Int -> TSPProblem -> TSPProblemSource
Performs the bulk of the work for exchanging elements of the cycle. This version no longer assumes the indices are ordered due to confusion this caused in my own code. In addition there was an oversight, when exchanging indices 0 and last. This is now fixed.
evaluateRouteNaive :: TSPProblem -> TSPProblemSource
A brute force recalculation of the current length of the path. Use sparingly.
randomiseRoute :: RandomGen g => g -> TSPProblem -> TSPProblemSource
Shuffles a simple list of cities and then passes off the work to setRoute.
setRoute :: [Int] -> TSPProblem -> TSPProblemSource
Take a path through the system and a problem, insert the path into the system, calculating distances and setting up appropriate look up tables. It does not validate the list in terms of going through all the cities, or going through a city more than once (though this is likely to break other parts of the system very very fast). It does organise the list so that the starting node is vertex 0.
Uses the evaluateRouteNaive
to calculate the length of the path via a brute
force method. This is not expected to be used frequently.
makeASymmetricTSPMap :: RandomGen g => (Double, Double) -> Int -> g -> TSPProblemSource
Construct a TSPProblem instance for an Asymmetric TSP. That is, the distance
from A-B is the not necessarily the same as B-A. The actual route will
not be set up initially, the dictionaries will be empty. This could be
used directly for a global search system (branch and bound), or use in
conjunction with setRoute
or randomiseRoute
to initialise for local search.
Internal data structure is always fully explicit matrix.
makeSymmetricTSPMap :: RandomGen g => InternalStorage -> (Double, Double) -> Int -> g -> TSPProblemSource
Construct a TSPProblem instance for a Symmetric TSP. That is, the distance
from A-B is the same as B-A. The actual route will not be set up initially,
the dictionaries will be empty. This could be used directly for a global
search system (branch and bound), or use in conjunction with setRoute
or
randomiseRoute
to initialise for local search. Should be noted that this
does not create locations and calculate distances, but rather randomly
assigns distances to each edge, making them symmetric.
makeEuclideanTSPMap :: RandomGen g => InternalStorage -> (Double, Double) -> (Double, Double) -> Int -> g -> TSPProblemSource
Construct a TSPProblem instance for a Symmetric TSP. The route will not be initially set up, the dictionaries will be empty. This does create the vertices of the graph as points in a 2d space, and the lengths of edges are calculated, so this supports all internal storage types.