Traveling salesman with different begining and ending nodes

[luboxing]

Greeating!

I am wondering how to specify the problem of the traveling salesman problem (TSP) with different starting and ending nodes. I am able to replicate the proc optnetwork example below described in the SAS manual:

proc optnetwork
   direction = directed
   logLevel  = moderate
   links     = mycas.LinkSetIn
   outNodes  = mycas.NodeSetOut;
   tsp
      out    = mycas.TSPTour;
run;

But the example only applies to a TSP problem where the salesman goes back to the same node he started from. The problem I want to solve relaxes that requirement -- he only need to go to every node without returning to the starting point.

Any help would be highly appreciated!

Bo

[Ksharp]

Calling @RobPratt 

[RobPratt]

The standard approach to this variant is to introduce a dummy node with zero-cost edges to the other nodes, as shown in the “A Better Lower Bound from TSP” section here: https://support.sas.com/resources/papers/proceedings14/SAS101-2014.pdf

In the resulting tour, the two neighbors of the dummy node are the starting and ending nodes.

[luboxing · Accepted solution]

Thanks, Rob!