# 1-center and k-center problem / maxmin facility problem in Post

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

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.