I have a Travelling Salesman Problem, where I want to retrieve the "shortest" (approximate solution) circuit including the nodes n_1..n_n in a graph. The graph, however, includes a second set of nodes, say, o_1..o_n, which CAN but do not NEED to be included in the route (see picture).
i.e., this means, in the graph, I do not know the shortest paths between the nodes n_1..n_n which I want to travel.
Is there a more elegant way to retriev a relativley optimal solution than transforming the original graph into a graph only including the nodes n_1..n_n (e.g. by solving the shortest path problem for each pair of nodes [n_i|n_j]) and then using e.g. an evolutional algorithm to get a solution for the TSP?