# TSP with Optional Nodes

Suppose I have a graph $$G(N,V)$$, where $$V = R\cup S$$. $$R$$ is a set of nodes which must be visited, $$S$$ is a set of supporting nodes, i.e. nodes which can be used to build the route. The graph is described by an adjacency matrix $$\mathrm{A}$$. I already computed the distance matrix $$\mathrm{D}$$, i.e. the pairs of all shortest path between two nodes.

So, I am asked to build the optimal route which visits at least all the nodes in $$R$$. How can I cast the problem into TSP? Shall I use the $$\mathrm{D}$$ or the adjacency matrix $$\mathrm{A}$$? BFS or DFS could be useful?

I tried with this formulation (taken from a paper)

with this code:

# Create a Concrete Model
n = len(R)
starting_node = 'S_44'
model = ConcreteModel()
model.constraints = ConstraintList()

model.E = Set(initialize=edges.keys())
model.R = Set(initialize=R)  # Define set R
model.S = Set(initialize=S)     # Define set S
model.V = Set(initialize=R+S)

model.d = Param(model.V, model.V, initialize=dist_matrix)

# Variables
model.x = Var(model.E, within=NonNegativeIntegers)  # Decision variables x_ij
model.y = Var(model.E, within=NonNegativeReals)  # Additional variables y_ij

# Objective function
def objective_rule(model):
return sum(model.d[i,j] * model.x[i,j] for i,j in model.E   )

model.obj = Objective(rule=objective_rule, sense=minimize)
#SCSF forumaltion
model.cons0 = ConstraintList()
if e in model.R:
model.cons0.add( sum(model.x[e, j] for j in neigh if j!= e) == 1)

# Constraint 1
model.cons1 = ConstraintList()

if e in model.V:
model.cons1.add(sum(model.x[e, j] for j in neigh if j!= e ) ==
sum(model.x[j, e] for j in neigh if j!= e ))

# Constraint 2,3 Flow Conservation
model.cons2 = ConstraintList()
model.cons3 = ConstraintList()
if i in model.R and i != starting_node:
model.cons2.add(sum(model.y[e, i] - model.y[i,e] for e in neigh) == 1 )

if i in model.S and i != starting_node:
model.cons3.add(sum(model.y[e, i] - model.y[i,e] for e in neigh) == 0 )

#Commodity
model.cons4 = ConstraintList()
for i, j in model.E:
model.cons4.add(model.y[i, j] >= len(R) *  model.x[i,j])


but the solutions found are not good

Edges with x=1:
x[S_02,v_12] = 1.0
x[S_04,v_14] = 1.0
x[v_12,S_02] = 1.0
x[v_13,v_23] = 1.0
x[v_23,v_13] = 1.0
x[v_33,v_43] = 1.0
x[v_43,v_33] = 1.0
x[v_14,S_04] = 1.0
x[v_24,v_34] = 1.0
x[v_34,v_24] = 1.0
x[v_44,v_54] = 1.0
x[v_54,v_44] = 1.0


I drawn the graph with networks:

{'S_22': {'S_02': 60, 'S_33': 60, 'v_12': 51.75},
'S_02': {'S_22': 60, 'S_03': 30, 'v_12': 8.25},
'S_33': {'S_03': 90,
'S_22': 60,
'S_44': 60,
'v_13': 81.75,
'v_23': 73.5,
'v_33': 65.25,
'v_43': 57},
'S_03': {'S_33': 90, 'S_02': 30, 'S_04': 30, 'v_13': 8.25},
'S_44': {'S_04': 120,
'S_33': 60,
'v_14': 111.75,
'v_24': 103.5,
'v_34': 95.25,
'v_44': 87,
'v_54': 78.75},
'S_04': {'S_44': 120, 'S_03': 30, 'v_14': 8.25},
'v_12': {'S_02': 8.25, 'S_22': 51.75},
'v_13': {'S_03': 8.25, 'S_33': 81.75, 'v_23': 8.25},
'v_23': {'v_13': 8.25, 'S_33': 73.5, 'v_33': 8.250000000000004},
'v_33': {'v_23': 8.250000000000004, 'S_33': 65.25, 'v_43': 8.249999999999996},
'v_43': {'v_33': 8.249999999999996, 'S_33': 57},
'v_14': {'S_04': 8.25, 'S_44': 111.75, 'v_24': 8.25},
'v_24': {'v_14': 8.25, 'S_44': 103.5, 'v_34': 8.250000000000004},
'v_34': {'v_24': 8.250000000000004, 'S_44': 95.25, 'v_44': 8.249999999999996},
'v_44': {'v_34': 8.249999999999996, 'S_44': 87, 'v_54': 8.25},
'v_54': {'v_44': 8.25, 'S_44': 78.75}}


