ze_carlos_s
New Member
O título deste tópico também poderia ser "Como aliar os conhecimentos de programação ao BTT".
Há uns tempos atrás, ponderei se era possível uma coisa: percorrer todas as freguesias do meu concelho - Barcelos - num único fim-de-semana. Concretamente, ir ao centro de cada freguesia.
Ora Barcelos é “só” o concelho com mais freguesias em Portugal. Nada mais que 89 freguesias: 46 na margem sul e 43 na margem norte. O objectivo seria fazer uma margem em cada dia.
Após 10 minutos a tentar definir um percurso no Google Maps desisti. Demasiadas opções. Uma pergunta colocava-se: “Qual o melhor caminho para percorrer estas freguesias todas?”
Foi então que me lembrei de investigar a API do Google Maps
Descobri que era possível que, dando uma lista de localizações, era possível obter a matriz de distâncias! (Matrizes de distâncias não são mais do que aquelas tabelas que se viam nos almanaques antigamente que diziam a distância entre cada cidade).
ex: http://www.aguasdelindoia.com/images/distancia_entre_cidades.gif.
Coloquei todas as freguesias de Barcelos em ficheiros de texto que eram lidas por uma pequena aplicação para receber a matriz de distâncias entre todas as freguesias. Isto ir-me-ia permitir saber, a partir de uma dada freguesia, qual a distância para todas as outras freguesias do concelho. Dava para configurar que tipo de rota o Google Maps escolhia, portanto eu escolhi para ele definir rotas a pé, de modo a escolher caminhos secundários.
Já que o rio Cávado divide o concelho a meio, dividi em duas partes: parte Norte e parte Sul. Iria fazer uma margem em cada dia.
Agora que sabia a distância entre todas as freguesias, como usar esta informação para obter o melhor caminho possível de modo a passar em todas as freguesias e regressar ao ponto de partida?
Ora, este é um típico caso do Problema do Caixeiro Viajante (http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante), em que cada nó é uma freguesia e o custo das ligações é a sua distância. Eu quero passar em todas as freguesias e regressar ao ponto de partida percorrendo a menor distância possível.
Como o número de freguesias (nós) era elevado (46 a sul e 43 a norte) é muito demorado (mesmo para um computador) calcular o melhor percurso possível. Daí usar as chamadas heurísticas, que retornam soluções relativamente próximas do melhor valor possível. Para tal utilizei este código já feito (http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx).
As heurísticas não retornam sempre o mesmo resultado, portanto, corri o mesmo algoritmo várias vezes guardando apenas a melhor execução.
Consegui valores na ordem dos 115km para cada margem. Bem melhor que os 140km que consegui sendo eu a definir o meu percurso
Agora que tinha uma sequência quase óptima para fazer o percurso, foi só ir ao Google Maps e gerar o trajecto pela ordem obtida.
Tendo o percurso desenhado no Google Maps, importei para .kml, para o usar no Google Earth, de modo a poder adicionar waypoints mais à vontade, assim como fazer optimizações ao percurso. O Google Maps não contém todos os caminhos existentes, e no Google Earth deu para identificar muitos caminhos (essencialmente pelo meio dos montes) que reduziam consideravelmente a distância.
Para me certificar que passava mesmo no centro de cada freguesia, criei waypoints com a localização de cada igreja.
Finalmente, foi só converter o percurso para .gpx, colocar no GPS, já com os waypoints, e estava pronto para pedalar pelas freguesias fora
Este fim-de-semana, fiz-me às estradas, e, consegui cumprir o objectivo
Registos GPS:
Dia 1: http://www.endomondo.com/workouts/vJvxmHMAzpo
Dia 2: http://www.endomondo.com/workouts/hd3LPijYPhY
Para comprovar a passagem, tenho 89 fotos de 89 igrejas do concelho com a bike lá incluída
Isto foi muito desafiante, pois claramente se dividiu em duas fases, saber fazer um bom planeamento, e depois ter capacidade para aguentar os quilómetros todos em dois dias seguidos.
Fico à espera que alguém aqui da zona entre no desafio :mrgreen:
Há uns tempos atrás, ponderei se era possível uma coisa: percorrer todas as freguesias do meu concelho - Barcelos - num único fim-de-semana. Concretamente, ir ao centro de cada freguesia.
Ora Barcelos é “só” o concelho com mais freguesias em Portugal. Nada mais que 89 freguesias: 46 na margem sul e 43 na margem norte. O objectivo seria fazer uma margem em cada dia.
Após 10 minutos a tentar definir um percurso no Google Maps desisti. Demasiadas opções. Uma pergunta colocava-se: “Qual o melhor caminho para percorrer estas freguesias todas?”
Foi então que me lembrei de investigar a API do Google Maps
Descobri que era possível que, dando uma lista de localizações, era possível obter a matriz de distâncias! (Matrizes de distâncias não são mais do que aquelas tabelas que se viam nos almanaques antigamente que diziam a distância entre cada cidade).
ex: http://www.aguasdelindoia.com/images/distancia_entre_cidades.gif.
Coloquei todas as freguesias de Barcelos em ficheiros de texto que eram lidas por uma pequena aplicação para receber a matriz de distâncias entre todas as freguesias. Isto ir-me-ia permitir saber, a partir de uma dada freguesia, qual a distância para todas as outras freguesias do concelho. Dava para configurar que tipo de rota o Google Maps escolhia, portanto eu escolhi para ele definir rotas a pé, de modo a escolher caminhos secundários.
Já que o rio Cávado divide o concelho a meio, dividi em duas partes: parte Norte e parte Sul. Iria fazer uma margem em cada dia.
Agora que sabia a distância entre todas as freguesias, como usar esta informação para obter o melhor caminho possível de modo a passar em todas as freguesias e regressar ao ponto de partida?
Ora, este é um típico caso do Problema do Caixeiro Viajante (http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante), em que cada nó é uma freguesia e o custo das ligações é a sua distância. Eu quero passar em todas as freguesias e regressar ao ponto de partida percorrendo a menor distância possível.
Como o número de freguesias (nós) era elevado (46 a sul e 43 a norte) é muito demorado (mesmo para um computador) calcular o melhor percurso possível. Daí usar as chamadas heurísticas, que retornam soluções relativamente próximas do melhor valor possível. Para tal utilizei este código já feito (http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx).
As heurísticas não retornam sempre o mesmo resultado, portanto, corri o mesmo algoritmo várias vezes guardando apenas a melhor execução.
Consegui valores na ordem dos 115km para cada margem. Bem melhor que os 140km que consegui sendo eu a definir o meu percurso
Agora que tinha uma sequência quase óptima para fazer o percurso, foi só ir ao Google Maps e gerar o trajecto pela ordem obtida.
Tendo o percurso desenhado no Google Maps, importei para .kml, para o usar no Google Earth, de modo a poder adicionar waypoints mais à vontade, assim como fazer optimizações ao percurso. O Google Maps não contém todos os caminhos existentes, e no Google Earth deu para identificar muitos caminhos (essencialmente pelo meio dos montes) que reduziam consideravelmente a distância.
Para me certificar que passava mesmo no centro de cada freguesia, criei waypoints com a localização de cada igreja.
Finalmente, foi só converter o percurso para .gpx, colocar no GPS, já com os waypoints, e estava pronto para pedalar pelas freguesias fora
Este fim-de-semana, fiz-me às estradas, e, consegui cumprir o objectivo
Registos GPS:
Dia 1: http://www.endomondo.com/workouts/vJvxmHMAzpo
Dia 2: http://www.endomondo.com/workouts/hd3LPijYPhY
Para comprovar a passagem, tenho 89 fotos de 89 igrejas do concelho com a bike lá incluída
Isto foi muito desafiante, pois claramente se dividiu em duas fases, saber fazer um bom planeamento, e depois ter capacidade para aguentar os quilómetros todos em dois dias seguidos.
Fico à espera que alguém aqui da zona entre no desafio :mrgreen: