[pgrouting-users] TSP Euclidean distance function

[Stephen Woodbridge]

Here is an interesting way deal with this problem:

create or replace function pgr_makeDistanceMatrix(sqlin text, OUT 
dmatrix double precision[], OUT ids integer[])
   as
$body$
declare
     sql text;
     r record;

begin
     dmatrix := array[]::double precision[];
     ids := array[]::integer[];

     sql := 'with nodes as (' || sqlin || ')
         select i, array_agg(dist) as arow from (
             select a.id as i, b.id as j, st_distance(st_makepoint(a.x, 
a.y), st_makepoint(b.x, b.y)) as dist
               from nodes a, nodes b
              order by a.id, b.id
            ) as foo group by i order by i';

     for r in execute sql loop
         dmatrix := array_cat(dmatrix, array[r.arow]);
         ids := ids || array[r.i];
     end loop;

end;
$body$
language plpgsql stable cost 10;


with dm  as (
     select * from pgr_makeDistanceMatrix(
         'select source_id as id, x, y
            from tsp_00
           where source_id in (1,7,16,3,5)')
),
   ids as (
     select (row_number() over (order by id asc))-1 as rnum, id
       from (
             select unnest(ids) as id
               from dm
             ) foo
)
select a.seq, b.rnum, b.id, d.dmatrix[a.seq+1][b.rnum+1] as dist
   from pgr_tsp(
                (select dmatrix from dm),
                (select rnum from ids where id=7)::integer
        ) a,
        ids b,
        dm d
  where a.id=b.rnum;


i; j; id; cost
0; 3; 7; 6
1; 0; 1; 2.23606797749979
2; 1; 3; 3
3; 2; 5; 4.47213595499958
4; 4; 16; 0                <<-- this line seems to be bad see below


Since it took me all afternoon and evening to figure this out I will 
leave that as an exercise for the reader, but feel free to ask questions.

I think the whole second query can be wrapped in a stored procedure 
where it takes sql string the gets dropped into the dm CTE and returns 
the results.

I think there is a bug in my logic somewhere because I always seem to 
get back one row there the seq=rnum and the cost is zero so this not is 
not linked to the path.

But my brain is too fried to make sense of this anymore tonight.

Thoughts,
   -Steve

On 6/28/2013 10:17 AM, Stephen Woodbridge wrote:
> Hi All,
>
> I'm trying to understand how the old TSP code was supposed to work, as
> it is not making any sense to me. So the signature is:
>
> select * from pgr_tsp(sql text, ids text, start_id integer, end_id
> integer);
>
> sql - sql that selects some number of point that have id, x, and y, ie:
> 'select id, x, y from table'
> ids - is a comma separated list of ids, :ie: '3,27,44,6'
> start_id - must be one of the ids in the ids list
> end_id - [optional] will be the end of the path if passed in, otherwise
> assumes a loop. must be in ids
>
> Currently 'sql' can select an arbitrary list of nodes greater than the
> list of ids. This does not make any sense to me and the code behaves
> badly in this case. For example if you select 100 points in the sql and
> only have 5 in the ids list what does this mean? Why is the ids list
> separate from the sql?
>
> Currently the code only works cleanly if the the sql returns exactly the
> list of ids. ie:
>
> select * from pgr_tsp(
>    'select id, x, y from mytable where id in (3,27,44,6)',
>   '3,27,44,6',
>   3, -1);
>
> This seems redundant and messy at best.
> Can anyone clear up what was supposed to happen in the old version?
>
> I'm temped to just through out the old code and rewrite this as a
> wrapper that computes a distance matrix and calls the matrix function,
> or something like that.
>
> Thoughts, use cases?
>
> -Steve
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users