Cá¡lculo de melhor rota entre diversos pontos

[zatlima]

Alguém conhece algum programa compatível com os mapas do TrackSource que permita criar a melhor rota entre diversos pontos. Por exemplo, eu indico um ponto de partida e 5 pontos por onde a rota deve passar, com isso o programa procuraria a melhor rota definindo inclusive qual a ordem de visita dos pontos.
Tentando exemplificar ainda melhor, a rota mais rápida poderia ser a sequência de pontos 1, 3, 2, 5, 4 e 6, enquanto a rota mais curta seria a sequência 1, 2, 4, 3, 5 e 6.
Sei que este é um problema de computação complicado, mas seria muito útil para sistemas de entregas, por exemplo. Ao sair do depósito o motorista definiria os endereços de entrega e o programa sugeriria a melhor rota passando por todos os endereços.

[elderluis]

Desconheço a existência de qualquer aplicativo que faça isso automaticamente, no entanto, é possível fazer isso na mão usado o MapSource.

Veja qual é o ponto mais próximo a partir da origem e na seqüência qual é o ponto mais proximo dele, trace a segunda rota, e assim por diante. Se forem poucos, conforme o exemplo, uns 5 ou 6, dá pra fazer na unha msm... agora, se forem muitos, aí vai complicar um pouco.

O MapSource informa a distância percorrida pela rota, por aí é possível definir uma escala crescente de distância.

[paulocarvalho]

Esse problema é conhecido por "Traveling Salesman" ou "Caxeiro Viajante" que é do tipo NP-hard. Usando tentativa e erro, esse problema que tende a ser O(n!) onde n é o número de pontos no mapa (imagine 300000! de um mapa como o de São Paulo, levaria mais tempo que o Universo levará para atingir o equilíbrio termodinâmico).

Existem algoritmos baseados em heurísticas (soluções quasi-ótimas) e algoritmos exatos focados no tipo de grafo do problema (ex.: sistema de roteamento de passageiros em vôos).

Para um número pequeno de pontos tais como você citou, a solução simples seria aplicar uma algoritmo de rotas ponto-a-ponto comum (desses que temos nas ferramentas e no GPS) entre os pontos em várias seqüências e rankear aquela combinação que der uma seqüência de rotas de menor custo.

[paulocarvalho]

Eu poderia até experimentar colocar um sistema assim dentro do Editor, desde que eu implemente as prioridades que hoje existem para ele.

[zatlima]

Elder e Paulo
Valeu pelos comentários, eu já sabia que era um problema computacional complicado e que o problema cresce de acordo com o número de pontos.
Paulo, se você for colocar esse recurso no Editor de nós, lembre-se de limitar o número de nós disponíveis para essa nova ferramenta, senão daqui a pouco vai ter neguinho te queimando na fogueira porque seu algoritimo trava o computador quando ele tenta criar uma rota com "apenas" 500 nós.
Um abração

[paulocarvalho]

Elder e Paulo
Valeu pelos comentários, eu já sabia que era um problema computacional complicado e que o problema cresce de acordo com o número de pontos.
Paulo, se você for colocar esse recurso no Editor de nós, lembre-se de limitar o número de nós disponíveis para essa nova ferramenta, senão daqui a pouco vai ter neguinho te queimando na fogueira porque seu algoritimo trava o computador quando ele tenta criar uma rota com "apenas" 500 nós.
Um abração

Fique tranqüilo. As soluções para esse tipo de problema dependem de uma heurística, que é um processo de tomada de decisão para o qual não há prova matemática de que ela leva ao melhor caminho. Conforme havia dito acima, as soluções podem não ser ótimas, mas São aceitáveis, daí o fato de o problema ser considerado NP-hard, de Non-deterministic (comportamento imprevisível) Polinomial (tempo de execução pelo menos linear, mas pode ser quadrático, cúbico, etc.). O hard quer dizer "uma forte tendência a ser", mas pode não ser dependendo da heurística adotada.

[paulocarvalho]

Elder e Paulo
Valeu pelos comentários, eu já sabia que era um problema computacional complicado e que o problema cresce de acordo com o número de pontos.
Paulo, se você for colocar esse recurso no Editor de nós, lembre-se de limitar o número de nós disponíveis para essa nova ferramenta, senão daqui a pouco vai ter neguinho te queimando na fogueira porque seu algoritimo trava o computador quando ele tenta criar uma rota com "apenas" 500 nós.
Um abração

Na verdade existem poucos problemas que rodam em O(1). A maioria dos problemas práticos têm dependência de n, mas existem uns que crescem mais do que outros. Por exemplo, o nosso algoritmo de roteamento roda em O(n log n), o que é considerado aceitável.

[elderluis]

Alguém sabe dizer qual é o sistema utilizado pelos Correios?? será que eles têm algum software próprio para isso, principalmente para o sistema sedex??? Com certeza deve haver algum parâmetro básico para indicação das seqüencias das entregas, e com o detalhe de serem dezenas (suponho) a cada saída.

[Wallace]

Duvido, pois é mega banguçado rs rs
Eles dividem por área, mas dentro da área acho que não tem tanta inteligencia assim.

[paulocarvalho]

Alguém sabe dizer qual é o sistema utilizado pelos Correios?? será que eles têm algum software próprio para isso, principalmente para o sistema sedex??? Com certeza deve haver algum parâmetro básico para indicação das seqüencias das entregas, e com o detalhe de serem dezenas (suponho) a cada saída.

Esse tipo de coisa você encontra em pacotes de pesquisa operacional, os quais, por razões óbvias, custam dezenas se não centenas de milhares de dólares, já que otimização em logística tem impacto profundo no resultado operacional de uma empresa como os Correios ou uma companhia aérea.

[marceloaf]

Ois, boa noite.

Esta funcionalidade não seria mais o menos o que a Garmin "diz que faz" com os GPSs da série nuvi 700? Vejam no site da garmin, nuvi 770, na aba de features. A funcionalidade seria a "Plan Ahead". Link abaixo:

https://buy.garmin.com/shop/shop.do?cID=134&pID=10623

Ou eu viajei na maionese?

Abraços,
Marcelo Franco.

[Wallace]

Pelo que entendi é isso mesmo que parece que também seria a:
Auto sort multiple destinations (provides most direct route).
Eu pedi um Nuvi 5000 que também teria isso.
Quando chegar testamos isso rs

[paulocarvalho]

Ois, boa noite.

Esta funcionalidade não seria mais o menos o que a Garmin "diz que faz" com os GPSs da série nuvi 700? Vejam no site da garmin, nuvi 770, na aba de features. A funcionalidade seria a "Plan Ahead". Link abaixo:

https://buy.garmin.com/shop/shop.do?cID=134&pID=10623

Ou eu viajei na maionese?

Abraços,
Marcelo Franco.

Pelo que está escrito no enunciado, parece que realmente se trata de uma solução para o problema do caxeiro viajante implementada em hardware portátil. Tenho que tirar o chapéu para a Garmin. Verifiquem se não se trata apenas de rotear ponto-a-ponto, ou seja, você já sabe a ordem de visita e o GPS simplesmente calcula as diversas rotas entre pares de pontos em seqüência.

[Ruy Lerac]

Os modelos mais sofisticados dos nuvis fazem sim a escolha da melhor rota para vários destinos. O próprio gps define a ordem dos destinos para obter a melhor rota, dentro das preferências do usuário.