Module tsp.tsp_heu
TSP - Some simple heuristics for the symmetric TSP.
Expand source code
"""
TSP - Some simple heuristics for the symmetric TSP.
"""
import numpy as np
import networkx as nx
from tsp.tsp_plot import displayRoute
from tsp.tsp_plot import plotEdgeList
#---------------------------------------------------------------------
def __chk_wfunc( problem ):
"""
Check which version of tsplib95 applies and set the (edge) weight
function accordingly
"""
try:
_ = problem.wfunc # tsplib95 version before 0.7.1
except:
problem.wfunc = problem._wfunc # tsplib95, version 0.7.1
#---------------------------------------------------------------------
def nearestNeighbour( problem ):
"""
Computes solution using nearest neighbour with random start point.
Parameters:
**problem** : class
TSP problem object has returned by function load_problem
of the package tsplib95.
Returns:
**routeLen** : int
Length of the route.
**route** : list of int
List of points on the route where route[-1] is the last node visited.
"""
__chk_wfunc( problem )
unRouted = [ i for i in problem.get_nodes()]
routeLen = 0
# Choose random start point
node = np.random.choice(unRouted)
route = [ node ]
unRouted.remove(node)
while len(unRouted) > 0:
nextNode = min( unRouted, key = lambda j : problem.wfunc(node,j) )
unRouted.remove(nextNode)
route.append(nextNode)
routeLen += problem.wfunc(node,nextNode)
node = nextNode
routeLen += problem.wfunc(node,route[0])
return routeLen, route
#---------------------------------------------------------------------
def doInsertion( problem, nearest=True ):
"""
Computes solution using nearest or farthest insertion with random
start point.
Parameters:
**problem** : class
TSP problem object has returned by function load_problem
of the package tsplib95.
**nearest** : bool, optional
If false, farthest insertion is applied. Otherwise
nearest insertion is applied (default)
Returns:
**routeLen** : int
Length of the route.
**route** : list of int
List of points on the route where route[-1] is the last node visited.
"""
def insCost( node, i, route ):
"""
Return cost to insert node at position between i and i+1 in
the route.
"""
j1 = route[i]
j2 = route[(i+1) % len(route)]
delta = problem.wfunc(node,j1)+problem.wfunc(node,j2)-problem.wfunc(j1,j2)
return delta
__chk_wfunc(problem)
# Initialize the the route with some randomly selected edge
unRouted = [ node for node in problem.get_nodes()]
n1 = np.random.choice(unRouted)
unRouted.remove(n1)
n2 = np.random.choice(unRouted)
unRouted.remove(n2)
route = [n1,n2,n1]
routeLen = problem.wfunc(n1,n2)*2
sign = 1
if not nearest : sign = -1
while len(unRouted) > 0:
# Determine unrouted node closest (or farthest) to a routed node
nextNode = None
minDist = np.Inf
for j in unRouted:
dist = min( [sign*problem.wfunc(j,node) for node in route] )
if dist < minDist:
dist = minDist
nextNode = j
# Insert nextNode at cheapest insertion place
ins_at = min([i for i in range(len(route))],\
key = lambda i : insCost( nextNode, i, route ) )
routeLen += insCost(nextNode,ins_at,route)
route.insert(ins_at+1,nextNode)
unRouted.remove( nextNode )
return routeLen, route[:-1]
#---------------------------------------------------------------------
def minSpanTree( problem, display=True, animate=True, wait_func=None,
fontsize=6):
"""
Apply the minimum spanning tree heuristic.
Parameters:
**problem** : class
TSP problem object has returned by function load_problem
of the package tsplib95.
**display** : bool, optional
I true (default) a figure of the minimum spanning tree,
the Eulerian cycle and the resulting route is displayed.
**animate** : bool, optional
If true (default) the Eulerian cycle and the route are
drawn in an animated way.
**wait_func** : function, optional
Waiting function called after drawing (intermediate) solutions
when display=True. Will be required when Matplotlib.pyplot
is in interactive mode, as then the window has not explicitly
to be destroyed to proceed with the computations. The function
itself does not take any arguments, and should ask for some
user action to continue.
**fontsize** : int, optional
Size of the font used to display node numbers (only
relevant if display=True)
Returns:
**routeLen** : int
Length of the route.
**route** : list of int
List of points on the route where route[-1] is the last node visited.
"""
__chk_wfunc(problem)
# Represent problem data using a networkx graph object
G = problem.get_graph()
# Obtain the minimum spanning tree and the Eulerian graph by doubling the tree
T = nx.minimum_spanning_tree(G)
E = nx.MultiGraph( T )
E.add_edges_from(T.edges)
tLen = sum( T.get_edge_data(*e)['weight'] for e in T.edges )
# Display the minimum spanning tree
if display:
plotEdgeList( problem, E.edges, title='Minimum spanning '+\
'tree/Eulerian graph. Length= '+str(tLen),\
fontsize=fontsize, wait_func=wait_func)
circuit = [u for u,_ in nx.eulerian_circuit(E)]
circuit.append(circuit[0])
if display:
displayRoute( problem, circuit, 2*tLen, animate=animate,\
title='Eulerian circuit',fontsize=fontsize,wait_func=wait_func)
# Build the TSP route by taking shortcuts in the Eulerian cycle
route = list(dict.fromkeys(circuit)) # This removes duplicates from the circuit
routeLen = sum( problem.wfunc(route[i-1],route[i]) for i in range(1,problem.dimension) )
routeLen += problem.wfunc(route[-1],route[0])
if display:
displayRoute( problem, route, routeLen, animate=animate,\
title='Found tour',fontsize=fontsize,wait_func=wait_func)
return routeLen, route
#---------------------------------------------------------------------
def christofides( problem, display=True, animate=True, wait_func=None,
fontsize=6 ):
"""
Apply the Christofides' heuristic.
Parameters:
**problem** : class
TSP problem object has returned by function load_problem
of the package tsplib95.
**display** : bool, optional
I true (default) a figure of the minimum spanning tree,
the Eulerian cycle and the resulting route is displayed.
**animate** : bool, optional
If true (default) the Eulerian cycle and the route are
drawn in an animated way.
**wait_func** : function, optional
Waiting function called after drawing (intermediate) solutions
when display=True. Will be required when Matplotlib.pyplot
is in interactive mode, as then the window has not explicitly
to be destroyed to proceed with the computations. The function
itself does not take any arguments, and should ask for some
user action to continue.
**fontsize** : int, optional
Size of the font used to display node numbers (only
relevant if display=True)
Returns:
**routeLen** : int
Length of the route.
**route** : list of int
List of points on the route where route[-1] is the last node visited.
"""
__chk_wfunc(problem)
# Represent problem data using a networkx graph object
G = problem.get_graph()
# The graph may contain edges connecting a node to itself
# We first remove all these simple loops
G.remove_edges_from(nx.selfloop_edges(G))
# Initialize the graph (that later will be Eulerian)
# as a multigraph that first contains the edges from
# a minimim spanning tree of G
E = nx.MultiGraph( nx.minimum_spanning_tree(G) )
tLen = sum( E.get_edge_data(*e)['weight'] for e in E.edges )
# Find the nodes of odd degree in the minimum spanning tree
odd = [ node for node in E.nodes if E.degree(node) % 2 > 0 ]
# Display the minimum spanning tree and mark the odd nodes
if display:
plotEdgeList( problem, E.edges, specialNodes=odd, title=\
'Minimum spanning tree (odd nodes are red)',\
fontsize=fontsize, wait_func=wait_func)
# Obtain the subgraph of G induced by the "odd" nodes
oddG = G.subgraph( odd )
# Compute a perfect minimum-cost matching in the graph O of
# odd nodes. We do that by transforming the problem into the
# problem of finding a maximum weight matching of maximum
# cardinality. Note that this changes the weights also in G
# and not not only in oddG.
wmax = max( oddG[e[0]][e[1]]['weight'] for e in oddG.edges )
for e in oddG.edges:
oddG[e[0]][e[1]]['weight'] = wmax - oddG[e[0]][e[1]]['weight']
M = nx.max_weight_matching( oddG, maxcardinality=True )
# Add the edges from the matching to the spanning tree to obtain Eulerian graph
tLen += sum( problem.wfunc(e[0],e[1]) for e in M )
E.add_edges_from( M )
if display:
plotEdgeList( problem, E.edges, specialEdges=M, specialNodes=odd,\
title="Spanning tree + matching of odd nodes (red edges)",\
fontsize=fontsize, wait_func=wait_func )
# Obtain an Eulerian circuit in the graph oddG+M
circuit = [u for u,_ in nx.eulerian_circuit(E)]
circuit.append(circuit[0])
if display:
displayRoute( problem, circuit, 2*tLen, title='Eulerian circuit', \
animate=animate,fontsize=fontsize, wait_func=wait_func)
# Build the TSP route by taking shortcuts in the Eulerian cycle
route = list(dict.fromkeys(circuit)) # This removes duplicates from the circuit
routeLen = sum( problem.wfunc(route[i-1],route[i]) for i in range(1,problem.dimension) )
routeLen += problem.wfunc(route[-1],route[0])
if display:
displayRoute( problem, route, routeLen, title='Found tour',\
animate=animate,fontsize=fontsize,wait_func=wait_func)
return routeLen, routeFunctions
def christofides(problem, display=True, animate=True, wait_func=None, fontsize=6)-
Apply the Christofides' heuristic.
Parameters
problem : class
TSP problem object has returned by function load_problem of the package tsplib95.
display : bool, optional
I true (default) a figure of the minimum spanning tree, the Eulerian cycle and the resulting route is displayed.
animate : bool, optional
If true (default) the Eulerian cycle and the route are drawn in an animated way.
wait_func : function, optional
Waiting function called after drawing (intermediate) solutions when display=True. Will be required when Matplotlib.pyplot is in interactive mode, as then the window has not explicitly to be destroyed to proceed with the computations. The function itself does not take any arguments, and should ask for some user action to continue.
fontsize : int, optional
Size of the font used to display node numbers (only relevant if display=True)Returns
routeLen : int
Length of the route.
route : list of int
List of points on the route where route[-1] is the last node visited.Expand source code
def christofides( problem, display=True, animate=True, wait_func=None, fontsize=6 ): """ Apply the Christofides' heuristic. Parameters: **problem** : class TSP problem object has returned by function load_problem of the package tsplib95. **display** : bool, optional I true (default) a figure of the minimum spanning tree, the Eulerian cycle and the resulting route is displayed. **animate** : bool, optional If true (default) the Eulerian cycle and the route are drawn in an animated way. **wait_func** : function, optional Waiting function called after drawing (intermediate) solutions when display=True. Will be required when Matplotlib.pyplot is in interactive mode, as then the window has not explicitly to be destroyed to proceed with the computations. The function itself does not take any arguments, and should ask for some user action to continue. **fontsize** : int, optional Size of the font used to display node numbers (only relevant if display=True) Returns: **routeLen** : int Length of the route. **route** : list of int List of points on the route where route[-1] is the last node visited. """ __chk_wfunc(problem) # Represent problem data using a networkx graph object G = problem.get_graph() # The graph may contain edges connecting a node to itself # We first remove all these simple loops G.remove_edges_from(nx.selfloop_edges(G)) # Initialize the graph (that later will be Eulerian) # as a multigraph that first contains the edges from # a minimim spanning tree of G E = nx.MultiGraph( nx.minimum_spanning_tree(G) ) tLen = sum( E.get_edge_data(*e)['weight'] for e in E.edges ) # Find the nodes of odd degree in the minimum spanning tree odd = [ node for node in E.nodes if E.degree(node) % 2 > 0 ] # Display the minimum spanning tree and mark the odd nodes if display: plotEdgeList( problem, E.edges, specialNodes=odd, title=\ 'Minimum spanning tree (odd nodes are red)',\ fontsize=fontsize, wait_func=wait_func) # Obtain the subgraph of G induced by the "odd" nodes oddG = G.subgraph( odd ) # Compute a perfect minimum-cost matching in the graph O of # odd nodes. We do that by transforming the problem into the # problem of finding a maximum weight matching of maximum # cardinality. Note that this changes the weights also in G # and not not only in oddG. wmax = max( oddG[e[0]][e[1]]['weight'] for e in oddG.edges ) for e in oddG.edges: oddG[e[0]][e[1]]['weight'] = wmax - oddG[e[0]][e[1]]['weight'] M = nx.max_weight_matching( oddG, maxcardinality=True ) # Add the edges from the matching to the spanning tree to obtain Eulerian graph tLen += sum( problem.wfunc(e[0],e[1]) for e in M ) E.add_edges_from( M ) if display: plotEdgeList( problem, E.edges, specialEdges=M, specialNodes=odd,\ title="Spanning tree + matching of odd nodes (red edges)",\ fontsize=fontsize, wait_func=wait_func ) # Obtain an Eulerian circuit in the graph oddG+M circuit = [u for u,_ in nx.eulerian_circuit(E)] circuit.append(circuit[0]) if display: displayRoute( problem, circuit, 2*tLen, title='Eulerian circuit', \ animate=animate,fontsize=fontsize, wait_func=wait_func) # Build the TSP route by taking shortcuts in the Eulerian cycle route = list(dict.fromkeys(circuit)) # This removes duplicates from the circuit routeLen = sum( problem.wfunc(route[i-1],route[i]) for i in range(1,problem.dimension) ) routeLen += problem.wfunc(route[-1],route[0]) if display: displayRoute( problem, route, routeLen, title='Found tour',\ animate=animate,fontsize=fontsize,wait_func=wait_func) return routeLen, route def doInsertion(problem, nearest=True)-
Computes solution using nearest or farthest insertion with random start point.
Parameters
problem : class
TSP problem object has returned by function load_problem of the package tsplib95.
nearest : bool, optional
If false, farthest insertion is applied. Otherwise nearest insertion is applied (default)Returns
routeLen : int
Length of the route.
route : list of int
List of points on the route where route[-1] is the last node visited.Expand source code
def doInsertion( problem, nearest=True ): """ Computes solution using nearest or farthest insertion with random start point. Parameters: **problem** : class TSP problem object has returned by function load_problem of the package tsplib95. **nearest** : bool, optional If false, farthest insertion is applied. Otherwise nearest insertion is applied (default) Returns: **routeLen** : int Length of the route. **route** : list of int List of points on the route where route[-1] is the last node visited. """ def insCost( node, i, route ): """ Return cost to insert node at position between i and i+1 in the route. """ j1 = route[i] j2 = route[(i+1) % len(route)] delta = problem.wfunc(node,j1)+problem.wfunc(node,j2)-problem.wfunc(j1,j2) return delta __chk_wfunc(problem) # Initialize the the route with some randomly selected edge unRouted = [ node for node in problem.get_nodes()] n1 = np.random.choice(unRouted) unRouted.remove(n1) n2 = np.random.choice(unRouted) unRouted.remove(n2) route = [n1,n2,n1] routeLen = problem.wfunc(n1,n2)*2 sign = 1 if not nearest : sign = -1 while len(unRouted) > 0: # Determine unrouted node closest (or farthest) to a routed node nextNode = None minDist = np.Inf for j in unRouted: dist = min( [sign*problem.wfunc(j,node) for node in route] ) if dist < minDist: dist = minDist nextNode = j # Insert nextNode at cheapest insertion place ins_at = min([i for i in range(len(route))],\ key = lambda i : insCost( nextNode, i, route ) ) routeLen += insCost(nextNode,ins_at,route) route.insert(ins_at+1,nextNode) unRouted.remove( nextNode ) return routeLen, route[:-1] def minSpanTree(problem, display=True, animate=True, wait_func=None, fontsize=6)-
Apply the minimum spanning tree heuristic.
Parameters
problem : class
TSP problem object has returned by function load_problem of the package tsplib95.
display : bool, optional
I true (default) a figure of the minimum spanning tree, the Eulerian cycle and the resulting route is displayed.
animate : bool, optional
If true (default) the Eulerian cycle and the route are drawn in an animated way.
wait_func : function, optional
Waiting function called after drawing (intermediate) solutions when display=True. Will be required when Matplotlib.pyplot is in interactive mode, as then the window has not explicitly to be destroyed to proceed with the computations. The function itself does not take any arguments, and should ask for some user action to continue.
fontsize : int, optional
Size of the font used to display node numbers (only relevant if display=True)Returns
routeLen : int
Length of the route.
route : list of int
List of points on the route where route[-1] is the last node visited.Expand source code
def minSpanTree( problem, display=True, animate=True, wait_func=None, fontsize=6): """ Apply the minimum spanning tree heuristic. Parameters: **problem** : class TSP problem object has returned by function load_problem of the package tsplib95. **display** : bool, optional I true (default) a figure of the minimum spanning tree, the Eulerian cycle and the resulting route is displayed. **animate** : bool, optional If true (default) the Eulerian cycle and the route are drawn in an animated way. **wait_func** : function, optional Waiting function called after drawing (intermediate) solutions when display=True. Will be required when Matplotlib.pyplot is in interactive mode, as then the window has not explicitly to be destroyed to proceed with the computations. The function itself does not take any arguments, and should ask for some user action to continue. **fontsize** : int, optional Size of the font used to display node numbers (only relevant if display=True) Returns: **routeLen** : int Length of the route. **route** : list of int List of points on the route where route[-1] is the last node visited. """ __chk_wfunc(problem) # Represent problem data using a networkx graph object G = problem.get_graph() # Obtain the minimum spanning tree and the Eulerian graph by doubling the tree T = nx.minimum_spanning_tree(G) E = nx.MultiGraph( T ) E.add_edges_from(T.edges) tLen = sum( T.get_edge_data(*e)['weight'] for e in T.edges ) # Display the minimum spanning tree if display: plotEdgeList( problem, E.edges, title='Minimum spanning '+\ 'tree/Eulerian graph. Length= '+str(tLen),\ fontsize=fontsize, wait_func=wait_func) circuit = [u for u,_ in nx.eulerian_circuit(E)] circuit.append(circuit[0]) if display: displayRoute( problem, circuit, 2*tLen, animate=animate,\ title='Eulerian circuit',fontsize=fontsize,wait_func=wait_func) # Build the TSP route by taking shortcuts in the Eulerian cycle route = list(dict.fromkeys(circuit)) # This removes duplicates from the circuit routeLen = sum( problem.wfunc(route[i-1],route[i]) for i in range(1,problem.dimension) ) routeLen += problem.wfunc(route[-1],route[0]) if display: displayRoute( problem, route, routeLen, animate=animate,\ title='Found tour',fontsize=fontsize,wait_func=wait_func) return routeLen, route def nearestNeighbour(problem)-
Computes solution using nearest neighbour with random start point.
Parameters
problem : class
TSP problem object has returned by function load_problem of the package tsplib95.Returns
routeLen : int
Length of the route.
route : list of int
List of points on the route where route[-1] is the last node visited.Expand source code
def nearestNeighbour( problem ): """ Computes solution using nearest neighbour with random start point. Parameters: **problem** : class TSP problem object has returned by function load_problem of the package tsplib95. Returns: **routeLen** : int Length of the route. **route** : list of int List of points on the route where route[-1] is the last node visited. """ __chk_wfunc( problem ) unRouted = [ i for i in problem.get_nodes()] routeLen = 0 # Choose random start point node = np.random.choice(unRouted) route = [ node ] unRouted.remove(node) while len(unRouted) > 0: nextNode = min( unRouted, key = lambda j : problem.wfunc(node,j) ) unRouted.remove(nextNode) route.append(nextNode) routeLen += problem.wfunc(node,nextNode) node = nextNode routeLen += problem.wfunc(node,route[0]) return routeLen, route