Algoritmos para localização ideal de pontos

Estou tentando comparar locais de onde milhares de instalações foram realmente construídas e onde eles seriam idealmente localizados para minimizar o tempo de viagem da população (representada por blocos censitários ou centróides do trato). Estou tendo problemas para encontrar muita coisa sobre como localizar pontos de maneira ideal.

Eu tenho uma idéia de como escolher esses locais, mas o grande número de pontos a serem colocados no espaço significa que qualquer algoritmo não otimizado de forma inteligente vai levar muito tempo, possivelmente anos. Assim, minha pergunta: Existem algoritmos padrão para escolher onde localizar um número fixo de pontos ?

No final, adotarei o algoritmo que encontrar como ponto de partida e o adaptarei para incorporar mais informações do que apenas a população conta. Assim, a resposta preferida incluiria uma descrição detalhada do algoritmo, código ou seria escrita em uma linguagem de código aberto, para que eu possa replicá-lo e estendê-lo. No entanto, se o ArcGIS tiver uma função conveniente para essa otimização, ficaria feliz em começar com isso.

point algorithm optimization Ari B. Friedman
fonte

Seria útil ter uma descrição mais clara - de preferência quantitativa - do que significa "ótimo". Por exemplo, você está interessado no tempo médio de viagem de ida e volta até a instalação mais próxima ou em alguma outra medida de proximidade? Independentemente da sua medida do custo da viagem, você deseja comparar o custo da configuração existente com o melhor custo que poderia ser alcançado realocando qualquer instalação existente ou deseja permitir que as instalações sejam removidas por completo? Embora a remoção de uma instalação aumente o tempo médio de viagem, ela reduz o custo de construção e manutenção das instalações.

whuber

@whuber Por enquanto, estou apenas interessado em minimizar algumas funções razoáveis da distância (como moscas-do-corvo ou seu quadrado). O eventual problema de otimização incluirá os fatores que você identificou e mais (custo para realocar uma instalação, etc.). Mas, por enquanto, eu só queria uma maneira padrão de escolher locais para minimizar a distância, tanto porque é um ponto de partida para avançar em direção ao algoritmo final, quanto porque estou em dúvida sobre continuar esse projeto e querer explorar a estimativa mais bruta. antes de refiná-lo.

Ari B. Friedman

Respostas:

Você pode querer verificar o algoritmo de agrupamento K-means .

Na mineração de dados, o agrupamento k-means é um método de análise de agrupamentos que visa particionar n observações em k agrupamentos nos quais cada observação pertence ao agrupamento com a média mais próxima. Isso resulta em um particionamento do espaço de dados nas células Voronoi.

Aqui está outra definição :

O agrupamento k-means é um método de classificação / agrupamento de itens em k grupos (onde k é o número de grupos pré-selecionados). O agrupamento é feito minimizando a soma das distâncias ao quadrado (distâncias euclidianas) entre os itens e o centróide correspondente.

Um centróide é "o centro de massa de um objeto geométrico de densidade uniforme", embora aqui consideremos vetores médios como centróides.

insira a descrição da imagem aqui

Figura 1. Um gráfico de dispersão em cluster. Os pontos pretos são pontos de dados. As linhas vermelhas ilustram as partições criadas pelo algoritmo k-means. Os pontos azuis representam os centróides que definem as partições

Na sua situação, o bloco censitário ou os centróides da trilha seriam a entrada e o número de pontos N seria o número de clusters. Aqui está um tutorial para você começar.

RK
fonte

Interessante. Eu nunca pensei em K-meios para isso, mas acho que os centróides preferem ter a propriedade que eu quero.

Ari B. Friedman

Você pode querer testá-lo e ver como ele se comporta :)

Parece ter um bom desempenho nos dados da amostra, mas a implementação de R não tem a capacidade de ponderar (por população, neste caso). Talvez eu precise reescrever a função para permitir a ponderação. Lá vai meu fim de semana ;-)

Ari B. Friedman

Tome cuidado: o k-means não localiza pontos de maneira ideal para a maioria dos problemas de viagem. É ideal quando o custo de uma viagem é proporcional ao quadrado de sua distância. A solução para custos típicos, que têm uma relação linear com a distância, é extremamente difícil de obter.

whuber

@whuber De fato. Isso é esclarecido em uma exposição rápida com código detalhado (Fortran e C ++) aqui . Os custos de viagem são em relação aos cuidados de emergência, portanto, um custo de viagem supra-linear não é totalmente irracional, embora seja improvável que o quadrado esteja exatamente correto.

Ari B. Friedman

Eu co-escrevi um artigo sobre esse problema em 1996, veja

Modelagem e otimização de fluxos usando modelos de interação espacial paralela (1996), Turton & Openshaw, PROCEDIMENTOS DO EURO-PAR'96, VOLUME II.

Você pode baixar uma cópia do citeseer

Nós também escrevemos

Turton I., Openshaw S. (1997) Parallel Spatial Interaction Models. Modelagem Geográfica e Ambiental, Volume 1, número 2, páginas 179-197.

mas não consigo encontrar uma cópia online.

Ian Turton
fonte