TSP - output the path

Support
1

Hi ! I’m fairly new to AMPL and would like some help ;

i am doing a simplified version of the TSP problem, with no definied start or end node.
Everything works great and my output is this ;
x :=
A A 0
A B 0
A C 1
A D 0
B A 0
B B 0
B C 0
B D 1
C A 0
C B 1
C C 0
C D 0
D A 0
D B 0
D C 0
D D 0
;

Is there any way for AMPL to give the path ?
It would, by itself, print/display : “path is A-C-B-D” ?

Thanks in advance.

2

Here’s an example that you can adapt to your needs. Supposing that you write

set N;
var x {N,N};

in your model and

set N := A B C D ;

in your data, you could use the following AMPL statements to determine and display the path:

set PATH ordered within N;

let PATH := {j in N: card {i in N: x[i,j] = 1} = 0};
let {i in 2..card(N)} PATH := PATH union {j in N: x[last(PATH),j] = 1};

print {i in PATH} i & (if i!=last(PATH) then " ->" else "");

There are four nodes but only 3 arcs in the solution, so the first let statement initializes set PATH to contain the one node (A) that does not have any arcs leading into it. Then the second let statement follows the path for 3 steps.

1 Like