Usage¶
To use TSPLIB 95 in a project:
import tsplib95
Loading problems and solutions is easy:
>>> problem = tsplib95.load_problem('path/to/ulysses16.tsp')
>>> problem
<tsplib95.models.Problem at 0x105030d30>
>>> solution = tsplib95.load_solution('path/to/ulysses16.opt.tour')
>>> solution
<tsplib95.models.Solution at 0x104314d68>
Note
tsplib95 does not ship with any problem files itself. The problems
and solutions are standalone files. load_problem
and load_solution
take a filesystem path as an argument, not the name of a problem. Feel
free to download and use any of the original TSPLIB problem files
commonly used and referenced by the community, find others, or write
your own. Any file that adheres to the TSPLIB95 file format standards
should load without error.
Both have the base attributes, but let’s focus on a problem object first:
>>> problem.name # not specified
>>> problem.comment
'Odyssey of Ulysses (Groetschel/Padberg)'
>>> problem.type
'TSP'
>>> problem.dimension
16
Problems can be specified in several ways according to the TSPLIB format. Here’s how this particular problem is specified:
>>> problem.display_data_type
'COORD_DISPLAY'
>>> problem.edge_data_format # not specified
>>> problem.edge_weight_format # not specified
>>> problem.edge_weight_type
'GEO'
>>> problem.node_coord_type # not specified
Regardless of how the problem is specified, nodes and edges are accessible in the same way. Nodes and edges are returned as generators since there could be a significant number of them:
>>> list(problem.get_nodes())
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> list(problem.get_edges())[:5]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5)]
We can find the weight of the edge between nodes 1 and, say, 11,
using wfunc
:
>>> problem.wfunc
<function tsplib95.models.Problem._create_distance_function.<locals>.adapter>
>>> problem.wfunc(1, 11)
26
If the distance function for the problem is “SPECIAL” you must provide a custom distance function. The function must accept two node coordinates and return the distance between them. Let’s create one:
>>> import random
>>> import math
>>>
>>> def euclidean_2d_jitter(a, b):
... x1, y1 = a
... x2, y2 = b
... dist = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
... return dist * random.random() * 2
...
Of course, you may want to leverage the existing distance functions:
>>> from tsplib95 import distances
>>>
>>> def euclidean_jitter(a, b):
... dist = distances.euclidean(a, b) # works for n-dimensions
... return dist * random.random() * 2
...
You can either provide that function at load time or you can also set it on
an existing Problem
instance:
>>> problem = tsplib95.load_problem('example.tsp', special=euclidean_2d_jitter)
>>> problem.special = euclidean_jitter
Note that setting the special function on a problem that has explicit edge weights has no effect.
You can get a networkx.Graph
instance from the problem:
>>> G = problem.get_graph()
>>> G.nodes
NodeView((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16))
And you can trace the tours found in a Solution
:
>>> solution = tsplib95.load_solution('ulysses16.opt.tour')
>>> problem.trace_tours(solution)
[73]
Note that it returns a list of tour distances, one for each tour defined in the solution.