and the distance matrix is:

{"S_22":{"S_22":0,"S_02":60,"S_33":60,"S_03":90,"S_44":120,"S_04":120,"v_12":51.75,"v_13":98.25,"v_23":106.5,"v_33":114.75,"v_43":117,"v_14":128.25,"v_24":136.5,"v_34":144.75,"v_44":153,"v_54":161.25},"S_02":{"S_22":60,"S_02":0,"S_33":120,"S_03":30,"S_44":180,"S_04":60,"v_12":8.25,"v_13":38.25,"v_23":46.5,"v_33":54.75,"v_43":63,"v_14":68.25,"v_24":76.5,"v_34":84.75,"v_44":93,"v_54":101.25},"S_33":{"S_22":60,"S_02":120,"S_33":0,"S_03":90,"S_44":60,"S_04":120,"v_12":111.75,"v_13":81.75,"v_23":73.5,"v_33":65.25,"v_43":57,"v_14":128.25,"v_24":136.5,"v_34":144.75,"v_44":147,"v_54":138.75},"S_03":{"S_22":90,"S_02":30,"S_33":90,"S_03":0,"S_44":150,"S_04":30,"v_12":38.25,"v_13":8.25,"v_23":16.5,"v_33":24.750000000000004,"v_43":33,"v_14":38.25,"v_24":46.5,"v_34":54.75,"v_44":63,"v_54":71.25},"S_44":{"S_22":120,"S_02":180,"S_33":60,"S_03":150,"S_44":0,"S_04":120,"v_12":171.75,"v_13":141.75,"v_23":133.5,"v_33":125.25,"v_43":117,"v_14":111.75,"v_24":103.5,"v_34":95.25,"v_44":87,"v_54":78.75},"S_04":{"S_22":120,"S_02":60,"S_33":120,"S_03":30,"S_44":120,"S_04":0,"v_12":68.25,"v_13":38.25,"v_23":46.5,"v_33":54.75,"v_43":63,"v_14":8.25,"v_24":16.5,"v_34":24.750000000000004,"v_44":33,"v_54":41.25},"v_12":{"S_22":51.75,"S_02":8.25,"S_33":111.75,"S_03":38.25,"S_44":171.75,"S_04":68.25,"v_12":0,"v_13":46.5,"v_23":54.75,"v_33":63,"v_43":71.25,"v_14":76.5,"v_24":84.75,"v_34":93,"v_44":101.25,"v_54":109.5},"v_13":{"S_22":98.25,"S_02":38.25,"S_33":81.75,"S_03":8.25,"S_44":141.75,"S_04":38.25,"v_12":46.5,"v_13":0,"v_23":8.25,"v_33":16.500000000000004,"v_43":24.75,"v_14":46.5,"v_24":54.75,"v_34":63,"v_44":71.25,"v_54":79.5},"v_23":{"S_22":106.5,"S_02":46.5,"S_33":73.5,"S_03":16.5,"S_44":133.5,"S_04":46.5,"v_12":54.75,"v_13":8.25,"v_23":0,"v_33":8.250000000000004,"v_43":16.5,"v_14":54.75,"v_24":63,"v_34":71.25,"v_44":79.5,"v_54":87.75},"v_33":{"S_22":114.75,"S_02":54.75,"S_33":65.25,"S_03":24.750000000000004,"S_44":125.25,"S_04":54.75,"v_12":63,"v_13":16.500000000000004,"v_23":8.250000000000004,"v_33":0,"v_43":8.249999999999996,"v_14":63,"v_24":71.25,"v_34":79.5,"v_44":87.75,"v_54":96},"v_43":{"S_22":117,"S_02":63,"S_33":57,"S_03":33,"S_44":117,"S_04":63,"v_12":71.25,"v_13":24.75,"v_23":16.5,"v_33":8.249999999999996,"v_43":0,"v_14":71.25,"v_24":79.5,"v_34":87.75,"v_44":96,"v_54":104.25},"v_14":{"S_22":128.25,"S_02":68.25,"S_33":128.25,"S_03":38.25,"S_44":111.75,"S_04":8.25,"v_12":76.5,"v_13":46.5,"v_23":54.75,"v_33":63,"v_43":71.25,"v_14":0,"v_24":8.25,"v_34":16.500000000000004,"v_44":24.75,"v_54":33},"v_24":{"S_22":136.5,"S_02":76.5,"S_33":136.5,"S_03":46.5,"S_44":103.5,"S_04":16.5,"v_12":84.75,"v_13":54.75,"v_23":63,"v_33":71.25,"v_43":79.5,"v_14":8.25,"v_24":0,"v_34":8.250000000000004,"v_44":16.5,"v_54":24.75},"v_34":{"S_22":144.75,"S_02":84.75,"S_33":144.75,"S_03":54.75,"S_44":95.25,"S_04":24.750000000000004,"v_12":93,"v_13":63,"v_23":71.25,"v_33":79.5,"v_43":87.75,"v_14":16.500000000000004,"v_24":8.250000000000004,"v_34":0,"v_44":8.249999999999996,"v_54":16.499999999999996},"v_44":{"S_22":153,"S_02":93,"S_33":147,"S_03":63,"S_44":87,"S_04":33,"v_12":101.25,"v_13":71.25,"v_23":79.5,"v_33":87.75,"v_43":96,"v_14":24.75,"v_24":16.5,"v_34":8.249999999999996,"v_44":0,"v_54":8.25},"v_54":{"S_22":161.25,"S_02":101.25,"S_33":138.75,"S_03":71.25,"S_44":78.75,"S_04":41.25,"v_12":109.5,"v_13":79.5,"v_23":87.75,"v_33":96,"v_43":104.25,"v_14":33,"v_24":24.75,"v_34":16.499999999999996,"v_44":8.25,"v_54":0}}

