[pgrouting-dev] New TSP API
Stephen Woodbridge
woodbri at swoodbridge.com
Sun May 19 16:57:12 PDT 2013
OK, I just push a new function for tsp:
select * from pgr_tsp('{{0,1,2,3},{1,0,3,2},{2,3,0,4},{3,2,4,0}}', 2);
seq | id
-----+----
0 | 2
1 | 0
2 | 1
3 | 3
(4 rows)
The above is just one simple way to define a matrix[4][4]
i/j 0, 1, 2, 3
0: {0, 1, 2, 3},
1: {1, 0, 3, 2},
2: {2, 3, 0, 4},
3: {3, 2, 4, 0}
So the result is a loop from 2-0-1-3-2
edge: cost
2-0 : 2
0-1 : 1
1-3 : 2
3-2 : 4
for a total cost of 2+1+2+4 = 9
I'm looking into how to create an aggregate to assemble recordss into an
array.
But this is a start.
-Steve
On 5/19/2013 12:25 PM, Stephen Woodbridge wrote:
> 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
>>
>
> _______________________________________________
> 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