turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Find a Community

- Home
- /
- SAS Programming
- /
- SAS/GRAPH and ODS Graphics
- /
- Simulating all the possible routes starting on one...

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

08-20-2015 04:02 PM

I am trying to simulate combinations based on 5 coordinates (datset below):

data coord;

input x 1. y 1.;

datalines;

11

32

55

91

14

run;

Every combination must begin with (1,1) and end with (1,1) i.e.

(1,1) -> (3,2)-> (5,5)-> (9,1)-> (1,4)-> (1,1)

and all combinations must be unique and finally that there can't be the above route and

(1,1) ->(1,4)-> (9,1)-> (5,5)-> (3,2)-> (1,1)

as both routes are the same but in opposite directions.

Is there a way to do this in sas?

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Hugo123

09-09-2015 11:38 AM

The code below should do what you require.

Just a few notes.

1) I've stuck the x and the y coordinate together as it's easier to deal with them in this way.

2) I've hard coded the 1,1 coordinate as it does not change. This can however be incorporated into the data if you require.

3) The data set outds2 also contains a list of the routes you require and outds3 contains the reverse of these routes.

/*Set up the initial table*/

data coord;

input xy 8.;

datalines;

32

55

91

14

run;

/*Find all unique routes*/

proc sql noprint ;

create table outds as

select 11 as c1,

a.xy as c2,

b.xy as c3,

c.xy as c4,

d.xy as c5,

11 as c6

from coord as a,

coord as b,

coord as c,

coord as d

where a.xy ne b.xy and a.xy ne c.xy and a.xy ne d.xy and b.xy ne c.xy and b.xy ne d.xy and c.xy ne d.xy ;

select count(*) into :nobserv from outds ;

quit ;

/*Find the routes which are the reverse of already known routes*/

data outds2 (drop=c2_2 c3_2 c4_2 c5_2);

do i = 1 to &nobserv-1 ;

do j = i+1 to &nobserv ;

set outds point=i ;

set outds (rename=(c2=c2_2 c3=c3_2 c4=c4_2 c5=c5_2)) point=j ;

if c2=c5_2 and c3=c4_2 and c4=c3_2 and c5=c2_2 then output ;

end ;

end ;

stop ;

run ;

/*Remove the reverse routes from the main data set*/

proc sql ;

create table outds3 as

select *

from outds

except all

select *

from outds2 ;

quit ;

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Hugo123

09-11-2015 09:07 AM - edited 09-11-2015 09:08 AM

Hi, here's another approach that uses LEXPERM to generate the permutations of nodes (same answer as the other posted solution with some paths shown in the reverse order) ...

*** generate permutations of four nodes;****data perm;****array x(4) $2 ('32' '14' '55' '91');****do j=1 to fact(4);**** rc=lexperm(j, of x(*));**** output;****end;****keep x:;****run;**

*** identify duplicates (left-2-right = right-2-left, output only one of the pair);**

**data check;**

**retain x0 x5 '11';****set perm nobs=howmany;****s1 = catt(of x1-x4);****do j=_n_ to howmany;**** set perm point=j;**** s2 = catt(of x4-x1);**** if s1 eq s2 then leave;****end;****if s1 eq s2 then output;****keep x:;****run;**

data set CHECK ...

**Obs x0 x1 x2 x3 x4 x5**

** 1 11 91 55 32 14 11**** 2 11 55 91 32 14 11**** 3 11 91 32 55 14 11**** 4 11 32 91 55 14 11**** 5 11 55 32 91 14 11**** 6 11 32 55 91 14 11**** 7 11 91 55 14 32 11**** 8 11 55 91 14 32 11**** 9 11 91 14 55 32 11****10 11 55 14 91 32 11****11 11 91 32 14 55 11****12 11 91 14 32 55 11**

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Hugo123

09-14-2015 02:39 PM

This is an enumeration of the possible paths in the Traveling Salesman problem. As the number of points grows, brute-force enumeration becomes prohibitive, but you can use various optimization schemes to obtain optimal or nearly optimal paths.

Do an internet search for +SAS "Traveling salesman" to see many solutions in SAS for the TSP.