• Does this answer your question? How to visit a subset of network nodes in a single trip? Commented Apr 16 at 14:08
• Hi, thank you. It is very similar but I need a route back to the source. So the algotihm shall output the path, the sequence of nodes, to follow in order to visit the required nodes and go back home...
– gdm
Commented Apr 16 at 14:15
• In the accepted answer to the linked question, just don’t change the distances back to the source to zero. Commented Apr 16 at 17:59
• @RobPratt ok, but to me is quite difficult to implement it...it is not quite clear...
– gdm
Commented Apr 17 at 7:33

Here's a way to solve the problem with two calls to the network solver in SAS (disclaimer: I work for SAS).

data LinkData;
input from $$to$$ cost;
datalines;
S_22 S_33 60.00
S_22 v_12 51.75
S_02 S_22 60.00
S_02 S_03 30.00
S_02 v_12 8.25
S_33 S_44 60.00
S_33 v_13 81.75
S_33 v_23 73.50
S_33 v_33 65.25
S_33 v_43 57.00
S_03 S_33 90.00
S_03 S_04 30.00
S_03 v_13 8.25
S_44 v_14 111.75
S_44 v_24 103.50
S_44 v_34 95.25
S_44 v_44 87.00
S_44 v_54 78.75
S_04 S_44 120.00
S_04 v_14 8.25
v_13 v_23 8.25
v_23 v_33 8.25
v_33 v_43 8.25
v_14 v_24 8.25
v_24 v_34 8.25
v_34 v_44 8.25
v_44 v_54 8.25
;

data MustNodeData;
input node \$;
datalines;
v_12
v_13
v_14
v_23
v_24
v_33
v_34
v_43
v_44
v_54
;

proc optmodel;
set NODES = union {<i,j> in LINKS} {i,j};
set <str> MUSTNODES;
print cost;

/* solve all-pairs shortest path problem in original graph */
set PAIRS = {i in MUSTNODES, j in MUSTNODES: i < j};
num d {PAIRS} init 0;
solve with network / shortpath=(source=MUSTNODES sink=MUSTNODES) links=(weight=cost) out=(spweights=d);
print d;

/* solve traveling salesman problem in complete graph on MUSTNODES */
set <str,str> TOUR;
solve with network / tsp links=(weight=d) out=(tour=TOUR);
print {<i,j> in TOUR} d;
quit;


The shortest-path distances are:

     v_13  v_14  v_23  v_24  v_33  v_34  v_43  v_44   v_54
v_12 46.50 76.50 54.75 84.75 63.00 93.00 71.25 101.25 109.50
v_13       46.50  8.25 54.75 16.50 63.00 24.75  71.25  79.50
v_14             54.75  8.25 63.00 16.50 71.25  24.75  33.00
v_23                   63.00  8.25 71.25 16.50  79.50  87.75
v_24                         71.25  8.25 79.50  16.50  24.75
v_33                               79.50  8.25  87.75  96.00
v_34                                     87.75   8.25  16.50
v_43                                            96.00 104.25
v_44                                                    8.25


An optimal TSP tour (with objective value 285) is as follows:

v_12 v_13  46.50
v_12 v_54 109.50
v_13 v_23   8.25
v_14 v_24   8.25
v_14 v_43  71.25
v_23 v_33   8.25
v_24 v_34   8.25
v_33 v_43   8.25
v_34 v_44   8.25
v_44 v_54   8.25


Now expand each link in the tour to a shortest path in the original graph.