[pgrouting-dev] Having problems under standing the distance matrix of TSP in respect to route network pgroute version 2, possible solution
Dave Potts
dave.potts at pinan.co.uk
Sat Jun 15 11:34:27 PDT 2013
On 15/06/13 14:28, Stephen Woodbridge wrote:
Nice Idea, but one of the problems I have is that I am VERY lazy!
When I create a source/target/cost table I only tend to populate it with
existing routes, so if I have path at cost of 42 betweens nodes 2 and 3
I will create an entry like
2 3 42
I have no desire to create an entry for journey between nodes 5 6 that
does not exist or having to provide a value for journey between myself
and myself eg a journey from node 2 to node 2, I think the suggested
solution would require me to create entries like
2 2 0
5 6 0 etc
So I had a crack at writing a function based on Steves original
screenplay. I think it needs a lot more work, when I create the
temporary tables, I get a diagnostic from psql saying that its created
a table. There must be a better way of doing it
Its invoked as
select mktsparray(' select source,target ,cost from edge_table2');
-- Make a distance matrix for the traveling salesman problem
--
-- Input is an sql string that provides source, target and the cost
-- of getting between them
--
--
CREATE or REPLACE FUNCTION mktsparray(tag_name text) RETURNS float []
LANGUAGE plpgsql
AS $$
DECLARE
ret_array float [][];
array_size integer;
tsp_details record;
BEGIN
ret_array := null;
-- create a copy of the source
EXECUTE 'DROP TABLE IF EXISTS tsp_src';
EXECUTE 'DROP TABLE IF EXISTS tsp_map';
create temporary table tsp_src ( id serial not null,source
integer not null,
target integer not null, cost float
not null);
-- create a tsp node to matrix lookup table
create temporary table tsp_map ( id serial not null primary
key, nid integer);
EXECUTE 'insert into tsp_src (source, target, cost)'|| tag_name;
insert into tsp_map (nid) select nid from (select distinct
source as nid from edge_table2 union select distinct target as nid from
edge_table2) as foo;
-- should generate a matrix count(*) X count(*) of tsp_map
select count(*) INTO array_size from tsp_map;
-- by default populate the return results with zero, so any
unknown
-- routes will not be listed
ret_array :=array_fill(0,ARRAY [ array_size,array_size]);
-- Loop trough the input looking for any listed routes
FOR tsp_details IN EXECUTE
'select c.nid as src ,b.nid as tar,a.cost as cos
from tsp_src a, tsp_map b, tsp_map c
where a.target= b.nid and a.source=
c.nid and a.cost > 0
group by b.id,c.id,a.cost' LOOP
ret_array[tsp_details.src][tsp_details.tar]:=tsp_details.cos;
END LOOP;
return ret_array;
END
$$;
> Dave,
>
> I thought a lot about this problem before coming up with the matrix.
> The problem really boils down to how do you define your data that you
> want to fetch with "select * from xyz", ie: your inputs and what you
> need to solve TSP, ie: your outputs. In this case a symmetrix NxN
> matrix that is fully populated.
>
> One idea I had was to structure xyz something like:
>
> node_a, node_b, cost
>
> but then you have to count the distinct nodes, and create a map to
> indices and a reverse map as you as you mention. But this is all
> pretty trivial to do in SQL.
>
> create temporary table xyz_map (
> id serial not null primary key,
> nid integer
> );
>
> insert into xyz_map values (nid) select nid from (
> select distinct node_a as nid from xyz
> union
> select distinct node_b as nid from xyz
> ) as foo;
>
> select array_agg(row) as matrix from (
> select a.id, array_agg(cost) as row
> from xyz a, xyz_map b, xyz_map c
> where a.node_a=b.nid and a.node_b=c.nid
> group by a.id
> order by c.id
> ) foo order by foo.id;
>
> I have not tested this, but I think it is close to what you would
> work. I would then do some checking of matrix to make sure it is
> symmetric and filled out.
>
> -Steve
>
> On 6/15/2013 1:37 AM, Dave Potts wrote:
>> On 14/06/13 14:19, Daniel Kastl wrote:
>>
>> I can try and have a play, my problem being that I am more a C/java
>> programmer than an sql programmer. I prefer to deal with standard sql
>> constructs rather that data base specfic stuff.
>>
>> I can see why you got for the matrix solution, if avoid all those
>> node/hash lookup problems.
>>
>> If coding an select * from xyz solution , you have to deal with the case
>> that a node may be any number in the range 1-32^2 and that has to be
>> mapped on to an array of given size by using some type of hashing
>> function and a reverse lookup has to be done on the return.
>>
>> The store procedure has its attractions because its version neutral, it
>> will work as well on linix box as well as a Windoz box.
>>
>> I see what I can come up with.
>>
>> DAve.
>> //
>>>
>>>
>>>
>>> On Fri, Jun 14, 2013 at 10:07 PM, Stephen Woodbridge
>>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>>
>>> Hi Dave,
>>>
>>> I'm not totally opposed to this, but I would like to discuss how
>>> you plan to structure the data and what your query would look like.
>>>
>>> There is another possibility that I like better and that would be
>>> to write stored procedure that takes you sql query and returns a
>>> matrix.
>>>
>>> matrix[][] pgr_matrix(sql text)
>>>
>>> Then you can do something like:
>>>
>>> select * from pgr_tsp(pgr_matrix('select * from matrix_table'),
>>> 27);
>>>
>>>
>>> This idea I really like, because we might also be able to use it then
>>> for Razequl's VRP solver.
>>>
>>> Daniel
>>>
>>>
>>>
>>>
>>> --
>>> Georepublic UG & Georepublic Japan
>>> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
>>> Web: http://georepublic.de <http://georepublic.de/>
>>>
>>>
>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list