topic Re: Traveling salesman with different begining and ending nodes in Mathematical Optimization, Discrete-Event Simulation, and OR

Traveling salesman with different begining and ending nodes

luboxing — Mon, 08 Aug 2022 05:56:41 GMT

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!

Re: Traveling salesman with different begining and ending nodes

Ksharp — Mon, 08 Aug 2022 12:00:21 GMT

Calling @RobPratt

Re: Traveling salesman with different begining and ending nodes

RobPratt — Mon, 08 Aug 2022 13:02:52 GMT

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.

Re: Traveling salesman with different begining and ending nodes

luboxing — Mon, 08 Aug 2022 17:44:26 GMT

Thanks, Rob!