Em um último artigo, descrevi um algoritmo que permite que você crie rotas a pé mais interessantes (em oposição a mais curtas, como todas as que o Yandex-Google faz) entre dois pontos. O algoritmo carregou vistas, parques e outros objetos agradáveis e interessantes para os pedestres do Open Street Map e estabeleceu uma rota através deles. Como resultado, o caminho pode ser 10 a 20% maior, mas muito mais pitoresco e interessante.
Fotos da cidade - Alex 'Florstein' Fedorov
Nos comentários, muitos escreveram que, além das rotas entre dois pontos, eles estariam interessados em construir rotas circulares que começariam e terminariam no mesmo ponto e caberiam em um determinado limite de tempo. Por exemplo, se você tiver duas horas de trem ou encontrar amigos, não terá tempo de ir a algum lugar longe durante esse período, mas é bem possível dar um passeio e ver a beleza nas proximidades.
Após várias experiências, compus um algoritmo genético que constrói rotas muito boas (para mim) nessa situação. Sob descrição do gato do princípio de operação e alguns exemplos.
Portanto, os usuários desejam fazer um pequeno tour pela área circundante e retornar ao ponto de início no tempo especificado (geralmente de uma a duas horas). Como se viu, esse tipo de caminhada é bastante procurada. Por exemplo, o artigo "Padrões de movimento de turistas em um destino" descreve o estudo de faixas de 250 turistas em Hong Kong, enquanto 40% dos turistas começaram a explorar a cidade a partir de uma rota circular em um raio de 500 metros do hotel. No entanto, muitas vezes as pessoas ficam por aqui, sem saber o que é interessante pode ser visto nas proximidades.
A tarefa é complicada se não estiver no centro turístico (onde quer que você vá - você encontrará algo interessante em qualquer lugar), mas em algum lugar nos arredores, onde você precisa procurar pontos turísticos.
Raio e seleção de atrações
Para construir uma rota, primeiro precisamos selecionar as atrações que queremos visitar. E para isso, você precisa determinar a área de sua pesquisa em torno do ponto de partida. Se o usuário definir o tempo máximo de caminhada em M minutos, o ponto mais distante ao qual você pode chegar e ter tempo para retornar é o ponto à distância (V * M / 2), em que V é a velocidade do pedestre.
A velocidade média preferida de um pedestre pode ser considerada 1,4 metros por segundo. No entanto, ao passear, a pessoa fica um pouco mais lenta, pois passa um tempo extra em um passeio. Criei algumas rotas pela cidade e caminhei por elas, comparando o tempo da caminhada com o que o aplicativo previa. Como resultado, verificou-se que minha velocidade média de caminhada era cerca de 20% menor, ou seja, aproximadamente 1,1 m / s. Desde que parei periodicamente para tirar fotos, verifique com o mapa, às vezes eu atravessava a rua mais uma vez para escolher o melhor ângulo ou comprar sorvete.
Realizei experimentos em áreas desconhecidas da cidade, usando meu algoritmo lá, você pode encontrar todo tipo de coisas interessantes sobre as quais eu nunca tinha ouvido falar antes. Por exemplo, um monumento ao primeiro folheto.
A escolha de um ponto de interesse a uma distância máxima levará à construção de uma rota circular degenerada. Como o pedestre não terá mais tempo de seguir o caminho mais curto em uma linha reta, ele poderá visitar apenas esta atração, indo até ela e retornando pela mesma rua, como mostra a seta vermelha.
Aqui podemos ir ao parque mais longe ou visitar vários pontos ao mesmo tempo mais perto
Mas essa situação contradiz a ideia de rotas circulares interessantes, porque na verdade vimos apenas uma rua e um objeto, mas quero ver mais. Portanto, de acordo com os resultados das experiências, foi escolhido um raio igual a um terço da distância máxima. Com esse raio de busca, o pedestre terá tempo suficiente para alcançar o ponto de interesse mais distante ao longo do raio e, se necessário, percorra a mesma distância ao longo do acorde em busca de outros objetos interessantes e retorne no tempo.
Questões de abordagem frontal
Ok, reunimos uma lista de atrações candidatas. Resta agora escolher qual deles e em que ordem queremos inspecionar. Provavelmente, não teremos tempo para visitá-los, portanto, precisamos escolher o subconjunto mais interessante deles.
Primeiro, tentei formular e construir um algoritmo seqüencial simples. No entanto, eu me deparei rapidamente com vários problemas.
Se considerarmos a situação da figura acima, não está claro por onde começar a construir a rota. Se o parque é a atração mais importante, mas a mais distante, a partir de então teremos uma versão degenerada, sobre a qual escrevemos anteriormente.
A próxima solução óbvia é, de alguma forma, agrupar os pontos turísticos e tentar procurar o caminho para o cluster mais lucrativo e depois entrar nele. Mas aqui novamente, tudo não está claro: de qual cluster iniciar, que caminho seguir. Você sempre pode cair na armadilha do tipo que seguimos o caminho errado e corremos para o "deserto" - uma área sem vistas que não temos tempo suficiente para passar por cima e voltar ao ponto de partida.
Em algum momento, ficou claro para mim que eu estava praticamente realizando o trabalho do algoritmo genético: eu traço diferentes rotas no mapa e tento determinar o quanto eu pessoalmente gostaria delas.
Algoritmo genético
Tendo recebido uma lista numerada de atrações, o algoritmo deve escolher um subconjunto ordenado, que formará a base da rota circular. A rota final, neste caso, é um dos locais de muitas atrações principais (não queremos repetições e não precisamos usar todos os objetos possíveis).
Conhecendo a fórmula para o número de veiculações de n a k, podemos estimar o número possível de opções. Se considerarmos a rota de uma hora em torno da Praça do Palácio em São Petersburgo, haverá 54 candidatos para as principais atrações após filtrar e agrupar em um raio de 1320 metros (que é definido como descrito acima).
Mingau infernal de um monte de pontos turísticos no centro, uma saída de depuração de áreas de visibilidade calculada de acordo com o algoritmo do artigo anterior
O princípio de seleção e classificação é descrito em um artigo anterior, além de excluirmos objetos com um interesse menor que 3 (por causa de objetos menores, é improvável que uma pessoa esteja pronta para ir longe, a menos que não haja mais nada por perto). Assim, o número possível de rotas pode ser calculado pela fórmula do número de veiculações de 54 a 5, é 379501200. Para uma rota de 2 horas, dentro do raio dos quais já caem 151 pontos de interesse, esse número será igual a 73423236600. Bem, um pouco demais para uma pesquisa simples.
Cromossomos e operadores genéticos
Os cromossomos, neste caso, são uma linha na qual cada elemento é o número da atração de chave correspondente. Para tarefas em que os cromossomos são permutações ou arranjos, existem variantes otimizadas especiais de operadores genéticos. Esses operadores retêm a propriedade do cromossomo para permanecer uma permutação ou colocação do conjunto inicial de elementos.
- O Crossover Parcialmente Mapeado (PMX) é usado para cruzamento.
- Para a mutação, é utilizada a troca de locais de dois genes aleatórios (Swap Mutator).
Uma descrição da operação desses operadores com exemplos pode ser encontrada, por exemplo, no trabalho "Algoritmos genéticos para o problema do vendedor ambulante: uma revisão de representações e operadores".
Função de fitness
A função de condicionamento físico deve levar em conta os seguintes fatores para criar uma rota circular interessante:
- O interesse total de todas as principais atrações visitadas deve ser o maior possível.
- O tempo total de viagem deve ser o mais próximo possível do especificado pelo usuário, a rota não deve ser muito mais longa ou muito mais curta. Rotas curtas são permitidas apenas quando não há atrações suficientes nas proximidades.
- A rota não deve cruzar-se. Para cada auto-interseção, adicionamos porcentagens de penalidade ao valor total da função.
- O formato da rota deve estar próximo ao círculo, deve capturar a maior área possível da cidade e evitar casos degenerados. Para isso, colocamos na função a proporção da área da figura descrita pela rota para a área do círculo em que as vistas foram pesquisadas.
Aqui está um exemplo de uma boa viagem de ida e volta. Passa por dois parques e nunca visita o mesmo lugar duas vezes
Aqui está um exemplo de uma rota claramente malsucedida. Ele contém galhos sem saída, onde o pedestre terá que retornar ao longo do caminho examinado e interseções automáticas. Nos cruzamentos, o tempo é geralmente desperdiçado em vão para reexaminar seções já vistas da cidade.
Na verdade, a má rota foi obtida pela genética, na qual os pontos 3 e 4 foram desativados para a função de condicionamento físico (multas por travessia automática e por uma área pequena)
Nuances
Durante os testes, surgiram mais algumas nuances.
Prazo excedido
Durante o trabalho de genética, contamos o comprimento do percurso ao longo de linhas retas entre os pontos. E depois que selecionamos objetos para comunicação usando o algoritmo genético, procuramos o caminho entre eles usando o algoritmo do artigo anterior. Nesse caso, o caminho pode ficar mais longo e ficar sem tempo. Afinal, na cidade, muitas vezes o caminho mais curto ao longo da rua pode ser muitas vezes maior que uma linha reta.
Em média, a diferença geralmente é de 10 a 20% e a colocamos na função de condicionamento físico (ou seja, a genética procura uma rota com uma margem de tempo, que é consumida ao definir uma rota detalhada). Às vezes, não é suficiente - você precisa recalcular a rota novamente. Temos lugares em cidades onde a diferença entre as rotas “como um pássaro” e “como um pedestre” é de quilômetros.
Entre os pontos de 50 metros em uma linha reta, mas um quilômetro e meio ao longo das calçadas e passagens que contornam.
No entanto, mesmo assim, o algoritmo às vezes excede o tempo definido pelo usuário, mas todos podem decidir por si mesmo se ele tem de 10 a 15 minutos extras ou se precisa concluir a caminhada mais cedo.
Veneza
Quando o algoritmo estava pronto, decidi adicionar as principais cidades turísticas da Europa por diversão. Ficou interessante: as cidades são diferentes em todos os lugares, os recursos de mapeamento no OSM também, como resultado, eu constantemente precisava terminar alguma coisa.
Especificamente, a busca por rotas circulares foi interrompida em Veneza. Como este é um exemplo único de uma cidade com áreas não relacionadas - as ilhas são separadas pelo Grande Canal, através do qual não há pontes, a travessia é possível apenas por balsa.
Como resultado, o algoritmo selecionou parte dos objetos de um lado do estreito, parte do outro, e não conseguiu encontrar um caminho de terra entre eles e caiu. Eu tive que adicionar uma verificação sobre a acessibilidade de todas as atrações desde o ponto de partida.
Às vezes você ainda precisa voltar da mesma maneira
No exemplo do parque acima, há um trecho da rota em que você precisa voltar da mesma maneira - é uma pequena península na qual fica um monumento com um avião. O único caminho leva a esta península, e será necessário retornar ao longo dela. Portanto, esses reembolsos não podem ser completamente proibidos. O algoritmo para isso aumenta o peso de todas as arestas que já foram percorridas, reduzindo a probabilidade de um retorno ao longo delas, mas ainda torna isso possível.
Embora às vezes ainda funcione mal. Por exemplo, eles reclamam da catedral principal de Kaliningrado. Está localizado em uma ilha no meio do rio por onde passa a ponte. A partir dessa ponte, há uma descida e um caminho para a catedral, aparentemente o algoritmo aumenta muito o peso desse único caminho, o que torna o retorno não lucrativo. Como resultado, ele quase nunca leva à catedral, embora essa seja uma das principais atrações da cidade. Ainda requer algum tipo de refinamento.
Resultados
O algoritmo genético é uma coisa pouco imprevisível, então, às vezes, é buggy e cria ziguezagues estranhos. Mas, em geral, estou satisfeito com o resultado. O que é especialmente interessante, o algoritmo funciona não apenas no centro turístico (onde não é um problema para se divertir), mas também nos arredores da cidade. Onde, muitas vezes, sem dicas, encontrar algo interessante é muito difícil.
Mesmo nos sacos de dormir no sudoeste de São Petersburgo, você pode encontrar monumentos suficientes para uma caminhada de duas horas
Você pode experimentar o algoritmo em uma das 77 cidades suportadas em nosso site Sight Safari ou em nosso aplicativo Android (sim, finalmente o concluímos).
É especialmente interessante como o algoritmo funcionará em cidades com terrenos e elevações complexos. Adicionamos suporte à análise de elevação à biblioteca de desbravadores do Graphopper, mas não podemos verificar como deveria ser - Peter é uma cidade muito plana.
Em geral, tente, escreva críticas, são as rotas que estão sendo construídas corretamente. Você pode solicitar imediatamente a adição de novas cidades.