A Rota Perfeita no Google Maps

Uma das coisas que falta no Google Maps, é a capacidade de calcular a rota mais eficiente de forma a visitar vários pontos.

Sim, eu sei que podemos definir pontos por onde passar, mas se estivermos no Porto e marcarmos Faro e depois Lisboa, a rota que nos surge segue essa mesma ordem.
O que eu queria era, marcando vários pontos, a Google sugerisse a rota mais rápida de forma a passar por eles todos com o caminho mais curto possível.

Esse problema é conhecido em inglês por the Traveling SalesPerson (TSP), ou em português: o problema do vendedor ambulante ou, à moda antiga, do "caixeiro viajante".

Imaginando que um vendedor tem que visitar vários clientes, qual a forma de o fazer, percorrendo a menor distância possível?

É isso que este senhor fez, usando o algoritmo de resolução do TSP e a API do Google Maps.

Cálculo da Viagem mais Rápida entre vários pontos no Google Maps


Uma vez que o processo de cálculo é complexo e aumenta exponencialmente com cada novo ponto a calcular, o método que ele implementou apenas calcula a rota até nove pontos - acima disso, usa um método heurístico que pode não ser o mais ideal, mas que se aproxima bastante e pode ser calculado rapidamente. Para os mais curiosos, podem ler neste post como é que ele implementou isto.