[pgrouting-dev] New TSP API

Stephen Woodbridge woodbri at swoodbridge.com
Sun May 19 09:25:03 PDT 2013 

OK, so both you an Daniel are looking at the problem from some higher 
level than I am dealing with. So we will have to build some layers to 
bridge the gap between that and the low level code that I have to deal with.

The solver takes as arguments:

num - the size of the matrix
matrix - a num*num array of float8

and returns an array of num indices which it the optimal order.

This will be very close to the first API I create. At this level it 
needs to be this simple. At a higher level some one can map ids to array 
indexes and map them back again.

Regarding, null cell values or negative cell values, I guess I can set 
them to infinity. I'm not going to try and modify the algorithm to 
eliminate arbitrary rows.

Postgresql supports an an array type and multi-dimensional arrays. Most 
people do not use them, but it is a convenient type for passing the data 
to this algorithm.

If I can get this to work, then we can look at layering something 
smarter on top of that.

The bottom line is if your data can not be put into a distance matrix 
then you do not have a problem that can be solved by TSP. Now we just 
need to make it easier to put the data into a distance matrix.

-Steve

On 5/19/2013 11:39 AM, Dave Potts wrote:
> 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
>
>
>
> _______________________________________________
> 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