Module tsp.concorde
TSP - Python interface to Concorde - A C-library for solving TSPs.
Last update: 22 July, 2022
Remark: Concorde is a TSP solver written in C and created by D. Applegate, R. Bixby, V. Chvatal and W. Cook. The code is available from http://www.math.uwaterloo.ca/tsp/concorde and permission to use it is granted for academic purposes only.
Expand source code
"""
TSP - Python interface to Concorde - A C-library for solving TSPs.
Last update: 22 July, 2022
Remark:
Concorde is a TSP solver written in C and created by D. Applegate,
R. Bixby, V. Chvatal and W. Cook. The code is available from
http://www.math.uwaterloo.ca/tsp/concorde and permission to use it
is granted for academic purposes only.
"""
import numpy as np
import ctypes, pathlib, platform, time
from tsplib95 import load_problem
import os, sys
__CC_Lib = None
__CPX_Lib = None
#---------------------------------------------------------------------
def __loadConcorde():
"""
Find and load cplex and concorde library.
"""
cplexLib = None
concordeLib = None
onWindows = 'Windows' in platform.system()
onMac = 'darwin' in platform.system().lower()
if onWindows:
cplexDLL = 'cplex*.dll'
concordeDLL = 'libconcorde.dll'
else:
# Not sure if this works on OSX/Darwin
cplexDLL = 'libcplex*.so'
concordeDLL = 'libconcorde.so'
# Check if the CPLEX callable library is present. On Linux and Mac, we
# will also have to explictly load this library before Concorde is
# is loaded, as Concorde depends on Cplex. On Windows, it suffices
# to load Concorde as the the Concorde Library has been linked with
# the Cplex static library. If we find more than one Cplex dynamic
# link library, take the most recent version.
try:
cpxEnv = next( p for p in os.environ if 'CPLEX_STUDIO_BINARIES' in p )
except:
cpxEnv = 'PATH'
cpxBins = os.getenv(cpxEnv)
sep = ';' if onWindows else ':'
dirLst = [ p for p in cpxBins.split(sep) if 'cplex' in p.lower()]
lastVer= 0
for direc in dirLst:
for pathName in pathlib.Path( direc ).rglob( cplexDLL ):
testLib = str(pathlib.Path.resolve(pathName))
if not testLib is None:
fname = pathName.stem
if fname[-1].isdigit():
numVer = int( ''.join([c for c in fname if c.isdigit()]) )
if numVer > lastVer:
lastVer = numVer
cplexLib = testLib
if cplexLib is None:
print("Could not find CPLEX dynamic link library.")
print("Make sure that Cplex's binary folder is in the PATH environment variable or")
print("that environment variable CPLEX_STUDIO_BINARIES is defined and set correctly!")
return( False )
# The dynamic link library libconcorde.so (libconcorde.dll on Windows)
# is expected to reside in the same directory as this module "concorde.py"
if onWindows:
prefix = 'win//'
elif onMac:
prefix = 'mac/'
else:
prefix = 'linux/'
concordeHome=pathlib.Path(__file__).resolve().parent
concordeFile = pathlib.PurePath.joinpath(concordeHome,prefix+concordeDLL)
if concordeFile.is_file():
concordeLib = str( concordeFile )
else:
print("Could not find Concorde's dynamic link library.")
return( False )
# Libraries found. Now try to load them. Cplex first, as Concorde
# depends on Cplex
global __CPX_Lib
global __CC_Lib
if not onWindows:
__CPX_Lib = ctypes.CDLL(cplexLib, mode=ctypes.RTLD_GLOBAL)
if __CPX_Lib is None: return( False )
__CC_Lib = ctypes.CDLL(concordeLib, mode=ctypes.RTLD_GLOBAL)
if __CC_Lib is None:
print("Error occured when loading library ",concordeLib )
return( False )
return( True )
#---------------------------------------------------------------------
def solveTSP( problem, route=None, exact=True, logFile=None ):
"""
Invokes Concorde's TSP solver on the TSP instance *problem*.
Parameters:
**problem** : class
TSP problem object has returned by TSPlib95.
**route** : list of int
If not none it should contain a permutation list of cities
to be used as initial solution.
**exact** : bool
If true (default) it is tried to solve the instance exactly
by means of Concorde's branch-and-cut solver; otherwise
Concorde only applies the Lin-Kernighan heuristic.
**logFile** : str
If not None, it need to be the name of file, where to
redirect output from Concorde.
Returns:
**routeLen** : int
Length of the route.
**route** : list of int
Computed route (route[0] is the depot and route[-1] is the
last customer).
"""
if __CC_Lib is None:
print("Concorde Library not loaded!")
return 0, []
try:
_ = problem.wfunc
except:
problem.wfunc = problem._wfunc
nn = problem.dimension
nodeLst = list( problem.get_nodes() )
n = ctypes.c_int( nn )
seed = ctypes.c_int( int( time.time() ) )
tiLim = ctypes.c_double(0.0)
LKonly = ctypes.c_char(1-int(exact))
# Compute the distance matrix
dist=np.array( list(problem.wfunc(nodeLst[i],nodeLst[j]) for i in range(1,nn) \
for j in range(i)), dtype = ctypes.c_int )
pdist = dist.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) )
# Number the nodes from 0 to n-1
nodeIdx = dict(zip(nodeLst,range(nn)))
# Redirect output from Concorde?
if logFile is None:
logPtr = ctypes.c_char_p(0)
else:
logPtr = ctypes.c_char_p(logFile.encode('utf-8'))
old_out = sys.stdout # saver when on windows
# Create integer array representing the tour
if route is None:
tLen = ctypes.c_double( 0.0 )
tour = np.zeros(nn, dtype=ctypes.c_int)
else:
tLen = ctypes.c_double( 1.0 )
tour = np.array(list(nodeIdx[i] for i in route), dtype=ctypes.c_int)
ptour= tour.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) )
# Call concorde for computing TSP tour
__CC_Lib.solve_STSP.restype = ctypes.c_int
status = __CC_Lib.solve_STSP( LKonly, n, seed, tiLim, pdist,\
logPtr, ctypes.byref(tLen), ptour )
# Following is safer when on Windows
if not logFile is None: sys.stdout = old_out
if status < 2:
routeLen = int(tLen.value)
route = [ nodeLst[i] for i in tour ]
return routeLen, route
else:
return np.Inf, []
#---------------------------------------------------------------------
def solveTSPmatrix( dist, route=None, exact=True, logFile = None ):
"""
Invokes Concorde's TSP solver.
Parameters:
**dist** : numpy array of c_int
Contains the lower triangle part of the symmetric
distance matrix. That is the distance between the
i-th node and the j-th node (i=0,...,n-1 and i > j)
is given by dist[(i-1)i/2 + j].
**route** : list of int, optional
If not None, it need to be a permutation of the n nodes
which is used as an initial route.
**exact** : bool
If true (default) it is tried to solve the instance
exactly by means of Concorde's branch-and-cut solver;
otherwise Concorde only applies the Lin-Kernighan
heuristic.
**logFile** : str
If not None, it need to be the name of file, where to
redirect output from Concorde.
Returns:
**routeLen** : int
Length of the route (routeLen).
**route** : list of int
Computed route (route[0] is the depot and route[-1] is the
last customer).
"""
if __CC_Lib is None:
print("Concorde Library not loaded!")
return 0, []
# Number of nodes
n = int(0.5+np.sqrt(0.25+2*len(dist) + 1.0E-7))
nn = ctypes.c_int( n )
seed = ctypes.c_int( int( time.time() ) )
tiLim = ctypes.c_double(0.0)
LKonly = ctypes.c_char(1-int(exact))
minIndx = 0
if route is None:
tLen = ctypes.c_double( 0.0 )
tour = np.zeros(n, dtype=ctypes.c_int)
else:
minIndx = min(route)
tour = np.array( route, dtype=ctypes.c_int ) - minIndx
tLen = ctypes.c_double( 1.0 )
ptour= tour.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) )
# Redirect output from Concorde?
if logFile is None:
logPtr = ctypes.c_char_p(0)
else:
logPtr = ctypes.c_char_p(logFile.encode('utf-8'))
old_out = sys.stdout
pdist = dist.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) )
# Call concorde for computing TSP tour
__CC_Lib.solve_STSP.restype = ctypes.c_int
status = __CC_Lib.solve_STSP( LKonly, nn, seed, tiLim, pdist,\
logPtr, ctypes.byref(tLen), ptour )
# Following is safer when on Windows
if not logFile is None: sys.stdout = old_out
if status < 2:
routeLen = int(tLen.value)
route = [ i+minIndx for i in tour ]
return routeLen, route
else:
return np.Inf, []
#---------------------------------------------------------------------
def solveTSPgraph( G, length='weight', route=None, exact=True, logFile = None ):
"""
Invokes Concorde's TSP solver and tries to solve a TSP
on the graph G.
Parameters:
**G** : networkx graph object
Undirected graph on which the TSP should be solved.
**length** : str
attribute/key in the graph's edge data that specifies
the edge length, default='weight'.
**route** : list of int, optional
If not None, it need to be a permutation of the n nodes
which is used as an initial route.
**exact** : bool, optional
If true (default) it is tried to solve the instance
exactly by means of Concorde's branch-and-cut solver;
otherwise Concorde only applies the Lin-Kernighan
heuristic.
**logFile** : str, optional
If not None, it need to be the name of file, where to
redirect output from Concorde.
Returns:
**routeLen** : int
Length of the route (routeLen).
**route** : list of int
Computed route (route[0] is the depot and route[-1] is the
last customer).
"""
if __CC_Lib is None:
print("Concorde Library not loaded!")
return 0, []
seed = ctypes.c_int( int( time.time() ) )
tiLim = ctypes.c_double(0.0)
LKonly = ctypes.c_char(1-int(exact))
# number of nodes and edges
n = G.number_of_nodes()
m = G.number_of_edges()
nn = ctypes.c_int( n )
mm = ctypes.c_int( m )
# Number the nodes from 0 to n-1
nodeIdx = dict(zip(G.nodes,range(n)))
# Edge lengths required for Concorde
elen = np.array([G[e[0]][e[1]][length] for e in G.edges],dtype=ctypes.c_int )
p_elen = elen.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) )
# End nodes of edges required for Concorde
elist = np.zeros(2*m, dtype=ctypes.c_int)
for i, e in enumerate(G.edges):
elist[2*i], elist[2*i+1] = nodeIdx[e[0]], nodeIdx[e[1]]
p_elist = elist.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) )
# Set up C array for the initial tour
if route is None:
tLen = ctypes.c_double( 0.0 )
tour = np.zeros(n, dtype=ctypes.c_int)
else:
tour = np.array( [nodeIdx[i] for i in route], dtype=ctypes.c_int )
rLen = sum( G[route[i-1]][route[i]][length] for i in range(1,n) )\
+ G[route[-1]][route[0]][length]
tLen = ctypes.c_double( rLen )
ptour= tour.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) )
# Redirect output from Concorde?
if logFile is None:
logPtr = ctypes.c_char_p(0)
else:
logPtr = ctypes.c_char_p(logFile.encode('utf-8'))
old_out = sys.stdout
# Call concorde for computing TSP tour
__CC_Lib.solve_STSP.restype = ctypes.c_int
status = __CC_Lib.solve_sparseTSP( LKonly, nn, mm, seed, tiLim,\
p_elist, p_elen, logPtr, ctypes.byref(tLen), ptour )
# Following is safer when on Windows
if not logFile is None: sys.stdout = old_out
if status < 2:
routeLen = int(tLen.value)
route = list( np.array( G.nodes)[tour] )
return routeLen, route
else:
return np.Inf, []
#---------------------------------------------------------------------
def solveTSPdat( n, dist=None, route=None, exact=True, logFile = None ):
"""
Invokes Concorde's TSP solver. This function is DEPRECATED and is
actually to be replaced by either calling solveTSPgraph or
solveTSPmatrix. The function is only kept for reasons of
compatibility with functions 'postOptim' and 'improveRoute'
in the module 'vrp.vrp_util'. All parameters are the same
as for function 'solveTSPmatrix', except n which is the number
of nodes. Note that dist need actually be present and should
not be None (otherwise None is also returned).
Returns:
Same as for solveTSPmatrix
"""
if __CC_Lib is None:
print("Concorde Library not loaded!")
return 0, []
if dist is None: return 0, []
return solveTSPmatrix(dist, route=route, exact=exact, logFile=logFile)
#---------------------------------------------------------------------
def solveTSPLib( fname, exact=True, logFile=None ):
"""
Solve a TSPLIB instance stored in file *fname* by means of
Concorde's TSP solver.
Parameters:
**fname** : str
Name (including) the path to the data file (format TSPLIB).
**exact** : bool
If true (default) it is tried to solve the instance exactly
by means of Concorde's branch-and-cut solver; otherwise
Concorde only applies the Lin-Kernighan heuristic.
**logFile** : str
If not None, it need to be the name of file, where to
redirect output from Concorde.
Returns:
**routeLen** : int
Length of the route (routeLen).
**route** : list of int
Computed route (route[0] is the depot and route[-1] is the
last customer).
"""
if __CC_Lib is None:
print("Concorde Library not loaded!")
return 0, []
else:
# We first create a pointer to an integer array
problem = load_problem(fname)
tour = np.zeros(problem.dimension, dtype=ctypes.c_int)
iptr = ctypes.POINTER( ctypes.c_int )
ptour= tour.ctypes.data_as( iptr )
# Redirect output from Concorde?
if logFile is None:
logPtr = ctypes.c_char_p(0)
else:
logPtr = ctypes.c_char_p(logFile.encode('utf-8'))
old_out = sys.stdout
# Initialize other parameters of c-function solve_TSLPlib
seed = ctypes.c_int( int( time.time() ) )
status = ctypes.c_int(0)
tiLim = ctypes.c_double(0.0)
fnmeptr = ctypes.c_char_p(fname.encode('utf-8'))
LKonly = ctypes.c_char(1-int(exact))
__CC_Lib.solve_TSPlib.restype = ctypes.c_double
tLen = __CC_Lib.solve_TSPlib( LKonly, fnmeptr, seed, tiLim,\
logPtr, ptour, ctypes.byref(status) );
routeLen = tLen
nodeLst = [node for node in problem.get_nodes()]
route = [ nodeLst[i] for i in tour ]
# Following is safer when on Windows
if not logFile is None: sys.stdout = old_out
return routeLen, route
#---------------------------------------------------------------------
is_ready = __loadConcorde()Functions
def solveTSP(problem, route=None, exact=True, logFile=None)-
Invokes Concorde's TSP solver on the TSP instance problem.
Parameters
problem : class
TSP problem object has returned by TSPlib95.
route : list of int
If not none it should contain a permutation list of cities to be used as initial solution.
exact : bool
If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic.
logFile : str
If not None, it need to be the name of file, where to redirect output from Concorde.Returns
routeLen : int
Length of the route.
route : list of int
Computed route (route[0] is the depot and route[-1] is the last customer).Expand source code
def solveTSP( problem, route=None, exact=True, logFile=None ): """ Invokes Concorde's TSP solver on the TSP instance *problem*. Parameters: **problem** : class TSP problem object has returned by TSPlib95. **route** : list of int If not none it should contain a permutation list of cities to be used as initial solution. **exact** : bool If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic. **logFile** : str If not None, it need to be the name of file, where to redirect output from Concorde. Returns: **routeLen** : int Length of the route. **route** : list of int Computed route (route[0] is the depot and route[-1] is the last customer). """ if __CC_Lib is None: print("Concorde Library not loaded!") return 0, [] try: _ = problem.wfunc except: problem.wfunc = problem._wfunc nn = problem.dimension nodeLst = list( problem.get_nodes() ) n = ctypes.c_int( nn ) seed = ctypes.c_int( int( time.time() ) ) tiLim = ctypes.c_double(0.0) LKonly = ctypes.c_char(1-int(exact)) # Compute the distance matrix dist=np.array( list(problem.wfunc(nodeLst[i],nodeLst[j]) for i in range(1,nn) \ for j in range(i)), dtype = ctypes.c_int ) pdist = dist.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) ) # Number the nodes from 0 to n-1 nodeIdx = dict(zip(nodeLst,range(nn))) # Redirect output from Concorde? if logFile is None: logPtr = ctypes.c_char_p(0) else: logPtr = ctypes.c_char_p(logFile.encode('utf-8')) old_out = sys.stdout # saver when on windows # Create integer array representing the tour if route is None: tLen = ctypes.c_double( 0.0 ) tour = np.zeros(nn, dtype=ctypes.c_int) else: tLen = ctypes.c_double( 1.0 ) tour = np.array(list(nodeIdx[i] for i in route), dtype=ctypes.c_int) ptour= tour.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) ) # Call concorde for computing TSP tour __CC_Lib.solve_STSP.restype = ctypes.c_int status = __CC_Lib.solve_STSP( LKonly, n, seed, tiLim, pdist,\ logPtr, ctypes.byref(tLen), ptour ) # Following is safer when on Windows if not logFile is None: sys.stdout = old_out if status < 2: routeLen = int(tLen.value) route = [ nodeLst[i] for i in tour ] return routeLen, route else: return np.Inf, [] def solveTSPLib(fname, exact=True, logFile=None)-
Solve a TSPLIB instance stored in file fname by means of Concorde's TSP solver.
Parameters
fname : str
Name (including) the path to the data file (format TSPLIB).
exact : bool
If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic.
logFile : str
If not None, it need to be the name of file, where to redirect output from Concorde.Returns
routeLen : int
Length of the route (routeLen).
route : list of int
Computed route (route[0] is the depot and route[-1] is the last customer).Expand source code
def solveTSPLib( fname, exact=True, logFile=None ): """ Solve a TSPLIB instance stored in file *fname* by means of Concorde's TSP solver. Parameters: **fname** : str Name (including) the path to the data file (format TSPLIB). **exact** : bool If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic. **logFile** : str If not None, it need to be the name of file, where to redirect output from Concorde. Returns: **routeLen** : int Length of the route (routeLen). **route** : list of int Computed route (route[0] is the depot and route[-1] is the last customer). """ if __CC_Lib is None: print("Concorde Library not loaded!") return 0, [] else: # We first create a pointer to an integer array problem = load_problem(fname) tour = np.zeros(problem.dimension, dtype=ctypes.c_int) iptr = ctypes.POINTER( ctypes.c_int ) ptour= tour.ctypes.data_as( iptr ) # Redirect output from Concorde? if logFile is None: logPtr = ctypes.c_char_p(0) else: logPtr = ctypes.c_char_p(logFile.encode('utf-8')) old_out = sys.stdout # Initialize other parameters of c-function solve_TSLPlib seed = ctypes.c_int( int( time.time() ) ) status = ctypes.c_int(0) tiLim = ctypes.c_double(0.0) fnmeptr = ctypes.c_char_p(fname.encode('utf-8')) LKonly = ctypes.c_char(1-int(exact)) __CC_Lib.solve_TSPlib.restype = ctypes.c_double tLen = __CC_Lib.solve_TSPlib( LKonly, fnmeptr, seed, tiLim,\ logPtr, ptour, ctypes.byref(status) ); routeLen = tLen nodeLst = [node for node in problem.get_nodes()] route = [ nodeLst[i] for i in tour ] # Following is safer when on Windows if not logFile is None: sys.stdout = old_out return routeLen, route def solveTSPdat(n, dist=None, route=None, exact=True, logFile=None)-
Invokes Concorde's TSP solver. This function is DEPRECATED and is actually to be replaced by either calling solveTSPgraph or solveTSPmatrix. The function is only kept for reasons of compatibility with functions 'postOptim' and 'improveRoute' in the module 'vrp.vrp_util'. All parameters are the same as for function 'solveTSPmatrix', except n which is the number of nodes. Note that dist need actually be present and should not be None (otherwise None is also returned).
Returns
Same as for solveTSPmatrix
Expand source code
def solveTSPdat( n, dist=None, route=None, exact=True, logFile = None ): """ Invokes Concorde's TSP solver. This function is DEPRECATED and is actually to be replaced by either calling solveTSPgraph or solveTSPmatrix. The function is only kept for reasons of compatibility with functions 'postOptim' and 'improveRoute' in the module 'vrp.vrp_util'. All parameters are the same as for function 'solveTSPmatrix', except n which is the number of nodes. Note that dist need actually be present and should not be None (otherwise None is also returned). Returns: Same as for solveTSPmatrix """ if __CC_Lib is None: print("Concorde Library not loaded!") return 0, [] if dist is None: return 0, [] return solveTSPmatrix(dist, route=route, exact=exact, logFile=logFile) def solveTSPgraph(G, length='weight', route=None, exact=True, logFile=None)-
Invokes Concorde's TSP solver and tries to solve a TSP on the graph G.
Parameters
G : networkx graph object
Undirected graph on which the TSP should be solved.
length : str
attribute/key in the graph's edge data that specifies the edge length, default='weight'.
route : list of int, optional
If not None, it need to be a permutation of the n nodes which is used as an initial route.
exact : bool, optional
If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic.
logFile : str, optional
If not None, it need to be the name of file, where to redirect output from Concorde.Returns
routeLen : int
Length of the route (routeLen).
route : list of int
Computed route (route[0] is the depot and route[-1] is the last customer).Expand source code
def solveTSPgraph( G, length='weight', route=None, exact=True, logFile = None ): """ Invokes Concorde's TSP solver and tries to solve a TSP on the graph G. Parameters: **G** : networkx graph object Undirected graph on which the TSP should be solved. **length** : str attribute/key in the graph's edge data that specifies the edge length, default='weight'. **route** : list of int, optional If not None, it need to be a permutation of the n nodes which is used as an initial route. **exact** : bool, optional If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic. **logFile** : str, optional If not None, it need to be the name of file, where to redirect output from Concorde. Returns: **routeLen** : int Length of the route (routeLen). **route** : list of int Computed route (route[0] is the depot and route[-1] is the last customer). """ if __CC_Lib is None: print("Concorde Library not loaded!") return 0, [] seed = ctypes.c_int( int( time.time() ) ) tiLim = ctypes.c_double(0.0) LKonly = ctypes.c_char(1-int(exact)) # number of nodes and edges n = G.number_of_nodes() m = G.number_of_edges() nn = ctypes.c_int( n ) mm = ctypes.c_int( m ) # Number the nodes from 0 to n-1 nodeIdx = dict(zip(G.nodes,range(n))) # Edge lengths required for Concorde elen = np.array([G[e[0]][e[1]][length] for e in G.edges],dtype=ctypes.c_int ) p_elen = elen.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) ) # End nodes of edges required for Concorde elist = np.zeros(2*m, dtype=ctypes.c_int) for i, e in enumerate(G.edges): elist[2*i], elist[2*i+1] = nodeIdx[e[0]], nodeIdx[e[1]] p_elist = elist.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) ) # Set up C array for the initial tour if route is None: tLen = ctypes.c_double( 0.0 ) tour = np.zeros(n, dtype=ctypes.c_int) else: tour = np.array( [nodeIdx[i] for i in route], dtype=ctypes.c_int ) rLen = sum( G[route[i-1]][route[i]][length] for i in range(1,n) )\ + G[route[-1]][route[0]][length] tLen = ctypes.c_double( rLen ) ptour= tour.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) ) # Redirect output from Concorde? if logFile is None: logPtr = ctypes.c_char_p(0) else: logPtr = ctypes.c_char_p(logFile.encode('utf-8')) old_out = sys.stdout # Call concorde for computing TSP tour __CC_Lib.solve_STSP.restype = ctypes.c_int status = __CC_Lib.solve_sparseTSP( LKonly, nn, mm, seed, tiLim,\ p_elist, p_elen, logPtr, ctypes.byref(tLen), ptour ) # Following is safer when on Windows if not logFile is None: sys.stdout = old_out if status < 2: routeLen = int(tLen.value) route = list( np.array( G.nodes)[tour] ) return routeLen, route else: return np.Inf, [] def solveTSPmatrix(dist, route=None, exact=True, logFile=None)-
Invokes Concorde's TSP solver.
Parameters
dist : numpy array of c_int
Contains the lower triangle part of the symmetric distance matrix. That is the distance between the i-th node and the j-th node (i=0,…,n-1 and i > j) is given by dist[(i-1)i/2 + j].
route : list of int, optional
If not None, it need to be a permutation of the n nodes which is used as an initial route.
exact : bool
If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic.
logFile : str
If not None, it need to be the name of file, where to redirect output from Concorde.Returns
routeLen : int
Length of the route (routeLen).
route : list of int
Computed route (route[0] is the depot and route[-1] is the last customer).Expand source code
def solveTSPmatrix( dist, route=None, exact=True, logFile = None ): """ Invokes Concorde's TSP solver. Parameters: **dist** : numpy array of c_int Contains the lower triangle part of the symmetric distance matrix. That is the distance between the i-th node and the j-th node (i=0,...,n-1 and i > j) is given by dist[(i-1)i/2 + j]. **route** : list of int, optional If not None, it need to be a permutation of the n nodes which is used as an initial route. **exact** : bool If true (default) it is tried to solve the instance exactly by means of Concorde's branch-and-cut solver; otherwise Concorde only applies the Lin-Kernighan heuristic. **logFile** : str If not None, it need to be the name of file, where to redirect output from Concorde. Returns: **routeLen** : int Length of the route (routeLen). **route** : list of int Computed route (route[0] is the depot and route[-1] is the last customer). """ if __CC_Lib is None: print("Concorde Library not loaded!") return 0, [] # Number of nodes n = int(0.5+np.sqrt(0.25+2*len(dist) + 1.0E-7)) nn = ctypes.c_int( n ) seed = ctypes.c_int( int( time.time() ) ) tiLim = ctypes.c_double(0.0) LKonly = ctypes.c_char(1-int(exact)) minIndx = 0 if route is None: tLen = ctypes.c_double( 0.0 ) tour = np.zeros(n, dtype=ctypes.c_int) else: minIndx = min(route) tour = np.array( route, dtype=ctypes.c_int ) - minIndx tLen = ctypes.c_double( 1.0 ) ptour= tour.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) ) # Redirect output from Concorde? if logFile is None: logPtr = ctypes.c_char_p(0) else: logPtr = ctypes.c_char_p(logFile.encode('utf-8')) old_out = sys.stdout pdist = dist.ctypes.data_as( ctypes.POINTER( ctypes.c_int ) ) # Call concorde for computing TSP tour __CC_Lib.solve_STSP.restype = ctypes.c_int status = __CC_Lib.solve_STSP( LKonly, nn, seed, tiLim, pdist,\ logPtr, ctypes.byref(tLen), ptour ) # Following is safer when on Windows if not logFile is None: sys.stdout = old_out if status < 2: routeLen = int(tLen.value) route = [ i+minIndx for i in tour ] return routeLen, route else: return np.Inf, []