[pgrouting-dev] New TSP API

[Dave Potts]

Hi,


Is there any sort of time tablethisn idea?

I must admit,  I have a need for this type of thing and with out looking 
at the existing code its difficult to comment.

  Due to the nature of the data that I am working with every node has 
its set of data, so I prefer a solution that uses a generic sql 
expression as a parmeter i.e. something like

select target,cost,reverse_cost, etc where source =XXXXX

Where XXXXX is a supply argument that gets provided invoked when data is 
need.

Dave.

On 19/05/13 15:58, Daniel Kastl wrote:
>
>
>         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>
>         <mailto:pgrouting-dev at lists.osgeo.org
>         <mailto: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
>         <mailto:daniel.kastl at georepublic.de>
>         <mailto: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
>         <mailto:pgrouting-dev at lists.osgeo.org>
>         http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>     _______________________________________________
>     pgrouting-dev mailing list
>     pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>     http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> -- 
> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130519/44f9a65e/attachment-0001.html>