7

is there anybody who has already solved the 1- and k-center problem within PostGIS (optionally with distance metric obtained by pgrouting)?

References:

What I did so far for the 1-center problem (I found a similar solution elsewhere) :

// Generate min. cost table for all pairs
INSERT into catchments 
SELECT  
    seq, id1 as source, id2 as target, cost 
FROM     
  pgr_apspWarshall('
    SELECT id, source, target, cost 
    FROM network WHERE city = ''New York''', false, false);

// Select max(min(distance))
SELECT source, max(cost) as maxcost 
FROM catchments 
WHERE cost <= 10 **km** GROUP BY source ORDER BY maxcost ASC;

However, the second step misses the initial choice.

EDIT: Someone has already asked a question about OSS and location allocation which is a nearby topic. However, in the tools listed (Grass v.net.alloc)the functionality divides an area into districts based on predefined hubs/facilities/stations. To emphasize, I current question is about ab-initio optimization without previous definitions of location.

EDIT2: the Floyd-Warshall algorithm returns only the path information which has not previously been calculated- that is called dynamic programming in this sense. Well, now the question remains how to reestablish the full information to run the 1-center problem?

  • Could you explain what you mean by the 2nd step misses the initial choice? – John Powell Feb 4 '16 at 18:28
  • @JohnBarça, referring to the minimax facility location in Wikipedia, I think the point search for the point which minimizes max(min(distance)) is wrong. Summation over the max(min(distance)) could be a solution. I'll try later. – Frank Feb 5 '16 at 7:37
  • Actually, the ASCending order of maximum cost delivers a lot of nodes with zero or little costs. Investigating. – Frank Feb 5 '16 at 16:45
1

Ok, the 1-center problem can be solved using a tree algorithm like Dijkstra. I did not find any good way to reconstruct the complete tree using the much faster Floyd-Warshall algorithm (I think multiple self-joins are necessary).

However, the following code solves the problem. Nevertheless, using Dijktra (O(n^2)) we obtain a complexity ~n^3, which is quite costly (my motivation for Floyd's). Maybe another guy can come up with a faster idea.

To achieve acceptable run times, I overlayed a honeycomb structure (grid) onto the network. Then I only calculated the distance matrix for the center nodes of each honeycomb.

// Generate min. cost table for all pairs
INSERT into catchments 
WITH nodes as (select source from network)
SELECT nodes.source, network.target,
  (SELECT sum(cost) FROM (
     SELECT * FROM pgr_dijkstra('
       SELECT 
         id, source, target, cost
       FROM network',
       nodes.source, -- start node
       network.target, -- end node
       false,
       false)) AS foo ) AS cost
     FROM network, nodes;

// Select max(min(distance)) as center node
SELECT source, max(cost) as maxcost 
FROM catchments 
GROUP BY source ORDER BY maxcost ASC;

Honeycomb grids can be most easily achieved by using cartoDB functionality (github):

 CREATE VIEW hexagon_grid_250m AS
   SELECT row_number() OVER () AS id, the_geom FROM
   (SELECT CDB_HexagonGrid(geom, 250) as the_geom FROM city_area) AS hex,
   city_area AS a WHERE st_intersects(a.geom,hex.the_geom) = true

Select the nearest node in respect to the centroid of each honeycomb (only on PostGIS 2.2 + Postgreql 9.5):

SELECT grid.id, grid.the_geom, (SELECT n.the_geom
  FROM network AS n
  ORDER BY n.the_geom <-> st_centroid(grid.the_geom) LIMIT 1) AS nearest_node 
FROM 
  hex.hexagon_grid_250m AS grid

I hope you'll like my idea and maybe come up with an improved one.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.