Problema de 1 centro y k centro / problema de máxima facilidad en Post

Question

¿hay alguien que ya haya resuelto el problema de 1- y k-centro dentro de PostGIS (opcionalmente con la métrica de distancia obtenida por pgrouting)?

Referencias:

• Problema de 1 centro en Wikipedia y centro de gráficos en Wikipedia
• Problema de localización de instalaciones en Wikipedia

Lo que hice hasta ahora para el problema de 1 centro ( He encontrado una solución similar en otro lugar ) :

// 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;

Sin embargo, el segundo paso falla en la elección inicial.

EDITAR: Alguien ya ha preguntado a pregunta sobre el OSS y la asignación de lugares, que es un tema cercano. Sin embargo, en las herramientas enumeradas (Grass v.net.alloc) la funcionalidad divide un área en distritos basados en centros/instalaciones/estaciones predefinidas. Para enfatizar, mi pregunta actual es sobre la optimización ab-initio sin definiciones previas de ubicación.

EDIT2: el algoritmo de Floyd-Warshall sólo devuelve la información de la trayectoria que no se ha calculado previamente, lo que se denomina programación dinámica en este sentido. Pues bien, ahora queda la pregunta de cómo restablecer la información completa para ejecutar el problema de 1 centro.

Answer 1

Ok, el problema de 1 centro puede ser resuelto usando un algoritmo de árbol como Dijkstra. No he encontrado ninguna buena manera de reconstruir el árbol completo utilizando el algoritmo de Floyd-Warshall, mucho más rápido (creo que son necesarios múltiples autoenlaces).

Sin embargo, el siguiente código resuelve el problema. No obstante, utilizando Dijktra (O(n^2)) obtenemos un complejidad ~n^3 que es bastante costoso (mi motivación para el de Floyd). Tal vez otro tipo puede llegar a una idea más rápida .

Para conseguir unos tiempos de ejecución aceptables, he superpuesto un estructura de nido de abeja (red) en la red. A continuación, sólo calculé la matriz de distancias para los nodos centrales de cada panal.

// 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;

Las rejillas en forma de panal pueden lograrse más fácilmente utilizando la funcionalidad de cartoDB (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

Seleccionar el nodo más cercano respecto al centroide de cada panal (sólo en 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

Espero que te guste mi idea y que tal vez se te ocurra una mejorada.