[pgrouting-dev] New TSP API

[Daniel Kastl]

>
>> SELECT * FROM pgr_tsp( 'SELECT id, start, end, cost FROM distances,
>> origin int [, destination int])
>>
>
> I can do this, so each record is one cell. What are "start" and "end"? are
> these vertex ids or are they indices? Does the use KNOW that they need to
> also have a row for (end,start) as well as (start,end)? These things are
> less obvious and there for have more room for errors.
>

Well start and end is just "id1" and "id2".
You could actually also have two costs there, one for each direction (like
cost and reverse_cost).


>
> I suppose we could write an aggregate function that takes your query and
> returns matrix[][]. But we still need to define how to deal with null
> values in the matrix.
>

I know I said "matrix", but actually I didn't think about matrix ;-)
I thought about pairs of id's with cost(s). So it wouldn't be an [m][m]
matrix but more like a table with m*m/2 records (if there is a cost for
each direction for each combination).
I don't know how it should be later internally for the algorithm, but I
would say, that a query (table) always has a fix number of columns and a
variable number of rows.

In the end this would look like a graph, where all nodes are connected with
all nodes.


>
> select pgr_makematrix(i, j, cost) from
>     (select start as i, end as j, cost from distances) as foo;
>
> Then this could be passed as the SQL to the TSP. We need to keep each
> function simple and make them chainable or we limit the usefulness of them.
>

Exactly ;-)


>
> Any thoughts on how to deal with NULLs in the matrix?
>
> We could have some default rules like?
> 1. if the null is on a diagonal set it to zero
> 2. if the cell(i,j) is null and cell(j,i) is not use cell(j,i)
> 3. otherwise report an error
>
>
If you always have pairs A <-> B then you won't have a diagonal set.
In case there is no way in one direction (maybe even in both directions),
then this could be -1 for example?
Then it would be same as negative cost for Dijkstra or Astar and it won't
be taken into account.

Daniel



> Thoughts?
>
> -Steve
>
>
>  ... which would return the matrix in an optimized order.
>> I think it would be nice to be able to set origin and destination point.
>> But destination could be optional.
>>
>> Daniel
>>
>>
>>
>>
>>
>>
>>
>>     I'm not interested in computing the distance matrix because I will
>>     not be able to do it "right" for any given use case and it limits
>>     how people can use the function.
>>
>>     Thoughts?
>>
>>     -Steve
>>     ______________________________**___________________
>>     pgrouting-dev mailing list
>>     pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>>     http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>>
>>     <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>>
>>
>> --
>> Georepublic UG & Georepublic Japan
>> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl@**georepublic.de<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<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<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>



-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130519/9fb2bd21/attachment.html>